动态排序的 STL 容器
我对STL相当陌生，所以我想知道是否有动态可排序的容器？ 目前，我当前的想法是将向量与各种排序算法结合使用，但考虑到将条目插入排序向量的（大概）线性复杂性，我不确定是否有更合适的选择。
为了“动态地”澄清，我正在寻找一个可以在运行时修改排序顺序的容器 - 例如，按升序排序，然后按降序重新排序。
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.
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（12）
STL 映射和集合都是排序容器。
我赞同 Doug T 的书籍推荐——Josuttis STL 书是我见过的最好的学习书和参考书。
Effective STL也是一本学习STL内部细节以及什么的优秀书籍你应该做和不应该做的事。
STL maps and sets are both sorted containers.
I second Doug T's book recommendation - the Josuttis STL book is the best I've ever seen as both a learning and reference book.
Effective STL is also an excellent book for learning the inner details of STL and what you should and shouldn't do.
对于“STL 兼容”排序向量，请参阅 Loki 中的 A. Alexandrescu 的 AssocVector。
For "STL compatible" sorted vector see A. Alexandrescu's AssocVector from Loki.
答案一如既往，视情况而定。
set和multiset适用于保持项目排序，但通常针对添加、删除和获取的平衡集进行优化。 如果您有男性查找操作，那么排序的向量可能更合适，然后使用lower_bound来查找元素。此外，在运行时以不同顺序进行排序的第二个要求实际上意味着
set和multiset不合适，因为谓词无法在运行时修改。因此我会推荐一个排序向量。 但请记住将与传递给上一个排序的相同谓词传递给
lower_bound，因为如果传递错误的谓词，结果将是未定义的并且很可能是错误的。The answer is as always it depends.
setandmultisetare 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 sortedvectormay be more appropriate and then uselower_boundto lookup the element.Also your second requirement of resorting in a different order at runtime will actually mean that
setandmultisetare not appropriate because the predicate cannot be modified a run time.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.集合和多重集合使用底层二叉树； 您可以定义 <= 运算符供您自己使用。 这些容器会自行排序，因此如果您要切换排序参数，可能不是最佳选择。 如果您要大量使用向量和列表，那么向量和列表可能是最好的； 一般来说，列表有它自己的排序（通常是合并排序），您可以在向量上使用 stl 二进制搜索算法。 如果插入占主导地位，则列表优于向量。
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.
事情没那么简单。 根据我的经验，插入/删除的使用频率低于查找。 排序向量的优点是占用更少的内存并且对缓存更友好。 如果碰巧有与 STL 映射兼容的版本（就像我之前链接的版本），那么很容易来回切换并针对每种情况使用最佳容器。
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.
您绝对应该使用集合/地图。 就像 hazzen 所说，插入/查找的时间复杂度为 O(log n)。 你不会用排序向量得到这个； 使用二分查找可以得到 O(log n) 的查找结果，但插入的时间复杂度为 O(n)，因为插入（或删除）一个项目可能会导致向量中所有现有的项目发生移位。
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.
理论上，关联容器（集合、多重集合、映射、多重映射）应该是您的最佳解决方案。
实际上，这取决于您放入的元素的平均数量。
对于少于 100 个元素，向量可能是最佳解决方案，因为：
- 避免连续分配-释放
- 由于数据局部性，缓存友好
这些优点可能会优于连续排序。
显然，这还取决于您需要执行多少次插入删除操作。 您要进行每帧插入/删除吗？
更一般地说：您谈论的是性能关键型应用程序吗？
记住不要过早优化...
in theory an associative container (set, multiset, map, multimap) should be your best solution.
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?
More generally: are you talking about a performance-critical application?
remember to not prematurely optimize...
听起来你想要一个 多索引容器。 这允许您创建一个容器并告诉该容器您可能想要遍历其中的项目的各种方式。 然后，容器保留多个项目列表，并且这些列表在每次插入/删除时更新。
如果你确实想对容器重新排序，你可以调用
std： :sort函数适用于任何std::deque、std::vector，甚至是简单的 C 风格数组。 该函数采用可选的第三个参数来确定如何对内容进行排序。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 anystd::deque,std::vector, or even a simple C-style array. That function takes an optional third argument to determine how to sort the contents.stl没有提供这样的容器。 您可以定义自己的，由set/multiset或vector支持，但是每次排序函数更改时，您都必须通过调用以下方法重新排序：sort（对于向量）或通过创建新集合（对于set/multiset）。如果您只想从递增排序顺序更改为递减排序顺序，可以通过调用
rbegin()和rend()而不是rbegin()在容器上使用反向迭代器代码>begin()和end()。vector和set/multiset都是可逆容器，因此这对任何一个都适用。The
stlprovides no such container. You can define your own, backed by either aset/multisetor avector, but you are going to have to re-sort every time the sorting function changes by either callingsort(for avector) or by creating a new collection (forset/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()andrend()instead ofbegin()andend(). Bothvectorandset/multisetare reversible containers, so this would work for either.std::set基本上是一个排序的容器。std::setis basically a sorted container.如果您知道要对单个值进行升序和降序排序，那么 set 就是您的朋友。 当您想沿相反方向“排序”时，请使用反向迭代器。
如果您的对象很复杂，并且您将根据对象中的成员字段以多种不同的方式进行排序，那么使用向量和排序可能会更好。 尝试一次完成所有插入，然后调用一次排序。 如果这不可行，那么对于大型对象集合，双端队列可能是比向量更好的选择。
我认为，如果您对该级别的优化感兴趣，您最好使用实际数据来分析您的代码。 （这可能是这里任何人都能给出的最好建议：如果您千载难逢的话，在每次插入后调用 sort 可能并不重要。）
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.
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.
I think that if you're interested in that level 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.)
您需要查看 std::map
地图是根据 < 排序的。 为 keyType 提供的运算符。
或者
也按<排序> 模板参数的运算符，但不允许重复元素。
它
与 std::set 做同样的事情，但允许相同的元素。
我强烈推荐 Josuttis 的“C++ 标准库”以获取更多信息。 它是 std 库最全面的概述，非常易读，并且充满了晦涩难懂的信息。
另外，正如 26 人中的 17 人提到的，Meyers 的《Effective Stl》值得一读。
You'll want to look at std::map
The map is sorted based on the < operator provided for keyType.
Or
Also sorted on the < operator of the template argument, but does not allow duplicate elements.
There's
which does the same thing as std::set but allows identical elements.
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.
Also, as mentioned by 17 of 26, Effective Stl by Meyers is worth a read.