Chinaunix

标题: 问一个有关于c++ vector的问题 [打印本页]

作者: redpigcool 时间: 2012-04-18 13:59
标题: 问一个有关于c++ vector的问题
想问问，对于vector，如果想向其中添加元素，是不是只能用push_back （insert end）。

感觉push_back的效率对于小的元素来说还可以，如果push的是一个大的元素，那么其间的拷贝的开销有些大。

以前写C的时候，都是直接向数组的最后一个元素的后面一个写入，然后再手动的增加数组大小。这样不需要一个从一个临时元素转到最后的数组中。

不过对与c++的vector，不知道有没有这样的方法，可不可以访问vector最后一个元素后面那个元素（end（）），然后再增加vector的size。

网上查了查，没发现可以有这样做的，所以想问问大家对于vector中储存大元素是怎么处理的。

作者: mpstat 时间: 2012-04-18 14:04
....这都什么乱七八糟的,拷贝文件的效率跟vector扩容的效率有关系吗?

作者: 幻の上帝 时间: 2012-04-18 14:05
resize什么的然后直接访问。
元素构造开销不能无视的，或者觉得resize分配空间的时机不靠谱的，可以事先reserve。

作者: hgrany 时间: 2012-04-18 16:06
你往里push_back对象,开销能不大嘛. push_back本身就会产生 replacement new. 更别说resize时的对象复制了.

往里放指针才是王道. 如果非要放对象, 也不是没办法. 用vs2010以上版本的, 使用move constructor

作者: 家住马戏团 时间: 2012-04-18 18:40
同四楼，存指针，
有个还不错的办法，写一个objectpool，管理足够多的对象，需要用到时去objectpool中申请。

作者: redpigcool 时间: 2012-04-19 03:12

hgrany 发表于 2012-04-18 16:06
你往里push_back对象,开销能不大嘛. push_back本身就会产生 replacement new. 更别说resize时的对象复制了. ...

还是这个问题，如果是存指针，那么对象也要放在一个地方，这样指针才有意义，对象放在那里呢？另开一个数组么？

即便是放在另一个数组，如果这个数组的大小不够，也要realloc，那么之前存放的指针也就没有意义了。

个人感觉vector添加元素的方法还是不够灵活。。。

作者: walleeee 时间: 2012-04-19 03:36
呵呵，cu终于有人考虑到这个问题了。

动态数据结构少用，这是原则。

对于你这里的知道大小可以resize之后，直接下标访问你的元素。

但是我们自己对Array类有自己的设计，我们的办法简单，一个Alloc接口，直接返回已经管理好的，并length+1。

push_back这些接口就是用来愚弄学生的，但是还在被大行其道的教，乱用错用，导致问题太多了，最后回过头来说c++咋样咋样的不好，低效，未免一叶障目了。

对于一些常见的，看似动态，其实某些层面来说并非动态，比如path这个东西，一般认为不知道该多大。
但是我都是用1k字符数组来放，对99.999%来说，这足够了。非要用个string，然后说我的不对。
我说，对，你说的是对，我的确用得有问题，只是没关系，你用string吧。

作者: walleeee 时间: 2012-04-19 03:41
回复 5# 家住马戏团

我觉得你说的都不是办法。

只是你说的也是大多数常见的所谓办法。

pool这个东西可以加在很多个层面之间，stl的alloctor就算是一种，还可以直接加在malloc这个层面，就是heapalloc就算一个。
内存一般不要pool，因为malloc等没你想的那么弱，你程序分配5亿次内存，看看一共花多少时间？如果内存都成了效率瓶颈，那程序员真该去死了。但是问题是该不该浪费，比如你这里说的去存个指针什么的，显然不不该去浪费的，因为没那个必要。

对于其他资源，比如文件，比如线程，这些东西加个pool就显得合理，因为创建这些对象太麻烦，中间过程需要太多的计算，况且这些资源一般都比较固定。

作者: walleeee 时间: 2012-04-19 03:47
总之，如果你非要用vector，并且知道要多大，那直接resize再用，如果你不知道多大，也非要用vector，那你可以按照马戏团说的，存指针。这里还有个问题就是vector的设计是存pod类似的资源，就是存平凡的资源，对于非平凡资源就比较麻烦，存指针也算是一个选择。但是存指针问题来了，你使用起来又不方便，所以还是麻烦。

