《STL基础之vector、list、deque》

【vector、list、deque导读】vector、list、deque这三种序列式的容器，算是比较的基础容器，也是大家在日常开发中常用到的容器，因为底层用到的数据结构比较简单，笔者就将他们三者放到一起做下对比分析，介绍下基本用法，对比下三者的性能。

     

1. vector特性和原理   

     vector是个很基础的容器，其内部也就是一段连续的内存空间，具有动态扩容的能力，支持随机访问容器中的元素，查找元素的时间复杂度是O(1)，插入、删除元素（除开尾部，而且vector还有备用空间的情况）会引起内存的拷贝，存在性能问题。vector提供常用的元素操作接口有：push_back、pop_back、erase、clear、insert。还有获取vector大小的size()接口、容量的capacity()接口。

    下面给出一些示例，演示vector是如何去操作元素的？

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;class A
{
public:A() {cout << "A()" << endl;}~A(){cout << "~A()" << endl;}A(const A& other){cout << "A(const A& other)" << endl;}A& operator=(const A& other){cout << "A& operator=(const A& other)" << endl;}A(const A&& other){cout << "A(const A&& other)" << endl;}A& operator= (const A&& other){cout << "A& operator= (const A&& other)" << endl;}
};int main()
{A aa;vector<A> iv(2, aa);std::cout << "size: " << iv.size() << " capacity: " << iv.capacity() << endl;std::cout << "after push back" << std::endl;iv.push_back(aa);std::cout << "size: " << iv.size() << " capacity: " << iv.capacity() << endl;return 0;
}

运行结果如下：

    iv初始化的时候，往容器中插入了两个A类对象，调用了A的拷贝构造函数两次，此时iv元素个数和容量大小都是2，随后又往iv尾部插入一个A类对象，因为iv没有多余的剩余空间，那么此时vector另外寻找了个新的空间，大小为3，并把之前的两个A类对象拷贝到新的空间中去。为啥动态扩容之后，vector的大小变成了3，而不是原来大小的两倍？很炸裂，那我们就调试最新的STL源码。

    很震惊，STL做了优化和改进，动态扩容不再是两倍的扩充了，而是根据元素的实际个数来扩充，所以以前老旧的观念需要改正。

std::cout << "after pop back" << std::endl;
iv.pop_back();
iv.pop_back();
std::cout << "size: " << iv.size() << " capacity: " << iv.capacity() << endl;

这个时候，我们在尾部弹出两个元素，那么此时又是一种什么结果？

     弹出两个元素，引起A类对象的析构，元素个数变成了1，容量的大小依然是3。

     vector的删除接口erase，有按照范围删除、也有删除指定位置的元素，这两个接口的源码如下：

iterator erase(iterator first, iterator last)
{iterator i = copy(last, finish, first);destory(i, finish);finish = finish - (last - first);return first;
}iterator erase(iterator position)
{if (position + 1 != end())copy(position + 1, finish, position);--finish;destory(finish);return position;      
}

        可以看出无论是删除指定范围的元素还是删除指定位置的元素，都会涉及到元素的拷贝或者移动赋值；以下示例程序也能验证我们的结论。

std::cout << " after erase " << std::endl;
iv.erase(iv.begin(), iv.begin() + 1);
std::cout << "size: " << iv.size() << " capacity: " << iv.capacity() << endl;

    从上述运行结果可以看到，删除iv容器中首个元素，引起了后面两个元素的移动，也即第二个元素挪到第一个位置去，第三个元素挪到第二个位置去。

2、 list特性和原理

     list背后的数据结构是环状双向链表，支持元素的双向遍历查找，因此list容器在元素查找上的时间复杂度为O(n)，但是插入元素、删除元素的时间复杂度始终为O(1)。list支持的元素操作有push_front、push_back、erase、pop_front、pop_back、remove、unique、merge、reverse、sort，其实这些操作，无非就是对底层的链表进行头部插入、尾部删除、翻转、排序、合并等操作。

#include <iostream>
#include <list>int main()
{list<A> li;std::cout << li.size() << endl;A a;li.push_back(a);li.push_back(a);li.insert(li.begin(), a);li.erase(li.begin());return 0;
}

  运行结果：

    可以看出往list容器中push元素或者insert元素，都会引起元素的拷贝构造。

3、 deque特性和原理

    deque 是由一段一段定量连续的空间构成，一旦需要在deque的前面或者尾端增加新空间，此时只需申请一段定量的连续空间，串接在deque的头部或者尾端。deque的整体架构图如下：

       map并不是键值对map，而是一个指针数组，里面存储的是一个个指针，里面每个指针指向一段段连续的内存空间，这些分段的内存分别用来存储数据。虽然内存是分段的，但是给外部的表象是连续的内存空间，原因在于deque的迭代器设计的很巧妙。

template<class T, class Ref, class Ptr, size_t BufSiz>
struct __deque_iterator
{typedef T** map_pointer;  //指向管控中心maptypedef __deque_iterator self;T* cur;  //指向缓冲区当前的元素T* first; //指向缓冲区一个元素T* last; //指向缓冲区最后一个元素map_pointer node; //管控中心的节点
}

      假设我们在遍历元素的时候，走到了第二个缓冲区的末尾节点，此时，应该如何跳转到下一个缓冲区，且看deque的源码。

void set_node(map_pointer new_node)
{node = new_node;//下一个节点的首位元素便是firstfirst = *new_node;last = first + difference_type(buffer_size());
}self& operator++()
{++cur;if (cur == last){//跳转到下一个节点set_node(node + 1);cur = first;}return *this;
}

     好，再验证下deque插入元素，是否会涉及到插入对象的拷贝。

A a;
deque<A> idque(2, a);
idque.push_back(a);
idque.push_front(a);
idque.insert(idque.begin(), a);
idque.insert(idque.end(), a);

      在头部、尾部插入元素，只会拷贝当前的对象，并不会涉及到其它对象的拷贝或者移动。那如果在容器的中间端插入对象呢？

cout << "after insert" << endl;
idque.insert(idque.begin() + 2, a);

    可以清晰看到，在中间部位插入对象，还是会影响到其它元素的移动，现在新版的STL倒是做了优化和改进，使用移动构造或者移动赋值的方式去搬移对象，而不是单纯地拷贝构造或赋值。

4、 性能比对

int main()
{// 获取当前时间作为示例auto start = std::chrono::system_clock::now();A a;deque<A> idque;time_t t1 = time(NULL);for (int i = 0; i < 100 * 10000; ++i){idque.push_front(a);}// 计算差值auto end = std::chrono::system_clock::now();auto duration = end - start;cout << "deque: " << duration.count() << endl;list<A> li;start = std::chrono::system_clock::now();for (int i = 0; i < 100 * 10000; ++i){li.push_back(a);}end = std::chrono::system_clock::now();duration = end - start;cout << "list: " << duration.count() << endl;vector<A> iv;start = std::chrono::system_clock::now();for (int i = 0; i < 100 * 10000; ++i){iv.push_back(a);}end = std::chrono::system_clock::now();duration = end - start;cout << "vector: " << duration.count() << endl;return 0;
}