STL——c++偷懒妙招

dingziyang888 · 2025-11-24 15:04:42 · 算法·理论

更新日志

• 2025/9/19 14:30 更新至 vector
• 2025/9/19 16:30 更新至 queue
• 2025/9/19 19:25 更新至 daaeque
• 2025/9/19 22:05 更新至 priority_queue 并修改了部分内容
• 2025/9/20 21:51 更新至 set
• 2025/9/22 22:25 更新至 map 并修改了部分内容

  前言

  在写数据结构的时候，大部分的插入删除写起来都十分复杂，那么今天蒟蒻就来讲一讲 STL 的部分容器。

iterator

简介

iterator 是 STL 中的首要内容，意为“迭代器”，建立一个 iterator 可以遍历一个支持遍历的 STL 容器，它就像一个指针，访问当前的元素时像指针一样在前面加星号就可以了。
特别地，

• 对于 map，访问键值用 it->first，访问具体值时用 it->second。
• 对于以结构体为元素的容器，访问元素 a 用 it->a 即可
  定义方法：

  vector <int>::iterator it;

  也可以：

  auto it;

  实例

  以遍历一个 vector <int> v 为例：

  for (vector <int>::iterator it = v.begin(); it != v.end(); it++)
  printf("%d\n", *it);

  也可以

  for (auto it = v.begin(); it != v.end(); it++)
  printf("%d\n", *it);

  vector

  简介

  平时我们开数组，最多大小只能开到 INT_MAX（int 数组），而 vector 就能解决空间的问题，可以在添加元素的时候动态地增加数组大小。
  访第 i 个元素时，和数组一样，用 [] 访问即可。
  定义方法

  vector <类型名> 变量名;

  函数

  以下是一些常用函数：

• front()：返回对第一个元素的引用；
• back()：返回对最后一个元素的引用；
• clear()：清空 vector；
• empty()：判断是否为空；
• begin()：返回一个迭代器，指向第一个元素；
• end()：返回一个迭代器，指向最后一个元素的下一个位置；
• rbegin()：返回逆向一个迭代器，指向最后一个元素；
• rend()：返回逆向一个迭代器，指第一个元素的前一个位置；
• pop_back()：删除 vector 的最后一个元素；
• push_back(value)：将 value 放到 vector 的最后；
• size()：返回 vector 中元素的个数；
• erase(it)：删除 it 迭代器指向的位置，返回下一元素迭代器；
• erase(first,last)：删除 [first,last) 区间内的元素，返回 last 迭代器；
• insert(it,value)：将 value 插入迭代器 it 指向的位置，并返回其迭代器；
• insert(it,num,value)：将 num 个 value 插入迭代器 it 指向的位置；
• insert(it,first,last)：将区间 [first,last) 内的元素插入迭代器 it 指向的位置。

  实例

  一个 vector 的应用：P2853 Cow Picnic，有兴趣的读者可以自行尝试。

stack

简介

数据结构——栈，一般方法是用数组模拟，top 表示栈顶，而 stack 可以帮我们实现。
定义方法：

stack <类型名> 变量名;

函数

下面是一些常用函数：

• empty()：判断是否为空；
• pop()：移除栈顶元素；
• push(value)：value 入栈；
• size()：返回栈中元素个数；
• top()：引用栈顶元素。

  实例

  经典应用：P1449 后缀表达式；
  拓展：P1175，P10473。

queue

简介

我们在广搜（广度优先搜索，breadth first search，简称 bfs）中需要用数据结构——队列来实现，队列一般用数组模拟， hd 指向队头，tl 指向队尾，而 queue 也可以帮我们实现。
定义方法：

queue <类型名> 变量名;

函数

下面是一些常用函数：

• empty()：判断是否为空；
• pop()：移除队首元素；
• push(value)：value 从队尾入队；
• size()：返回队列中元素个数；
• front()：返回队首元素的引用；
• back()：返回队尾元素的引用。

  实例

  广搜题都可以用 queue 来实现，例如 P1135 奇怪的电梯；

  deque

  简介

  上面我们介绍了 queue，是一个单端队列，而 deque 是一个双端队列，功能更加强大。
  定义方法：

  deque <类型名> 变量名;

  函数

  下面是一些常用函数：