所以，不要随意去用什么vector这些东西，应该根据自己的需要设计一个数据结构。通用和泛型，这些不过是某些人的意淫，并给你看到了几个特例而已，真正的现实项目中，很少发现。当然，话又说回来，抽象本来就是一个基本能力也是终极能力，把一些常见的功能，常用的数据结构提炼出来，这是应该的，值得这么做。但是不要想到是一了百了，随便都可以用，这就不太好。

前面都当我自己在说，看懂也好，看不懂也好，没关系，我只是记在这里而已。

作者: walleeee 时间: 2012-04-19 03:49
回复 4# hgrany

move语义还是会有转移构造被调用，这里任然需要拷贝内存。

但是move语义有个好处，就是对一些非平凡资源，比如文件描述符等，那就是好东西了。

move语义在我看来算是11的一个亮点，其实也不过是块补丁。

作者: walleeee 时间: 2012-04-19 03:51
回复 3# 幻の上帝

reserve是一个预估。必说的也不错，先reserve，然后直接获取地址下标来拷贝（[]而非at这个，之间区别你懂）。最后来个resize。我不记得resize是否会重新去分配内存并把之前的无效。如果没有，那当然这么做也还勉强行。

vector这个名字也是个邪门，向量，呵呵，真想得出来。

作者: walleeee 时间: 2012-04-19 03:54
LZ这里还有个问题就是，是否过早优化？我觉得，即便就算是直接按照你原路的用，vector也不该成为整个程序的效率瓶颈（除非你就是个计算密集程序）。有空优化下磁盘，买个ssd来用用，或者优化下网络，这些都比优化内存更爽。

还有，调整高层面的结构有时候也会拿到意外的效率提升。但是这个比较难，别龙巧成拙。

作者: 家住马戏团 时间: 2012-04-19 06:48
本帖最后由家住马戏团于 2012-04-19 06:49 编辑

回复 8# walleeee

分配内存自然不会是瓶颈，但一些大对象的构造还是很耗时的，C++不比C，很多情况下构造函数里都会有复杂的初始化过程，这样在运行时动态创建，然后用完析构的话，耗时就很多。所以在程序的一开始创建足够多的对象，用pool保存，程序结束时释放，这样节省下来的时间就颇客观，当然只在内存充裕的情况适用。

作者: newmax123 时间: 2012-04-19 08:56
vector的push 成为你的瓶颈了吗？
瓶颈在于对象的构造？
用指针解决。多次new 造成的内存碎片问题？已经成为问题了？
简单办法减少不必有的new delete. 复杂办法 pool 解决终极办法随机应变，选择一个适合的办法

1k buff 存放string 足够了？业务环境不同毫无可比性，你做一下爬虫试试看。

在没有足够的水平前不要妄图自己写一个自增长的array, 你的水平还不够。反驳我？你把 stl 源码看一遍以后再来谈这个问题。

作者: hgrany 时间: 2012-04-19 09:05
回复 6# redpigcool

都有指针了,怎么还会不知道对象放在呢? 你不会是把所有的对象都放栈上吧.

作者: hgrany 时间: 2012-04-19 09:19
回复 10# walleeee

一个设计良好的move函数, 是不会有内存,资源复制的. 本质上来说, move ctor就是旧的放弃所有权,新的获得. 用不着拷贝.

但很多时候事情并不都是那么完美. 这里所说的设计良好,限制还是挺多的. 比如, 一个新类的成员是另一个类的实例, 这个类可能是很久以前写的, 属于我们触碰不到的部分. 那些老代码自然不可能有move ctor了. 这种情况下给新类加move ctor是没有意义的.

存指针不存对象的另外一个重要原因是: 你不可能push_back 一个派生类的实例到存储基类对象的vector中去.

作者: redpigcool 时间: 2012-04-19 09:37

walleeee 发表于 2012-04-19 03:54
LZ这里还有个问题就是，是否过早优化？我觉得，即便就算是直接按照你原路的用，vector也不该成为整个程序的 ...

恩，谢谢你的意见。我之前一直都写c，虽然麻烦点，但是自己都能控制。

