【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; //指向管控中心map
typedef __deque_iterator self;
T* cur; //指向缓冲区当前的元素
T* first; //指向缓冲区一个元素
T* last; //指向缓冲区最后一个元素
map_pointer node; //管控中心的节点
}假设我们在遍历元素的时候，走到了第二个缓冲区的末尾节点，此时，应该如何跳转到下一个缓冲区，且看deque的源码。
void set_node(map_pointer new_node)
{
node = new_node;
//下一个节点的首位元素便是first
first = *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;
}
