C++ 动态排序的 STL 容器

Dynamically sorted STL containers

提问by dlanod

I'm fairly new to the STL, so I was wondering whether there are any dynamically sortable containers? At the moment my current thinking is to use a vector in conjunction with the various sort algorithms, but I'm not sure whether there's a more appropriate selection given the (presumably) linear complexity of inserting entries into a sorted vector.

我对 STL 还很陌生，所以我想知道是否有任何可动态排序的容器？目前，我目前的想法是将向量与各种排序算法结合使用，但鉴于将条目插入排序向量的（大概）线性复杂性，我不确定是否有更合适的选择。

To clarify "dynamically", I am looking for a container that I can modify the sorting order at runtime - e.g. sort it in an ascending order, then later re-sort in a descending order.

为了“动态”澄清，我正在寻找一个可以在运行时修改排序顺序的容器 - 例如按升序对其进行排序，然后按降序重新排序。

采纳答案by moswald

If you know you're going to be sorting on a single value ascending and descending, then set is your friend. Use a reverse iterator when you want to "sort" in the opposite direction.

如果您知道要按升序和降序对单个值进行排序，那么 set 就是您的朋友。当您想以相反的方向“排序”时，请使用反向迭代器。

If your objects are complex and you're going to be sorting in many different ways based on the member fields within the objects, then you're probably better off with using a vector and sort. Try to do your inserts all at once, and then call sort once. If that isn't feasible, then deque may be a better option than the vector for large collections of objects.

如果您的对象很复杂，并且您将根据对象内的成员字段以多种不同的方式进行排序，那么使用向量和排序可能会更好。尝试一次完成所有插入，然后调用 sort 一次。如果这不可行，那么对于大型对象集合，deque 可能是比 vector 更好的选择。

I think that if you're interested in thatlevel of optimization, you had better be profiling your code using actual data. (Which is probably the best advice anyone here can give: it may not matter that you call sort after each insert if you're only doing it once in a blue moon.)

我认为，如果您对这种级别的优化感兴趣，最好使用实际数据分析您的代码。（这可能是这里任何人都可以给出的最好建议：如果您只在蓝色月亮中执行一次，则在每次插入后调用 sort 可能无关紧要。）

回答by Doug T.

You'll want to look at std::map

你会想看看 std::map

std::map<keyType, valueType>

The map is sorted based on the < operator provided for keyType.

地图根据为 keyType 提供的 < 运算符进行排序。

Or

或者

std::set<valueType>

Also sorted on the < operator of the template argument, but does not allow duplicate elements.

也按模板参数的 < 运算符排序，但不允许重复元素。

There's

有

std::multiset<valueType>

which does the same thing as std::set but allows identical elements.

它与 std::set 做同样的事情，但允许相同的元素。

I highly reccomend "The C++ Standard Library" by Josuttis for more information. It is the most comprehensive overview of the std library, very readable, and chock full of obscure and not-so-obscure information.

我强烈推荐 Josuttis 的“C++ 标准库”以获取更多信息。它是 std 库最全面的概述，非常易读，并且充满了晦涩难懂的信息。

Also, as mentioned by 17 of 26, Effective Stl by Meyers is worth a read.

此外，正如 26 篇中的 17 篇所述，Meyers 的 Effective Stl 值得一读。

回答by Max Lybbert

It sounds like you want a multi-index container. This allows you to create a container and tell that container the various ways you may want to traverse the items in it. The container then keeps multiple lists of the items, and those lists are updated on each insert/delete.

听起来您想要一个多索引容器。这允许您创建一个容器并告诉该容器您可能想要遍历其中的项目的各种方式。然后容器保留多个项目列表，并且在每次插入/删除时更新这些列表。

If you really want to re-sort the container, you can call the std::sortfunction on any std::deque, std::vector, or even a simple C-style array. That function takes an optional third argument to determine how to sort the contents.

如果您真的想对容器重新排序，您可以std::sort在任何std::deque、std::vector甚至是简单的 C 样式数组上调用该函数。该函数采用可选的第三个参数来确定如何对内容进行排序。

回答by hazzen

The stlprovides no such container. You can define your own, backed by either a set/multisetor a vector, but you are going to have to re-sort every time the sorting function changes by either calling sort(for a vector) or by creating a new collection (for set/multiset).

在stl没有提供这样的容器。您可以定义自己的，由 aset/multiset或 a 支持vector，但每次排序函数更改时，您都必须通过调用sort（for a vector）或创建新集合（for set/multiset）来重新排序。

