排序好的 STL list 插入元素怎么做最好？

neodreamerus

最近学习STL，并且用了用list，发现效率很低。
不知道问题出在哪里。

要实现的东西如下：程序需要不断读入数据，每次读入的数据解析成一个Object，
并放入STL Container, 我用的container 是list, 因为这些Object需要排序。

我是这么做的：

先定义一个list 叫objlist,
list<Object> objlist;

然后每次读到一个新的Object就将它排序插入该list，方法是定义一个tmp list, 然后放入新读到的new_object,
然后调用objlist的merge函数。

list<Object> tmp;
tmp.push_back(new_object);
objlist.merge(tmp, compare);

但是这样做很运行起来很慢, 怎么做才可以快点呢.
最后list大概有15万个Object，每个Object大概是60个字节。

自己用C实现的list, 新元素插入时用最简单的linear search找到插入位置，最后运行时间是用STL list的1/10

drangon

list你也可以用linear search，然后insert的啊，为什么要临时的list然后merge呢？

如果真的有排序需求，插入比较多，用树才对啊，比如set

windoze

回复 1# neodreamerus

我用的container 是list, 因为这些Object需要排序

这个因果关系怎么来的？

seanking1987

用tmp.list再merge是因为merge合并两个列表产生一个整齐排列的组合链表吗？

我查了下list有个排序(sort)，用原有的list先push_back再用sort不知道是不是会快一些

fender0107401

list里面存指针，别直接存对象。

fender0107401

还有就是为什么要merge呢？

neodreamerus

回复 3# windoze
用Vector排序的话会把要排序的对象拷贝很多次, 所以用list


   

neodreamerus

回复 6# fender0107401
merge的话会排序

   

windoze

回复 7# neodreamerus

简单的话，你可以不在容器里放元素，放个unique_ptr，这样元素就不会多次copy
当然，既然你一直需要元素是有序的，最根本的方法还是用set，如果元素会重复就用multiset。

幻の上帝

neodreamerus 发表于 2015-09-05 11:01
回复 3# windoze
用Vector排序的话会把要排序的对象拷贝很多次, 所以用list

标准库里的不管什么容器直接对付的元素都是能CopyConstructible/MoveConstructible（看具体操作）的值，所以避免元素复制不是选择容器的理由。要减少开销要么实现转移构造要么就直接用智能指针代替；要有序就该直接用关联容器。
选择序列容器的合理理由是不需要快速根据键访问且需要根据位置随机访问或减少其它开销。选择forward_list/list而不是其它序列容器的合理理由是不需要随机访问、需要O(1)插入/删除、需要splice或需要插入删除不导致其它迭代器失效的迭代器。选择list而不是forward_list的合理理由是需要两端操作或双向迭代。
LZ从一开始就错得离谱。