但是现在要用别人写的c++的接口，必须要用C++，所以这个问题也只是提前想了想，因为我写的确实是超级计算密集型的程序，不是一般的应用软件。

感觉每个对象都new一下，然后再存指针这个方法不太可行，因为对象的数量级太大。哎要是能不用c++还真是不想用，用了c++又懒得自己写数据结构，毕竟有stl。

作者: shanehan 时间: 2012-04-19 11:57
这么纠结，你心里应该知道怎么解决，内存池也可以，自己写数据结构也可以，就是懒得写，妄想stl有解决方案，是吧？

作者: redpigcool 时间: 2012-04-19 12:29

shanehan 发表于 2012-04-19 11:57
这么纠结，你心里应该知道怎么解决，内存池也可以，自己写数据结构也可以，就是懒得写，妄想stl有解决方案， ...

哈哈，是啊，被你说中了。既然都从c到c++了，当然希望能少写的东西，毕竟拖着stl那么大一个库。

当然如果实在不行，还是要自己写。。。

作者: gtkmm 时间: 2012-04-19 12:36

向vector里放smart_pointer，
或者用boost里的侵入式容器。

作者: 幻の上帝 时间: 2012-04-19 12:36

walleeee 发表于 2012-04-19 03:51
回复 3# 幻の上帝

resize是可能会初始化/销毁对象的。得考虑元素构造/析构开销的话还是指针吧。
vector本身不邪门，倒是“向量”这个翻译邪门。vector本来就兼有直观几何意义和代数意义两方面含义，并且以现代数学的观点来看后者才是本质。“向量”字面上只强调了一方面，数学课又先讲直观意义，难免有些误导。

上面有人说的move不会有内存复制也太绝对了点。基本类型的move和copy开销是一样的。就算对象里面只有指针成员，数量多了move也成问题（当然比deep copy是好多了），要是dereference相对move/copy操作频率少的话宁可再加一层指针。

作者: SpringfieldKing 时间: 2012-04-19 12:41
同意二楼，如果觉得内存拷贝都算慢的话，那就没有快的了

作者: SpringfieldKing 时间: 2012-04-19 12:44
回复 7# walleeee

和push_back有什么关系

作者: 幻の上帝 时间: 2012-04-19 13:07
回复 23# SpringfieldKing

即便是已经reserve了不重分配空间，push_back也得维护size，如果事先知道有多少的话就增加size的操作浪费了。
更何况很多人根本就没reserve的意识……

作者: walleeee 时间: 2012-04-19 13:13
回复 23# SpringfieldKing

你说有什么关系？

作者: 幻の上帝 时间: 2012-04-19 13:14

walleeee 发表于 2012-04-19 03:47
总之，如果你非要用vector，并且知道要多大，那直接resize再用，如果你不知道多大，也非要用vector，那你可 ...

存指针要是用unique_ptr/shared_ptr复杂性倒是可以接受的。
通用不是意淫，尽管经常带来额外的麻烦。总之记住不会用就别装着会用、滥用就好。
至于泛型，不过是在给静态类型擦屁股而已（元编程什么的论外）。

作者: walleeee 时间: 2012-04-19 13:18
回复 21# 幻の上帝

你觉得把vector另外取的名字，比如array是不是对初学者更友好？或者叫dynamic array也行。
因为我只是感觉对一些常见数据结构的称呼是：数组，列表，平衡术。。。很少听到，向量，列表，平衡术。。。
况且大多翻译过来的书都使用数组，包括在用vector的时候都叫数组。这情何以堪。

“dereference相对move/copy操作频率少的话宁可再加一层指针。”
得不偿失。就跟我说的，内存这点操作都成了瓶颈，那真是骇人听闻。另外加层指针，数据局部性这些都要遭破坏。

作者: walleeee 时间: 2012-04-19 13:29
回复 17# redpigcool

C实现一些常规数据结构的简易之处在于我个人觉得抽象层次更高，根本就抛开了是不是个所谓的对象，直接面向内存，就是一块内存，没其他资源。这里，当然可能会有一些具体的初始化函数来构造内存之外的资源。

