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()：清空容器。

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

image-20241210081117939

priority_queue<int, vector<int>, greater<int>> 解析

  1. priority_queue<int>:
    • priority_queue 是 C++ STL（标准模板库）中的一个容器适配器，用于实现优先队列。
    • 优先队列是一个特殊的队列，元素总是按优先级顺序被访问，优先级高的元素总是先被取出。
    • 默认情况下，priority_queue 使用 最大堆（即，优先队列中最优先的元素是当前堆中的最大元素）。
  2. vector<int>:
    • 这部分指定了 priority_queue 内部使用的底层容器。默认情况下，priority_queue 使用一个 vector 来存储元素。
    • vector<int> 表示优先队列会存储 int 类型的元素，并且底层数据结构是一个动态数组（vector）。
  3. greater<int>:
    • greater<int> 是一个函数对象（比较器），它指定了如何比较队列中的元素。
    • greater<int> 表示一个 升序比较器，即它会把 较小的元素优先 放到队列前面。
    • 默认情况下，priority_queue 是一个最大堆，它是通过 less<int>（即大于比较）来实现的，而 greater<int> 则实现了一个最小堆（即小于比较）。这使得 pq 中的元素会按照从小到大的顺序排列。

为什么 std::sort 必须在 std::unique 之前使用？

std::unique 只能去除相邻的重复元素。它不会去除容器中所有不相邻的重复元素。例如，假设容器中有 1, 2, 3, 1, 4, 5, 1，如果在调用 std::unique 之前没有对容器排序，std::unique 将无法去除所有重复元素，因为它只会处理相邻的元素。因此，为了确保所有重复元素都能被去除，必须先对容器进行排序，使得相同的元素排列在一起，然后才能通过 std::unique 去除它们。

a[n]

std::sort(a,a+n);

m = std::unique（a,a+n）-n;

std::cin 输入流 （空格分割）

stringstream 字符串流

begain（），end（）

vector<>

clear() , resize() , push_back() , pop_back() , empty() ， 可重复

set<>

自动排序：默认升序

不可重复

不可修改

insert（），find（），count（）， erase（），empty（）

stack<>

priority_queue<>

push() ,pop() ,top()

queue

push() ,pop() ,front()

ctrl + tab + 上下左右 代替鼠标切换文件

Ctrl + W：一个字符、一个字符串、一行、两行代码逐渐扩选

Alt + Shift + 左键：针对要编辑的部分快速选中多行

std::advance(iter, n);

如果 n 为正数，迭代器会向前移动；如果 n 为负数，迭代器会向后移动。