一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 467|回复: 12
收起左侧

[算法题] 一个关于C++的vector的问题

[复制链接] |试试Instant~ |关注本帖
glaciersilent 发表于 2015-7-3 12:54:24 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 glaciersilent 于 2015-7-3 13:01 编辑

最近闲来无事改用C++刷了刷题,感觉好不习惯。。。 下面这题是combinations, 典型backtrack题 一个代码是这样的
  1. class Solution {
  2. public:
  3.     vector<vector<int> > combine(int n, int k) {
  4.         vector<vector<int> > rslt;
  5.         vector<int> path(k, 0);
  6.         combine(n, k, rslt, path);
  7.         return rslt;
  8.     }
  9. private:
  10.     void combine(int n, int k, vector<vector<int> > &rslt, vector<int> &path) {
  11.         if (k == 0) {
  12.             rslt.push_back(path);
  13.             return;
  14.         }
  15.         for (int i = n; i >= 1; i--) {
  16.             path[k - 1] = i;
  17.             combine(i - 1, k - 1, rslt, path);
  18.         }
  19.     }
  20. };
复制代码
请问下rslt.push_back(path)这一句为什么在rslt中的path不会在后来被改变呢?在java上会写成rslt.add(new ArrayList<Integer>(path)),相当于deep copy一个path 防止后来path改变的话影响到rslt,c++里头是什么机制避免了这个呢?难道push_back()自带copy吗? 楼主C++纯新手 这个问题估计比较初级 请大家指教。

评分

1

查看全部评分

iFighting 发表于 2015-7-3 13:06:06 | 显示全部楼层
Java里面秉持的一切皆引用的的思想,而C++里面push_back参数传进来的时候默认有一个拷贝复制函数。
回复 支持 反对

使用道具 举报

atlaszzz 发表于 2015-7-3 13:11:28 | 显示全部楼层
本帖最后由 atlaszzz 于 2015-7-3 13:17 编辑

http://www.cplusplus.com/reference/vector/vector/push_back/
回复 支持 反对

使用道具 举报

 楼主| glaciersilent 发表于 2015-7-3 13:33:20 | 显示全部楼层
atlaszzz 发表于 2015-7-3 13:11
http://www.cplusplus.com/reference/vector/vector/push_back/

多谢 明确说了copy
回复 支持 反对

使用道具 举报

 楼主| glaciersilent 发表于 2015-7-3 13:34:18 | 显示全部楼层
iFighting 发表于 2015-7-3 13:06
Java里面秉持的一切皆引用的的思想,而C++里面push_back参数传进来的时候默认有一个拷贝复制函数。

了解了~ 这样其实挺简洁 java的collection套collection的那种有时候还得手动copy
回复 支持 反对

使用道具 举报

stellari 发表于 2015-7-3 13:34:35 | 显示全部楼层
Q: "难道push_back()自带copy吗"

A: 简单地来说,你确实可以理解成这样。Java中的所有对象变量都是“引用”。所以,对象变量之间的赋值和拷贝,仅仅改变“某个对象的引用数”的,而不改变内存中“对象的实际数目”;但是在C++中,只要一个对象变量没有明确定义为指针或引用类型,那么这个对象变量就是“某个对象本身”,任何对象变量之间的赋值和拷贝,都会导致新对象的创建。这也就是你在private combine中为何一定要传入vector &的原因。
回复 支持 反对

使用道具 举报

 楼主| glaciersilent 发表于 2015-7-3 14:00:09 | 显示全部楼层
stellari 发表于 2015-7-3 13:34
Q: "难道push_back()自带copy吗"

A: 简单地来说,你确实可以理解成这样。Java中的所有对象变量都是“引 ...

学习了~ 不过还是有点不清楚 这个push_back()传入的是reference类型,但是传入reference的content还是会被复制并加到vector中,这是不是这个方法实现中的特别处理啊?而combine()中的引用的content就永远不会被复制
回复 支持 反对

使用道具 举报

pro 发表于 2015-7-3 17:13:16 | 显示全部楼层
glaciersilent 发表于 2015-7-3 14:00
学习了~ 不过还是有点不清楚 这个push_back()传入的是reference类型,但是传入reference的content还是会 ...

传入的的确是reference,但rslt的类型是vector<vector<int>>。元素类型是vector<int>。注意是vector<int>而不是vector<int>&。

push_back()的意思是我希望这个vector somehow在最后增加一个元素。这个元素原来是不存在的。那就只有两种选择:
1:你告诉push_back()你希望这个新元素长什么样,他照样construct一个新的放进去。
这种方案对应push_back(const T& value);
2:你已经把新元素做好了,push_back()拿到之后就直接放进去了。
这种方案对应push_back(T&& value);

第一种方案在执行过后,你给的那个引用和vector里的那个新元素显然除了长得一样之外没有任何关系。
第二种方案涉及到std::move()。在执行完之后这个元素已经被move进去了,从而不再存在于原来的scope里了。

这都是非常符合直觉的做法。并没有什么“特别”的。不要把Java中的assumption带入进来思考。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

stellari 发表于 2015-7-3 17:21:00 | 显示全部楼层
glaciersilent 发表于 2015-7-3 14:00
学习了~ 不过还是有点不清楚 这个push_back()传入的是reference类型,但是传入reference的content还是会 ...

注意a.push_back(x)的意思不是说“把x加入到a的末尾”,而是“在a的末尾添加一个新对象成员,其值由传入的x决定。”你的vector中的元素是实实在在的对象vector<int>,所以无论给入的是什么,都会真正地创建一个新的vector<int>,并加入到vector中。输入参数仅仅是用来决定新创建的这个vector<int>的内容是什么。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

sevenwonder 发表于 2015-7-4 01:59:50 | 显示全部楼层
pro 发表于 2015-7-3 17:13
传入的的确是reference,但rslt的类型是vector。元素类型是vector。注意是vector而不是vector&。

push ...

第二种方案表示没见过。能否再多说点啊?
回复 支持 反对

使用道具 举报

 楼主| glaciersilent 发表于 2015-7-4 03:46:45 | 显示全部楼层
pro 发表于 2015-7-3 17:13
传入的的确是reference,但rslt的类型是vector。元素类型是vector。注意是vector而不是vector&。

push ...

Thanks~ 说的太清楚了
回复 支持 反对

使用道具 举报

 楼主| glaciersilent 发表于 2015-7-4 03:46:59 | 显示全部楼层
stellari 发表于 2015-7-3 17:21
注意a.push_back(x)的意思不是说“把x加入到a的末尾”,而是“在a的末尾添加一个新对象成员,其值由传入 ...

多谢 彻底明白了!
回复 支持 反对

使用道具 举报

pro 发表于 2015-7-4 06:21:33 | 显示全部楼层
sevenwonder 发表于 2015-7-4 01:59
第二种方案表示没见过。能否再多说点啊?

http://en.cppreference.com/w/cpp/container/vector/push_back
看这个例子吧。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 13:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表