只是问题依旧，c一样要拷贝内存，反而在拷贝之后还需要去初始化其他资源，而没有c++类似的那种析构/构造机制。这个在c社区也是有很多人在需求，要求标准实现。c++在这里就比叫好用。

我觉得你不用在这里卡着，就按“幻の上帝”他说的来。当然他那个好像也有点问题
“resize是可能会初始化/销毁对象的。得考虑元素构造/析构开销的话还是指针吧。”
所以，你如果能估量，那就估量，如果不能估量，那就只用去用指针。自己看吧，我那个Alloc不适合你用，不花一些时间去理解他的设计，用起来非常容易出错，理解了就会达到我说的，根本没有任何内存浪费，一个指针都不浪费，对于你这个问题，也不会出现拷贝这些东西。

c++有他的好处，就你这里你就体会得出来，用c来搞这个，你觉得会更简单？况且还得自己去init/free，而不能构造/析构这种语言机制。

既然是计算密集型，那可以根据需要去设计数据结构，不一定非要套个stl。我之前就和ow说了，stl极易错用乱用，因为用起来实在太方便了。最后导致的问题太多。

作者: walleeee 时间: 2012-04-19 13:39
回复 13# 家住马戏团

不是c++不比c
你要初始化的还是得初始化，有什么区别？你c不外乎去另外人肉一个初始化函数，然后来人肉调用。复杂也主要不是和语言相关，而是问题本身复杂，随便你什么语言。你可以叫c--，c++，c，c-，c+，c=随便你，甚至叫你口述，依然是那么复杂。

这样在运行时动态创建，然后用完析构的话，耗时就很多

这里说的不错。所以你前面说的pool就有这个价值。但是内存却不必。因为内存是常态资源，放回去，拿出来，就这个成对操作是很快的，因为内存一般空闲链表的实现决定了。

“所以在程序的一开始创建足够多的对象，用pool保存，程序结束时释放”
这里也不是太好。我喜欢把废弃的，暂时不用的对象存起来，比如你用一个空闲链表也可以，让后需要的时候截一个。当然，这些小技巧，以及所谓的考虑对现在的操作系统和体系结构以及计算能力，意义没有以前那么大，而且确会大大产生复杂，因为除了问题本身，这里又带来了问题，问题终会产生复杂性。叠加。

这样节省下来的时间就颇客观，当然只在内存充裕的情况适用

某些特定场合是你说的这样，非常客观。但是看情况吧，关键要能认识到整体的优化点在哪里，而不是靠猜。

作者: walleeee 时间: 2012-04-19 13:50
回复 14# newmax123

你以为我没做过你说的所谓爬虫？

url长度我知道没有明确的说法，我给16k，至今没问题，你说什么？据我所知，url在设计的时候考虑一般4k足够，很多标准也假设了是4k最大，具体rfc我现在给你找不到想不起。

1k存path，你觉得有什么问题，溢出么？win的路径一般是255字符，最多也不过512，路径层次也不会太深，对于linux下面那些文件系统，1k一般足够99.99%，你还想要什么？100%么？我觉得一个程序能80%工作就够了。大于1k的我完全可以据掉，因为我要处理那么多数据，多一个少一个无关紧要。

不是“vector的push 成为你的瓶颈了吗”，而是你说的vector不必要的扩展生长导致了拷贝复制如此等等的操作。这些你用push_back这种接口，你能避免么？除了你说的指针，这个依然要拷贝指针，你说他不是瓶颈，对，他的确不是瓶颈，那你这里和之前存对象拷贝什么区别，依然拷贝指针，你说他浪费了么？我觉得是，因为依然要存指针。数组就是数组，该怎么就怎么。

终极办法随机应变

哪里来的终极办法？算了，总之尽可能灵活的设计规避掉一些可以预料的问题，减少自己的麻烦。

你把 stl 源码看一遍以后

stl源码？哼。你以为我没看过？你太看不起人自以为是了。我看stl源码包括侯捷那本书是2，3年前的事情了。最后一次用stl也是2，3年前的事情了。还有《c++标准库扩展》这些就是放屁，《超越标准库boost》也差不多就是屁。
什么通用，什么泛型，什么可重用，真是想得美好。

作者: walleeee 时间: 2012-04-19 13:58
回复 16# hgrany

