C++ STL容器时间复杂度下的最佳选择
引言
今天一个电话面试的HR问了我许多问题，当问到我关于STL的时间复杂度的问题，我就开始支支吾吾了。
要知道，通常状况下对于STL的使用，我只是概念上的了解他们的优劣，可是在使用上仍是比较随性的，除非遇到频繁操做的数据结构才考虑具体该用哪一种STL，但到用的时候向来都是google 百度的。程序员
仍是备一备吧，否则也应付不了HR。web
简介
STL在C++11中还算是火热，想必你们早有耳闻，对于泛型编程而言，或者数据结构而言，STL都显得尤其重要。今天让咱们来了解一下，根据时间复杂度这个条件，挑选最适合本身程序的STL。面试
容器类型
连续内存的容器：这种类型容器包含vector、deque。特色是在一块连续的内存块上存放数据，因此有数据插入和删除的时候，若是不是在序列的 或者两端那么花费的代价是很是大的，由于须要保证连续内存，同时给新元素腾出空间或者填充删除元素的空间，若是存储的是复杂结构的话就要花费大量的时间进行拷贝操做（能够存储复杂结构的指针来弥补这个缺陷，这个讨论在另个总结中进行）。算法
基于节点的容器：这类容器是剩余的几个list、set、multiset、map、multimap.这类容器中的数据是分别存储在不一样的内存块中，可能连续也可能不连续（通常不认为是连续的），这样的容器在插入删除元素的时候修改的只是节点的指针，这样的消耗是很是小的。编程
使用注意
在使用的过程当中，须要考虑的问题有元素顺序、标准的一致性、迭代器能力、内存布局和C的兼容性、查找速度这些，考虑了这些问题你选择的容器应该会很是适合你当前的情景。数组
须要大量添加新元素：数据结构
vector在大量添加元素的时候问题最大，由于他的一种最多见的内存分配实现方法是当前的容量(capacity)不足就申请一块当前容量2倍的新内存空间，而后将全部的老元素所有拷贝到新内存中，添加大量元素的时候的花费的惊人的大。若是因为其余因素必须使用vector，而且还须要大量添加新元素，那么可使用成员函数reserve来事先分配内存，这样能够减小不少没必要要的消耗。svg
list对这种状况的适应能力就很是好，都是常数时间的插入消耗。deque前面说过了，他是vector和list的折衷形式，内存不够了就申请一块新的内存，但并不拷贝老的元素。函数
查找速度：布局
这个因素主要取决于算法，而算法最终是做用在容器中元素上的，因此这里的查找速度指的是容器可以达到的最好查找效率。
对于序列容器须要分两种状况，区分依据是元素是否排序，1)对于已经排序的序列容器，使用binary_search、lower_bound、upper_bound、equal_range能够得到对数时间复杂度的查找速度(O(logN));2)而未排序的序列容器二分查找确定是用不了，能达到的最好的时间复杂度是线性的(O(n))。
对于关联容器，存储的时候存储的是一棵红黑树(一种更为严格的平衡二叉树,文档最后有介绍)，老是能达到对数时间复杂度(O(logN))的效率，由于关联容器是按照键值排好序的。
是不是连续内存：
连续内存的容器有个明显的缺点，就是有新元素插入或老元素删除的时候，为了给新元素腾出位置或者填充老元素的空缺，同一块内存中的其余数据须要进行总体的移位，这种移位的拷贝代价有时是很是巨大的。标准容器中的vector、deque是连续内存的，其中vector是彻底连续内存，而deque是vector和list的折衷实现，是多个内存块组成的，每一个块中存放的元素连续内存，而内存块又像链表同样链接起来。
因此须要考虑在操做的过程当中是否有在任意位置插入元素的需求，有这种需求的话尽可能避免使用连续内存的vector、deque
元素的排序：
序列容器中的元素不会自动排序，程序员插入什么顺序内存中就是什么顺序，而关联容器不是这样的，他会以本身的键值按照某种等价关系(equivalence)进行排序。因此默认状况下序列容器中的元素是无序的，而关联容器中的元素是有序的。
因此容器在遍历元素的时候序列容器输出的顺序和插入的顺序式一致的，关联容器就不必定了。下面给出两个例子：
经过例子看到序列容器vector遍历的顺序和插入的顺序是同样的，而关联容器set把插入的元素按照某种顺序从新组织了，因此选择容器的时候若是很在乎插入顺序的话就选择序列容器。
内存是否和C兼容：
适合的容器只有一个vector，意思就是若是须要把容器中的数据放到C类型的数组中那么不须要作多余复杂的操做，若是有vector v，只须要直接使用&v[0]就能够获得v中第一个元素的指针，由于vector和C数组的内存布局是同样的，这个要求同时也是标准C++委员会制定的标准。因此能保证有这样特性的容器只有vector，那么vector之外的其余STL容器中的数据若是须要变换成C数组形式，或者C数组放到其余类型容器中，能够把vector做为一个桥梁，下面给个例子：
//假设函数void read(const int* pInt, unsigned int num);
//从pInt指针位置开始读取num个int型数据
std::set<int> temp_set;
... //省略给temp_set插入元素的操做
std::vector<int> temp_vector(temp_set.begin(), temp_set.end());
if (!temp_vector.empty())
read(&temp_vector[0], temp_vector.size());
容器优缺点
用哪一种容器的选择看起来很是繁琐，头脑中若是有个每一个容器大概的模型，在选择的时候会更为轻松点。
Vector的数据模型就是数组。
优势：内存和C彻底兼容、高效随机访问、节省空间
缺点：内部插入删除元素代价巨大、动态大小查过自身容量须要申请大量内存作大量拷贝。
List 的数据结构模型是链表
优势：任意位置插入删除元素常量时间复杂度、两个容器融合是常量时间复杂度
缺点：不支持随机访问、比vector占用更多的存储空间
Deque的数据模型是数组和链表的折衷：
优势：高效随机访问、内部插入删除元素效率方便、两端push pop
缺点：内存占用比较高
Map、set、multimap、multiset的数据结构模型是二叉树(红黑树)
优势：元素会按照键值排序、查找是对数时间复杂度、经过键值查元素、map提供了下标访问
容器特性
| 容器类型 | 容器特性 |
|---|---|
| vector | 典型的序列容器，C++标准严格要求次容器的实现内存必须是连续的惟一能够和标准C兼容的stl容器，任意元素的读取、修改具备常数时间复杂度，在序列尾部进行插入、删除是常数时间复杂度，但在序列的头部插入、删除的时间复杂度是O(n)，能够 在任何位置插入新元素，有随机访问功能，插入删除操做须要考虑 |
| deque | 典型的序列容器，C++标准严格要求次容器的实现内存必须是连续的，惟一能够和标准C兼容的stl容器，任意元素的读取、修改具备常数时间复杂度，在序列尾部进行插入、删除是常数时间复杂度，但在序列的头部插入、删除的时间复杂度是O(n)，能够 在任何位置插入新元素，有随机访问功能，插入删除操做须要考虑 |
| list | 典型的序列容器，C++标准严格要求次容器的实现内存必须是连续的，惟一能够和标准C兼容的stl容器，任意元素的读取、修改具备常数时间复杂度，在序列尾部进行插入、删除是常数时间复杂度，但在序列的头部插入、删除的时间复杂度是O(n)，能够 在任何位置插入新元素，有随机访问功能，插入删除操做须要考虑 |
| set | 关联容器，元素不容许有重复，数据被组织成一棵红黑树，查找的速度很是快，时间复杂度是O(logN) |
| multiset | 关联容器，和set同样，却别是容许有重复的元素，具有时间复杂度O(logN)查找功能。 |
| map | 关联容器，按照{键，值}方式组成集合，按照键组织成一棵红黑树，查找的时间复杂度O(logN)，其中键不容许重复 |
| multimap | 和map同样，区别是键能够重复 |
C++支持状况
总结
1） 若是须要随机访问，用vector
2） 若是存储元素的数目已知，用vector
3） 须要任意位置随机插入删除，用list
4） 只有须要更多在容器的首部尾部插入删除元素，用deque
5） 元素是复杂结构用list，也能够用vector存储指针(须要额外的精力去维护内存)，看需求
6） 若是操做是基于键值，用set map
7） 若是须要常常的搜索，用map set
8） map set 的区别是map中的元素都是pair
本文章参考STL容器的适用状况，对该文章进行了补充，但愿可以帮助到读者。