一、序列式容器vector、list、deque

vector

• vector的底层实现：vector在底层使用一个数组实现的

• 特点：
  • 因为vector使用数组实现的，因此元素是保存在连续的内存中的，所以通过索引取值的速度非常快
  • 因为是连续存储，所以在中间进行元素的增加或者删除非常耗时，可能伴随着移动元素以及内存重分配
  • 内存重分配之后，vector原来的指针、引用、迭代器都会失效，因为元素的地址改变了
• 一般没有特殊要求时，都需要vector
• 更多细节参阅vector源码剖析：https://blog.****.net/qq_41453285/article/details/103565158

list

• list的底层实现：list在底层使用一个双向的环形链表实现的

• 特点：
  • 因为list是使用链表实现的，所以在任意位置进行增加或者删除速度都比较快（指针的交换）
  • 另外，由于其不像vector一样拥有的连续的内存空间，不支持索引访问，所以查找的速度比较慢，因为需要遍历链表
  • 另外，它额外开销比较大，因为链表的节点需要存储指针
  • 无论是增加还是删除元素，其迭代器、指针、引用都不会失效，因为元素的地址没有改变
• 当需要频繁的对元素进行增加或者删除时，list是比较好的选择
• 更多细节参阅list源码剖析：https://blog.****.net/qq_41453285/article/details/103565158

deque

• deque的底层实现：
  • deque在底层是由多个(多段)vector组成的
  • 如下图所示，右边的缓冲区就是deque实际存储数据的地方，每一个缓冲区都是一个数组；然后使用map（STL中称为中控器）来保存每一个数组的指针
  • 当我们操作deque时就是通过找到map指针，然后找到对应的缓冲区，然后对元素进行操作的

• 特点：
  • deque支持在头部和尾部进行增删元素（如下图所示），所以在头部和尾部删除和增加元素的速度非常快
  • 因为其底层也是vector实现的，因此也支持索引取值
  • 对内存有限制的系统中，deque比vector可以包含更多元素，因为它不止使用一块内存
  • 存取元素的时候，deque的内部结构会多出一个间接过程，相比vector操作会慢一些
• 当需要在两端频繁的对元素进行增加或者删除时，deque是比较好的选择

• 更多细节参阅deque源码剖析：https://blog.****.net/qq_41453285/article/details/103614247

二、容器适配器stack、queue

• stack和queue其实内部都是调用上面封装好的vector、list、deque等结构来实现的
• stack和queue在内部调用vector、list、deque等它们提供好的方法来实现各种操作

stack

• deque的底层实现：在内部默认以deque实现stack。因为deque是双向开口的数据结构，所以只要封闭其头端开口既可以形式一个stack

• 特点：
  • stack是一种栈结构
  • stack允许新增元素、移除元素、取得最顶端元素。但除了最顶端外，没有任何其他方法可以存取stack的其他元素。换言之stack不允许有遍历行为
  • 将元素推入stack的动作称为push，将元素推出stack的动作称为pop
•  
• 更多细节参阅stack源码剖析：https://blog.****.net/qq_41453285/article/details/103631022

queue

• queue的底层实现：在内部默认以deque实现queue。因为deque是双向开口的数据结构，所以只要封闭其底端的出口和前端的入口就可以形成一个queue​​​​​​​

• 特点：
  • queue是一种队列结构
  • queue允许新增元素、移除元素、从最底端加入元素、取得最顶端元素
  • 但除了最底端可以加入、最顶端可以取出外，没有任何其他方法可以存取queue的其他元素。换言之queue不允许有遍历行为
  • 将元素推入queue的动作称为push，将元素推出 queue的动作称为pop
• 更多细节参阅queue源码剖析：https://blog.****.net/qq_41453285/article/details/103631323