关于c ++：动态排序的STL容器

Dynamically sorted STL containers

我是STL的新手，所以我想知道是否有任何可动态排序的容器？目前，我目前的想法是将向量与各种排序算法结合使用，但是鉴于将条目插入已排序向量的线性复杂性，我不确定是否存在更合适的选择。

为了"动态"地说明问题，我正在寻找一个可以在运行时修改排序顺序的容器-例如按升序排序，然后再按降序重新排序。

您将要看看std :: map

1	std::map<keyType, valueType>

映射基于为keyType提供的<运算符进行排序。

要么

1	std::set<valueType>

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

有

1	std::multiset<valueType>

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

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

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

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

如果您的对象很复杂，并且要根据对象内的成员字段以多种不同的方式进行排序，那么使用向量和排序可能会更好。尝试一次全部插入，然后调用sort一次。如果那不可行，那么对于大对象集合，双端队列可能比矢量更好。

我认为，如果您对这种优化水平感兴趣，则最好使用实际数据对代码进行性能分析。 (这可能是这里任何人都可以提供的最佳建议：如果您只在蓝色月亮中执行一次，则在每次插入后都调用sort可能没关系。)

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

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

stl不提供这样的容器。您可以定义自己的，以set/multiset或vector为后盾，但是每次排序功能发生变化时，都必须通过调用sort(对于vector)或创建一个新集合(用于set/multiset)。

如果只想从增加的排序顺序更改为减少的排序顺序，则可以通过调用rbegin()和rend()而不是begin()和end()在容器上使用反向迭代器。 vector和set/multiset都是可逆容器，因此无论哪种都可以。

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

集和多集使用底层的二叉树；您可以定义<=运算符供您自己使用。这些容器保持其自身的排序状态，因此，如果要切换排序参数，可能不是最佳选择。如果要使用很多方法，向量和列表可能是最好的。一般而言，list都有自己的排序(通常是mergesort)，您可以在向量上使用stl二进制搜索算法。如果插入将占据主导地位，则列出的表现将超过向量。

答案一如既往地取决于。

set和multiset适合使项目保持排序，但通常针对均衡的添加，删除和提取进行了优化。如果您有大量查找操作，则排序的vector可能更合适，然后使用lower_bound查找元素。

同样，在运行时以不同顺序重新排序的第二个要求实际上将意味着set和multiset不适用，因为无法在运行时修改谓词。

因此，我建议使用排序向量。但是请记住将相同的谓词传递给您传递给上一个排序的lower_bound，因为结果将是不确定的，并且如果传递错误的谓词很可能是错误的。

从理论上讲，关联容器(集合，多集，地图，多地图)应该是您的最佳解决方案。

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

更笼统地说：您在谈论性能至关重要的应用程序吗？

记住不要过早优化...

不是那么简单。以我的经验，插入/删除的使用少于查找。排序向量的优点是占用更少的内存，并且对缓存更友好。如果碰巧具有与STL映射兼容的版本(例如我之前链接的版本)，则可以轻松地来回切换并针对每种情况使用最佳容器。

您绝对应该使用集合/地图。就像hazzen所说的，您将获得O(log n)插入/查找。您将不会获得带有排序向量的矢量。您可以使用二分查找来获得O(log n)查找，但是插入为O(n)，因为插入(或删除)一个项目可能会导致向量中所有现有的项目发生移位。

有关"与STL兼容"的排序向量，请参阅Loki的A. Alexandrescu的AssocVector。

STL映射和集合都是已排序的容器。