Jon*_*vis 382
向量:
- 连续的记忆.
- 为未来元素预先分配空间,因此需要额外的空间超出元素本身所需的空间.
- 每个元素只需要元素类型本身的空间(没有额外的指针).
- 可以在添加元素时为整个矢量重新分配内存.
- 最后的插入是不变的,摊销时间,但在其他地方的插入是昂贵的O(n).
- 向量末尾的擦除是恒定时间,但对于其余的,它是O(n).
- 您可以随机访问其元素.
- 如果向向量添加元素或从向量中删除元素,则迭代器将失效.
- 如果需要元素数组,可以轻松获取底层数组.
列表:
- 非连续的记忆.
- 没有预先分配的内存.列表本身的内存开销是不变的.
- 每个元素都需要额外的空间用于保存元素的节点,包括指向列表中下一个和前一个元素的指针.
- 永远不必因为添加元素而为整个列表重新分配内存.
- 插入和删除都很便宜,无论它们出现在列表的哪个位置.
- 将列表与拼接相结合很便宜.
- 您无法随机访问元素,因此获取列表中的特定元素可能会非常昂贵.
- 即使您在列表中添加或删除元素,迭代器仍然有效.
- 如果你需要一个元素数组,你将不得不创建一个新元素并将它们全部添加到它,因为没有底层数组.
一般情况下,当你不关心你正在使用什么类型的顺序容器时使用vector,但是如果你在容器中的任何地方进行多次插入或擦除,那么你将需要使用清单.或者,如果您需要随机访问,那么您将需要向量,而不是列表.除此之外,根据您的应用程序,您自然会需要一个或另一个,但总的来说,这些都是很好的指导方针.
- 另一个考虑是`list`在你擦除元素时释放内存,但`vector`却没有.除非使用`swap()`技巧,否则`vector`在减小其大小时不会降低其容量. (6认同)
- 此外,从免费商店分配不是免费的.:)向向量添加新项目执行O(log n)免费存储分配,但您可以调用`reserve()`将其减少为O(1).将新项添加到列表(即不拼接它们)执行O(n)个免费存储分配. (2认同)
- @nXqd:如果需要向向量添加N个元素,请调用v.reserve(v.size()+ N),使其仅执行一次免费存储分配.swap()技巧在这里:http://stackoverflow.com/questions/253157/how-to-downsize-stdvector (2认同)
- @bk1e 在 c++11 之后你可以调用 'std::vector::shrink_to_fit()' (2认同)
Mar*_*ork 88
您希望将大量项目重复插入序列末尾的情况.
查看每种不同类型容器的复杂性保证:
- Bjarne Strostrup实际上做了一个测试,他在那里生成随机数,然后分别将它们添加到列表和向量中.进行插入以便始终对列表/向量进行排序.即使这通常是"列表域",向量也会以大幅度的优势超越列表.原因是内存访问缓慢,缓存对顺序数据更有效."GoingNative 2012"的主题演讲中提供了所有这些内容 (15认同)
- @Notinlist - 以下是"下一个不可能"的内容吗？v.insert(v.begin(),i) (14认同)
- 不,在向量的末尾插入元素是分摊的常量时间.内存分配仅偶尔发生,您可以预先分配矢量以防止它.当然,如果你*必须*保证一致的恒定时间插入,我想这仍然是一个问题. (9认同)
- @Notinlist - 我同意你的意见,只是因为我不希望OP认为界面不存在,以防万一想要在(表演)脚上射击自己. (4认同)
- @skydoor:一个文字处理器. (3认同)
- 在末尾插入元素也很重要，因为它会导致内存分配和元素复制成本。而且，在向量的开头插入 elenets 几乎是不可能的，`list` 有 `push_front` (2认同)
Han*_*ant 30
如果您不需要经常插入元素,那么向量将更有效.它具有比列表更好的CPU缓存局部性.换句话说,访问一个元素使得下一个元素很可能存在于缓存中,并且可以在不必读取慢速RAM的情况下进行检索.
Tom*_*dor 28
这里的大多数答案错过了一个重要细节:为什么？
你想把什么保留在容器中？
如果它是ints 的集合,那么std::list在每个场景中都会丢失,无论你是否可以重新分配,你只能从前面删除等等.列表遍历较慢,每次插入都会花费你与分配器的交互.准备一个list<int>节拍的例子是非常困难的vector<int>.即便如此,deque<int>可能会更好或更接近,而不仅仅是使用列表,这会产生更大的内存开销.
但是,如果你正在处理大而丑陋的数据 - 而且很少 - 你不想在插入时进行全面分配,并且由于重新分配而进行复制将是一场灾难 - 那么你可能会更好地使用list<UglyBlob>比vector<UglyBlob>.
尽管如此,如果你再次切换到vector<UglyBlob*>甚至是vector<shared_ptr<UglyBlob> >- 列表将落后.
因此,访问模式,目标元素数量等仍会影响比较,但在我看来 - 元素大小 - 复制成本等.
- 在阅读 Meyers 的《Effective STL》时，我还有一个反思：“list<T>”的一个特殊属性是在 *O(1)* 中“拼接”的可能性。如果您需要恒定时间拼接，列表也可能是选择的结构；） (2认同)
Unc*_*ens 16
std :: list的一个特殊功能是拼接(将一部分或整个列表链接或移动到不同的列表中).
或者,如果您的内容复制起来非常昂贵.在这种情况下,例如,使用列表对集合进行排序可能更便宜.
另请注意,如果集合很小(内容复制起来不是特别昂贵),即使您在任何地方插入和删除,矢量仍可能优于列表.列表单独分配每个节点,这可能比移动一些简单的对象要昂贵得多.
我认为没有非常严格的规则.这取决于你最想要对容器做什么,以及你期望容器的大小和包含的类型.向量通常胜过列表,因为它将其内容分配为单个连续块(它基本上是动态分配的数组,在大多数情况下,数组是保存一堆内容的最有效方法).
xyz*_*xyz 14
让它变得简单-
在一天结束时，当您在 C++ 中选择容器感到困惑时，请使用此流程图图像（感谢我）：-
向量-
- 载体基于传染性记忆
- 向量是小数据集的方法
- 向量在遍历数据集时执行速度最快
- 向量插入删除在庞大的数据集上很慢，但对于非常小的数据集很快
列表-
- 列表基于堆内存
- list 是获取非常大的数据集的方法
- list 在遍历小数据集时相对较慢，但在遍历大数据集时速度较快
- 列表插入删除在庞大的数据集上很快，但在较小的数据集上很慢
jok*_*oon 13
好吧,我班上的学生似乎无法向我解释何时使用向量更有效,但在建议我使用列表时他们看起来很开心.
这就是我理解它的方式
列表:每个项目都包含下一个或上一个元素的地址,因此使用此功能,您可以随机化项目,即使它们未排序,顺序也不会更改:如果内存碎片化,则效率很高.但它还有另一个非常大的优势:您可以轻松插入/删除项目,因为您唯一需要做的就是更改一些指针.缺点:要读取随机单个项目,您必须从一个项目跳到另一个项目,直到找到正确的地址.
向量:当使用向量时,内存比常规数组更有条理:每个第n项存储在第(n-1)项之后和第(n + 1)项之前.为什么它比列表更好？因为它允许快速随机访问.方法如下:如果您知道向量中项目的大小,并且它们在内存中是连续的,则可以轻松预测第n个项目的位置; 你不必浏览列表中的所有项目来阅读你想要的那个项目,使用矢量,你可以直接阅读它,但你不能使用列表.另一方面,修改矢量数组或更改值要慢得多.
列表更适合跟踪可在内存中添加/删除的对象.当您想要从大量单个项目中访问元素时,向量更合适.
我不知道如何优化列表,但你必须知道如果你想要快速读取访问,你应该使用向量,因为STL紧固列表有多好,它在读取访问中的速度不会高于向量.
将答案总结在表格中以供快速参考：
| 向量 | 列表 | |
|---|---|---|
| 使用权 | 快点 | 慢点 |
| 插入/删除操作 | 慢点 | 快点 |
| 内存分配 | 连续的 | 不连续 |
| 尺寸预分配 | 需要预约 | 无需预约 |
| 每个元素所需的空间 | 仅适用于元素本身 | 对于元素和指向下一个元素 （以及可选的前一个元素）的指针 |
就向量和列表而言，我注意到的主要区别如下：
向量
向量将其元素存储在连续的内存中。因此，向量内部可以进行随机访问，这意味着访问向量的元素非常快，因为我们只需将基地址与项索引相乘即可访问该元素。事实上，为此目的只需要 O(1) 或常数时间。
由于向量基本上包装了一个数组，因此每次将元素插入向量（动态数组）时，它都必须通过查找新的连续内存块来调整自身大小以容纳新元素，这是非常耗时的。
它不会消耗额外的内存来存储指向其中其他元素的任何指针。
列表
列表将其元素存储在非连续内存中。因此，在列表内部不可能进行随机访问，这意味着要访问其元素，我们必须使用指针并遍历列表，这相对于向量来说速度较慢。这需要 O(n) 或比 O(1) 慢的线性时间。
由于列表使用非连续内存，因此在列表中插入元素所花费的时间比其向量对应项的情况要高效得多，因为避免了内存的重新分配。
它消耗额外的内存来存储指向特定元素之前和之后的元素的指针。
因此，记住这些差异，我们通常会考虑内存、频繁的随机访问和插入来决定给定场景中向量与列表的获胜者。
| 归档时间： |
|
| 查看次数： |
273277 次 |
| 最近记录： |