slist 相对于 vector 的优势？
我需要的只是一个动态增长的数组。 我不需要随机访问，总是插入到最后并从头到尾读取。
slist 似乎是第一选择，因为它提供了足够的我需要的东西。 但是，我无法说出使用 slist 而不是向量可以获得什么好处。 此外，我读到的一些关于 STL 的材料说，“向量通常是访问元素以及从序列末尾添加或删除元素的最有效的时间”。 因此，我的问题是：对于我的需求，slist真的是比vector更好的选择吗？ 提前致谢。
What I need is just a dynamically growing array. I don't need random access, and I always insert to the end and read it from the beginning to the end.
slist seems to be the first choice, because it provides just enough of what I need. However, I can't tell what benefit I get by using slist instead of vector. Besides, several materials I read about STL say, "vectors are generally the most efficient in time for accessing elements and to add or remove elements from the end of the sequence". Therefore, my question is: for my needs, is slist really a better choice than vector? Thanks in advance.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
对于初学者来说，
slist是非标准的。对于您的选择，链表会比向量慢，相信它。 造成这种情况的原因有两个：
然而，std::deque 在性能上几乎总是优于
std::deque可能会更快。 深入的性能分析表明，尽管存在相反的偏见，std::vector（如果不需要随机访问）。For starters,
slistis non-standard.For your choice, a linked list will be slower than a vector, count on it. There are two reasons contributing to this:
However, a
std::dequewill probably be even faster. In-depth performance analysis has shown that, despite bias to the contrary,std::dequeis almost always superior tostd::vectorin performance (if no random access is needed), due to its improved (chunked) memory allocation strategy.是的，如果您总是从头到尾阅读，slist（链接列表）听起来像是要走的路。 可能的例外是，如果您要同时在末尾插入大量元素。 那么，如果适当地使用保留，向量可能会更好。
当然，进行分析以确保它更适合您的应用程序。
Yes, if you are always reading beginning to end, slist (a linked list) sounds like the way to go. The possible exception is if you will be inserting a large quantity of elements at the end at the same time. Then, the vector could be better if you use reserve appropriately.
Of course, profile to be sure it's better for your application.
Matt Austern（《泛型编程和 STL》的作者和通用 C++ 大师）是单链表的强烈拥护者，将其纳入即将推出的 C++ 标准； 请参阅他的演讲 http://www.accu-usa.org/Slides/SinglyLinkedLists。 ppt 和他的长文 http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2543.htm 了解更多详细信息，包括对所涉及的权衡的讨论，可能会指导您选择这个数据结构。 （请注意，当前建议的名称是
forward_list，尽管slist是 SGI 的 STL 和其他流行库中传统的命名方式）。Matt Austern (author of "Generic Programming and the STL" and general C++ guru) is a strong advocate of singly-linked lists for inclusion in the forthcoming C++ standard; see his presentation at http://www.accu-usa.org/Slides/SinglyLinkedLists.ppt and his long article at http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2543.htm for more details, including a discussion of the trade-offs involved that may guide you in possibly choosing this data structure. (Note that the currently proposed name is
forward_list, thoughslistis how it was traditionally named in SGI's STL & other popular libraries).我会同意（或者可能是第三...）std::vector 或 std::deque 可以完成这项工作的观点。 我唯一要添加的是一些额外的因素，这些因素应该指导在
std::vector和std::list之间做出决定。 这些与T的特性以及你打算使用什么算法有很大关系。首先是内存开销。
Std::list是基于节点的容器，因此如果T是原始类型或相对较小的用户定义类型，则基于节点的链接的内存开销可能会增加不可忽略 - 考虑到std::list可能为每个元素使用至少3 * sizeof(int)存储空间，而std: :vector将仅使用sizeof(int)存储，标头开销较小。Std::deque与std::vector类似，但开销较小，与N呈线性关系。下一个问题是复制构建的成本。 如果
T(T const&)非常昂贵，那么请避开std::vector因为它会导致出现一堆副本，其大小为向量增长。 这就是std::deque明显获胜的地方，而std::list也是竞争者。通常指导容器类型决策的最后一个问题是您的算法是否可以处理
std::vector和std::deque的迭代器失效约束。 如果您将大量操作容器元素（例如，排序、插入中间或洗牌），那么您可能需要倾向于std::list因为操作顺序只需要重置一些链接指针。I'll second (or maybe third...) the opinion that
std::vectororstd::dequewill do the job. The only thing that I will add is a few additional factors that should guide the decision betweenstd::vector<T>andstd::list<T>. These have a lot to do with the characteristics ofTand what algorithms you plan on using.The first is memory overhead.
Std::listis a node-based container so ifTis a primitive type or relatively small user-defined type, then the memory overhead of the node-based linkage might be non-negligible - consider thatstd::list<int>is likely to use at least3 * sizeof(int)storage for each element whereasstd::vectorwill only usesizeof(int)storage with a small header overhead.Std::dequeis similar tostd::vectorbut has a small overhead that is linear toN.The next issue is the cost of copy construction. If
T(T const&)is at all expensive, then steer clear ofstd::vector<T>since it cause a bunch of copies to occur as the size of the vector grows. This is wherestd::deque<T>is a clear winner andstd::list<T>is also a contender.The final issue that usually guides the decision on container type is whether your algorithms can work with the iterator invalidation constraints of
std::vectorandstd::deque. If you will be manipulating the container elements a lot (e.g., sorting, inserting in the middle, or shuffling), then you might want to lean towardsstd::listsince manipulating the order requires little more than resetting a few linkage pointers.我猜你的意思是“slist”的 std::list 。 当您需要快速、随机访问一系列元素、保证连续内存和快速顺序读取（IOW，从头到尾）时，向量非常有用。 当您需要在序列的开头或结尾快速（恒定时间）插入或删除项目，但不关心随机访问或顺序读取的性能时，列表是很好的选择。
差异的原因在于两者的实现方式。 向量在内部实现为项目数组，在添加项目时达到其大小/容量时需要重新分配。 列表被实现为双向链表，这可能会导致顺序读取的缓存未命中。 列表的随机访问还需要从列表中的第一个（或最后一个）项目开始扫描，直到找到您请求的项目。
I'm guessing you mean std::list by "slist". Vectors are good when you need fast, random-access to a sequence of elements, with guaranteed contiguous memory, and fast sequential reading (IOW, from the beginning to the end). Lists are good when you need fast (constant-time) insertion or deletion of items at the beginning or end of the sequence, but don't care about the performance of random-access or sequential reading.
The reason for the difference is the way the 2 are implemented. Vectors are implemented internally as an array of items, which needs to be reallocated when its size/capacity is reached on adding an item. Lists are implemented as a doubly-linked list, which can cause cache-misses for sequential reading. Random-access for lists also requires scanning from the first (or last) item in the list, until it locates the item you're requesting.
对我来说，std::deque 听起来不错。 它具有向量的内存优势，例如为每个“slab”分配连续内存（有利于 CPU 缓存），每个元素没有像 std::list 那样的开销，并且不需要将整个集合重新分配为 std::vector做。 详细了解std::deque
Sounds like a good job for std::deque to me. It has the memory benefits of a vector like contiguous memory allocation for each "slab" (good for CPU caches), no overhead for each element like with std::list and it does not need to reallocate the whole set as std::vector does. Read more about std::deque here