• front()：返回第一个元素的引用；
• back()：返回最后一个元素的引用；
• begin()：返回指向第一个元素的迭代器；
• end()：返回指向最后一个元素下一个位置的迭代器；
• rbegin()：返回指向后一个元素的逆向迭代器；
• rend()：返回指向第一个元素前一个位置的逆向迭代器；
• empty()：判断队列是否为空；
• size()：返回 deque 中的元素个数；
• clear()：清空 deque 中的所有元素；
• insert(it, value)：在迭代器 it 指向的位置插入 value；
• erase(it)：删除迭代器 it 指向的元素；
• push_back(value)：在 deque 末尾添加元素 value；
• pop_back()：移除 deque 末尾的元素；
• push_front(value)：在 deque 前端添加元素 value；
• pop_front()：删除 deque 前端的元素；
• resize(conut)：重新构造一个长度为 count 的 deque，多出部分用默认值填充。

  实例

  有一些用 queue 的题可以用 deque 来优化，有兴趣的读者可以自行尝试。

priority_queue

简介

priority_queue 被称为优先队列，可以实现堆结构。
定义格式：

priority_queue <类型名> 变量名;

priority_queue 默认是大根堆，而小根堆的定义格式为：

priority_queue <int, vector<int>, greater<int> >a;

如果用结构体 node 来作为堆的元素，则要重载运算符，例如：

struct node{
    int a, b;
    bool operator<(const node&X)const{
        if (a != X.a)
            return a < X.a;
        return b < X.b;
    }
};

函数

以下是一些常用函数：

• empty()：判断是否为空；
• pop()：移除优先级最高的元素；
• push(value)：value 入队；
• size()：返回 priority_queue 中元素个数；
• top()：返回优先级最高元素的引用；

  实例

  一个简单的应用：P1090 合并果子。

  set

  简介

  在数学中，集合指没有重复元素的集，而 STL 中的 set 可以帮我们实现这一内容，定义方法：

  set <类型名> 变量名:

  函数

  下面是一些常用函数：

• begin()：返回一个迭代器，指向第一个元素；
• end()：返回一个迭代器，指向最后一个元素的下一个位置；
• insert(value)：value 插入 set；
• find(value)：在 set 中查找 value，找到指向 value 的迭代器，否则返回 end()；
• erase(it)：删除迭代器 it 指向的位置；
• erase(value)：删除 value；
• erase(first,last)：删除 [first,last) 内的元素；
• empty()：判断是否为空；
• size()；返回 set 中元素个数；
• clear()：清空 set 中的所有元素；
• lower_bound(value)：返回一个迭代器，指向第一个 \ge value 的元素所在位置；
• upper_bound(value)：返回一个迭代器，指向第一个 > value 的元素所在位置。

  实例

  一个应用：P2234 营业额统计，有兴趣的读者可以自行尝试。

  拓展

  set 指的是没有重复元素的集合，而可重集则需要用 multiset 来实现，除了上面有的函数，multiset 还有一个函数： count(value)：返回值为 value 的元素个数。

  map

  简介

  map 被称为映射，它的功能与 set 十分相似，区别在于 map 操作的对象不是单个，而是对组 pair。简单来说，就是操作一个包含两个元素的结构体，第一个元素称为 first（表示键值 key），第二个元素称为 second（表示值 value），描述从 key 到 value 的一个映射。事实上，set 也可以看作是 key 与 value 相等的一个映射。
  定义方法：

  map <类型名，类型名> 变量名;

  函数

  下面是一些常用函数：

• begin()：返回一个迭代器指向第一个元素；
• end()：返回一个迭代器指向最后一个元素的下一个位置；
• insert(pair)：pair 插入 map；
• find(x)：map 中查找 key 为 x 的元素，找到返回指向 x 的迭代器，否则返回 end()；
• erase(it)：删除迭代器 it 指向的位置；
• erase(x)：删除键值 key 为 x 的元素；
• erase(first,last)：删除键值在区间 [first,last) 内的元素；
• empty()：判断是否为空；
• size()：返回 map 中元素个数；
• clear()：清空 map 中所有元素；
• lower_bound()：返回一个迭代器，指向第一个键值 key \ge x 的元素所在位置；
• upper_bound()：返回一个迭代器，指向第一个键值 key>x 的元素所在位置。

  实例

  map 的适用范围很广，很多桶排序都可以用 map 实现，包括很多统计的题，有兴趣的读者可以自行尝试。

  后记

  实在不知道写什么