If you just want to change from increasing sort order to decreasing sort order, you can use the reverse iterator on your container by calling rbegin()and rend()instead of begin()and end(). Both vectorand set/multisetare reversible containers, so this would work for either.

如果你只是想改变增加的排序顺序递减排序顺序，您可以通过调用使用容器上的反向迭代器rbegin()和rend()而不是begin()和end()。这两个vector和set/multiset是可逆的容器，所以这会为工作的。

回答by Torlack

std::setis basically a sorted container.

std::set基本上是一个排序的容器。

回答by JProgrammer

The answer is as always it depends.

答案一如既往，视情况而定。

setand multisetare appropriate for keeping items sorted but are generally optimised for a balanced set of add, remove and fetch. If you have manly lookup operations then a sorted vectormay be more appropriate and then use lower_boundto lookup the element.

set并且multiset适用于保持项目排序，但通常针对一组平衡的添加、删除和获取进行了优化。如果您有男子气概的查找操作，则 sortedvector可能更合适，然后用于lower_bound查找元素。

Also your second requirement of resorting in a different order at runtime will actually mean that setand multisetare not appropriate because the predicate cannot be modified a run time.

此外，您在运行时以不同顺序使用的第二个要求实际上意味着set并且multiset不合适，因为不能在运行时修改谓词。

I would therefore recommend a sorted vector. But remember to pass the same predicate to lower_boundthat you passed to the previous sort as the results will be undefined and most likely wrong if you pass the wrong predicate.

因此，我会推荐一个排序向量。但是请记住将相同的谓词lower_bound传递给您传递给前一个排序的谓词，因为如果您传递错误的谓词，结果将是未定义的并且很可能是错误的。

回答by zweiterlinde

You should definitely use a set/map. Like hazzen says, you get O(log n) insert/find. You won't get this with a sorted vector; you can get O(log n) find using binary search, but insertion is O(n) because inserting (or deleting) an item may cause all existing items in the vector to be shifted.

您绝对应该使用集合/地图。就像 hazzen 说的，你得到 O(log n) 插入/查找。你不会用排序的向量得到这个；您可以使用二分搜索获得 O(log n) 查找，但插入是 O(n)，因为插入（或删除）一个项目可能会导致向量中的所有现有项目被移动。

回答by yrp

It's not that simple. In my experience insert/delete is used less often than find. Advantage of sorted vector is that it takes less memory and is more cache-friendly. If happen to have version that is compatible with STL maps (like the one I linked before) it's easy to switch back and forth and use optimal container for every situation.

没那么简单。根据我的经验，插入/删除的使用频率低于查找。排序向量的优点是占用内存少，对缓存更友好。如果碰巧有与 STL 映射兼容的版本（就像我之前链接的那个），很容易来回切换并为每种情况使用最佳容器。

回答by ugasoft

in theory an associative container (set, multiset, map, multimap) should be your best solution.

理论上，关联容器（set、multiset、map、multimap）应该是最好的解决方案。

In practice it depends by the average number of the elements you are putting in. for less than 100 elements a vector is probably the best solution due to: - avoiding continuous allocation-deallocation - cache friendly due to data locality these advantages probably will outperform nevertheless continuous sorting. Obviously it also depends on how many insertion-deletation you have to do. Are you going to do per-frame insertion/deletation?

实际上，这取决于您放入的元素的平均数量。对于少于 100 个元素，向量可能是最好的解决方案，因为： - 避免连续分配-解除分配 - 由于数据局部性，缓存友好，但这些优势可能会胜过连续排序。显然，这还取决于您必须执行多少次插入-删除操作。您要进行每帧插入/删除吗？

More generally: are you talking about a performance-critical application?

更笼统地说：您是在谈论性能关键型应用程序吗？

remember to not prematurely optimize...

记住不要过早优化...

回答by user864791

Set and multiset use an underlying binary tree; you can define the <= operator for your own use. These containers keep themselves sorted, so may not be the best choice if you are switching sort parameters. Vectors and lists are probably best if you are going to be resorting quite a bit; in general list has it's own sort (usually a mergesort) and you can use the stl binary search algorithm on vectors. If inserts will dominate, list outperforms vector.

Set 和 multiset 使用底层二叉树；您可以定义 <= 运算符供您自己使用。这些容器保持自己排序，因此如果您要切换排序参数，则可能不是最佳选择。如果您要大量使用，向量和列表可能是最好的；一般来说，列表有它自己的排序（通常是归并排序），您可以对向量使用 stl 二进制搜索算法。如果插入占主导地位，则列表优于向量。