题
我对STL相当陌生,所以我想知道是否有动态可排序的容器?目前,我当前的想法是将向量与各种排序算法结合使用,但考虑到将条目插入排序向量的(大概)线性复杂性,我不确定是否有更合适的选择。
为了“动态”地澄清,我正在寻找一个可以在运行时修改排序顺序的容器 - 例如按升序排序,然后按降序重新排序。
解决方案
如果您知道要对单个值进行升序和降序排序,那么 set 就是您的朋友。当您想沿相反方向“排序”时,请使用反向迭代器。
如果您的对象很复杂,并且您将根据对象内的成员字段以多种不同的方式进行排序,那么使用向量和排序可能会更好。尝试一次完成所有插入,然后调用一次排序。如果这不可行,那么对于大型对象集合,双端队列可能是比向量更好的选择。
我认为如果你有兴趣 那 优化级别,您最好使用实际数据来分析您的代码。(这可能是这里任何人都能给出的最好建议:如果您千载难逢的话,在每次插入后调用 sort 可能并不重要。)
其他提示
你会想看看 std::map
std::map<keyType, valueType>
该映射根据为 keyType 提供的 < 运算符进行排序。
或者
std::set<valueType>
还对模板参数的 < 运算符进行排序,但不允许重复元素。
有
std::multiset<valueType>
它与 std::set 执行相同的操作,但允许相同的元素。
我强烈推荐 Josuttis 的“C++ 标准库”以获取更多信息。它是 std 库最全面的概述,非常易读,并且充满了晦涩难懂的信息。
另外,正如 26 人中的 17 人提到的,Meyers 的《Effective Stl》值得一读。
这 stl
没有提供这样的容器。您可以定义自己的,由以下任一支持 set/multiset
或一个 vector
, ,但是每次排序函数发生变化时,您都必须通过调用重新排序 sort
(为一个 vector
)或通过创建一个新集合(对于 set/multiset
).
如果您只想从递增排序顺序更改为递减排序顺序,可以通过调用在容器上使用反向迭代器 rbegin()
和 rend()
代替 begin()
和 end()
. 。两个都 vector
和 set/multiset
是可逆容器,所以这对任何一个都适用。
std::set
基本上是一个排序的容器。
您绝对应该使用集合/地图。就像 hazzen 所说,插入/查找的时间复杂度为 O(log n)。你不会用排序向量得到这个;使用二分查找可以得到 O(log n) 的查找结果,但插入的时间复杂度为 O(n),因为插入(或删除)一个项目可能会导致向量中的所有现有项目发生移位。
事情没那么简单。根据我的经验,插入/删除的使用频率低于查找。排序向量的优点是占用更少的内存并且对缓存更友好。如果碰巧有与 STL 映射兼容的版本(就像我之前链接的版本),那么很容易来回切换并针对每种情况使用最佳容器。
理论上,关联容器(集合、多重集合、映射、多重映射)应该是您的最佳解决方案。
实际上,这取决于您放入的元素的平均数量。对于少于 100 个元素,向量可能是最佳解决方案,因为:- 避免持续分配 - 划分 - 由于数据局部性而导致的缓存友好,但这些优势可能会超越连续排序。显然,这还取决于您需要执行多少次插入删除操作。您要进行每帧插入/删除吗?
更普遍:您是在谈论性能关键型应用程序吗?
记住不要过早优化...
答案一如既往,视情况而定。
set
和 multiset
适用于保持项目排序,但通常针对添加、删除和获取的平衡集进行优化。如果你有男性化的查找操作,那么排序 vector
可能更合适,然后使用 lower_bound
查找元素。
另外,您在运行时以不同顺序进行排序的第二个要求实际上意味着 set
和 multiset
不合适,因为谓词无法在运行时修改。
因此我会推荐一个排序向量。但请记住将相同的谓词传递给 lower_bound
您传递给前一个排序的结果将是未定义的,并且如果您传递错误的谓词,结果很可能是错误的。
集合和多重集合使用底层二叉树;您可以定义 <= 运算符供您自己使用。这些容器会自行排序,因此如果您要切换排序参数,可能不是最佳选择。如果您要大量使用向量和列表,那么向量和列表可能是最好的;一般来说,列表有它自己的排序(通常是合并排序),您可以在向量上使用 stl 二进制搜索算法。如果插入占主导地位,则列表优于向量。
STL 映射和集合都是排序容器。
我赞同 Doug T 的书籍推荐——Josuttis STL 书是我见过的最好的学习书和参考书。
有效的STL 也是一本学习STL内部细节以及你应该做什么和不应该做什么的优秀书籍。
对于“STL 兼容”排序向量,请参见 A.Alexandrescu 的 AssocVector 来自 洛基.