Dynamically sorted STL containers我是STL的新手，所以我想知道是否有任何可动态排序的容器？ 目前，我目前的想法是将向量与各种排序算法结合使用，但是鉴于将条目插入已排序向量的线性复杂性，我不确定是否存在更合适的选择。 为了"动态"地说明问题，我正在寻找一个可以在运行时修改排序顺序的容器-例如 按升序排序，然后再按降序重新排序。 您将要看看std :: map
映射基于为keyType提供的<运算符进行排序。 要么
也按模板参数的<运算符排序，但不允许重复的元素。 有
它和std :: set做同样的事情，但是允许相同的元素。 我强烈推荐Josuttis的" C ++标准库"以获取更多信息。它是std库的最全面概述，非常易读，并且充斥着晦涩难懂的信息。 另外，如26中的17所述，Meyers的Effective Stl值得一读。 如果您知道要对单个值进行升序和降序排序，那么set是您的朋友。当您想以相反的方向"排序"时，请使用反向迭代器。 如果您的对象很复杂，并且要根据对象内的成员字段以多种不同的方式进行排序，那么使用向量和排序可能会更好。尝试一次全部插入，然后调用sort一次。如果那不可行，那么对于大对象集合，双端队列可能比矢量更好。 我认为，如果您对这种优化水平感兴趣，则最好使用实际数据对代码进行性能分析。 (这可能是这里任何人都可以提供的最佳建议：如果您只在蓝色月亮中执行一次，则在每次插入后都调用sort可能没关系。) 听起来您想要一个多索引容器。这使您可以创建一个容器，并告诉该容器您可能要遍历其中的项目的各种方式。然后，容器保留该项目的多个列表，并且这些列表在每次插入/删除时都会更新。
如果您确实想对容器进行重新排序，则可以在任何
如果只想从增加的排序顺序更改为减少的排序顺序，则可以通过调用
集和多集使用底层的二叉树；您可以定义<=运算符供您自己使用。这些容器保持其自身的排序状态，因此，如果要切换排序参数，可能不是最佳选择。如果要使用很多方法，向量和列表可能是最好的。一般而言，list都有自己的排序(通常是mergesort)，您可以在向量上使用stl二进制搜索算法。如果插入将占据主导地位，则列出的表现将超过向量。 答案一如既往地取决于。
同样，在运行时以不同顺序重新排序的第二个要求实际上将意味着
因此，我建议使用排序向量。但是请记住将相同的谓词传递给您传递给上一个排序的 从理论上讲，关联容器(集合，多集，地图，多地图)应该是您的最佳解决方案。
实际上，它取决于您要放入的元素的平均数量。 更笼统地说：您在谈论性能至关重要的应用程序吗？ 记住不要过早优化... 不是那么简单。以我的经验，插入/删除的使用少于查找。排序向量的优点是占用更少的内存，并且对缓存更友好。如果碰巧具有与STL映射兼容的版本(例如我之前链接的版本)，则可以轻松地来回切换并针对每种情况使用最佳容器。 您绝对应该使用集合/地图。就像hazzen所说的，您将获得O(log n)插入/查找。您将不会获得带有排序向量的矢量。您可以使用二分查找来获得O(log n)查找，但是插入为O(n)，因为插入(或删除)一个项目可能会导致向量中所有现有的项目发生移位。 有关"与STL兼容"的排序向量，请参阅Loki的A. Alexandrescu的AssocVector。 STL映射和集合都是已排序的容器。 我第二次推荐道格·T(Doug T)的书籍-Josuttis STL书籍是我见过的最好的学习书籍和参考书。 关于学习STL的内部细节以及您应该做和不应该做的事情，有效的STL也是一本很好的书。 |
