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也是一本很好的书。 |