算法笔记的笔记——第6章 C++标准模板库（STL）

vector

• 变长数组
• 长度根据需要而自动改变的数组
• 可以用来以邻接表的方式储存图

使用

• 头文件：#include <vector>
• 命名空间：using namespace std;

定义

vector<typename> name;

相当于一维数组name[SIZE]，但长度可变。typename可以为任何类型，例如int、double、char、结构体登，也可以是STL标准容器，如vector、set、queue等。如果typename也是一个STL容器，定义时要在>>中间加上空格。

vector<int> name;
vector<double> name;
vector<char> name;
vector<node> name;	// node是结构体类型
vector<vector<int> > name;	// >>之间要加空格

容器内元素的访问

• 通过下标访问：vi[index]

• 通过迭代器访问：

  迭代器类似指针，定义为vector<typename>::iterator it;

  把迭代器指向开头：it = vi.begin()

  用迭代器访问值：*(it + i)

  vi[i]和*(vi.begin() + i)是等价的。

  尾元素地址的下一个地址：vi.end()

  iterator还有自加操作：it++、++it

  只有在vector和string中才允许使用vi.begin()+i这种迭代器加整数的写法。

常用函数

• push_back(x)：在vector后面添加一个元素
• pop_back()：删除vector的尾元素
• size()：获得vector中元素的个数
• clear()：清空vector中的所有元素
• insert(it, x)：向vector的任意迭代器it处插入一个元素x
• erase(it)：删除it处的元素
• erase(first, last)：删除[first, last)内的所有元素

set

• 集合
• 内部自动递增排序且不含重复元素

使用

• 头文件：#include <set>
• 命名空间：using namespace std;

定义

set<typename> name;

和vector写法类似

set<int> name;
set<double> name;
set<char> name;
set<node> name;
set<set<int> > name;

容器内元素的访问

只能通过迭代器访问：set<typename>::iterator it;

可以通过*it访问set里的元素。不能使用*(it + i)。

for (set<int>::iterator it = st.begin(); it != st.end(); it++) {
    ...
}

常用函数

• insert(x)：将元素插入set容器中
• find(value)：返回set中对应值为value的迭代器
• erase(it)：要删除的元素的迭代器
• erase(value)：要删除元素的值
• erase(first, last)：first为要删除区间的起始迭代器，last为要删除区间的末尾迭代器的下一个地址
• size()：获得set内元素的个数
• clear()：清空set中的所有元素

延伸

• 元素不唯一用multiset
• 不排序用unordered_set

string

使用

• 头文件：#include <string>
• 命名空间：using namespace std;

定义

string str = "abcd";

内容访问

• 通过下标访问（和字符数组类似）
• 如果要读入和输出整个字符串，只能用cin和cout；或者用str.c_str()将string类型转换为字符数组
• 通过迭代器访问：和vector一样

常用函数

• +=：string的加法，可以直接把两个string拼接起来
• ==、!=、<、<=、>、>=：两个string可以直接比较大小，规则是字典序
• length()、size()：返回字符串的长度
• insert(pos, string)：在pos位置处插入字符串string
• insert(it, it2, it3)：it为原字符串欲插入的位置，it2和it3为待插字符串首尾迭代器（左闭右开区间）
• erase(it)：删除单个元素，it为要删除元素的迭代器
• erase(first, last)：删除区间内元素，first和last为首尾迭代器（左闭右开区间）
• erase(pos, length)：pos为要删除的起始位置，length为要删除的字符个数
• clear()：清空string中的数据
• substr(pos, len)：返回从pos开始、长度为len的子串
• string::npos：常数-1
• find(str2)：返回str2在str中的位置，如果没找到返回-1
• find(str2, pos)：从pos开始找str2
• replace(pos, len, str2)：把str从pos位置开始、长度为len的子串替换为str2
• replace(it1, it2, str2)：把迭代器[it1, it2)范围的子串替换为str2

map

• 将任何基本类型（包括STL）映射到任何基本类型（包括STL）
• 会以键的顺序从小到大自动排序

使用

• 头文件：#include <map>
• 命名空间：using namespace std;

定义

map<typename1, typename2> mp;

typename1是键的类型，typename2是键值的类型。键是唯一的。

字符串必须使用string，不能使用字符串数组。

内容访问

• 通过下标访问，map[key]

• 通过迭代器访问

  it->first访问键，it->second访问值

常用函数

