我注意到在有效的STL
向量是这样一种序列 默认情况下应该使用。
这是什么意思?似乎忽略效率向量可以做任何事情。
谁能给我一个场景，其中向量不是一个可行的选择，但必须使用列表?
当前回答
想要重复将大量项插入序列末尾以外的任何位置的情况。
看看每种不同类型的容器的复杂度保证:
标准容器的复杂性保证是什么?
其他回答
List是双链表，所以很容易插入和删除一个元素。我们只需要改变这几个指针，而在向量中如果我们想在中间插入一个元素那么它后面的每个元素都要移动一个下标。此外，如果向量的大小已满，那么它必须首先增加它的大小。所以这是一个昂贵的手术。 因此，在这种情况下，只要需要更频繁地执行插入和删除操作，就应该使用案例列表。
想要重复将大量项插入序列末尾以外的任何位置的情况。
看看每种不同类型的容器的复杂度保证:
标准容器的复杂性保证是什么?
我班上的学生似乎无法向我解释什么时候使用向量更有效，但他们在建议我使用列表时看起来很高兴。
这是我的理解
列表: 每一项都包含下一个或上一个元素的地址，所以有了这个功能，你可以随机项，即使它们没有排序，顺序也不会改变:如果你的内存是碎片化的，它是有效的。 但是它还有一个非常大的优势:你可以很容易地插入/删除项，因为你唯一需要做的就是改变一些指针。 缺点: 要读一个随机的条目，你必须从一个条目跳到另一个条目，直到你找到正确的地址。
Vectors: When using vectors, the memory is much more organized like regular arrays: each n-th items is stored just after (n-1)th item and before (n+1)th item. Why is it better than list ? Because it allow fast random access. Here is how: if you know the size of an item in a vector, and if they are contiguous in memory, you can easily predict where the n-th item is; you don't have to browse all the item of a list to read the one you want, with vector, you directly read it, with a list you can't. On the other hand, modify the vector array or change a value is much more slow.
列表更适合用于跟踪可以在内存中添加/删除的对象。 当您希望从大量单个项中访问一个元素时，向量更适合。
我不知道列表是如何优化的，但你必须知道，如果你想要快速读取访问，你应该使用向量，因为STL固定列表有多好，它在读取访问方面不会像向量那样快。
| std::vector | std::list |
|---|---|
| Contiguous memory. | Non-contiguous memory. |
| Pre-allocates space for future elements, so extra space required beyond what's necessary for the elements themselves. | No pre-allocated memory. The memory overhead for the list itself is constant. |
| Each element only requires the space for the element type itself (no extra pointers). | Each element requires extra space for the node which holds the element, including pointers to the next and previous elements in the list. |
| Can re-allocate memory for the entire vector any time that you add an element. | Never has to re-allocate memory for the whole list just because you add an element. |
| Insertions at the end are constant, amortized time, but insertions elsewhere are a costly O(n). | Insertions and erasures are cheap no matter where in the list they occur. |
| Erasures at the end of the vector are constant time, but for the rest it's O(n). | It's cheap to combine lists with splicing. |
| You can randomly access its elements. | You cannot randomly access elements, so getting at a particular element in the list can be expensive. |
| Iterators are invalidated if you add or remove elements to or from the vector. | Iterators remain valid even when you add or remove elements from the list. |
| You can easily get at the underlying array if you need an array of the elements. | If you need an array of the elements, you'll have to create a new one and add them all to it, since there is no underlying array. |
一般来说，当你不关心你使用的是哪种类型的顺序容器时，使用vector，但如果你在容器的任何地方做很多插入或擦除，而不是在末尾，你就会想要使用list。如果你需要随机访问，你就需要向量，而不是列表。除此之外，在某些情况下，根据应用程序需要其中一个或另一个，但一般来说，这些都是很好的指导原则。
在表格中总结答案以供快速参考:
| Vector | List | |
|---|---|---|
| Access | Faster | Slower |
| Insert/Delete Operations | Slower | Faster |
| Memory Allocation | Contiguous | Non-contiguous |
| Size Pre-allocation | Need to be reserved | Not necessary to reserve |
| Space Required Per Element | Only for the element itself | For element and pointers to next (and optionally previous elements) |
推荐文章
- 在每个列表元素上调用int()函数?
- 将Set<T>转换为List<T>的最简洁的方法
- c++中size_t和int的区别是什么?
- 在C和c++中静态变量存储在哪里?
- 在Python中插入列表的第一个位置
- 在javascript中从平面数组构建树数组
- 为什么标准迭代器范围是[begin, end]而不是[begin, end]?
- c++双地址操作符?(& &)
- 函数标题中的箭头操作符(->)
- Python数据结构按字母顺序排序
- 如何在c++中初始化一个向量
- 返回类型为'?:'(三元条件运算符)
- 当分配vector时，它们使用的是堆上的内存还是堆栈上的内存?
- 互斥实例/教程?
- 如何添加一个'或'条件在#ifdef
