包括栈/队列/优先队列这样的数据结构, 提供顺序容器的不同接口(也就是说基于顺序容器构建). 这三种数据结构分别对应于 std::stack  std::queue  std::priority_queue .

和手写栈/队列相比有自动管理内存的优势. 优先队列基本上就拿来当堆用了w

容器适配器都基于顺序容器作为底层容器, 所以各种操作的时间复杂度与底层容器的对应操作相等. 以下未特殊说明的时间复杂度均为底层容器默认时的时间复杂度

 std::stack 和 std::queue 默认使用 std::deque 作为底层容器. 而 std::priority_queue 则默认使用 std::vector 作为底层容器.

然而这三类容器适配器都丧心病狂地不支持 clear (清空操作) 

2.1.4.1 std::stack

字面意思, 就是个栈. 除了各种基本操作外还非常"良心"地支持了两个栈之间的赋值操作=w=. 

话不多说, 直接上成员好了w

1. std::stack::top  $O(1)$

用于访问栈顶元素. 返回的是引用所以理论上也可以用于修改栈顶元素.

2. std::stack::empty  $O(1)$

STL容器常见用法, 返回该栈是否为空.

3. std::stack::size  $O(1)$

STL容器常见用法, 返回该栈中所存储的元素个数.

4. std::stack::push  $O(1)$

将一个作为参数的值压入栈顶.

5. std::stack::pop  $O(1)$

将栈顶元素弹出(不返回栈顶元素的值)

6. std::stack::swap  与交换底层容器一致, 当容器是 std::array 时 $O(n)$, 否则 $O(1)$

将该stack中的内容与另一个stack交换.

7.六种大小比较运算符( != == > >= < <= ) $O(n)$

按照字典序比较两个栈中的内容

2.1.4.2 std::queue

字面意思, 就是个队列. 同样除了push/pop这些基本操作外"良心"地支持了两个queue间的赋值与字典序比较.

1. std::queue::front  $O(1)$

访问队首元素. 返回引用, 一般也可用于修改.

2. std::queue::back  $O(1)$

访问队尾元素(这次也不是左闭右开), 日常引用.

3. std::queue::empty  $O(1)$

熟悉的操作, 判定队列是否为空.

4. std::queue::size  $O(1)$

依然是熟悉的操作, 返回队列中元素的个数.

5. std::queue::push  $O(1)$

向队尾插入一个元素.

6. std::queue::pop  $O(1)$

删除队首元素(不返回队首的元素值)

7. std::queue::swap  <同stack> (博主懒癌再次发作)

交换两个队列中的所有信息.

8.六种大小比较运算符 != == > >= < <=  $O(n)$

按字典序比较两个队列中的信息.

2.1.4.3 std::priority_queue

字面意思, 优先队列. OI里一般当做一个封装好的堆来用. 模板参数按顺序是:元素类型/底层容器类型(默认std::vector<T>)/比较方式 , 在这时可以自定义比较函数, 但是要先指定底层容器w. 对于如何扩展它的功能请看最下面的STL使用技巧. (突然发现优先队列原生滋磁的操作是容器适配器里最少的OwO)

1. std::priority_queue::top  $O(1)$

访问堆顶元素(优先队列默认为大端堆, 即最大的元素在队首), 不过要注意是top不是front...

2. std::priority_queue::empty  $O(1)$

熟悉操作++, 判断队列是否为空.

3. std::priority_queue::size  $O(1)$

返回队列中的元素数量.

4. std::priority_queue::push  $O(nlog(n))$

将一个值插入优先队列中.

5. std::priority_queue::pop  $O(nlog(n))$

将优先队列队首元素弹出(同样不返回队首元素的值/迭代器)

6. std::priority_queue::swap  <同stack>

交换两个优先队列中的信息.

 

2.2 迭代器

迭代器是用于指向容器中的数据的类, (虽然平常的操作似乎和指针没啥区别, 也支持 operator* 和 operator-> w) 不同的容器根据其内部结构与实现原理的不同也会提供功能不同的迭代器. 迭代器有五种类型(C++17标准及以后是六种, 增加了一个连续迭代器的概念), 分别是输入迭代器 输出迭代器 向前迭代器 双向迭代器 随机访问迭代器. 这些迭代器按照支持的操作的不同来分类.

STL中某种容器对应的迭代器类型可以直接在容器类型名(带有模板参数)后加 ::iterator 来使用. 比如对于 std::set<int> , 则对应的迭代器类型名为 std::set<int>::iterator .

同时满足输出迭代器和四种迭代器之一二者的定义的迭代器也被称为可变迭代器. 不满足输出迭代器定义的也被称为不可变迭代器或常迭代器.

似乎可以认为迭代器是个容器中专用的指针...?

毕竟容器中的存储结构不一定连续, 所以当指针的位置发生移动时实际的下一个元素所在的内存可能并非刚好在上一个元素之后, 而是经过一定的算法计算出来的. 这也就造成普通指针在容器中无法使用. 这时我们可以选择使用运算符重载特性来在偏移迭代器时执行对应的算法, 保证指向内存的合法性.

注:迭代器都可以支持形如这样的操作:  *it  ++it 

至于分类可以理解为不同类型的迭代器一般有不同的定位自由度. 下面我们从限制最多的一直到最自由的开始说.

2.2.1 输入迭代器