维护有序的对象集合
我对对象集合有以下要求：
- 动态大小（理论上无限，但实际上几千个就足够了）
- 有序，但允许在任意位置重新排序和插入。
- 允许删除
- 索引访问 - 随机访问
- 计数
我存储的对象并不大，只有几个属性和一个或两个小数组（256 个布尔值）
在编写链接列表之前，是否有我应该了解的内置类？
I have the following requirements for a collection of objects:
- Dynamic size (in theory unlimited, but in practice a couple of thousand should be more than enough)
- Ordered, but allowing reorder and insertion at arbitrary locations.
- Allows for deletion
- Indexed Access - Random Access
- Count
The objects I am storing are not large, a couple of properties and a small array or two (256 booleans)
Is there any built in classes I should know about before I go writing a linked list?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
原始答案：这听起来像标准库中的
std::list（双向链表）。新答案：
更改规范后，只要向量中间的元素不超过几千个，并且向量中间不存在大量插入和删除，
std::vector就可以工作。向量运算的低常数可能会抵消中间插入和删除的线性复杂性。如果您在开头和结尾处进行大量插入和删除操作，std::deque也可能有效。Original answer: That sounds like
std::list(a doubly linked list) from the Standard Library.New answer:
After your change to the specs, a
std::vectormight work as long as there aren't more than a few thousand elements and not a huge number of insertions and deletions in the middle of the vector. The linear complexity of insertion and deletion in the middle may be outweighed by the low constants on the vector operations. If you are doing a lot of insertions and deletions just at the beginning and end,std::dequemight work as well.-插入和删除：这对于任何STL容器都是可能的，但问题是需要多长时间才能完成。任何链表容器（列表、映射、集合）都将在恒定时间内完成此操作，而类数组容器（向量）将在线性时间内完成此操作（使用恒定摊销分配）。
-排序：考虑到您可以随时保留排序的集合，这不是什么大问题，任何 STL 容器都允许这样做。对于地图和集合，您无需执行任何操作，它们已经负责始终保持集合排序。对于向量或列表，您必须完成这项工作，即您必须对新元素所在的位置进行二分搜索并将它们插入那里（但 STL 算法拥有您所需的所有部分）。
- 重新排序：如果您需要获取已根据规则 A 排序的当前集合，并根据规则 B 重新排序该集合，这可能会出现问题。像 map 和 set 这样的容器通过排序规则进行参数化（作为类型），这意味着要使用它，您必须从原始集合中提取每个元素，并将它们插入具有新排序规则的新集合中。但是，如果您使用向量容器，则可以随时使用 STL 排序功能来采用您喜欢的任何规则。
-随机访问：您说您需要随机访问。就我个人而言，我对随机访问的定义意味着可以在恒定时间内访问集合中的任何元素（通过索引）。有了这个定义（我认为这是相当标准的），任何链表实现都不合格，它让您只剩下使用类似数组的容器（例如 std::vector）的唯一选择。
结论，要拥有所有这些属性，最好使用 std::vector 并实现您自己的排序插入和排序删除（对向量执行二分搜索以查找要删除的元素或插入新元素的位置）。如果您需要存储的对象很大，并且它们排序所依据的数据（名称、ID 等）很小，您可能会考虑通过保存未排序的对象链表（带有完整信息）并保留键的排序向量以及指向链表中相应节点的指针（当然，在这种情况下，前者使用 std::list，后者使用 std::vector）。
顺便说一句，我不是 STL 容器方面的专家，所以我上面的内容可能是错误的，你自己想想吧。亲自探索 STL，我相信您会找到您需要的东西，或者至少找到您需要的所有部分。也许，也看看 Boost 库。
-Insertion and Deletion: This is possible for any STL container, but the question is how long it takes to do it. Any linked-list container (list, map, set) will do this in constant time, while array-like containers (vector) will do it in linear time (with constant-amortized allocation).
-Sorting: Considering that you can keep a sorted collection at all times, this isn't much of an issue, any STL container will allow that. For map and set, you don't have to do anything, they already take care of keeping the collection sorted at all times. For vector or list, you have to do that work, i.e. you have to do binary search for the place where the new elements go and insert them there (but STL Algorithms has all the pieces you need for that).
-Resorting: If you need to take the current collection you have sorted with respect to rule A, and resort the collection with respect to rule B, this might be a problem. Containers like map and set are parametrized (as a type) by the sorting rule, this means that to resort it, you would have to extract every element from the original collection and insert them in a new collection with a new sorting rule. However, if you use a vector container, you can just use the STL sort function anytime to resort with whatever rule you like.
-Random Access: You said you needed random access. Personally, my definition of random access means that any element in the collection can be accessed (by index) in constant time. With that definition (which I think is quite standard), any linked-list implementation does not qualify and it leaves you with the only option of using an array-like container (e.g. std::vector).
Conclusion, to have all those properties, it would probably be best to use a std::vector and implement your own sorted insertion and sorted deletion (performing binary search into the vector to find the element to delete or the place to insert the new element). If your objects that you need to store are of significant size, and the data according to which they are sorted (name, ID, etc.) is small, you might consider splitting the problem by holding a unsorted linked-list of objects (with full information) and keeping a sorted vector of keys along with a pointer to the corresponding node in the linked-list (in that case, of course, use std::list for the former, and std::vector for the latter).
BTW, I'm no grand expert with STL containers, so I might have been wrong in the above, just think for yourself. Explore the STL for yourself, I'm sure you will find what you need, or at least all the pieces that you need. Maybe, look at Boost libraries too.
您没有指定足够的要求来选择最佳容器。
STL 容器被设计为根据需要增长。
允许重新排序吗？ std::map 无法重新排序：您可以从一个 std::map 中删除并使用不同的顺序插入到另一个 std::map 中，但作为不同的模板实例化，两个变量将具有不同的类型。 std::list 有一个
sort()成员函数 [感谢 Blastfurnace 指出这一点]，对于大型对象特别有效。使用非成员 std::sort() 函数可以轻松地对 std::vector 进行排序，对于微小对象尤其有效。可以在地图或列表中在任意位置进行高效插入，但如何找到这些位置？在列表中，搜索是线性的（您必须从您已经知道的地方开始，并逐个元素向前或向后扫描）。 std::map 提供了高效的搜索，就像已经排序的向量一样，但插入向量涉及移动（复制）所有后续元素以腾出空间：在事物方案中，这是一个代价高昂的操作。
所有容器都允许删除，但是您会遇到与插入完全相同的效率问题（即，如果您已经知道位置，则列表快速，地图快速，向量中的删除速度很慢，尽管您可以“标记” " 元素被删除但没有删除它们，例如使字符串为空，在结构中具有布尔标志）。
向量以数字方式索引（但可以进行二分搜索），通过任意键映射（但没有数字索引）。列表没有索引，必须从已知元素线性搜索。
std::list提供了一个 O(n)size()函数（这样它就可以提供 O(1) 的拼接），但是您可以轻松地自己跟踪大小（假设你不会拼接）。其他 STL 容器的size()时间已经是 O(1)。结论
考虑使用 std::list 是否会导致对所需元素进行大量低效的线性搜索。如果没有，那么列表确实可以为您提供高效的插入和删除。度假还是不错的
映射或哈希映射将允许快速查找和轻松插入/删除，无法重新排序，但您可以轻松地将数据移出到具有另一种排序标准的另一个映射（具有中等效率）。
向量允许快速搜索和就地排序，但最差的插入/删除是使用元素索引的随机访问查找最快的。
You haven't specified enough of your requirements to select the best container.
STL containers are designed to grow as needed.
Allowing reorder? A std::map can't be reordered: you can delete from one std::map and insert into another using a different ordering, but as different template instantiations the two variables will have different types. std::list has a
sort()member function [thanks Blastfurnace for pointing this out], particularly efficient for large objects. A std::vector can be resorted easily using the non-memberstd::sort()function, particularly efficient for tiny objects.Efficient insertion at arbitrary locations can be done in a map or list, but how will you find those locations? In a list, searching is linear (you must start from somewhere you already know about and scan forwards or backwards element by element). std::map provides efficient searching, as does an already-sorted vector, but inserting into a vector involves shifting (copying) all the subsequent elements to make space: that's a costly operation in the scheme of things.
All containers allow for deletion, but you have the exact-same efficiency issues as you do for insertion (i.e. fast for list if you already know the location, fast for map, deletion in vectors is slow, though you can "mark" elements deleted without removing them, e.g. making a string empty, having a boolean flag in a struct).
vector is indexed numerically (but can be binary searched), map by an arbitrary key (but no numerical index). list is not indexed and must be searched linearly from a known element.
std::listprovides an O(n)size()function (so that it can provide O(1) splice), but you can easily track the size yourself (assuming you won't splice). Other STL containers already have O(1) time forsize().Conclusions
Consider whether using a std::list will result in lots of inefficient linear searches for the element you need. If not, then a list does give you efficient insertion and deletion. Resorting is good.
A map or hash map will allow quick lookup and easy insertion/deletion, can't be resorted, but you can easily move the data out to another map with another sort criteria (with moderate efficiency.
A vector allows fast searching and in-place resorting, but the worst insert/deletion. It's the fastest for random-access lookup using the element index.