1 sort

STL中的sort并非只是普通的快速排序，除了对普通的快速排序进行优化，它还结合了插入排序和堆排序。根据不同的数量级别以及不同情况，能自动选用合适的排序方法。当数据量较大时采用快速排序，分段递归。一旦分段后的数据量小于某个阀值，为避免递归调用带来过大的额外负荷，便会改用插入排序。而如果递归层次过深，有出现最坏情况的倾向，还会改用堆排序。

2 vector

• 变长一维数组，连续存放的内存块，有保留内存，堆中分配内存；
• 支持[]操作，高效率的随机访问;
• 在最后增加元素时，一般不需要分配内存空间，速度快；在中间或开始操作元素时要进行内存拷贝效率低；

• vector高效的原因在于配置了比其所容纳的元素更多的内存，内存重新配置会花很多时间；

  注：需要高效的随即存取，而不在乎插入和删除使用vector。
  

  3 list

• 双向链表，内存空间上可能是不连续的，无保留内存，堆中分配内存;

• 不支持随机存取，开始和结尾元素的访问时间快,其它元素都O(n)；

• 在任何位置安插和删除元素速度都比较快，安插和删除操作不会使其他元素的各个pointer，reference，iterator失效；

  注：大量的插入和删除，而不关心随即存取使用list。
  

  4 deque

• 双端队列，在堆上分配内存，一个堆保存几个元素，而堆之间使用指针连接；

• 即内存空间分布是小片的连续，小片间用链表相连；
• 所以deque空间的重新分配要比vector快，重新分配空间后，原有的元素是不需要拷贝的。
• 支持[]操作，在首端和末端插入和删除元素比较快，在中部插入和删除则比较慢，像是list和vector的结合；

注：关心插入和删除并关心随即存取折中使用deque。

5 set / multiset

• 有序集合，使用平衡二叉树存储，按照给定的排序规则（默认按less排序）对set中的数据进行排序；
• set中不允许有重复元素，multiset中运行有重复元素；
• 两者不支持直接存取元素的操作；
• 因为是自动排序，查找元素速度比较快；

• 不能直接改变元素值，否则会打乱原本正确的顺序，必须先下删除旧元素，再插入新的元素。

  

6 map / multimap

• 字典库，一个值映射成另一个值，使用平衡二叉树存储，按照给定的排序规则对map中的key值进行排序；
• map中的key值不允许重复，multimap中的key允许重复；
• key值不能改变， 根据已知的key值查找元素比较快；

• 插入和删除操作比较慢。

  

7 hash_map

hash_map使用hash表来排列配对，hash表是使用关键字来计算表位置。当这个表的大小合适，并且计算算法合适的情况下，hash表的算法复杂度为O(1)的，但是这是理想的情况下的，如果hash表的关键字计算与表位置存在冲突，那么最坏的复杂度为O(n)。<br />     选用map还是hash_map，关键是看关键字查询操作次数，以及你所需要保证的是查询总体时间还是单个查询的时间。如果是要很多次操作，要求其整体效率，那么使用hash_map，平均处理时间短。如果是少数次的操作，使用 hash_map可能造成不确定的O(N)，那么使用平均处理时间相对较慢、单次处理时间恒定的map，便更好些。<br />     默认情况下内部数据不排序。

8 各容器对比