维护对象的有序集合

Question

我为对象的集合以下要求：

• 动态大小（理论上是无限的，但在实际操作两三千应该绰绰有余）
• 有序，但允许在任意位置重新排序和插入。
• 允许为删除
• 索引访问 - 随机存取
• 计数

我存储的对象是不是很大，几个属性和一个小阵列或两个（256布尔值）

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

Answer 1

原始回答：这听起来像来自标准库的std::list（一个双向链表）。

新的回答： 在您更改规格后，只要数量不超过几千个元素，并且在向量的中间没有大量的插入和删除操作，std::vector就可能工作。中间插入和删除的线性复杂度可能会超过矢量操作的低常数。如果您在开始和结束时进行了大量插入和删除操作，则std::deque也可能会有效。

Answer 2

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

动态大小（理论上是无限的，但在实际操作两三千应该是绰绰有余）

STL容器被设计成需要成长。

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

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

可以在地图或列表中完成在任意位置的高效插入，但如何找到这些位置？在列表中，搜索是线性的（您必须从您已知的某个地方开始并逐个向前或向后扫描）。 std :: map提供了高效的搜索，就像一个已经排序好的向量一样，但是插入到向量中需要移动（复制）所有后续元素来创建空间：这是一个代价高昂的操作。

允许删除

所有容器允许删除，但你必须将完全相同的效率问题，你插入的名单做（即快，如果你已经知道的位置，快速在地图，向量中的删除速度很慢，尽管您可以“标记”已删除的元素而不删除它们，例如，使字符串为空，在结构中包含布尔标志）。

索引访问 - 随机存取

矢量是通过任意的键（但没有数值指标）索引的数值（但是可以是二进制搜索），地图。列表未被编入索引，必须从已知元素中线性搜索。

计数

std::list提供了一个O（n）的size()功能（以便它可以提供O（1）拼接），但你可以轻松地跟踪自己的大小（假设你不会拼接）。其他STL容器已经有O（1）个时间为size()。

结论

考虑是否使用一个std ::将导致大量的您需要的元素低效线性搜索列表。如果没有，那么列表确实会给你有效的插入和删除。度假很好。

地图或哈希地图将允许快速查找和轻松插入/缺失，无法使出，但是你可以很容易地将数据移动到另一个地图与其他分类标准（中度效率。

一向量允许快速搜索和就地求助，但是最差的插入/删除。它是使用元素索引进行随机访问查找最快的。

Answer 3

- 插入和删除：这对任何STL容器都是可能的，但问题（list，map，set）会在一段时间内完成这个工作，而类似数组的容器（vector）会在线性时间内完成这个工作（使用常量分摊的分配）。

解决方案：考虑到您可以随时保留一个已排序的集合，这不是什么大问题，任何STL容器都会允许。对于地图和设置，您不必做任何事情，他们已经注意保持集合在任何时候都是分类的。对于向量或列表，您必须完成这项工作，即您必须对新元素所在的位置进行二分搜索并将其插入（但STL算法包含您需要的所有部分）。

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

随机访问：你说你需要随机访问。就我个人而言，我对随机访问的定义意味着集合中的任何元素都可以在不变的时间内被访问（通过索引）。有了这个定义（我认为这是非常标准的），任何链接列表实现都不具备资格，并且只能使用类似数组的容器（例如std :: vector）。

结论：要拥有所有这些属性，最好使用std :: vector并实现自己的排序插入和排序删除（在向量中执行二进制搜索以查找要删除的元素或放置的位置插入新元素）。如果您需要存储的对象的大小很大，并且排序的数据（名称，ID等）很小，则可以考虑通过保留未排序的对象链接列表来分割问题（​​使用完整的信息），并保存一个排序的键向量以及指向链表中的相应节点的指针（在这种情况下，当然，前者使用std :: list，后者使用std :: vector）。顺便说一句，我不是STL容器的专家，所以我可能在上面写错了，只为自己想。自己探索STL，我相信你会找到你需要的东西，或者至少是你需要的所有东西。也许，也看看Boost库。