C++STL

STL 即标准模板库（Standard Template Library），是 C++ 标准库的一部分，里面包含了一些模板化的通用的数据结构和算法。由于其模板化的特点，它能够兼容自定义的数据类型，避免大量的造轮子工作。NOI 和 ICPC 赛事都支持 STL 库的使用，因此合理利用 STL 可以避免编写无用算法，并且充分利用编译器对模板库优化提高效率。

Boost 是除了标准库外，另一个久副盛名的开源 C++ 工具库，其代码具有可移植、高质量、高性能、高可靠性等特点。Boost 中的模块数量非常之大，功能全面，并且拥有完备的跨平台支持，因此被看作 C++ 的准标准库。C++ 标准中的不少特性也都来自于 Boost，如智能指针、元编程、日期和时间等。尽管在 OI 中无法使用 Boost，但是 Boost 中有不少轮子可以用来验证算法或者对拍，如 Boost.Geometry 有 R 树的实现，Boost.Graph 有图的相关算法，Boost.Intrusive 则提供了一套与 STL 容器用法相似的侵入式容器。

STL 容器

img

分类：

1. ==序列式==容器

  • vector(向量)后端可高效增加元素的顺序表.
  • array(数组)，定长的顺序表。
  • deque（双端队列）双端可高效增加元素的顺序表。
  • list（列表）可以沿双向遍历的链表。
  • forward_list（单向列表）只能沿一个方向遍历的链表。

2，==关联式==容器

  • set（集合）有序储存互异元素的容器
    • 不允许重复元素。存储唯一的元素，且自动按升序排序。
    • 元素的插入、删除和查找操作的时间复杂度为O(log n)。
  • multiset(多重集合)允许存储重复的元素，且也会自动按升序排序
    • 允许重复元素。
    • 与set类似，插入、删除和查找操作的时间复杂度同样为O(log n)。
  • map（映射）由{建，值}对组成的集合（也是集合）
    • 唯一性：每个键只能出现一次；如果插入一个已存在的键，则会更新其对应的值。
    • 有序性：map中的元素会根据键自动排序，默认情况下是升序排列。
    • 时间复杂度：插入、删除和查找操作的平均时间复杂度为O(log n)。

3，无序(并联式)容器

  • 无序（多重）集合(unordered_set/unordered_multiset)C++11，与 set/multiset 的区别在于元素无序，只关心「元素是否存在」，使用哈希实现。
    • 唯一性：unordered_set 中的每个元素都是唯一的，不能重复。
    • 无序性：元素的排列是基于哈希值的，不按照任何特定顺序存储。
    • 性能：插入、查找和删除操作的平均时间复杂度为 O(1)，但在最坏情况下可能会退化为 O(n)
  • 无序（多重）映射(unordered_map/unordered_multimap)C++11，与 map/multimap 的区别在于键 (key) 无序，只关心 “键与值的对应关系”，使用哈希实现。

容器适配器

容器适配器其实并不是容器。它们不具有容器的某些特点（如：有迭代器、有 clear() 函数……）。

​ 「适配器是使一种事物的行为类似于另外一种事物行为的一种机制」，适配器对容 器进行包装，使其表现出另外一种行为。

  • 栈(stack) 后进先出 (LIFO) 的容器，默认是对双端队列（deque）的包装。
  • 队列(queue) 先进先出 (FIFO) 的容器，默认是对双端队列（deque）的包装。
  • 优先队列(priority_queue) 元素的次序是由作用于所存储的值对上的某种谓词决定的的一种队列，默认是对向量（vector）的包装。

容器声明

都是 containerName<typeName,...> name 的形式，但模板参数（<> 内的参数）的个数、形式会根据具体容器而变。

本质原因：STL 就是「标准模板库」，所以容器都是模板类。

容器共有函数

= ：赋值运算符，赋值构造函数

begain() :返回指向开头元素的迭代器

end（）：返回指向末尾的下一个元素的迭代器。end() 不指向某个元素.end() 迭代器指向的是一个“哨兵”位置，表示容器的结束。可以用来判断迭代是否完成。

size():返回容器内的元素个数

max_size()：返回容器 理论上 能存储的最大元素个数。依容器类型和所存储变量的类型而变。

empty()：返回容器是否为空。

swap()：交换两个容器。

clear()：清空容器。

==/!=/</>/<=/>=：按 字典序 比较两个容器的大小.无序容器不支持 </>/<=/>=。