本质上来说, move ctor就是旧的放弃所有权,新的获得

一般这里必然有个资源转移，说白就是拷贝。move是对返回优化的一个标准加强，而返回优化依赖编译器实现。
让返回必须调用拷贝构造函数变成了调用转移构造，并且不调用临时对象的析构，而之前是必须会被析构，这里就必须去完全的复制拷贝，所以是一个语言级别的bug。move来修正这个。我的描述不清晰你可以去看标准给的表达。

但很多时候事情并不都是那么完美. 这里所说的设计良好,限制还是挺多的

显然是这样，凡事哪有说得那么简单。说的好听，做起来，那还是有些苦头。

那些老代码自然不可能有move ctor了. 这种情况下给新类加move ctor是没有意义的

move语义是给新代码的礼物，也为了让老代码，你说的没有move拷贝那些代码能兼容使用。这没什么问题，库一般会慢慢支持起来，因为move换来的效率还是可观的，关键是他修正了一个bug。我现在更关心的是各个编译器能快些达成一致，把标准完整实现了，这样我才敢用。c++11实现好了，是不是kde桌面会快一些？那个时候gnome咋办

你不可能push_back 一个派生类的实例到存储基类对象的vector中去

为什么不能？这里有个切片。我非要存为什么不可能，尽管这是一个普遍错误的做法。
可能是可能，只是不该这么做。

作者: walleeee 时间: 2012-04-19 13:59
回复 19# redpigcool

居然有人说stl是大库。唉

作者: walleeee 时间: 2012-04-19 14:02
回复 24# 幻の上帝

你没理解我的意思。

reserve了直接[]访问，这个不会触发例外。用完了resize一下。

当然，也可以直接resize一下，然后[]访问填充，但是你得提前知道要填充多少个。

resize里面应该也就是先reserve了再来设置大小。我只是担心我前面跟你说的，resize是不是依然会重新拷贝。讨论这个没意义。

作者: 幻の上帝 时间: 2012-04-19 22:24
回复 33# walleeee

resize()对于构造/析构开销大的对象，性能损失可能无法忽视。
全reserve()用[]访问倒不是不可以。但有个不方便的地方就是得时刻提防着不手贱。
1.超过size()的部分必须先写再读，否则UB。
2.不确认用完不resize()。
3.不push_back()之类。
照你的手法倒是可以都符合。

作者: 幻の上帝 时间: 2012-04-19 22:32
本帖最后由幻の上帝于 2012-04-19 22:34 编辑

回复 27# walleeee

动态数组应该叫什么我倒是无所谓。不过C/C++的array和传统意义上的array有相当大的区别，简单叫array说不过去。而C++11也有array了，和内建array类似，大小是编译时确定的。
得再加一层指针按你的方式理解大概是相当极端的情况了：构造函数塞了一大堆不像内存那么容易拿到的资源申请。这种风格的好坏不论，可以肯定的是实际有可能用。
上面说的“频率少”是有点不太对，实际的性能瓶颈确认起来当然没那么简单。

作者: walleeee 时间: 2012-04-19 22:37
回复 34# 幻の上帝

就这一个就让人觉得python等众舒心。效率？狗屁。

作者: walleeee 时间: 2012-04-19 22:42
回复 35# 幻の上帝

构造函数只把对象初始化到一个无效状态，比如char*置nullptr。而不要分配任何可能失败的资源。
这是原则，任何其他原则都不能破坏这个原则。

实际的性能瓶颈确认起来当然没那么简单

当然。这需要一些经验，甚至要靠运气，猜测和实验。不过也有一些做这个事情的工具。

作者: redpigcool 时间: 2012-04-20 11:49
回复 37# walleeee

恩，谢谢。我也是这么想的，既然不能控制调用构造的时机，尽量把构造函数的开销降到最低，然后根据需要初始化。

作者: walleeee 时间: 2012-04-20 15:08
回复 38# redpigcool

这个原则，之所以这样做，并非为了你说的效率那么简单。事情很复杂，你多实验，大可以用你现在觉得正确的方式来搞，搞多了就会有想法。

作者: 幻の上帝 时间: 2012-04-20 19:09
回复 37# walleeee

