STL中定义了三种顺序容器类型，分别是vector, list, deque（双向队列)，它们都是线性表，区别在于操作和作用于各种操作的开销上。另外STL还提供了三种容器适配器，分别是stack,queue,priority_queue，它们都是deque的重新封装。下面将分别介绍三种顺序容器，包括它们的性能分析和实现方式。注意本文不是讲解容器的使用方法，具体使用方法可以，可以google或者查看文档。

首先是vector，vector的实现方式是动态数组。显然既然是数组，那所有元素必然是连续存储的。vector主要靠不断维护三个指针（迭代器，vector中的迭代器本质就是指针，参考我的另一篇博客：浅谈cpp中vector中的迭代器）来工作的，它们分别是:_M_start, _M_finish, _M_end_of_storage 。_M_start指向第一个元素，_M_finish指向最后一个元素的下一个位置，即哨兵。_M_end_of_storage指向当前已分配地址的最后一个单元。其他两个都容易理解，主要看看_M_end_of_storage，为什么会有这个指针呢？这是因为vector为了减少分配内存的次数，会预先分配比已容纳元素更大的空间。在插入元素时，如果当前不够空间，则会重新分配内存，一般为原来空间的2倍关系分配。注意由于vector必须是连续存储，当重新分配内存时，就会破坏原来的连续性（谁能够保证一定在原来的位置的末端分配呢？）,因此重新分配内存时开销是巨大的，首先需要分配足够的内存，然后要把原来的元素逐一拷贝到新分配的内存上，然后还需要释放掉原来已经不需要的内存。如果存储的元素都是基本数据类型还好点，如果是类，则无论是类的拷贝还是调用析构函数释放内存，开销都可能很大。因此为了提高性能，vector总是尽一切可能减少内存分配次数，而同时又要兼顾不能过多分配内存造成空间浪费。注意这三个指针均是动态变化的，会随着容器的变化而自动更新，当调用begin()方法时，其实返回的正是_M_start,而end（）方法返回的是_M_finish，当计算capacity时，就需要用到_M_end_of_storage。

    下面讨论vector的性能。首先访问，由于本质是数组，而数组本身是支持随机访问的，因此访问元素开销很小，O(1)的时间完成，比如返回v[n]，则只需要返回 *(begin() + n)即可。再看看插入元素，如果在尾部追加元素，如果已分配的内存还足够大，则只需在尾部追加即可，即*_M_finish++ = new_item; 如果_M_finish已移到_M_end_of_storage，则表示已分配内存不足，需要重新分配，这个开销很大，前面已经解释。注意，虽然在尾部追加元素时遇到分配内存时开销巨大，但这种情况往往很少发生，因为大多数情况，内存都是足够的。如果需要在最前面添加元素，则不仅需要考虑内存问题，还需要移动元素，这个开销更大，因此vector不直接提供push_front方法，如果确实需要这样的操作，可以使用insert方法实现。但使用之前，一定要想想，真的有这个必要吗？你考虑了其中的开销吗？如果有100W个元素，需要移动100W次，你考虑过这样的成本吗？有没有其他的容器可供选择呢？删除元素和插入元素类似，只是不用考虑内存问题，当移除最后一个元素时，只需移动_M_finish指针并释放掉删除的元素即可（调用元素的析构函数),而移除中间元素，需要移动元素，O(n)的时间复杂度)。

    因此总结下，vector是连续存储的，适合随机访问，适合在尾部增删操作元素(这种情况，性能甚至优于list，因为list追加元素每次都需要分配一个元素节点的内存，而vector预先分配好了),但不适合在中间进行增删操作。

接下来讨论list，list实现方式是环形双向链表，学过数据结构的一定非常熟悉了，每个节点不仅保存着元素(data)，还分别有两个指针(prev,next)分别指向前一个节点和后一个节点，而最后一个节点的next指向第一个节点，第一个节点的prev指向最后一个节点。节点每次都是动态分配的，即每增加一个节点，需要new一个。存储方式显然不是连续的。节点定义如下：

struct _List_node_base {
  _List_node_base* _M_next;
  _List_node_base* _M_prev;
};

template <class _Tp>
struct _List_node : public _List_node_base {
  _Tp _M_data;
};

