我注意到在有效的STL

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

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

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


当前回答

当你想在容器之间移动对象时,你可以使用list::splice。

例如,一个图划分算法可以将常数数量的对象递归地划分到数量不断增加的容器中。对象应该初始化一次,并始终保持在内存中的相同位置。通过重新链接来重新排列比重新分配要快得多。

Edit: as libraries prepare to implement C++0x, the general case of splicing a subsequence into a list is becoming linear complexity with the length of the sequence. This is because splice (now) needs to iterate over the sequence to count the number of elements in it. (Because the list needs to record its size.) Simply counting and re-linking the list is still faster than any alternative, and splicing an entire list or a single element are special cases with constant complexity. But, if you have long sequences to splice, you might have to dig around for a better, old-fashioned, non-compliant container.

其他回答

当你想在容器之间移动对象时,你可以使用list::splice。

例如,一个图划分算法可以将常数数量的对象递归地划分到数量不断增加的容器中。对象应该初始化一次,并始终保持在内存中的相同位置。通过重新链接来重新排列比重新分配要快得多。

Edit: as libraries prepare to implement C++0x, the general case of splicing a subsequence into a list is becoming linear complexity with the length of the sequence. This is because splice (now) needs to iterate over the sequence to count the number of elements in it. (Because the list needs to record its size.) Simply counting and re-linking the list is still faster than any alternative, and splicing an entire list or a single element are special cases with constant complexity. But, if you have long sequences to splice, you might have to dig around for a better, old-fashioned, non-compliant container.

任何时候都不能使迭代器失效。

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

当你在序列中间有很多插入或删除时。例如,内存管理器。

列表只是stl中double - linkedlist的包装器,因此提供了您可能希望从d-linklist中获得的功能,即O(1)插入和删除。 向量是具有传染性的数据序列,其工作方式类似于动态数组。S-更容易遍历。