总结了STL容器的原理

容器

C++ 提供的容器有 vector , map , unordered_map , set , list , dequeue等

应用场景

set 和 map

共同点：都是C++的关联容器,只是通过它提供的接口对里面的元素进行访问，底层都是采用红黑树实现。
不同点：
- set：用来判断某一个元素是不是在一个组里面，使用的比较少；
- map：映射，相当于字典，把一个值映射成另一个值，可以创建字典
优点：查找某一个数的时间为O(log n)；遍历时采用 iterator，效果不错
缺点：每次插入值的时候，都需要调整红黑树，效率有一定影响

unordered_map

Hash表实现，虽然功能上和 map 有点像，但是由于原理上本质的区别，它是不能遍历迭代的，即无序。速度快查找时间复杂度 O(1)

vector

是动态数组，在堆中分配内存，元素连续存放，有保留内存，如果减少大小后，内存也不会释放；如果新值大于当前大小时才会重新分配内存。

优点：拥有一段连续的内存空间，并且起始地址不变，因此能够非常好的支持随机存取，即[]操作符；O(1)
缺点：对头部和中间进行添加删除元素操作需要移动内存，如果元素是结构或类，那么移动的同时还会进行构造和析构操作，所以性能不高

list

双向链表，元素也存放在堆中，每个元素都是放在一块内存中，他的内存空间可以是不连续的，通过指针来进行数据的访问。

缺点：这个特点使得它的随机存取变得非常没有效率，因此它没有提供[]操作符的重载。访问元素的时间复杂度 O(N)。
优点：它可以很有效率的支持任意地方的删除和插入操作。所以常用来做随机插入和删除操作容器。

deque

deque是一种优化了的对序列两端元素进行添加和删除操作的基本序列容器。通常由一些独立的区块组成，第一区块朝某方向扩展，最后一个区块朝另一方向扩展。它允许较为快速地随机访问但它不像vector一样把所有对象保存在一个连续的内存块，而是多个连续的内存块。并且在一个映射结构中保存对这些块以及顺序的跟踪。（因此在任意位置插入元素，不需要移动后面所有的元素，只用修改一页的内容）

优点：随机插入删除元素的速度介于 vector 和 list 之间，因为不需要复制所有元素
缺点：随机读取元素的速度也是介于 list 和 vector之间，因为deque需要处理内部跳转，读取速度没vector快，不支持resize 和 reserve 操作即不能自己显式的控制内存的大小。

迭代失效问题

	vector	deque	list	set、map
内部数据结构	数组(一段连续内存空间)	数组(多段连续内存空间)	双向环状链表	红黑树
插入操作	插入后元素总数不大于capacity，插入位置之后的迭代器会失效；大于capacity,所有迭代器都会失效	两端插入, 不会引起迭代器失效；中间插入, 所有迭代器失效	不会出现迭代器失效	不会出现迭代器失效
删除操作	删除位置之后的迭代器都会失效,但是erase会返回下一个有效的迭代器	两端删除, 被删除元素的迭代器失效中间删除, 所有迭代器失效	被删除节点的迭代器失效	被删除节点的迭代器失效
解决方法	iter =cont.erase(iter)		m.erase(iter++)	m.erase(iter++)

//要求删除键值为偶数的键值对
 map<int, int>::iterator it = m.begin();

 //错误实现：
 while (it != m.end()){
   if(it->second % 2 == 0){
     m.erase(it);
   }
   it++;
 }

 //正确实现：
 while (it != m.end()){
   if(it->second % 2 == 0){
     m.erase(it++); //重点！！！  it++的写法才行不能  m.rease(it); it++;
   }
   else{
     it++;
   }
 }

Ruowang's blogs

STL容器原理

容器