顺序容器

顺序容器主要有以下的几种

• vector 可变长度数组
• deque 双端队列
• list 双向链表
• forward_list 单向链表
• array 固定大小数组
• string 字符串容器

数据结构中最常用的数组，链表和队列，这里都提供了相应的容器，他们符合本身数据结构的特征

比如说：

• vector/string 他们能够快速的随机访问，在尾部插入/删除都很快，但是在其他部分插入和删除会有效率问题
• deque 支持快速随机访问，在头尾部插入/删除很快
• list/forward_list 在任意位置插入/删除都很快，但是随机访问会比较慢

迭代器

为了在不同的容器间定义普适的遍历访问操作，迭代器被发明了出来。在容器的起始和终点的下一个位置，定义了

• begin()
• end()
• cbegin()
• cend()
• rbegin()
• rend()
  两个操作

容器的基本操作

顺序容器有一些相同的基本操作。如下所示：

• insert 插入
• emplace 以init的形式插入
• erase 删除
• clear 清空
• size 大小
• empty 判空
• swap 交换元素
• operator 基本运算符

顺序容器的操作

添加元素

• push_back(t)
• emplace_back(args)
• push_front(t)
• emplace_front(args)
• insert
• emplace

其中只有能有前向操作的deque/list才有push_front/emplace_front操作

而insert和emplace操作都是基于迭代器的

• insert(p, t)
• emplace(p, args)
• insert(p, n, t)
• insert(p , b, e)
• insert(p, i1)

insert的返回值是指向新插入的第一个元素的迭代器

删除元素

• pop_back
• pop_front
• erase
• clear

需要注意的点是

• pop_back/pop_front的返回值是void
• pop_front不支持vector/string
• erase返回值是指向被删除元素后面的元素的迭代器
• erase操作的是迭代器，支持删除单个元素以及一段范围内的元素
  • erase(p)
  • erase(b, e)

容器操作可能会导致迭代器失效

因此永远不要保存end()

适配器

什么是容器适配器。本质上就是我们除了数组/链表这些基础的数据结构，我们还需要栈/优先队列等数据结构，这些数据结构本质上也是基于数组/链表的，因此我们称之为容器适配器。主要有以下的三种：

• stack
• queue
• priority_queue

因为他们是容器的适配器，因此他们具有容器的基本操作，如下所示：

• empty
• size
• swap
• operator

然而他们也有自己的特殊的操作

stack

• pop
• push
• emplace
• top

queue/priority_queue

• pop
• front
• back
• top
• push
• emplace

适配器的定义

默认情况下，stack和queue是由deque实现的，priority_queue是由vector实现的

因此我们可以如下的对是适配器进行定义

stack<int> s;
priority_queue<int> pq;

如果需要修改底层实现，可以添加第二个参数，如下所示；

stack<int, vector<int>> s;

对于优先队列，如果我们要修改默认的排序方式，则需要引入第三个参数，如下所示：

priority_queue<int, vector<int>， greater<int> > pq;