std::list 或 std::multimap
嘿，我现在有一个我创建的结构列表，每次添加新对象时我都会使用 std::list 排序方法对这个列表进行排序。 我想知道使用 std::multimap 或 std::list 会更快， 因为我每帧都会迭代整个列表（我正在制作游戏）。
我想听听您的意见，对于这次事件我应该使用什么。
Hey, I right now have a list of a struct that I made, I sort this list everytime I add a new object, using the std::list sort method.
I want to know what would be faster, using a std::multimap for this or std::list,
since I'm iterating the whole list every frame (I am making a game).
I would like to hear your opinion, for what should I use for this incident.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
std::multimap 可能会更快，因为每次插入的时间复杂度为 O(log n)，而列表的插入和排序则为 O(n log n)。
根据您的使用模式，您可能更适合使用排序的
向量。如果您一次插入一大堆项目，然后进行大量读取（即读取和写入不交错），那么您将使用vector、std 获得更好的性能::sort和std::binary_search。std::multimapwill probably be faster, as it is O(log n) per insertion, whereas an insert and sort of the list is O(n log n).Depending on your usage pattern, you might be better off with sorted
vectors. If you insert a whole bunch of items at once and then do a bunch of reads -- i.e. reads and writes aren't interleaved -- then you'll have better performance withvector,std::sort, andstd::binary_search.您可以考虑使用 lower_bound 算法来查找插入列表的位置。 http://stdcxx.apache.org/doc/stdlibref/lower-bound。 html
编辑：根据 Neil 的评论，请注意，这适用于任何序列容器（向量、双端队列等）
You might consider using the lower_bound algorithm to find where to insert into your list. http://stdcxx.apache.org/doc/stdlibref/lower-bound.html
Edit: In light of Neil's comment, note that this will work with any sequence container (vector, deque, etc.)
如果您不需要键/值对，
std::set或std::multiset可能比使用std::multimap更好。std::set参考：http://www.cplusplus.com/reference/stl/set/
参考对于
std::multiset：http://www.cplusplus.com/reference/stl/multiset/
编辑: (之前好像没说清楚)
一般来说，使用
std::(multi)set或std:(multi)map等容器比使用std::list更好> 并在每次插入元素时对其进行排序，因为std::list在容器中间插入元素时表现不佳。If you do not need Key/Value pairs
std::setorstd::multisetis probably better than usingstd::multimap.Reference for
std::set:http://www.cplusplus.com/reference/stl/set/
Reference for
std::multiset:http://www.cplusplus.com/reference/stl/multiset/
Edit: (seems like it was unclear before)
It is in general better to use a container like
std::(multi)setorstd:(multi)mapthan usingstd::listand sorting it afterwards everytime an element is inserted becausestd::listdoes not perform very good in inserting elements in the middle of the container.一般来说，迭代一个容器可能会花费与迭代另一个容器一样多的时间，因此，如果您不断向一个容器添加内容，然后迭代它，那么主要的问题是选择一个容器，以避免不断地重新分配内存和快速按照您想要的方式插入。
列表和多重映射都将避免仅仅通过添加元素来重新分配自身（就像使用向量一样），所以这主要是插入需要多长时间的问题。添加到列表末尾的时间复杂度为 O(1)，而添加到多重映射的时间复杂度为 O(log n)。但是，multimap 会按排序顺序插入元素，而如果您希望对列表进行排序，则必须在 O(n log n) 中对列表进行排序，或者以排序方式插入元素类似于 lower_bound 的东西，其复杂度为 O(n)。无论哪种情况，使用该列表都会更糟糕（至少在最坏的情况下）。
一般来说，如果您按排序顺序维护一个容器并不断向其中添加内容，而不是创建它并对其进行一次排序，则集合和映射会更有效，因为它们被设计为可排序的。当然，与往常一样，如果您真的关心性能，那么您需要做的是分析您的特定应用程序并查看哪个效果更好。然而，在这种情况下，我想说这几乎可以保证多重映射会更快（特别是如果你有很多元素的话）。
Generally speaking, iterating over a container is likely to take about as much time as iterating over another, so if you keep adding to a container and then iterating over it, it's mainly a question of picking a container that avoids constantly having to reallocate memory and inserts the way you want quickly.
Both list and multimap will avoid having to reallocate themselves simply from adding an element (like you could get with a vector), so it's primarily a question of how long it takes to insert. Adding to the end of a list will be O(1) while adding to a multimap will be O(log n). However, the multimap will insert the elements in sorted order, while if you want to have the list be sorted, you're going to have to either sort the list in O(n log n) or insert the element in a sorted manner with something like lower_bound which would be O(n). In either case, it will be far worse (in the worst case at least) to use the list.
Generally, if you're maintaining a container in sorted order and continually adding to it rather than creating it and sorting it once, sets and maps are more efficient since they're designed to be sorted. Of course, as always, if you really care about performance, profiling your specific application and seeing which works better is what you need to do. However, in this case, I'd say that it's almost a guarantee that multimap will be faster (especially if you have very many elements at all).