std::deque , 定义于头文件 <deque> , 相当于一个普通的双端队列. 但是与  std::queue 不同的是, 它不仅仅可以访问两端的元素, 内部的元素也可以访问与修改. 而与 std::vector 的不同之处在于, deque内部的存储是不连续的. 这给了deque在两端插入/删除元素时的严格 $O(1)$ 时间复杂度. 但是非连续的存储结构也使得deque中的随机访问与插入删除的复杂度猛增至 $O(n)$ . 所以deque在OI中基本上只是用于作为 std::queue 的一个扩充(毕竟这个可以在不弹出所有元素的情况下遍历内部的元素而且两端都可以插入/删除).

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

返回deque首部元素的引用, 用于对首部元素进行修改/读取. 同vector.

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

返回尾部元素的引用, 同vector.

3. std::deque::operator[]  $O(n)$

(港真一直以为deque和queue很像的我第一次看见这个操作表示震惊) 按下标访问元素, 返回引用, 同vector.

(实际上deque也支持通过 std::deque::at 来访问内部元素, 复杂度 $O(n)$, 用法和特性同vector)

4. std::deque::begin  $O(1)$

返回指向首部元素的迭代器, 同vector.

5. std::deque::end  $O(1)$

返回指向尾部元素后一个元素的迭代器. 同vector.

6. std::deque::rbegin  $O(1)$

(博主突然发现到目前为止一直都和vector一样诶...)

(突然懒癌发作) 同vector.

7. std::deque::insert  $O(n)$

插入若干值. 第一个参数为下标, 可以是代表下标的整数也可以是迭代器. 后面的参数是要插入的信息. 可以是一个值, 也可以是一个区间.

(vector其实也支持, 复杂度一样)

8. std::deque::erase  $O(n)$

删除若干值. 可以通过一对下标/迭代器指定区间, 也可以通过一个下标/迭代器和长度来指定一个区间.

(vector其实也支持, 复杂度也是一样=w=但是估计并没人用)

9. std::deque::push_back  $O(1)$

在尾部插入一个值. 同vector

10. std::deque::push_front  $O(1)$

在首部插入一个值. 同vector.

11. std::deque::pop_front  $O(1)$

删除首部的值. 同vector.

12. std::deque::pop_back  $O(1)$

删除尾部的值. 同vector.

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

按字典序比较两个deque的内容或者判断二者中的数据是否相同.

2.1.2 关联容器

关联容器的内部实现一般都是一个平衡树. 可以实现 $O(log(n))$ 时间复杂度的查找操作. 包括 std::set  std::map  std::multiset  std::multimap . 其中前面两个容器自带去重buff, 后面的是给那些可能有重复元素或者要计数的应用场所设计的.

关联容器的组合有时候可以得到非常强的效果. 毕竟内部有一个封装好的平衡树(

 std::set / std::map 分别和 std::multiset / std::multimap 对应, 支持的操作完全相同, 只是内部存储时的区别而已. 故省略multiset和multimap (懒癌再次发作)

2.1.2.1 std::set

STL提供的集合容器. 具有自动去重/自动排序等buff性质, 内部实现为平衡树所以可以拿来当树套树的次级树来偷懒(雾), 自动去重与排序后的结果可以使用迭代器在 $O(nlog(n))$ 的总时间复杂度内遍历. 配合迭代器与算法库食用可滋磁的操作还有查前驱/后继/K大等等操作.

常见操作如下:

1. std::set::begin  $O(1)$

返回指向首部元素的迭代器. 与多数STL容器相同.

2. std::set::end  $O(1)$

返回指向尾部元素的下一个元素的迭代器. STL日常左闭右开区间.

3. std::set::rbegin  $O(1)$

返回指向翻转后的区间的首部元素的迭代器. 可以用于快速访问尾部元素.

4. std::set::empty  $O(1)$

返回set是否为空

5. std::set::size  $O(1)$

返回set中的元素个数.

6. std::set::clear  $O(n)$

清空set中的数据.

7. std::set::insert  插入一个值为$O(log(n))$, 传入位置参考迭代器且位置参考有效则为均摊 $O(1)$ , 插入区间为 $O(dis*log(dis+n))$ (dis为区间长度)

向set中插入数据. 可以是一个值或者一个区间. 对于插入一个值还可以传入一个位置参考迭代器. 若插入刚好发生在位置参考迭代器的左侧或右侧则可以将复杂度优化至均摊 $O(1)$. 

8. std::set::erase  删除指定值为$O(log(n))$ , 删除指定迭代器指向的结点为均摊 $O(1)$ , 删除区间为 $O(log(n)+dis)$ (dis为区间长度)