学习记录
2026-07-25 15:03:23
发布于：浙江
36阅读
0回复
0点赞
2026/2/24
-
1.map:
-
(1).定义map：
- 导入：
#include <map> - 定义：
map<建的类型，值的类型> 名字;- 如：
map<int,int> m;
- 如：
- 导入：
-
(2). map相关操作：
函数 功能说明 begin()返回一个迭代器，指向map中的第一个键值对。 end()返回一个迭代器，指向map中最后一个键值对的下一个位置。 erase()根据键删除一个键值对。 clear()清空map中的所有键值对 empty()如果map为空则返回true size()返回map中键值对的数量 find()查找一个键是否存在于map中，如果找到了则返回该键对应的迭代器，否则返回map::end() swap()交换两个map rbegin()返回一个指向map尾部的逆向迭代器 rend()返回一个指向map头部的逆向迭代器 count()返回指定元素出现的次数 max_size()返回可以容纳的最大元素个数 insert()插入元素 key_comp()返回比较元素key的函数 value_comp()返回比较元素value的函数 -
(3). map的两种遍历方式：
-
// 方式1：范围for循环遍历
map<string, string> mp1;
for (auto &item : mp1) {
string key = item.first; // 键
string val = item.second; // 值
}
// 方式2：迭代器遍历
map<string, string> mp2;
for (auto it = mp2.begin(); it != mp2.end(); it++) {
cout << it->first << it->second << endl;
}
-
2.set
-
(1).定义set：
- 导入：
#include <set> - 定义：
set<类型> 名字;- 如：
set<int> s;
- 如：
- 导入：
-
(2).set的相关操作
函数 功能说明 begin()返回一个迭代器，指向集合中的第一个元素（ std::set为有序首元素，std::unordered_set为哈希表首个存储元素）。end()返回一个迭代器，指向集合中最后一个元素的下一个位置（尾后迭代器，不可解引用）。 erase()可按值、迭代器或迭代器范围删除集合中的元素，按值删除时返回删除的元素个数（0 或 1）。 clear()清空集合中的所有元素，清空后集合大小为 0。 empty()如果集合为空则返回 true，否则返回false。size()返回集合中当前存储的元素个数。 find()查找指定值的元素，找到则返回该元素的迭代器，未找到则返回 end()。swap()交换两个同类型集合的内容（元素、大小等），效率高。 rbegin()返回指向集合尾部的逆向迭代器（仅 std::set支持，unordered_set无逆向迭代器）。rend()返回指向集合头部的逆向迭代器（仅 std::set支持，unordered_set无逆向迭代器）。count()返回集合中指定值的元素出现次数（集合元素唯一，故返回值为 0 或 1）。 max_size()返回集合理论上可容纳的最大元素个数（受系统内存、编译器限制）。 insert()插入单个元素或元素范围，插入重复元素时会失败，返回 pair<迭代器, bool>标识结果。key_comp()返回用于比较集合元素（键）的比较函数对象（仅 std::set支持，unordered_set无此函数）。value_comp()返回用于比较集合元素（值）的比较函数对象（仅 std::set支持，unordered_set无此函数）。emplace()直接在集合中构造元素（避免拷贝/移动），效率比 insert()更高，返回值同insert()。emplace_hint()结合迭代器提示插入元素（仅 std::set有优化效果），进一步提升插入效率。bucket_count()返回哈希表的桶数量（仅 std::unordered_set支持，std::set无此函数）。 -
2026/2/25
-
1.deque
-
(1).定义deque：
- 导入：
#include <deque> - 定义：
deque<类型> 队列名;- 如：
deque<int> q;
- 如：
- 导入：
-
(2).deque的操作：
-
deque<int> q; //定义双端队列
int x; //一个数字
q.push_front(x); //在队首加入x
q.push_back(x); //在队尾加入x
q.pop_front(); //弹出队首
q.pop_back(); //弹出队尾
q.front(); //获取队首
q.back(); //获取队尾
q.empty(); //检测是否为空 空返回true 不空返回false
q.size(); //获取队列长度
q.clear(); //清空队列
-
2.list
-
(1).定义list：
- 导入：
#include <list> - 定义：
list<类型> 链表名;- 如：
list<int> L;
- 如：
- 导入：
-
-
3.pair
-
(1).定义pair：
- 导入：
#include <utility> - 定义：
pair<类型,类型> 变量名;- 如：
pair<int,int> p;
- 如：
- 导入：
-
2026/6/6
-
1.ST表
-
(1). ST表的数据结构定义：
- 表示左端点为，右端点为，区间长度为的区间最值。递推关系为：
其中表示
- 表示左端点为，右端点为，区间长度为的区间最值。递推关系为：
-
(2). ST表的相关代码：
void ST_create(){ // ST表的创建 for(int i = 1; i <= n; i++) { // 表示[i, i]区间的最值，区间长度为2^0 = 1 F[i][0] = a[i]; } // 下标 j 的取值范围 int k = log2(n); // 先枚举区间的长度 for(int j = 1; j <= k; j++) { // 左端点取值范围是 N - 2^j + 1 for(int i = 1; i <= n - (1 << j) + 1; i++) { F[i][j] = max(F[i][j - 1], F[i + (1 << (j - 1))][j - 1]); } } } int ST_query(int l, int r) { // 求[l, r]区间的最值 int k = log2(r - l + 1); //确定给每个小区间的长度，r-l+1是区间长度 return max(F[l][k], F[r - (1 << k) + 1][k]); //取最大值 }
-
2026/6/13
-
1.线段树
-
(1).如何建树：
// int -> long long void build(int p, int l, int r) { // 根节点 左节点 右节点 // 将左节点和右节点的数据放入p节点下 tree[p].l = l; tree[p].r = r; // 当前是叶子节点，当左节点等同于右节点时，已将到达最后一层 if(l == r) { tree[p].value = arr[l]; // 放入值，放入arr[r]也是一个道理 return ; // 结束，退出之后不执行了 或者写else形式 } // (l + r) >> 1 找出中间值 int mid = (l + r) / 2; build(p * 2, l, mid); // 构建左子树 build(p * 2 + 1, mid + 1, r); // 构建右子树 tree[p].value = tree[p * 2].value + tree[p * 2 + 1].value; // 回溯 } -
(2).单点修改：
// int -> long long void PointUpdate(int p, int x, int z) { // 单点修改 根节点 需要修改的节点 需要修改值 // 找到需要查询的位置 if(tree[p].l == tree[p].r) { // 对于找到的位置进行修改(给x的位置增加) tree[p].value += z; return ; } // 二分范围 int mid = (tree[p].l + tree[p].r) / 2; // 当前节点左右 区划分 if(x <= mid) { // 如果需要修改的左半边范围正好包含 update(p * 2, x, z); } else if(x > mid) { // 如果需要修改的右半边范围正好包含 update(p * 2 + 1, x, z); } tree[p].value = tree[p * 2].value + tree[p * 2 + 1].value; // 回溯 } -
(3).区间查询：
// int -> long long int query(int p, int x, int y) { // 区间查询 根节点 查询区间左 查询区间右 // 需要查询的范围包含了p下标的所有 if(x <= tree[p].l && y >= tree[p].r) { // 范围p下标包含的值 return tree[p].value; } int mid = (tree[p].l + tree[p].r) / 2; // 二分范围 int flag = 0; // 记录总和 if(x <= mid) { // 如果需要修改的范围正好包含 flag += query(p * 2, x, y); // 去左子树取值 } if(y > mid) { // 如果需要修改的范围正好包含 flag += query(p * 2 + 1, x, y); // 去右子树取值 } return flag; }
-
2026/6/20
-
1.线段树
-
(1).懒标记以及区间修改：
struct node { // 使用结构体的形式构建线段树 int l, r, w; // 左节点的起始点 右节点重点(l->r : p节点所包含的范围) 值 int lg; // lazytap 懒惰标记 }; node tree[N]; void lan(int p) { // 懒标记下传 if(tree[p].lg) { // 当前懒标记存在 // 将懒标记传给左右两个节点 tree[p * 2].w = tree[p * 2].w + (tree[p * 2].r - tree[p * 2].l + 1) * tree[p].lg; tree[p * 2 + 1].w = tree[p * 2 + 1].w + (tree[p * 2 + 1].r - tree[p * 2].l + 1) * tree[p].lg; tree[p * 2].lg = tree[p * 2].lg + tree[p].lg; tree[p * 2 + 1].lg = tree[p * 2 + 1].lg + tree[p].lg; tree[p].lg = 0; // 清空上一层的懒标记 已经传输完毕了 } } void ZoneUpdate(int p, int x, int y, int z) { //区间修改 根节点 需要修改的范围 需要修改的值 // 找出要修改的位置 if(x <= tree[p].l && y >= tree[p].r) { tree[p].w += (tree[p].r - tree[p].l + 1) * z; // 对于找到的位置进行修改（给x的位置增加） tree[p].lg += z; // 懒标记也要加 return ; } lan(p); // 懒标记下传 int mid = (tree[p].l + tree[p].r) / 2; // 当前节点左右 去划分 // 查找当前需要找的位置是在左半边还是右半边 if(x <= mid) { ZoneUpdate(p * 2, x, y, z); } if(y > mid) { ZoneUpdate(p * 2 + 1, x, y, z); } tree[p].w = tree[p * 2].w + tree[p * 2 + 1].w; // 回溯 }
-
2026/7/4
-
1.树状数组：
-
(1).lowbit：
- 函数是帮助我们找到二进制表达式中最低位 所对应的值
int lowbit(int x) { return x & (-x); }#define lowbit(x) (x & (-x))
- 函数是帮助我们找到二进制表达式中最低位 所对应的值
-
(2).单点修改：
void update(int x, int val) { // 单点修改 // x -> 要修改的下标 val -> 增加的值 while(x <= n) { c[x] += val; x += lowbit(x); // 由子节点向上更新a数组 } } -
(3).区间求和：
int sum(int x) { // 区间求和(1 到 x) int ans = 0; while(x != 0) { ans += c[x]; x -= lowbit(x); } return ans; }
-
2026/7/4
-
1.字典树
- (1).插入
void insert (string s) { // 插入单词s auto len = strlen(s); //单词长度 int root = 0; // 根结点编号为0 for (int i = 0; i < len; i++) { int id = s[i] - 'a'; // 第二种编号 if (!trie[root][id]) { // 如果之前没有从root到id的前缀 trie[root][id] = ++tot; // 插入 tot即为 } root = trie[root][id]; // 顺着字典树往下走 } } - (2).查找
bool find (string s) { auto len = strlen(s); int root = 0; // 从根节点开始找 for (int i = 0; s[i]; i++) { int x = s[i] - 'a'; if (trie[root][x] == 0) { return false; // 以root为头节点的x字母不存在 返回0 } root = trie[root][x]; // 为查询下个字母做准备 往下走 } return true; // 找到了 }
- (1).插入
这里空空如也
有帮助，赞一个