矢量是链表的特例吗？

Question

在谈到STL时,我有几个同学告诉我"向量是链接列表".

我还有一个人认为如果用迭代器调用erase()方法,它会破坏向量,因为它是一个链表.

他们也倾向于不明白为什么我总是认为向量是连续的,就像任何其他数组一样,并且似乎不理解随机访问的含义.矢量是否像常规数组一样严格连续,或者只是最连续？(例如,如果整个数组不适合,它将分配几个连续的段).

Answer 1

我很遗憾地说你的同学完全错了.如果你的同学可以诚实地说"向量是链接列表",那么你需要尊重告诉他们他们需要拿一本好的C++书(或任何体面的计算机科学书)并阅读它.或者甚至维基百科的矢量和列表文章.(另请参阅动态数组和链表的文章.)

向量(如std::vector)不是链表.(注意,std::vector不要派生自std::list).虽然它们都可以存储数据集合,但是矢量如何与链接列表完成不同.因此,它们在不同情况下具有不同的性能特征.

例如,插入是链接列表上的常量时间操作,而如果它插入到除结尾之外的某个位置,则它是向量上的线性时间操作.(但是,如果在向量的末尾插入,它将按照常量时间分摊.)

std::vectorC++中的类必须与C++标准连续:

23.2.4/1类模板 vector

A vector是一种支持随机访问迭代器的序列.此外,它支持(摊销)最后的恒定时间插入和擦除操作; 在中间插入和擦除需要线性时间.存储管理是自动处理的,但可以提供提示以提高效率.的元素vector被连续存储,也就是说如果v是vector<T, Allocator>其中T一些类型比其他的bool,那么它遵循的身份&v[n] == &v[0] + n对所有0 <= n < v.size().

比较一下std::list:

23.2.2/1类模板 list

A list是一种支持双向迭代器的序列,允许在序列中的任何位置进行恒定时间插入和擦除操作,并自动处理存储管理.与向量(23.2.4)和deques(23.2.1)不同,不支持对列表元素的快速随机访问,但是许多算法无论如何都只需要顺序访问.

显然,C++标准规定向量和列表是两个不同的容器,它们以不同的方式做事.

你不能通过简单地erase()用有效的迭代器调用来"破坏"一个向量(至少不是故意的).这会使它变得std::vector毫无用处,因为它的存在就是为你管理记忆!

Answer 2

vector将所有存储在一个地方.A vector甚至不像链接列表那样遥远.事实上,如果我必须选择两个彼此最不相同的数据结构,它将是vector和list."最多连续"是一个如何deque运作.

向量:

1. 保证所有元素的连续存储 - 将复制或移动元素.
2. O(1)访问时间.
3. O(n)用于插入或移除.
4. 迭代器在插入或删除任何元素时失效.

列表:

1. 根本没有连续存储 - 永远不会复制或移动元素.
2. O(n)访问时间 - 加上你将得到的所有令人讨厌的缓存未命中.
3. O(1)插入或移除.
4. 只要未删除该特定元素,迭代器就会有效.

如您所见,它们在每个数据结构用例中的行为都不同.