• find(key)：返回键为key的映射的迭代器
• erase(it)：删除迭代器处的元素
• erase(key)：删除键处的元素
• erase(first, last)：删除[first, last)的元素，first和last是迭代器
• size()：获取映射的对数
• clear()：清空map中的所有元素

延伸

• 一个键对应多个值用multimap
• 不排序用unordered_map（C++11）

queue

• 先进先出的队列

使用

• 头文件：#include <queue>
• 命名空间：using namespace std;

定义

queue<typename> name;

内容访问

用front()访问队首元素，用back()访问队尾元素。

常用函数

• push(x)：将元素x入队
• front()：队首元素
• back()：队尾元素
• pop()：令队首元素出队
• empty()：检测队列是否为空
• size()：返回元素个数

注意：使用front()和pop()之前，必须用empty()判断队列是否为空。

priority_queue

• 优先队列
• 底层用堆（heap）实现
• 队首元素是当前队列中优先级最高的

用法

• 头文件：#include <queue>
• 命名空间：using namespace std;

定义

priority_queue<typename> name;

元素访问

• top()：访问队首（堆顶）元素

常用函数

• push(x)：将元素x入队
• top()：获得队首（堆顶）元素
• pop()：令队首（堆顶）元素出队
• empty()：检测队列是否为空
• size()：返回队列内的元素个数

优先级设置

• 基本数据类型

  数字大的优先级越高，队首元素就是优先队列内元素最大的。

  priority_queue<int> q;
  priority_queue<int, vector<int>, less<int> > q;
  

  对基本数据类型来说，这两种定义是等价的。vector<int>写的是承载底层数据结构堆的容器，less<int>是对第一个参数的比较类，表示数字大的优先级大，greater<int>表示数字小的优先级大。

• 结构体类型

  重载运算符“<”（不能重载“>”，会编译错误）

  struct fruit {
      string name;
      int price;
      friend bool operator < (fruit f1, fruit f2) {
          return f1.price < f2.price;
      }
  }
  

注意：使用top()前必须用empty()判断优先队列是否为空。

stack

使用

• 头文件：#include <stack>
• 命名空间：using namespace std;

定义

stack<typename> name;

容器内元素访问

只能用top()访问栈顶元素。

常用函数

• push(x)：将元素x入栈
• top()：获得栈顶元素
• pop()：弹出栈顶元素
• empty()：检测栈是否为空
• size()：返回栈内元素个数

pair

用处不大，略

algorithm头文件常用函数

• 因为是C++的东西所以要加using namespace std;才能用

max()

max(x, y)返回x和y中的最大值，如果要返回三个数的最大值可以用max(x, max(y, z))的写法。

min()

min(x, y)返回x和y中的最小值。

abs()

abs(x)返回整数x的绝对值。如果要浮点数的绝对值，需要用math头文件下的fabs()。

swap()

swap(x, y)交换x和y的值。

reverse()

reverse(it, it2)将数组指针或迭代器[it, it2)内的元素进行反转。

next_permutation()

next_premutation(it, it2)给出一个序列在全排列中的下一个序列。如果有下一个序列返回true，否则返回false。在原数组上操作，范围为[it, it2)。

fill()

fill(it, it2)将数组或某容器的某一段区间内赋某个相同的值。可以是数组类型中对应范围内的任意值。

sort()

在第4章中已经说过。

lower_bound()和upper_bound()

• 用在有序数组或容器中
• lower_bound(first, last, val)：在[first, last)中寻找第一个值大于等于val的元素的位置，如果是数组返回指针，如果是容器返回迭代器
• upper_bound(first, last, val)：在[first, last)中寻找第一个值大于val的元素的位置，如果是数组返回指针，如果是容器返回迭代器
• 如果找不到元素，则返回可以插入该元素的位置的指针或迭代器

总结

元素访问

常用函数

本栏目推荐文章
• 2024/1/13 算法笔记
• Python学习笔记
• 类模板实现简单的数组
• HDP 笔记
• Openharmony 跑 CV 算法
• .NET中的加密算法总结(自定义加密Helper类续)
• 学习进度笔记2
• 微软企业库Unity学习笔记(一)
• 微软企业库Unity学习笔记(二)
• 算法练习题

笔记 算法 模板 标准 STL笔记 算法 模板 标准 模板 标准stl 容器 模板 标准stl 模板 标准stl gp 算法 模板 常用 标准 标准stl 模板stl 里程碑 标准stl 标准 方法gdb stl 模板 标准