动态排序的 STL 容器

StackOverflow https://stackoverflow.com/questions/67426

  •  09-06-2019
  •  | 
  •  

题

我对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》值得一读。

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

如果你确实想重新排序容器，你可以调用 std::sort 作用于任何 std::deque, std::vector, ，甚至是一个简单的 C 风格数组。该函数采用可选的第三个参数来确定如何对内容进行排序。

这 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 来自 洛基.

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top