维护一个有序对象集合

Question

我对一组对象有以下要求：

• 动态大小（理论上无限制，但实际上几千个应该足够了）
• 有序，但允许在任意位置重新排序和插入。
• 允许删除
• 索引访问 - 随机访问
• 计数

我存储的对象并不大，只有几个属性和一个小数组或两个（256布尔值）。

在我编写链表之前，是否有任何内置类应该知道？

- Aran Mulholland

---

您要存储的对象类型有多大？复制它是否很昂贵？容器中元素插入或删除的频率如何？您需要随机访问单个元素吗？您是否查看过STL容器？ - James McNellis

Answer 1

原始回答: 那听起来像是标准库中的std::list（双向链表）。

新回答: 在规格更改后，只要元素不超过几千个且向量中没有大量插入和删除，std::vector 可能会起作用。在向量操作的低常数被权衡的情况下，中间插入和删除的线性复杂度可能会被权衡。如果您只在开头和结尾进行了大量插入和删除，则std::deque也可能适用。

- Jeremiah Willcock

---

我看到他对你做了修改。他添加了随机访问，使得列表不再是可接受的选项。 - wheaties

@wheaties：感谢提醒 - 我刚刚更新了我的答案。尽管问题仍然提到编写链表，但链表不适用于快速随机访问。当然，这完全取决于随机访问与更新的比率。 - Jeremiah Willcock

很抱歉规格有所更改 - 一条评论让我意识到我需要更多的东西。感谢您更新的答案，非常感激。 - Aran Mulholland

Answer 2

您没有指定足够的要求来选择最佳容器。

动态大小（理论上无限，但实际上几千应该足够）

STL容器被设计为根据需要增长。

有序，但允许重新排序和在任意位置插入。

允许重新排序？std::map 不能被重新排序：您可以从一个 std::map 中删除并插入到另一个使用不同排序的 std::map 中，但作为不同的模板实例化，这两个变量将具有不同的类型。std::list 有一个 sort() 成员函数[感谢 Blastfurnace 指出这一点]，特别适用于大对象。一个 std::vector 可以使用非成员 std::sort() 函数轻松重新排序，特别适用于微小对象。

在任意位置进行高效插入可以在 map 或 list 中完成，但是如何找到这些位置呢？在列表中，搜索是线性的（您必须从某个已知的地方开始，并向前或向后逐个元素扫描）。std::map 提供了高效的搜索，已经排序的 vector 也是如此，但是插入到 vector 中涉及移动（复制）所有后续元素以腾出空间：在事物的计划中，这是一个昂贵的操作。

允许删除。

所有容器都允许删除，但插入时存在完全相同的效率问题（即对于列表，如果您已经知道位置，则速度很快；对于映射，速度很快；向量中的删除速度较慢，但可以“标记”已删除的元素而不移除它们，例如使字符串为空，在结构体中具有布尔标志）。

按索引访问 - 随机访问

向量是按数字索引的（但可以进行二进制搜索），映射按任意键索引（但没有数字索引）。列表未被索引，必须从已知元素线性搜索。

计数

std::list提供了O（n）的size()函数（以便可以提供O（1）的splice），但是您可以轻松地跟踪大小（假设您不会拼接）。其他STL容器的size()函数已经具有O（1）时间。

结论

请考虑使用std::list是否会导致需要大量低效的线性搜索所需的元素。如果没有，那么列表确实可以为您提供高效的插入和删除。重新排序很好。

使用映射或哈希映射可以快速查找和轻松插入/删除，但无法重新排序。但是，您可以使用另一种排序标准将数据轻松移动到另一个映射中（效率适中）。

向量允许快速搜索和原地重新排序，但最坏的插入/删除性能。对于使用元素索引进行随机访问查找，它是最快的。

- Tony Delroy

---

为什么你会说向量比列表更容易重新排序呢？ - etarion

要使用std::sort，您需要一个随机访问迭代器，因此最好使用vector<>而不是list<>。 - Keith

你可以使用map<>，但正如Tony所指出的，不能直接进行重新排序。不过，你可以为新的排序创建一个新的map类型，并从原来的map构造它。考虑到更高效的删除操作，这可能比vector更优越。 - Keith

std::list可以被重新排序。它有一个sort()成员函数。 - Blastfurnace

@Keith，@Tony：看看Blastfurnace——列表的结构使其更适合重新排序序列，因为您只需更改“链接”，而不必移动对象本身。 - etarion

Answer 3

-插入和删除：任何STL容器都可以实现这一点，但问题在于执行此操作需要多长时间。任何链表容器（list、map、set）都可以在常数时间内完成，而类似数组的容器（vector）则需要线性时间（具有恒定分摊分配）。

-排序：考虑到您可以随时保持已排序的集合，这不是什么问题，任何STL容器都允许这样做。对于map和set，您不必做任何事情，它们已经在任何时候都会保持集合排序。对于vector或list，您必须进行这项工作，即必须对新元素的位置进行二进制搜索，并将其插入到那里（但STL算法具有您所需的所有部件）。

-重新排序：如果您需要按照规则A对当前已排序的集合进行重新排序，并按照规则B对集合进行重新排序，则可能会出现问题。像map和set这样的容器是由排序规则参数化的（作为类型），这意味着要重新排序，您必须从原始集合中提取每个元素，并将它们插入到具有新排序规则的新集合中。但是，如果您使用vector容器，则可以随时使用STL sort函数以任何您喜欢的规则进行重新排序。

-随机访问：你说你需要随机访问。就我个人而言，我的随机访问定义是指集合中的任何元素都可以在常数时间内（通过索引）访问。根据这个定义（我认为这是相当标准的），任何链表实现都不符合要求，只能使用类似数组的容器（例如std::vector）。

结论是，为了具有所有这些属性，最好使用std::vector并实现自己的排序插入和排序删除（在向量中执行二进制搜索以查找要删除的元素或要插入新元素的位置）。如果您需要存储的对象具有重要大小，并且根据其排序的数据（名称、ID等）很小，则可以考虑通过保持对象的未排序链表（具有完整信息）并保持排序的键向量以及指向链表中相应节点的指针来分割问题（在这种情况下，当然，对于前者使用std::list，对于后者使用std::vector）。

顺便说一句，我不是STL容器的大专家，所以上面可能有错误，请自行思考。探索STL，我相信你会找到你需要的，或者至少找到你需要的所有部分。也许，看看Boost库。

- Mikael Persson

---

“map”和“set”不能使用链表实现，它们（几乎总是）作为自平衡二叉搜索树实现，例如红黑树。因此，这些容器的插入和删除复杂度是对数级别的，而不是常数级别的。 - James McNellis

谢谢指出！我一直有点好奇 map 和 set 到底是如何实现的，但从未真正调查过。 - Mikael Persson

典型的实现方式是红黑树，但标准并未强制规定。@James McNellis：实际上，人们可以将SkipList视为传统链表的扩展，并且它适用于map和set实现，尽管我从未在实践中见过这种情况。 - Matthieu M.