我注意到在有效的STL

向量是这样一种序列 默认情况下应该使用。

这是什么意思?似乎忽略效率向量可以做任何事情。

谁能给我一个场景,其中向量不是一个可行的选择,但必须使用列表?


当前回答

在表格中总结答案以供快速参考:

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)

其他回答

〇简单一点 在一天结束的时候,当你在c++中选择容器时感到困惑时,使用下面的流程图图像(对我说谢谢):-

向量,

Vector基于传染性记忆 矢量是小数据集的一种方式 Vector在遍历数据集时执行最快 向量插入删除在巨大数据集上很慢,但在非常数据集上很快 小

列表,

List基于堆内存 列表是非常庞大的数据集 List在遍历小数据集时相对较慢,但在 巨大的气候资料 列表插入删除在大数据集上速度快,但在小数据集上速度慢 的

保留迭代器的有效性是使用列表的原因之一。另一种情况是当你不希望在推送物品时重新分配向量。这可以通过巧妙地使用reserve()来管理,但在某些情况下,仅使用列表可能更容易或更可行。

这里的大多数答案都遗漏了一个重要的细节:为什么?

你想在集装箱里放些什么?

如果它是int型的集合,那么std::list在任何情况下都将丢失,不管你是否可以重新分配,你只从前面删除,等等。遍历列表的速度较慢,每次插入都需要与分配器进行交互。要准备一个例子是极其困难的,其中list<int>击败vector<int>。即使这样,deque<int>可能更好或关闭,而不仅仅是使用列表,这将有更大的内存开销。

然而,如果您正在处理大而丑陋的数据块——而且数量很少——您不想在插入时过度分配,而由于重新分配而进行复制将是一场灾难——那么您可能,也许,使用list<UglyBlob>比使用vector<UglyBlob>更好。

不过,如果你切换到vector<UglyBlob*>或甚至vector<shared_ptr<UglyBlob> >, - list仍然会滞后。

因此,访问模式、目标元素数量等仍然会影响比较,但在我看来,元素大小、复制成本等。

必须使用list的唯一硬性规则是需要将指针分发到容器元素的地方。

与vector不同,你知道元素的内存不会被重新分配。如果可以,那么可能会有指向未使用内存的指针,这在最好的情况下是一个大禁忌,在最坏的情况下是SEGFAULT。

(从技术上讲,*_ptr的向量也可以工作,但在这种情况下,你是在模拟列表,所以这只是语义。)

其他软规则与将元素插入容器中间可能存在的性能问题有关,因此最好使用list。

如果你不需要经常插入元素,那么向量会更有效。它具有比列表更好的CPU缓存位置。换句话说,访问一个元素使得下一个元素很有可能存在于缓存中,并且可以在不读取慢速RAM的情况下被检索。