不难看出，节点和我们数据结构上的节点定义类似，只不过_List_node_base没有data，然后_List_node继承并添加了data，这样的目的是为了使移动和迭代器分离。迭代器不再是vector中简单的指针，而是一个相对复杂的struct，不过我们仍然可以看作是指向节点指针的指针。由于本质是一个双向链表，因此只需要一个指针就可以访问所有元素，list中是_M_node，它指向最后一个节点。那第一个节点就是_M_node->_M_next。因此begin（）方法返回_M_node->_M_next, end()方法返回_M_node，当_M_node->_M_next == _M_node时，即_M_node指向自己时，说明链表为空。list正是通过不断维护_M_node这个节点指针来进行各种操作的。另外还有两个指针，分别是_M_put_node 和_M_put_get，这两个指针是临时指针，主要用于新建指针或删除指针时使用。原理就是这样，下面讨论性能：

首先是访问节点，访问最后一个节点或者第一个节点不需要移动指针，即最后一个节点返回_M_node -> _M_data即可，而第一个节点，只需要返回_M_node_->_M_next->_M_data，因此开销很小。但要访问中间节点时就必须通过移动节点了，至于向前还是向后移动，取决于节点的位置。因此list访问节点的时间复杂度是O(n)，相对于vector来说性能下降，因此list没有实现[ ]运算符重载。而插入和删除指定位置的节点，只需要修改指针，而不需要移动指针，性能比vector大大提高。

总结一下，list本质就是双向环形链表，不支持随机访问，插入删除操作开销小。另外，由于每次加入新节点时都需要分配内存，然后拷贝元素，如果是在尾部操作元素，则性能反而比vector要低。

最后剩下deque了，deque可以大致认为是vector和list的混合体。如果学过操作系统内存管理，那么就很容易理解了。vector类似于分区存储管理方式，list类似链式存储方式，而deque则类似于分页式存储管理方式（当然由于deque是整用整取，因此不存在内部碎片问题）。deque就像是分页式存储，首先需要一个map表（相当于页表），存储各个node的指针，每个node都是一个连续的缓冲区，用于实际保存元素，并且还有一些预留空间。需要查找某一个元素时，首先需要计算这个元素处于哪个node缓冲区，然后计算offset从该缓冲区中定位。逻辑上看起来deque也是连续存储的，但事实是由一段段连续的空间组合起来的。deque上的迭代器主要依靠_M_cur,_M_first,_M_last,_M_node四个指针来操作，_M_cur指向当前元素,_M_first指向缓冲区头，_M_last指向缓冲区尾，_M_node指向map表，为了逻辑上看起来是连续的，deque迭代器实现了各种运算符重载, 比如++ / + / --/ -等，虽然++看起来简单，实际需要一些计算，如果_M_cur所在缓冲区还有元素，则直接移动_M_cur即可，若移到该缓冲区尾部，则需要找到下一个缓冲区，然后指向第一个元素。其他操作类似。而要访问任意一个位置的元素时，需要先计算该元素在哪个缓冲区，然后计算offset偏移量找到该元素。由于已经实现了+ -操作，则只需要简单调用*（begin() + n）即可。这就非常类似vector了。因此deque逻辑上实现了和vetor一样的随机访问，时间复杂度也是O(1)，不过相对于vector，由于需要一些计算，效率上有点损失，不过这可以忽略不计。下面看看性能方面。

首先访问，上面已经说了，逻辑上支持随机访问。插入元素到指定位置，所在缓冲区还有预留空间，直接插入，并且该缓冲区需要移动元素，这比vector效率大大提高，因为不需要移动整个列表，而只是所在的缓冲区node。而如果所有缓冲区都满了，需要重新分配一个缓冲区，并把新元素放到新的缓冲区中，不需要额外的拷贝操作，只需修改map即可。如果只需要在头尾新增元素，尾部类似vector，看看还有没有预留空间，首部的话也类似，看看前面有没有预留空间，没有再分配一个缓冲区。因此deque在首部增删操作优于vector。

总结一下，deque可以看作是vector和list的折中方案，逻辑上实现了随机访问，在首尾操作开销很小。因此如果既要随机访问，又要各种插入删除操作，deque是一种不错的选择。

注意所有容器存储的都是原来元素的副本，而不是本身，因此不支持复制和赋值的元素类型不能放入容器中，比如IO类型对象就不能放入容器中，数组也不应该放入数组中，因此数组不支持直接赋值运算，即int a[5];int b[5] = a是非法的。如果容器放入的元素类型拷贝和析构开销都比较大，则应该考虑下放入元素的指针或许更好。

只有知道容器的内部实现原理，才能真正明智的选择容器的类型。

• 相关文章
• 全局相关文章