对大数据量（5w左右条记录）如何选择stl容器

Question

如题，我有5万条记录，我目前是存储在vector<ClassA>,然后按照某个关键字排序（用的是STL的sort排序），但是改成vector<ClassA*> 速度稍有改进，还是不能满足要求，是不是我容器选错了，求各位高人指点，这些记录没有重复值，只是做一个排序操作，后续就是按照读入的记录访问就可以了

Answer 1

后续就是按照读入的记录访问就可以, 如果这样可以用map应该更好些

Answer 2

用map好一些，二叉树的效率高一些。。但是要键值唯一性

Answer 3

容器可以使用reserve(似乎是),预先分配一部分,同时 设置分配粒度.比如当前满了 则再扩展N个,而不是1个1个扩展.
vector 内部的数据格式 和数组一样. 程序再操作时 比如更新
是先申请 原元素个数N+1 的内存,然后把原内容复制,过去,然后再删除原内存,数据量大用reserve预先分配
可以节约很多次内存从新分配和释放 应该可以改善情况.

Answer 4

就用vector<class*>类型，自己写个堆排序，我这有代码http://blog.csdn.net/zipper9527/article/details/6107107，你可以参考，速度上不会有问题的，排序是交换指针，不调用拷贝构造函数，已经很快了。另外map好像不支持排序参数，内部顺序是自动的。

Answer 5

速度稍有不能满足要求，问题不明确。
如果是排序速度不够，那么用list。
如果是查询速度不够，那么用vector，查询速度没有方法比vector折半查找更快。

Answer 6

排序很慢，同样的数据JAVA版本ArrayList.sort排序速度，与我改成C++版本后相比，C++明显慢很多！

Answer 7

如果stl解决不了。
网上有一个Qsort的代码，排1000万个int用时1秒，
5wan个class数据，如果排序指针，也就是瞬间的事了。

Answer 8

大数据量，自个用数组处理，安心。
stl容器，效率难保证