11

我对 STL 相当陌生，所以我想知道是否有任何可动态排序的容器？目前，我目前的想法是将向量与各种排序算法结合使用，但我不确定是否有更合适的选择，因为将条目插入排序向量的（大概）线性复杂性。

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

4

12 回答 12

17

你会想看看 std::map

std::map<keyType, valueType>

地图根据为 keyType 提供的 < 运算符进行排序。

或者

std::set<valueType>

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

有

std::multiset<valueType>

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

我强烈推荐 Josuttis 的“C++ 标准库”以获取更多信息。它是对 std 库最全面的概述，非常易读，并且充满了晦涩和不那么晦涩的信息。

此外，正如 17 of 26 所述，Meyers 的 Effective Stl 值得一读。

于 2008-09-15T22:01:17.153 回答
10

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

如果您的对象很复杂，并且您将根据对象中的成员字段以多种不同的方式进行排序，那么使用向量和排序可能会更好。尝试一次完成所有插入，然后调用一次排序。如果这不可行，那么对于大型对象集合，deque 可能是比向量更好的选择。

我认为，如果您对这种级别的优化感兴趣，您最好使用实际数据来分析您的代码。（这可能是这里任何人都可以给出的最好建议：如果您只在蓝月亮中执行一次，那么在每次插入之后调用 sort 可能并不重要。）

于 2008-09-15T22:42:39.863 回答
4

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

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

于 2008-09-16T00:15:03.840 回答
3

stl没有提供这样的容器。您可以定义自己的，由 aset/multiset或 a支持，但是每次排序函数通过调用（for a ）或创建新集合（for ）vector更改时，您都必须重新排序。sortvectorset/multiset

如果您只想从递增排序顺序更改为递减排序顺序，您可以通过调用rbegin()andrend()而不是begin()and来在容器上使用反向迭代器end()。两者vector和set/multiset都是可逆容器，因此这对任何一个都适用。

于 2008-09-15T22:39:38.403 回答
2

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

于 2008-09-15T21:59:40.280 回答
1

您绝对应该使用集合/地图。就像 hazzen 所说，你得到 O(log n) 插入/查找。你不会用排序的向量得到这个；您可以使用二进制搜索获得 O(log n) 查找，但插入是 O(n)，因为插入（或删除）一个项目可能会导致向量中的所有现有项目都被移动。

于 2008-09-15T22:11:00.470 回答
1

没那么简单。根据我的经验，插入/删除的使用频率低于查找。排序向量的优点是它占用更少的内存并且对缓存更友好。如果碰巧有与 STL 地图兼容的版本（就像我之前链接的那个），那么很容易来回切换并为每种情况使用最佳容器。

于 2008-09-15T22:21:29.370 回答
1

理论上，关联容器（set、multiset、map、multimap）应该是您的最佳解决方案。

在实践中，它取决于您放入的元素的平均数量。对于少于 100 个元素，向量可能是最好的解决方案，因为： - 避免连续分配 - 释放 - 由于数据局部性而缓存友好 这些优势可能仍然会胜过连续排序。显然，它还取决于您必须执行多少次插入删除。您要进行每帧插入/删除吗？

更一般地说：您是在谈论性能关键型应用程序吗？

切记不要过早优化...

于 2008-09-15T22:28:11.647 回答
1

答案总是视情况而定。

set并且multiset适用于保持项目排序，但通常针对一组平衡的添加、删除和获取进行优化。如果您有男子气概的查找操作，那么 sortedvector可能更合适，然后用于lower_bound查找元素。

此外，您在运行时以不同顺序使用的第二个要求实际上意味着set并且multiset不合适，因为谓词不能在运行时修改。

因此，我会推荐一个排序的向量。但是请记住将相同的谓词lower_bound传递给您传递给前一个排序的谓词，因为如果您传递了错误的谓词，结果将是未定义的并且很可能是错误的。

于 2008-09-15T23:39:27.123 回答
1

Set 和 multiset 使用底层的二叉树；您可以定义 <= 运算符供您自己使用。这些容器保持自己排序，因此如果您要切换排序参数，可能不是最佳选择。如果您要使用很多方法，则向量和列表可能是最好的；一般来说，列表有它自己的排序（通常是合并排序），你可以在向量上使用 stl 二进制搜索算法。如果插入占主导地位，则列表优于向量。

于 2011-10-04T19:35:04.513 回答
0

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

我支持 Doug T 的书籍推荐 - Josuttis STL 书籍是我所见过的最好的学习和参考书。

《 Effective STL》也是一本学习STL内部细节以及你应该做什么和不应该做什么的好书。

于 2008-09-15T22:01:42.067 回答
0

对于“STL 兼容”排序向量，请参见Loki中的 A. Alexandrescu 的 AssocVector 。

于 2008-09-15T22:05:26.553 回答