很遗憾，现实是构造函数仅表示对象生存期即将开始，并没有断言这个对象之后行为的丰富含义。
所以一些构造函数扮演重要角色的惯用法，如RAII、scope guard，就拒绝这种假设——额外的、不必要的对代码可靠性的依赖。
当然你可以约定这么做（顺便可以多加点限制，像构造函数禁止抛出异常等等），但既然没有任何规则保证这个限制总是成立，语言也没有提供检查违反这种约束的能力，你不得人肉检查所有还没有取得你信任的代码，或者干脆不使用这些代码。
于我而言，我拿不出精力集中于此，或者说宁可把这方面精力放在使程序更通用上（因为这不仅能解决这一个问题）。

可能根本的关键点在于，你认为对象应该只是状态的抽象，而我认为不仅如此——语言的规则限定了的既成事实就是这样（虽然我也不满这点：http://bbs.chinaunix.net/thread-3607796-9-1.html，88L）。

作者: 家住马戏团 时间: 2012-04-20 19:11
回复 37# walleeee

谁定的这个原则？

作者: newmax123 时间: 2012-04-23 13:43

walleeee 发表于 2012-04-19 13:50
回复 14# newmax123

url长度我知道没有明确的说法，我给16k，至今没问题，你说什么？据我所知，url在设计的时候考虑一般4k足够，很多标准也假设了是4k最大，具体rfc我现在给你找不到想不起。

1k存path，

16K 至今没问题，这就是你对代码的态度？
除了url ,需要关系的数据多了.

关于使用那种方法，我说得很清楚，只有最合适的方法，没有最好的方法，从目前情况看，我提供的方法是修改最少的。如果在特定的环境下，array比stl list 快上1个数量级也是毫无问题的，关键就是看环境的选择。

至于你喷stl boost烂的做法，我只想说我所公事的工程师里有中国最好的c++ 开发者之一，他为boost 写的库，也被要求提供这提供那，而且boost 本身的库质量是否如你所说如此的烂？请你用你的代码写出些比boost 更棒的东西再来喷。

作者: walleeee 时间: 2012-04-23 13:49
回复 43# newmax123

那你说说有什么数据需要关心？

算了，我问你一个问题，既然你做过爬虫，你当时是怎么存的url？

关于使用那种方法，我说得很清楚，只有最合适的方法，没有最好的方法，从目前情况看，我提供的方法是修改最少的。如果在特定的环境下，array比stl list 快上1个数量级也是毫无问题的，关键就是看环境的选择。

屁话。不要说屁话。论坛上屁话太多。

至于你喷stl boost烂的做法，我只想说我所公事的工程师里有中国最好的c++ 开发者之一，他为boost 写的库，也被要求提供这提供那，而且boost 本身的库质量是否如你所说如此的烂

滚，你这个一出，小心引来天雷

请你用你的代码写出些比boost 更棒的东西再来喷。

我写不出来是不是可以证明boost就很好？你逻辑没问题？你确定？

你先回答我前面那个问题再说。

作者: newmax123 时间: 2012-04-27 21:22

walleeee 发表于 2012-04-23 13:49
回复 43# newmax123

屁话多的是你，破坏一个世界很容易，我们要的是创建一个世界。眼高手低的主，哥哥我见得多了去了。不爽你可以把哥哥所有的帖子都翻一下，还有哥哥的大号你也去翻翻看。

至于boost, 你以为那帮子高手都像你这么弱智，写些东西出来被人骂？感觉不好就干翻别人的作品再来喷，否则你就老老实实的接受这个现实。

至于url 应该怎么存储，你就继续用你的16k buff吧。爬虫需要存储的就是个url吗？

作者: walleeee 时间: 2012-04-27 21:43
回复 45# newmax123

你写的有哪一句是实实在在有价值的话，不是屁话是什么？滚你md。

老子曾经在某公司，就有人号称它们的员工是目前国内算是最顶尖的，我艹，还不如cu上某些搞标准的强。

你觉得boost很强那是你的事，然后你也觉得你们公司搞boost的人强，我艹，你继续梦呓吧，并且，别人强不强关你鸟事。

最后，不要动不动冒出来说些没价值的屁话，老子看得都烦了，你自己看，是不是到处都是屁话。

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)