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

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

解决方案

回答

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

回答

我们将要看看std :: map

std::map<keyType, valueType>

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

或者

std::set<valueType>

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

有

std::multiset<valueType>

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

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

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

回答

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

我第二次推荐道格·T(Doug T)的书，Josuttis STL书是我所见过的最好的学习和参考书。

关于学习STL的内部细节以及我们应该做和不应该做的事情，有效的STL也是一本很好的书。

回答

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

回答

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

回答

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

回答

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

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

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

记住不要过早优化...

回答

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

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

回答

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

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

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

回答

答案一如既往地取决于。

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

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

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

回答

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

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