说一说STL 中有哪些常见的容器

[问答题]

说一说STL 中有哪些常见的容器

得分点

顺序容器、关联式容器、容器适配器

参考答案

标准回答

STL 中容器分为顺序容器、关联式容器、容器适配器三种类型，三种类型容器特性分别如下：

顺序容器

容器并非排序的，元素的插入位置同元素的值无关，包含 vector、deque、list。
- vector：动态数组
  
  元素在内存连续存放。随机存取任何元素都能在常数时间完成。在尾端增删元素具有较佳的性能。
- deque：双向队列
  
  元素在内存连续存放。随机存取任何元素都能在常数时间完成（仅次于 vector ）。在两端增删元素具有较佳的性能（大部分情况下是常数时间）。
- list：双向链表
  
  元素在内存不连续存放。在任何位置增删元素都能在常数时间完成。不支持随机存取。
关联式容器

元素是排序的；插入任何元素，都按相应的排序规则来确定其位置；在查找时具有非常好的性能；通常以平衡二叉树的方式实现，包含set、multiset、map、multimap。
- set/multiset
  
  set中不允许相同元素，multiset 中允许存在相同元素。
- map/multimap
  
  map 与 set 的不同在于 map 中存放的元素有且仅有两个成员变，一个名为 first，另一个名为 second，map 根据 first 值对元素从小到大排序，并可快速地根据 first 来检索元素。map 和multimap 的不同在于是否允许相同 first 值的元素。
容器适配器

封装了一些基本的容器，使之具备了新的函数功能，包含 stack、queue、priority_queue。
- stack：栈
  
  栈是项的有限序列，并满足序列中被删除、检索和修改的项只能是最进插入序列的项（栈顶的项），后进先出。
- queue：队列
  
  插入只可以在尾部进行，删除、检索和修改只允许从头部进行，先进先出。
- priority_queue：优先级队列
  
  内部维持某种有序，然后确保优先级最高的元素总是位于头部，最高优先级元素总是第一个出列。