跳转至

2023

  • 分类于 Algorithms
  • 需要 13 分钟阅读时间

Leetcode

训练

  • 简单、中等、困难在10、20、30分钟解决（倒计时计数
  • 题解在5、10、20分钟内理解，明白核心考点和解题思想，然后重写。
  • ACM模式练习

ACM输入处理

  • 基础cin如何读取字符，读取字符串
  • 接受一个字符串，遇“空格”、“TAB”、“回车”都结束
#include <iostream>
using namespace std;
int main(void)
{
    int a, b;
    while (cin >> a >> b) { }// 读到EOF结束
    while (cin) { // 读到EOF结束
      char ch = cin.get() //读取一个字符
    }
    return 0;
}

其余处理

//接受一个/多个字符
char ch; 
ch=cin.get();               //或者cin.get(ch); 
char a[20]; 
cin.get(a,20);            //可以接收空格


//getline() // 接受一行字符串，可以接收空格并输出
string str; 
getline(cin,str);  // #include<string> 
````

### cout输出处理

```c++
#include <iomanip> 
// 也可以使用 #include <bits/stdc++.h>
int main(void){
    int a = 255;
    cout << hex << a << endl;//以十六进制的形式输出
    cout << dec << a << endl;//以十进制的形式输出
    cout << oct << a << endl;//以八进制的形式输出
    //结果分别是ff 255 377
    return 0;
}
int main(void){
    double x = 3.141592658;

    //控制输出的宽度，就是printf("%10d");
    cout << setw(10) << x << endl;

    //限制输出有效数字的个数是5
    cout << setprecision(5) << x << endl;

    //fixed表示控制小数点后面的数字，两个连用就是小数点后面保留三位小数
    cout << fixed << setprecision(3) << x << endl;

    //输出结果分别是   3.14159  3.1416  3.142
    return 0;
}

考前准备

  • 弱点：
  • 字符串处理相关函数
    • 滑动窗口(有窗口的需求，如子数组；有滑动的判定)
    • 固定一端使得种类数能分类讨论。
    • KMP
  • 图算法
    • 最短路径实现
    • 拓扑排序
  • 动态规划

遇题对策

  1. 题意的准确理解
  2. 构造小样例，分析题意
  3. 题目的抽象
  4. 提取出独立的不可分子问题
  5. 题目的转化
  6. 从问题的反面，所求值的补集，使用不同的变量讨论情况
  7. 通过规律(数学规律)转换问题: 可以先从小例子分析，然后猜想验证
  8. 对于输入量多的题型，必定是以下几种情况
  9. 每次操作(query)是独立的，简单分解成独立任务即可
  10. 使用特殊数据结构(单调栈，优先队列)，边读边算边丢弃
  11. 读取后，处理成精简表示：
    1. 前缀和(子数组的元素和转换成两个前缀和的差, 注意为了sum[0]=0,设置sum[i]=A[0]+...A[i-1])
    2. 差分数组：B[i]=A[i]-A[i-1]
  12. 可以接受的高时间复杂度操作
    1. O(nlogn) 快排 10^5元素
  13. 题型的分类判断
  14. 常见的题型和考察知识点
  15. 陌生的技巧题
    1. 数学技巧题：图论、数值计算技巧
  16. 常见的错误
  17. 特殊输入忘记分析：0 或者 相等
  18. 边界判断错误以及越界：
    1. 数组越界, 数组下表总是写错一位
    2. for循环，或者判断的等于号缺失
    3. int 存储不下 需要long long
  19. 确实少考虑了某个边界的分析
    1. 中 2749. 得到整数零需要执行的最少操作数
  20. 循环调用太多层，导致函数栈溢出
    1. AddressSanitizer: stack-overflow on address 0x7ffe1ea87fc8 (pc 0x00000034e77b bp 0x7ffe1ea88060 sp 0x7ffe1ea87fc0 T0)
    2. 记录遍历过的点，树上记录father，图上记录遍历过点
  21. 自动补全导致的错误
    1. min与max的两行都写成min了
    2. 两层循环的i,j 有处写混了
    3. memset() size*n 导致堆栈上的数据全部变成0，程序访问无法访问的地址，gdb也无法执行，变量数值也完全错误
  22. 其余
    1. *(1/2)不是*0.5是*0

编程建议

  • 先注释理清思路，比如动态规划的下表，如何转移
  • 先注释写好想到的可能的forget的情况，防止写着写着忘记了。

快速debug

  • 除开肉眼快速排查上面的常见错误
  • vscode实机操作
  • 配置好头文件，和main函数
  • 找到错误样例的最小集合作为输入
  • vscode gdb

注意事项

  1. 以思路清晰简洁的代码解答优先，而不是追求O(n)的算法，导致解法复杂化
  2. 多用辅助变量来理清思路，编译器会优化，不会影响性能。
  3. 辅助数据结构的选择一定要切合题意。
  4. 存储中间数据，或者标记已经处理的情况(DP时记录hit值的次数，而不是是否hit，以便回退)
  5. 利用二维数组精简讨论的代码int direction[8][2] = {{2,1}, {2,-1}, {-2,1}, {-2,-1}, {1,2}, {1,-2}, {-1,2}, {-1,-2}};
  6. 计算时间复杂度
  7. 按照题目的上限计算

常用写法和技巧

二分答案、二分法

个人最爱写法

int maxR = *max_element(inputList.begin(), inputList.end());
 int left = 0, right = maxR;
 // 该方法的问题：默认right是不满足的，需要提前额外判断
 if(available(right)) return right;
 while(left + 1 < right) { 
  //由于无论是从left，right相差1、2、3、……开始
  //最终都会经过 left+1=right的阶段
  int mid = left + ((right-left)>>1); // 注意括号 >> 优先级最低
  long long tmpCntSum = 0;
  for(auto &x: inputList){
   tmpCntSum += (x>mid)? mid : x;
  }
  if(tmpCntSum <= cnt){
   left = mid; // while结束时 left 满足 其tmpCntSum <= cnt
  }else{
   right = mid; // while结束时 right 满足 其tmpCntSum > cnt
  }
 }
 //求 满足求和不大于cnt 的最大值：left
 return left;

其他写法

while (l < r) {
    int mid = (l + r + 1) >> 1;
    if (check(mid)) {
        l = mid;
    } else {
        r = mid - 1;
    }
}

二维遍历边界小技巧

int dirs[4][2] = {1,0,-1,0,0,1,0,-1}; 

auto check = [&](int x, int y){
    return x >= 0 && y >= 0 && x < n && y < m;
   };
for(auto &[addx, addy]: dirs){
  int nextx = x + addx;
  int nexty = y + addy;
  if(!check(nextx, nexty)) continue;
  ……
}

单调栈写法

stack<int> stk;
while (head) {
    while (!stk.empty() && stk.top() <= head->val)
        stk.pop(); // 保持从底到top单减


    stk.push(head->val); // 每个元素要加入
    head = head->next;
}

//vector 也行
vector<pair<int, int>> st; // 当前行的单调栈
for (int j = n - 1; j >= 0; --j) {
  while (!st.empty() && mn <= st.back().first)
    st.pop_back();
  st.emplace_back(mn, j);
}

常用技巧

  • iota构建用于排序的索引数组
  • itoa 是 希腊语的第九个字母，读[aɪ’otə]这个名称是从APL编程语言借鉴过来的。
  • 题目iota(id, id + n, 0); sort(id, id + n, [&heights](const auto &i, const auto &j) {return heights[i] > heights[j];}); 注意[&heights]的lambda表达式引用。
  • 快慢指针，原地去重/合并
  • 易 26. 删除有序数组中的重复项
  • 贪心枚举，确定枚举一个变量，从而贪心确定另一个。（不用双重循环）
  • 易 LCP 33. 蓄水
    • 转换思路，枚举另一维度的元素。

常见题型的框架、解法以及例题

模拟题

特征：明显的顺序处理数据O(1)空间O(1)操作

特征：有限个数集合使得时间复杂度降维

有限二维暴力题

贪心

  • 往往贪最大，和优先队列(最大堆)结合
  • 中 1054. 距离相等的条形码
    • 也可以，统计数量之后，先排偶数位，然后排奇数位。
  • 证明贪心的正确性：常用反证法
  • 假如不是贪心的方式成立，会转换或者有什么问题
  • 中 2517. 礼盒的最大甜蜜度：二分答案的子问题中，要证明打包方法，必包括两端的糖果。反证：假如情况不包含两端的糖果，该情况的两端必定可以向外扩展到两端。

考察数据结构

  • 抽象表示/题目特征(用于高效匹配题型)
  • 栈：输入数据量多，顺序push，逆序pop处理，后进先出
  • 哈希表：常见记录元素次数 ++map_cnt[x]
  • 常见的解法流程
  • 解法难点：
  • 存储元素不是简单的int，而是需要额外index信息的pair<int,int>
  • 相关拓展考点/难度延伸
  • 相关例题以及核心考点
  • 中 1019 链表中的下一个更大节点
    • 考察带额外信息的单调栈

常见困难题: 二维图带障碍的路径分析

特征：字符串相关

  • 字符串相关概念
  • 子串与子序列：子串要连续；子序列不需要连续，但是相对位置不改变。
  • 真后缀： 指除了 S 本身的 S 的后缀
  • 回文串：正着写和倒着写相同的字符串
  • 字符串基本处理
  • ASCII码 A在65 a在97
  • 大小写转换
    • char： str[i] = tolower(str[i]);//把大写全部转为小写
    • string, 第三个参数是转换之后，输出到原str字符串的起始地址。转换操作，可以选择toupper，tolower。
    • c++ string str="how are you"; transform(str.begin(),str.end(),str.begin(),::toupper);
  • 快速判断子字符串相同
  • 伪难 1147. 段式回文：暴力双指针匹配能通过O(n^2)，官方对字符串进行滚动哈希预处理变成O(n)
  • 难 1163. 按字典序排在最后的子串
    • 核心思想：只有后缀子字符串才是候选的最大字典序子字符串
    • python 的切片操作LC容忍度比较高
    • 指针 i 指向已知的最大后缀子字符串，j 指向待比较的后缀子字符串
    • 一个个比较时，失败时按道理是j++, 不一定是j+k+1。
    • 因为当 s[i+k]<s[j+k]时，s[j+1~j+k]内可能有更大子字符串，如cacacb字符串，比较caca与cacb时，后者有更大字串cb。
    • 但是通过如下关系能跳过大部分重复的区域
    • 当 s[i+k]<s[j+k]时，跳过了以 s[i,..,i+k] 为起始位置的所有后缀子串，因为它们的字典序一定小于对应的 s[j,..,j+k] 为起始位置的后缀子串（由于s[i+k]<s[j+k]）。
      • s[i,..,i+k] < s[j,..,j+k]，这时j = max(j + 1, i + k + 1);
    • 当 s[i+k]>s[j+k]时, 以s[i] > s[i+1,..,i+k] > s[j,..,j+k], 这时j=j+k+1
  • KMP算法：
  • 一种线性时间复杂度的字符串匹配算法,可以在一个字符串S内高效地定位模式字符串P的出现位置。
  • 思想：核心就是每次匹配过程中推断出后续完全不可能匹配成功的匹配过程，从而减少比较的趟数。
  • next数组实质上就是找出模式串中前后字符重复出现的个数，为了能够跳跃不可能匹配的步骤。next数组的定义为：next[i]表示模式串A[0]至A[i]这个字串，使得前k个字符等于后k个字符的最大值，特别的k不能取i+i,因为字串一共才i+1个字符，自己跟自己相等毫无意义。
  • next数组的信息，可以不用从头开始匹配，而是从重复位置开始匹配(类似双指针，或者滑动窗口的效果)

特征：图相关

  • 图论相关概念
  • 简单图：图中无自环与重边，反之为多重图
    • 自环：某边的两个端点都是同一点形成的环
  • 补图：对于无向简单图G，其补图中的边为G中边的补集
  • 图的表示
  • 数据以稠密图为主，
    • 有边权时：邻接矩阵vector<vector<int>> g;
    • g = vector<vector<int>>(n, vector<int>(n, INT_MAX / 2));
    • g[e[0]][e[1]] = e[2]; // e[2]权重
    • 无边权时：权重为1
  • 数据以稀疏图为主，使用
    • 有边权时：邻接表vector<vector<pair<int, int>>> m_adj;
    • m_adj[edge[0]].emplace_back(edge[1], edge[2]); // edge[2]权重,
    • 无边权时：邻接堆unordered_set<int> nes[n];
    • g[edge[0]].insert(edge[1]); g[edge[1]].insert(edge[0]);
    • 或者邻接表vector<vector<int>> g(n);
      • g[edge[0]].push_back(edge[1]); g[edge[1]].push_back(edge[0]);
  • 图中最短环
  • 难 2608. 图中的最短环
    • 先把图变成n点的邻接表vector<vector<int>> g(n);
    • 寻找最短，明显是从原点开始的BFS，由于要记录遍历的每个点的index和父亲节点，防止邻接表的BFS逆向，采用queue<pair<int,int>>
    • 环的判断，BFS过程中x如果有邻居y已经被遍历到，环大小为该层最小dist[x]+dist[y]+1
  • 图中最短路径
  • 难 2642. 设计可以求最短路径的图类
    • 虽然是单向路径，但是不保证无环。暴力回溯遍历，需要记录已经经过的点。虽然暴力法任然会超时
    • Dijkstra算法
    • 初始化: start距离0，其余无穷
    • 迭代步：
      • 当前点集V里距离最小的点x，就是该点到start的最小距离。find x for min(dis[x]) in V(N)或者int x = min_element(dis, dis + N) - dis;
      • 更新该点x邻居y的最短距离for (int y = 0; y < n; ++y) dis[y] = min(dis[y], dis[x] + g[x][y]); // g为邻接矩阵
      • 将x从V里剔除(已经找到)
    • 结束：
      • x为end，提前结束
      • x内容为无穷，说明其余的点start无法访问到。
    • Floyd 的以中间节点讨论的动态规划算法
    • 在一般图上，求单源最长（短）路径的最优时间复杂度为 O(nm)（Bellman-Ford 算法，适用于有负权图）或 O(m * log m)（Dijkstra 算法，适用于无负权图）。
    • 但在 DAG 上，我们可以使用 DP 求最长（短）路，使时间复杂度优化到 O(n+m)。
  • 拓扑排序 - Kahn 算法
  • 初始状态下，集合 S 装着所有入度为 0 的点（一般是队列，如果题目要求字典序之类，可以换成最大堆/最小堆实现的优先队列），拓扑排序结果L 是一个空列表。
  • 每次从 S 中取出一个点 u（可以随便取）放入 L, 然后将 u 的所有边\( (u, v_1), (u, v_2), (u, v_3) \cdots \)删除。对于边 (u, v)，若将该边删除后点 v 的入度变为 0，则将 v 放入 S 中。
  • 不断重复以上过程，直到集合 S 为空。检查图中是否存在任何边，如果有，那么这个图一定有环路，否则返回 L，L 中顶点的顺序就是拓扑排序的结果。
  • 华为230426机试一
    • 双队列BFS。（S为空时，还有入度不为0的点，有环
    • 或者往大更新每点的距离，返回最大值。（N次后还能更新点，说明有环

特征：树相关

  • 基本概念：区分二叉搜索树，平衡二叉树
  • 树具有相同的子问题结构，常用dfs递归
  • 中 6419. 使二叉树所有路径值相等的最小代价
  • 循环删除树上叶子节点
  • 难 2603. 收集树中金币
    • 思路1：删除叶子节点
    • 先把图变成n点的邻接表，但是由于要删除使用unordered_set<int> nes[n];
    • 叶子节点的判断nes[i].size() == 1， 删除叶子节点可能会导致新的叶子产生需要queue保存循环处理
    • 思路2：拓扑排序(基于Kohn算法：从多个入度为0的叶子节点开始BFS，取出ready的点，更新其他节点的度。但是每个节点有依赖度的属性dig[i],只有节点满足依赖才能入队继续BFS)

特征：每步k分支，穷举所有答案组合

  • 抽象表示/题目特征(用于高效匹配题型)
  • 回溯法
  • 常见的解法流程
  • 采用辅助数据结构记录选择某分支导致的影响次数，以便回退
  • 解法难点：
  • 时间复杂度较高，往往需要用动态规划等替代。迫不得已不要用。
  • 相关拓展考点/难度延伸
  • 相关例题以及核心考点
  • 中 2597. 美丽子集的数目
  • 中 6899. 达到末尾下标所需的最大跳跃次数
    • 回溯的时间复杂度过高k^1000。动态规划大约1000*k

BFS

  • BFS时，一般不经过重复节点，需要记录。
  • 原因：每个节点只有位置信息时，重复遍历节点肯定不满足最小步数的要求(至少加一)。可能导致死循环。
  • BFS每步的内容，或者记录的重复节点的内容: 一般不仅有位置，还有方向等其他信息。
  • 多源BFS + 并查集/二分答案
  • 要点：区分已经遍历和未经过的区域。如果不需要存储额外信息一个queue就能实现，因为swap(tmp,cur_queue)耗时。
  • ROI: 将两点连线通过BFS的属性值变成并查集，判断在集合内

特征：每步k分支，求解min步数

  • 抽象表示/题目特征(用于高效匹配题型)
  • BFS: 每步k分支，关心步数，每个分支互不影响
  • 常见的解法流程
  • 采用双队列，每个元素存储了每个节点所需信息，每次交换相当于树的遍历更深一层。
  • 解法难点：
  • 具体根据题目简化每个节点处理的时间复杂度
    • 记录候选集合，遍历后删除，避免重复访问
  • 相关拓展考点/难度延伸
  • 相关例题以及核心考点
  • 难 2612. 最少翻转操作数
    • 由于每个节点都要对大小为n的bannedSet判断，每次O(logn)，次数k，每节点时间复杂度O(klongn)
    • 一种记录已经遍历的候选集合方法
    • 发现其反转的奇偶特性，次数减半，同时将bannedSet的补集分成一半，每节点时间复杂度O(k/2 *long(n/2))
    • 而且由于记录了候选集合，遍历过可以防止重复访问，耗时会逐渐减小。
    • 最快的方法，发现候选集合是连续的。使用uf[x] = y;记录每个起始地址x，已经处理到地址y，也就是跳过了x~y的区域。

特征：问题能被分成多阶段求解(动态规划)

  • 抽象表示/题目特征(用于高效匹配题型)
  • 最优子结构
    • 问题的最优解所包含的子问题的解也是最优的
  • 无后效性
    • 即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。
  • 子问题重叠
    • 如果有大量的重叠子问题，我们可以用空间将这些子问题的解存储下来，避免重复求解相同的子问题，从而提升效率。
  • 常见的解法流程
  • 强烈建议先写记忆化搜索的DFS，除非超时而且有固定个数(eg.500)可以写成固定大小的数组的递推.
    • 递推会比记忆化搜索快7~8倍左右
    • 递推的边界太不直观了，而且容易出错
  • 确定dp数组（dp table）以及下标的含义
    • 将原问题划分为若干 阶段，每个阶段对应若干个子问题，提取这些子问题的特征（称之为 状态）；
  • 确定递推公式
    • 寻找每一个状态的可能 决策，或者说是各状态间的相互转移方式（用数学的语言描述就是 状态转移方程）。
  • dp数组如何初始化
  • 确定遍历顺序
  • 举例推导dp数组
    • 按顺序求解每一个阶段的问题。
  • 解法难点：
  • 记忆化搜索与从头递推是同时间复杂度的写法
  • 选择参数k，k的变化来分阶段, 寻找k与k+1间的转移关系
  • 二维DP，第二个维度间是怎么连续转移的？
  • 降低时间复杂度
    • 对于二维的DP，简单的阶段转移只需要O(1)时间，总时间O(mn)。
    • 复杂的题目阶段转移作为子问题，需要结合额外的方法简化时间复杂度
  • 降低空间复杂度
    • 分析每次转移使用和产生的数据，去除冗余的数据，二维DP从头递推使用滚动数组优化为O(n), 甚至可能简化为O(1)
  • 相关拓展考点/难度延伸
  • 相关例题以及核心考点
  • 如何选择分阶段参数和构建转移
    • 分阶段参数：输入序列的问题规模
    • 区间DP:
    • 中 300. 最长上升递增子序列
      • 分阶段参数：以A[i]为子序列结尾的最长子序列f(i)
      • 转移关系：遍历时新元素是否满足题意(递增)，很简单加入序列，转移到更长的公共子序列
      • \[f(i)=\max[\max_{j \in [0,i-1]}f(j),0]+1, \textbf{if}\ nums[j]<nums[i]\]
      • 初始化f[0]=1
      • 子问题寻找是满足 nums[j]<nums[i]的最大的已有序列，通过维护辅助数据M[n]存储长度为i的末尾元素的最小值。
      • 贪心优化：上升子序列长 -> 上升慢 -> 新加元素尽可能小 -> 维护长度为 i的最长上升子序列的末尾元素的最小值
    • 最长上升子序列变种
      • 核心思想：以最后最后一个元素为参数来DP，才能比较是否上升。
      • 难 面试题 08.13. 堆箱子 往往 return *max_element(dp.begin(), dp.end());
    • 中 1027. 最长等差数列
      • 分阶段参数：和上一条相同，由于要判断递增和等差，需要两个元素信息。根据差值j情况又不同
      • 以nums[i]结尾的等差为j的最长子序列长度
      • 转移关系
      • 未优化版本O(n^3)：\(\(f(i,j) = max[\max_{k\in [0,i-1]}f(k,j),0]+1, \textbf{if}\ a[i]-a[k]=j\)\)
      • 朴素的思路：把k维度优化掉，相同j的情况下，f随第一项单增，所以需要辅助数据记录值为a[i]-j对应的最后一个index
      • 思路二：优化差值j维度，从后向前遍历k，对于d=a[i]-a[k], 更新没处理的f(i,d)
    • 难 1187. 使数组严格递增
      • 分阶段参数：考虑包括index为i的前面元素，并且最后一个元素大小小于j的严格递增序列的最小操作数f(i,j)
      • 转移关系：被交换的\( a_2[p] \)也应该小于j。
      • 初始想法：$$f(i,j)=min[min(f(i,k_1),\textbf{if} k_1\in [0,j-1]), $$$$f(i-1,a_1[i]),\textbf{if} a_1[i]<j, $$\(\(min(f(i-1,k_2)+1), \textbf{if}\ k_2\in \{a_2[0],\cdots,a_2[p]\} , a_2[p]<j )]\)\)
      • 初始化：f(-1,x)=0
      • 二维DP 有许多冗余信息：
        • 如果只有最后一个min，后面每行答案一样。加上第二个min，也能保存每行元素单调递减。所以第一行min是冗余的。
        • 由于每行是单调递减的，所以最后一个min应该取最后一个
      • 转移公式化简：$$f(i,j)=min[f(i-1,a_1[i]),\textbf{if} a_1[i]<j, $$$$ f(i-1,a_2[p])+1, \textbf{if} max p ,a_2[p]<j )]$$
      • 还存在两个问题：
        • 第二个维度过大\( 10^9 \)：由于数的个数是有限的，可以排序后数位与数值一一对应，来处理数位。
        • 记忆化DFS时，考虑到第二个维度的范围比较大，可以用哈希表来记忆化。
        • 其次该转移公式容易DFS但是难以转化为递推？
      • 贪心优化：操作数少 -> 原本数组递增子序列越长 -> 被操作的数越紧密，剩下的未处理的数组的递增子序列就可能越长
    • 中 2606. 找到最大开销的子字符串
      • 子串的最大最小值
      • 分阶段参数：以A[i]为字串结尾的最大开销字串
      • 转移关系：新字串=前一个字串+新元素。保留每个以A[i]为字串结尾的字串数据来求最大最小值
    • 中 1043. 分隔数组以得到最大和
      • \[f(i)=\max_{j \in [max[i-k+1],i]}[f(j-1)+(i-j+1)\times \max_{p\in [j,i]}arr[p]]\]
      • 可以发现转移方程中有一个子区间最大值的子问题， 但是在写成递推时能顺便求解了。
    • 难 1335. 工作计划的最低难度
      • 求解a[n] d 个子数组的 最大值的和的最小值
      • 很自然的确定最后一个子数组的元素个数k来提取子问题，dfs(d-1, n-k)
      • 更快的，结合单调栈（太绕了，思路
    • 三维DP, 结果要从某个有限个数的维度遍历出来, 类似return [max(dfs(n,j) for j in range(J))
    • 中 6898. 字符串连接删减字母
      • 观察到有限的字母种类，
    • 0-1背包(受限的选择组合问题)
    • 分阶段参数：已经考虑的n个元素的个数，限制条件组成第二个参数
      • 也属于第一类：分阶段参数为输入序列的问题规模
    • OIWiki 有时限的最大化采药价值
      • 转移关系: 选与不选导致，\( max(f_{i-1}{k},f_{i-1}{k-w}+v) \)
      • 普通的0-1背包问题，使用滚动数组时，要注意遍历方向
    • 中 2597. 美丽子集的数目
      • 用乘法原理将总组合数问题分解成各个模数的组合数的乘积
      • 分阶段参数：包含的前n个元素的个数(单个模数的组合数求解的子问题里)
      • 转移关系：组合数关系(总组合数=选i的组合数+不选i的组合数)
    • 难 1125. 最小的必要团队
      • 状态压缩 + 集合版0-1背包
      • 状态压缩：由于输入数据一个小于16，一个小于64，压缩成二进制
      • 分阶段参数：dfs(i,j) 表示从前 i 个集合中选择一些集合，并集包含 j（题目限制需要），至少需要选择的集合个数。
      • 转移关系：dfs(i,j)=dfs(i−1,j delete set[i])+1
        • 边界：当j==0，限制已经满足了，dfs==0
      • 优化:递推查表法 vs 刷表法
    • 不相邻问题：打家劫舍四部曲
    • 一：一维序列不相邻问题，前一格和跳一格+自身里选最大
    • 二：一维环, 两种情况的最大值
      • 如果偷 nums[0]，那么 nums[1]和 nums[n−1]不能偷，问题变成从 nums[2]到 nums[n−2]的非环形版本，调用前面的代码即可
      • 如果不偷 nums[0]，那么问题变成从 nums[1]到 nums[n−1]的非环形版本
    • 三：树上的不相邻问题，很像树形DP
      • 需要一个根，来确定子树(DFS)方向。除开当前遍历的节点，还需要一个变量表示是否选择
      • 转移关系如下：x为i的子节点
        • 未选\( f(i,0)= \sum{max(f(x,1),f(x,0))} \)
        • 已选\( f(i,1)= \sum f(x,0) + a_i \)
    • 三拓展 难 2646. 最小化旅行的价格总和
      • 选择的点是1/2, 未选择是原代价。 而且每个节点有次数\( k_i \)
      • 转移关系如下：x为i的子节点
        • 未选\( f(i,0)= \sum{min(f(x,1),f(x,0))} + a_i * k_i \)
        • 已选\( f(i,1)= \sum f(x,0) + 0.5 a_i k_i \)
    • 四：和二分答案结合
  • 组合数问题：
    • 计数DP： 中 1079. 活字印刷
    • f[i][j] 表示用前 i 种字符构造长为 j 的序列的方案数。选k个字符进行放置。
  • 降低时间复杂度
  • 与二进制结合

特征： 数量有限的有无/是非关系(状态压缩)

  • 抽象表示/题目特征(用于高效匹配题型)
  • 题目或其子问题有明显的0-1关系，考虑位运算简化判断
  • 常见的解法流程
  • 将状态用二进制表示
    • 位运算按位与（&）、按位或（| ）、按位异或（^）、取反（~）、左移（<<）、右移（>>）
  • 位运算替代状态转换
    • 将元素 x 变成集合 {x}，即 1 << x。
    • 判断元素 x 是否在集合 A 中，即 ((A >> x) & 1) == 1。
    • 计算两个集合 A,B 的并集 \( A\cup B \)，即 A | B。
    • 例如 110 | 11 = 111。
    • 计算 \( A \setminus B \)，表示从集合 A 中去掉在集合 B 中的元素，即 A & ~B。
    • 例如 110 & ~11 = 100。
    • 全集 U={0,1,⋯ ,n−1}，即 (1 << n) - 1。
  • 解法难点：
  • 相关拓展考点/难度延伸
  • 相关例题以及核心考点
  • 中 1042. 不邻接植花
  • 难 1125. 最小的必要团队
  • 难 1483. 树节点的第 K 个祖先
    • 去掉 k 的最低位的 1: k &= k - 1
    • 转化为二进制的DP递推

问题：求动态区间(子区间)内的最大最小值

  • 抽象表示/题目特征(用于高效匹配题型)
  • 如问题
  • 常见的解法流程
  • 构建最小单调栈，区间变化的时候push，并且pop大于新元素的元素
  • 有时候也是动态规划， 比如 难 1335. 工作计划的最低难度
  • 解法难点：
  • 额外的要求导致的额外的判读和信息存储
  • 相关拓展考点/难度延伸
  • 相关例题以及核心考点
  • 中难 907. 子数组的最小值之和
    • 左右单调栈 + 贡献法
  • 难 2617. 网格图中最少访问的格子数
    • 解法：反转DP方向 + 二分查找单调栈
    • 求min，每一步在push时构建底大顶小递增的单调栈，后push元素要是能使用优先级最高的最小值，按题意新元素最近(idnex相差1), 所以能丢弃前面结果更大的元素。
    • 注意：由于是反转DP，由于新元素位于栈末尾，而且新元素的index小，所以单调栈中index也是单调递减的，所以能二分查找。
  • 难 1335. 工作计划的最低难度
    • 最快的方法: 单调栈递推DP

问题：求动态区间(子区间)内的最大值

  • 只能用动态规划（递推）
  • 问：子区间最大和，一维DP，对象是区间的末尾元素
  • 进阶(RedStar 230724)：子区间能改变一个值为x，问最大和。二维DP，第二维度是是否在区间内改变，再根据改变的位置是不是末尾来分成两种情况 dp[j][1]=max[max(dp[j-1][0]+x,x),max(dp[j-1][1]+nums[j],nums[j])]

问题：求动态区间(子区间)内的出现元素次数

  • 相关例题以及核心考点
  • 难 1157. 子数组中绝对众数
    • 绝对众数的快速暴力解法见文末：区间长度n时，每次查询需要O(n)
    • 分组：
    • 区间长度 \( \leq s \)，直接暴力即可。
    • 区间长度 \( > s \)，由于绝对众数定义其出现次数 \( >\frac{s}{2} \) ，因此可能的答案个数 \( \leq\frac{2n}{s} \)
    • \( s=\sqrt{2n} \) 时两者情况时间复杂度相等。
    • 线段树
    • 由于摩尔投票具有区间可加性，使用线段树可以直接查询区间内的绝对众数。然后查找众数在区间内的次数(map保存每个数的出现index有序集合，然后使用upper_bound和lower_bound)。 C++代码

问题：区间数值求和、绝对值、求个数(有限种类、奇偶个数)

特征：所有子数组x值的和 mod 10^7

问题：求满足条件的参数的最小/最大值

  • 抽象表示/题目特征(用于高效匹配题型)
  • 题目要求
    • 求解满足条件的一个最大或者最小值、最小最大值或者最大最小值
    • 单调性，答案是个临界值，两侧分别是满足条件和不满足条件。
  • 如果猜测一个答案mid，能作为条件参与到满足题目条件的判断中。
  • 答案数值有明显的上界和下界，作为二分答案的left和right
  • 常见的解法流程
  • 二分答案mid，判断当前mid的数值是否满足题目条件，来寻找满足条件的最大/最小答案。
  • 解法难点：
  • 每次判断是否满足题目如何实现
  • 相关拓展考点/难度延伸
  • 相关例题以及核心考点
  • 题单
  • 2560. 打家劫舍 IV
    • 选择k个中最大数值的最小值，将最大的最小值转换成不超过mid的限制
    • => 最大数值不超过mid的最大个数p的求解, p < k 则不满足条件
    • 条件判断转换成DP
  • 2616. 最小化数对的最大差值
    • 选择p数对的最大差值的最小值
    • => 最大差值不超过mid的最多数对数k， k < p则不满足条件
    • 条件判断转换成DP
  • 难 2528. 最大化城市的最小供电站数目
    • 部署电站k个后，城市最小电量的最大值
    • => 使得城市最小电量不小于mid，最少需要p个额外电站部署, p > k 则不满足条件
  • 华为 2023.04.12-实习笔试-第一题-购物系统的降级策略
  • 华为 P1006. 2022.9.21-数组取min
  • 华为230426 机试三
    • 二分答案，每种情况是一个最强祝福力场子问题

常见数学相关基础

模运算相关基础

  • 同余定理：
  • 给定一个正整数m，如果两个整数a和b满足a-b能够被m整除，即(a-b)/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(mod m)。对模m同余是整数的一个等价关系。
  • 性质
  • 对称性：若a≡b(mod m)，则b≡a (mod m)；
  • 传递性：若a≡b(mod m)，b≡c(mod m)，则a≡c(mod m)；
  • 同余式相加：若a≡b(mod m)，c≡d(mod m)，则a+c≡b+d(mod m)；
  • 同余式相乘：若a≡b(mod m)，c≡d(mod m)，则ac≡bd(mod m)。
  • 费马小定理
  • 若 p 为素数，gcd(a, p) = 1，则 \(\(a^{p - 1} \equiv 1 \pmod{p}\)\)。
  • 另一个形式：对于任意整数 a，有 \(\(a^p \equiv a \pmod{p}\)\)。
  • 欧拉定理
  • 欧拉函数：\( \varphi(n) \)，表示的是小于等于 n 和 n 互质的数的个数。
    • \( \varphi(1) \) = 1。
    • 当 n 是质数的时候，有 \( \varphi(n) \) = n - 1。
  • 若 gcd(a, m) = 1，则 \(\(a^{\varphi(m)} \equiv 1 \pmod{m}\)\)。

模运算，模数

质数（素数）

  • 质数（素数）相反的概念是合数
  • 平凡约数：1和它本身称为平凡约数；大于1小于它本身的约数称为非平凡约数。
  • 高效判断是否为质数，重点在上界i * i <= n
  • 如果某个整数大于 1 ，且不存在除 1 和自身之外的正整数因子，则认为该整数是一个质数。
bool is_prime(int n) {
  for (int i = 2; i * i <= n; ++i)
    if (n % i == 0)
      return false;
  return n >= 2; // 1 不是质数
}
  • 最快速的预处理(埃氏筛)：MAX内的质数序列, 考虑从头deny候选元素
  • 由于没有分支与访问有规律，会比复杂度低的欧拉筛快

存储质数和非质数的版本：

const int MX = 1e5;
bool np[MX + 1]; // 质数=false 非质数=true
int init = []() {
    np[1] = true; // 1 不是质数
    for (int i = 2; i * i <= MX; i++) {
        if (!np[i]) {
            for (int j = i * i; j <= MX; j += i) {
                np[j] = true;
            }
        }
    }
    return 0;
}();

质数push2vector：

const int MX = 1e6;
vector<int> primes; // 建议一个vector，一个数组
bool np[MX + 1]; // 默认是0

int init = []() {
    for (int i = 2; i <= MX; i++) { // 不能是 i*i
        if (!np[i]) {
            primes.push_back(i); // 预处理质数列表, 写在里面，不能是 i*i
            // for (int j = i; j <= MX / i; j++) // 避免int溢出的写法
            //     np[i * j] = true; //deny后续元素, i*i 开始
            // or
            for(int j = i*i; j <= MX; j+=i){
                np[j] = true;
            }
        }
    }
    return 0;
}();
  • 埃氏筛：通俗的写法 
    vector<int> generatePrimes(int n) {
  vector<bool> isPrime(n + 1, true);
  vector<int> primes;

  for (int p = 2; p * p <= n; ++p) {  // 使用了 i*i，素数要额外push
      if (isPrime[p]) {
          // primes.push_back(p);
          for (int i = p * p; i <= n; i += p) { // 新排除的是新质数的倍数
              isPrime[i] = false;
          }
      }
  }

  for (int p = 2; p <= n; ++p) {
      if (isPrime[p]) {
          primes.push_back(p);
      }
  }
  return primes;
}

基于费马小定理的O(log n)的伪素数判断方法。但是机试一般不会考。

众数

  • 绝对众数求解，
  • 绝对众数：该众数出现的次数大于N/2。
  • 摩尔投票算法：寻找一组元素中占多数元素(不能刚好占一半)的常数空间级时间复杂度算法。
  • 每次从序列里选择两个不相同的数字删除掉（或称为“抵消/对拼消耗/争擂台”），最后剩下一个数字或几个相同的数字，就是出现次数大于总数一半的那个。
j=k=0;
for(i=left;i<=right;i++)
  if(a[i]==j)
    k++;
  else if(k)
    k--;
  else{
    j=a[i];
    k=1;
  }

gcd, lcm

  • 最大公约数gcd，最小公倍数lcm
  • gcd(a, b) = gcd(b, a % b) 注意是求余数
    • 虽然平时都是调用函数，但是常见实现是
    • 欧几里得算法(辗转相除法): 原理: gcd(a,b)=gcd(b,a mod b), 大数除以小数得到余数，对三个数中的两小数重复，直到出现整除，较小数为最大公约数。
    • 更相减损术: 原理: gcd(a,b)=gcd(b,a - b), 大数减小数得到C，对三个数中的两小数重复，直到出现相等，即为最大公约数。
  • 最小公倍数lcm可以由gcd推导：lcm(a, b) = a * b / gcd(a, b)
  • 多个数的最大公约数： 由于有传递性，可以将两个树的gcd，传递下去
  • 多个数的最小公倍数：ans = lcm(a, b, c) = lcm(lcm(a, b), c),或者ans = tmp/gcd(tmp,c)*c先除后乘防止溢出。其中tmp=lcm(a,b)或者递归。

位运算

  • 中 2411. 按位或最大的最小子数组长度
  • 每个元素的影响或等于并集，按位或最大==数字1最多，即最大的并集
    • 没有增大==或结果相同=>子集=>前面不需要再遍历，剪枝
  • 中 1072. 按列翻转得到最大值等行数
  • 逆向思考，相等行间的关系
    • 相同的行1111 1111 or 0000 0000. 反转列变成 1101 1101 and 0010 0010
    • 可以发现将第一位变成1 后，答案就是同为某序列 1101的最大个数
  • 注意异或1相当于取反，异或0相当于不变。
  • 异或 也可以视作「不进位加法（减法）」或者「模 222 剩余系中的加法（减法）」

组合数问题

  • 基本公式：
  • 常见分解技巧：
  • 组合数关系(总组合数=选i的组合数+不选i的组合数)：
  • 乘法原理将总组合数分解成各个部分的组合数的乘积
  • 组合问题，常见解法：
  • 加加减减回溯法
  • 动态规划

不进位的加法

进制转换

  • n进制转换为十进制: 简单，a[i] * n^i
  • 十进制转换为n进制(n为正数)
  • 除n取余数，最后结果取反(reverse)
  • 十进制转换为(-n)进制(n为正数)
  • 每次取的余数k保证为正数在0到n-1之间。T=(-n)*p+k
  • 否则，调整T=(-n)*(p+1)+(k+n)。余数+n变正数，商++
  • 中 1073. 负二进制数相加
  • 但是这道题不能用进制转换做，会数据会溢出。 只能模拟按位加法，
  • 实现时有一个小问题， 关于负数整除与负数取余 
    vector<int> int2array(long long num){
  const int k = -2;
  vector<int> result;
  while(num){
      if(num > 0 || num%k==0){
          // num%k 余数 大于等于0
          result.push_back(num%k);
          num /= k;
      }else{
          result.push_back(num%k-k);
          num = num/k + 1;
      }
  }
  reverse(result.begin(), result.end());
  if(result.size()==0){return {0};}
  return result;
}

负数整除与负数取余

  • 负数整除
  • C++ 除法采用了向零取整(截断取整)：向0方向取最接近精确值的整数，换言之就是舍去小数部分。
  • 所以有(-a)/b==-(a/b)
  • 负数取余
  • 结论a%b=c中c的符号与a相同
  • 证明: 由于 被除数÷除数=商……余数，所以余数=被除数-商×除数。其中除数可由上面的C++ 除法推导
    • 讨论 7%(-4) (-7)%4 (-7)%(-4) 三种情况可知

模板写法

  • 抽象表示/题目特征(用于高效匹配题型)
  • 常见的解法流程
  • 解法难点：
  • 框架复杂？
  • 相关拓展考点/难度延伸
  • 相关例题以及核心考点
  • 1143 HARD xxx ：考察xxx

需要进一步的研究学习

暂无

遇到的问题

做了30天的leetcode，发现不会的还是不会。我就知道我

学而不思则罔

脑中一团浆糊，虽然学习了一些常见题型的框架、解法以及例题。

但是遇到新题目，是否能使用这些方法，以及如何转换使用还是没考虑清楚。

开题缘由、总结、反思、吐槽~~

参考文献

https://oi-wiki.org/

许多思路来自：灵茶山艾府

  • 分类于 Programming
  • 需要 22 分钟阅读时间

[C++ Basic] STL Data Structure

基础杂项

auto的使用

  • 当你想要拷贝range的元素时，使用 for(auto x : range).
  • 当你想要修改range的元素时，使用 for(auto && x : range)
  • 当你想要只读range的元素时，使用 for(const auto & x : range).

容器间的转换 begin end

vector<int>& nums1
unordered_set<int> nums_set(nums1.begin(), nums1.end());

unordered_set<int> result;
return vector<int>(result.begin(), result.end());

迭代器知识

前后第k个元素

  • std::prev 函数接受两个参数：一个是指向迭代器的参数，另一个是整数偏移量。它返回从指定迭代器开始向前移动指定偏移量后的迭代器。
  • std::next 函数接受两个参数：一个是指向迭代器的参数，另一个是整数偏移量。它返回从指定迭代器开始向前或向后移动指定偏移量后的迭代器。
auto prevIt = std::prev(it);

auto next2It = std::next(it, 2);

auto it2 = it;
advance(it2,k);

advance : 形似index的随机访问

  • std::advance 函数的实现方式取决于迭代器的类型。
  • 对于随机访问迭代器（后面解释），它会直接使用 += 运算符来实现移动。
  • 对于双向迭代器和输入迭代器，它会使用循环来实现移动。
  • 例如，以下是 std::advance 的一个简单实现, 这个实现使用了 C++17 的 if constexpr 特性，以便在编译时选择不同的实现方式。：
template <typename InputIt, typename Distance>
void advance(InputIt& it, Distance n) {
    if constexpr (std::is_same_v<std::random_access_iterator_tag,
                typename std::iterator_traits<InputIt>::iterator_category>) {
        it += n; //如果迭代器是随机访问迭代器（后面解释），它会使用 += 运算符来移动；
    } else {
        if (n >= 0) {
            while (n--) {
                ++it; //否则，它会使用循环来移动。
            }
        } else {
            while (n++) {
                --it;
            }
        }
    }
}

随机访问迭代器

  • 随机访问迭代器是一种迭代器类型，它支持在常数时间内访问序列中的任何元素。
  • 它们还支持指针算术运算，例如 + 和 - 运算符，以及下标运算符 []。
  • 例如，对于一个指向数组的随机访问迭代器 it，可以使用以下语法访问第 i 个元素：*(it + i) or it[i]
  • STL 中的容器 vector 和 deque 都提供了随机访问迭代器。除此之外，C++ 标准库中的很多算法也要求输入迭代器是随机访问迭代器，例如 std::sort 和 std::nth_element 等。

正向迭代器和反向迭代器

  • 由于类型不同经常需要转换
  • 对于一个正向迭代器 it，可以使用以下语法将其转换为反向迭代器rit：std::reverse_iterator<Iterator> rit(it);
  • 反向迭代器可以使用以下语法转换为正向迭代器：
std::reverse_iterator<Iterator> rit;
Iterator it = rit.base();

反向遍历

  • 建议使用rbegin rend。注意++it而不是--it。
  • rbegin指向最后一个元素
  • rend 指向reverse遍历的后一个元素。
for(auto it = collection.rbegin(); it != collection.rend(); ++it) {
    std::cout << *it << std::endl;
    // std::cout << it->first << ", " << it->second << std::endl;
}
  • 错误的原始写法, 错误原因showedPositive.begin()==(--showedPositive.begin()。
  • std设计了一个循环。
  • 同样的设计在showedPositive.rend()==(++showedPositive.rend())
  • 但是showedPositive.rbegin() != (--showedPositive.rbegin())
for(auto it=--showedPositive.end(); it!=--showedPositive.begin(); it--){

}

bitset

bitset类型存储二进制数位。

初始化

std::bitset<16> foo;
std::bitset<16> bar (0xfa2);
std::bitset<16> baz (std::string("0101111001"));

//foo: 0000000000000000
//bar: 0000111110100010
//baz: 0000000101111001

将数转化为其二进制的字符串表示

int i = 3;
string bin = bitset<16>(i).to_string(); //bin = "0000000000000011"
bin = bin.substr(bin.find('1'));        //bin = "11"

char 与 字符串

元音与index的相互映射

string vowel = "AEIOUaeiou";
if vowel.find(c) != std::string::npos;

voewl[0] = 'A';

string

读取空格分割的

stringstream txt(s);
string word;
while(txt>>word){
    // to do
}

遍历

string s;
for(auto && x : s)

打印string

printf("%s", your_string.c_str()); //不推荐
cout << your_string;

string不同于C语言的char来存储字符串

//复制
str3 = str1;    len = str3.size();
//连接
str1 = str1 + str2;  strcat( str1, str2);
//总长度
len = str3.size();  strlen(s1);

C++ string 成员函数 length() 等同于 size()，但是和 C 库函数 strlen() 有着本质区别

https://blog.csdn.net/K346K346/article/details/79546919

初始化

std::string s0 ("Initial string");

// constructors used in the same order as described above:
std::string s1;
std::string s2 (s0);
std::string s3 (s0, 8, 3);
std::string s4 ("A character sequence");
std::string s5 ("Another character sequence", 12);
std::string s6a (10, 'x');
std::string s6b (10, 42);      // 42 is the ASCII code for '*'
std::string s7 (s0.begin(), s0.begin()+7);

std::cout << "s1: " << s1 << "\ns2: " << s2 << "\ns3: " << s3;
std::cout << "\ns4: " << s4 << "\ns5: " << s5 << "\ns6a: " << s6a;
std::cout << "\ns6b: " << s6b << "\ns7: " << s7 << '\n';

//output
s1: 
s2: Initial string
s3: str
s4: A character sequence
s5: Another char
s6a: xxxxxxxxxx
s6b: **********
s7: Initial

插入insert

在指向位置的右边插入

// inserting into a string
#include <iostream>
#include <string>

int main ()
{
  std::string str="to be question";
  std::string str2="the ";
  std::string str3="or not to be";
  std::string::iterator it;

  // used in the same order as described above:
  str.insert(6,str2);                 // to be (the )question
  str.insert(6,str3,3,4);             // to be (not )the question
  str.insert(10,"that is cool",8);    // to be not (that is )the question
  str.insert(10,"to be ");            // to be not (to be )that is the question
  str.insert(15,1,':');               // to be not to be(:) that is the question
  it = str.insert(str.begin()+5,','); // to be(,) not to be: that is the question
  str.insert (str.end(),3,'.');       // to be, not to be: that is the question(...)
  str.insert (it+2,str3.begin(),str3.begin()+3); // (or )

  std::cout << str << '\n';
  return 0;
}

尾部插入char

不同的方法

std::string s = "C+";
char ch = '+';

s.push_back(ch);
s += ch; //string::operator+=, which is overloaded for chars and internally calls to the push_back() function.
s.append(1, ch); //1*ch个字符
s.append("abcd"); //后面添加abcd字符串

std::stringstream ss;
ss << s << ch;
ss >> s;

s.insert(s.length(), 1, ch);

截取string

// Copy three characters of s1 (starting
// from position 1)
//第一个参数是要截取的字符串，第二个参数是截取的开始位置，第三个参数是截取长度（可选）1。如果没有指定长度，则子字符串将延续到源字符串的结尾。
string r = s1.substr(1, 3);

// Take any string
string s = "dog:cat";
// Find position of ':' using find()
int pos = s.find(":");
// Copy substring after pos(include pos)
string sub = s.substr(pos);
// Copy substring before pos(not include pos)
string sub = s.substr(0 , pos);

反转reverse string

reverse(greeting.begin(),greeting.end());

寻找子元素位置

// log1 中找空格
int pos1 = log1.find_first_of(" ");

// 判断数字
bool isDigit1 = isdigit(log1[pos1 + 1]);

// 判断是否找到
if(s.find(goal) != string::npos){
}

npos是一个常数，表示size_t的最大值（Maximum value for size_t）。许多容器都提供这个东西，用来表示不存在的位置，类型一般是std::container_type::size_type。

string erase

三种情况

// string::erase
#include <iostream>
#include <string>

int main ()
{
  std::string str ("This is an example sentence.");
  std::cout << str << '\n';
                                           // "This is an example sentence."
  str.erase (10,8);                        //            ^^^^^^^^
  //去除index=10的连续8个元素
  std::cout << str << '\n';
                                           // "This is an sentence."
  str.erase (str.begin()+9);               //           ^
  //去除itr指向的元素
  std::cout << str << '\n';
                                           // "This is a sentence."
  str.erase (str.begin()+5, str.end()-9);  //       ^^^^^
  //去除[first,last).的元素
  std::cout << str << '\n';
                                           // "This sentence."
  return 0;
}

删除最后一个元素

std::string s = "C,C++,Java,";
if (!s.empty()) {
 s.pop_back();
}

if (!s.empty()) {
 s.resize(s.size() - 1);
}

if (!s.empty()) {
 s.erase(std::prev(s.end()));
}

if (!s.empty()) {
 s.erase(s.size() - 1);
}

容器适配器

STL 提供了 3 种容器适配器，分别为 stack 栈适配器、queue 队列适配器以及 priority_queue 优先权队列适配器。

stack 栈

stack<int> minStack;
minStack = stack<int>();

// 支持初始化，但是注意将整个数组元素推入堆栈，堆栈的顶部元素top将是数组的第一个元素。
std::vector<int> elements = {1, 2, 3, 4, 5};
std::stack<int> myStack(elements.begin(), elements.end());


!minStack.empty()
minStack.pop(); //该函数仅用于从堆栈中删除元素，并且没有返回值。因此，我们可以说该函数的返回类型为void。
minStack.push();
minStack.top();

stack

注意pop仅用于从堆栈中删除元素，并且没有返回值, 一般用法如下

top_value = stIn.top();
stIn.pop();

堆栈，先进先出

empty 该函数用于测试堆栈是否为空。如果堆栈为空，则该函数返回true，否则返回false。
size 该函数返回堆栈容器的大小，该大小是堆栈中存储的元素数量的度量。
top 该函数用于访问堆栈的顶部元素。该元素起着非常重要的作用，因为所有插入和删除操作都是在顶部元素上执行的。
push 该函数用于在堆栈顶部插入新元素。
pop 该函数用于删除元素，堆栈中的元素从顶部删除。
emplace 该函数用于在当前顶部元素上方的堆栈中插入新元素。
swap 该函数用于交换引用的两个容器的内容。

清空

stack不支持clear, 除开一个个pop

std::stack<int> myStack;
// 添加元素到 myStack

myStack = std::stack<int>(); // 清空 myStack, 丢弃原有对象

std::stack<int> emptyStack;
myStack.swap(emptyStack); // 清空 myStack

queue

empty() 如果 queue 中没有元素的话，返回 true。
size() 返回 queue 中元素的个数。

front() 返回 queue 中第一个元素的引用。如果 queue 是常量，就返回一个常引用；如果 queue 为空，返回值是未定义的。
back() 返回 queue 中最后一个元素的引用。如果 queue 是常量，就返回一个常引用；如果 queue 为空，返回值是未定义的。

push(const T& obj) 在 queue 的尾部添加一个元素的副本。这是通过调用底层容器的成员函数 push_back() 来完成的。
emplace() 在 queue 的尾部直接添加一个元素。
push(T&& obj) 以移动的方式在 queue 的尾部添加元素。这是通过调用底层容器的具有右值引用参数的成员函数 push_back() 来完成的。
pop() 删除 queue 中的第一个元素。
swap(queue<T> &other_queue) 将两个 queue 容器适配器中的元素进行互换，需要注意的是，进行互换的 2 个 queue 容器适配器中存储的元素类型以及底层采用的基础容器类型，都必须相同。

特点

  1. 队列中的数据元素遵循“先进先出”（First In First Out）的原则，简称FIFO结构；
  2. 在队尾添加元素，在队头删除元素。

操作

c++ #include< queue> 。定义：queue< int > q; 

q.empty()               如果队列为空返回true，否则返回false
q.size()                返回队列中元素的个数
q.pop()                 删除队列首元素但不返回其值
q.front()               返回队首元素的值，但不删除该元素
q.push()                在队尾压入新元素
q.back()                返回队列尾元素的值，但不删除该元素

C++ 清空队列(queue)的几种方法

直接用空的队列对象赋值 

queue<int> q1;
// process
// ...
q1 = queue<int>();
使用swap，这种是最高效的，定义clear，保持STL容器的标准。 
void clear(queue<int>& q) {
    queue<int> empty;
    swap(empty, q);
}

队列保存一对数

queue<pair<int, int> > gq;
gq.push({ 10, 20 });

pair<int, int> p;
int x,y;
p = gq.front();
x = p.first;
y = p.second;

队列保存结构体

typedef struct
{
    int y;
    int xbegin;
    int xend;
}triple;
queue<triple> threadq[64];
delaytask.push({x1+delay,y-1});
p = threadq[c].front(); 
p.xbegin;
p.xend;

deque 双端队列

deque 容器也擅长在序列尾部添加或删除元素（时间复杂度为O(1)），而不擅长在序列中间添加或删除元素。

begin() 返回指向容器中第一个元素的迭代器。
end() 返回指向容器最后一个元素所在位置后一个位置的迭代器，通常和 begin() 结合使用。
rbegin() 返回指向最后一个元素的迭代器。
rend() 返回指向第一个元素所在位置前一个位置的迭代器。
cbegin() 和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
cend() 和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
crbegin() 和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
crend() 和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。

size() 返回实际元素个数。
max_size() 返回容器所能容纳元素个数的最大值。这通常是一个很大的值，一般是 232-1，我们很少会用到这个函数。
resize() 改变实际元素的个数。
empty() 判断容器中是否有元素，若无元素，则返回 true；反之，返回 false。
shrink _to_fit() 将内存减少到等于当前元素实际所使用的大小。

at() 使用经过边界检查的索引访问元素。

front() 返回第一个元素的引用。
back() 返回最后一个元素的引用。
assign() 用新元素替换原有内容。
push_back() 在序列的尾部添加一个元素。
push_front() 在序列的头部添加一个元素。
pop_back() 移除容器尾部的元素。
pop_front() 移除容器头部的元素。

insert() 在指定的位置插入一个或多个元素。
erase() 移除一个元素或一段元素。
clear() 移出所有的元素，容器大小变为 0。
swap() 交换两个容器的所有元素。
emplace() 在指定的位置直接生成一个元素。
emplace_front() 在容器头部生成一个元素。和 push_front() 的区别是，该函数直接在容器头部构造元素，省去了复制移动元素的过程。
emplace_back() 在容器尾部生成一个元素。和 push_back() 的区别是，该函数直接在容器尾部构造元素，省去了复制移动元素的过程。

emplace_back() not support <brace-enclosed initializer list> for this

priority_queue(优先队列)

自定义其中数据的优先级, 让优先级高的排在队列前面,优先出队

#include <queue>

优先级排序原理

缺省情况下priority_queue利用max-heap（大顶堆）完成对元素的排序，这个大顶堆是以vector为表现形式的complete binary tree（完全二叉树）。

声明

priority_queue<Type, Container, Functional>

//自定义降序1
class _c{
public:

 bool operator () (const pair<int, int> &p, const pair<int, int> &q) const
 {
  return p.first < q.first;
 }
};
priority_queue<pair<int, int>, vector<pair<int, int>>, _c> pq;
//自定义降序2
auto cmp = [](pair<int,int>&a, pair<int,int>&b){return a.second<=b.second;};
priority_queue<pair<int,int>,vector<pair<int,int>>, decltype(cmp)> q(cmp);
//升序队列
priority_queue <int,vector<int>,greater<int> > q;
//降序队列
priority_queue <int,vector<int>,less<int> >q;

//greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）

//默认排序是less，但是在priority_queue是降序。在其余数据结构里都是升序
priority_queue<pair<int, int>> answer;
//example
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> busy;
  1. Type 就是数据类型，
  2. Container 就是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector），
  3. Functional 就是比较的方式，当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆

基本操作

size() 返回优先队列的大小。
empty() 它验证队列是否为空。基于验证，它返回队列的状态。

top() 此函数用于寻址优先队列的最顶层元素。

emplace() 它在优先队列的顶部插入一个新元素。
push() 它将新元素插入优先队列。
pop() 它将优先级最高的元素从队列中删除。
swap() 它将优先队列的元素与具有相同类型和大小的另一个队列交换。

顺序容器与关联容器

顺序容器包括vector、deque、list、forward_list、array、string，所有顺序容器都提供了快速顺序访问元素的能力。

关联容器包括set、map

关联容器和顺序容器有着根本的不同：关联容器中的元素是按关键字来保存和访问的。与之相对，顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的。

关联容器不支持顺序容器的位置相关的操作。原因是关联容器中元素是根据关键字存储的，这些操作对关联容器没有意义。而且，关联容器也不支持构造函数或插入操作这些接受一个元素值和一个数量值得操作。

关联容器支持高效的关键字查找和访问。

二叉树

分类

存储方式

链表，或者数组(如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。)

链式结构如下，注意左右孩子节点

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* a = new TreeNode();
a->val = 9;
a->left = NULL;
a->right = NULL;

遍历方式

深度遍历： 前/中/后序遍历。

注意：这里前中后，其实指的就是中间节点/根节点的遍历顺序

heap 堆

堆(Heap)是计算机科学中一类特殊的数据结构的统称。

堆通常是一个可以被看做一棵完全二叉树的数组对象。

堆满足下列性质：

  • 堆中某个节点的值总是不大于或不小于其父节点的值。
  • 每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
  • 或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
  • 堆总是一棵完全二叉树。

STL操作

  • make_heap()​​将区间内的元素转化为heap.
  • ​push_heap()​​对heap增加一个元素.
  • ​​pop_heap()​​对heap取出下一个元素.
  • ​sort_heap()​​对heap转化为一个已排序群集.
int myints[] = {10,20,30,5,15};
vector<int> v(myints,myints+5);
vector<int>::iterator it;

make_heap (v.begin(),v.end());//male_heap就是构造一棵树，使得每个父结点均大于等于其子女结点
cout << "initial max heap   : " << v.front() << endl;

pop_heap (v.begin(),v.end());//pop_heap不是删除某个元素而是把第一个和最后一个元素对调后[first,end-1]进行构树，最后一个不进行构树
v.pop_back();//删除最后一个的结点
cout << "max heap after pop : " << v.front() << endl;

v.push_back(99);//在最后增加一个结点
push_heap (v.begin(),v.end());//重新构树
cout << "max heap after push: " << v.front() << endl;

sort_heap (v.begin(),v.end());//把树的结点的权值进行排序，排序后，序列将失去堆的特性
//请在使用这个函数前，确定序列符合堆的特性，否则会报错！

hash_map VS unordered_map

由于在C++标准库中没有定义散列表hash_map，标准库的不同实现者将提供一个通常名为hash_map的非标准散列表。因为这些实现不是遵循标准编写的，所以它们在功能和性能保证上都有微妙的差别。

从C++11开始，哈希表实现已添加到C++标准库标准。决定对类使用备用名称，以防止与这些非标准实现的冲突，并防止在其代码中有hash_table的开发人员无意中使用新类。

所选择的备用名称是unordered_map，它更具描述性，因为它暗示了类的映射接口和其元素的无序性质。

可见hash_map ， unordered_map本质是一样的，只不过 unordered_map被纳入了C++标准库标准。

map vs unordered_map

  1. map
  2. 内部数据的组织，基于红黑树实现，红黑树具有自动排序的功能，因此map内部所有的数据，在任何时候，都是有序的。其中每个键都是唯一的，可以插入或删除，但不能更改。但是与键关联的值可以更改。
  3. 红黑树是一种含有红黑结点并能自平衡的二叉查找/搜索树, 别称平衡二叉B树（symmetric binary B-trees）
  4. unordered_map(hash_map)
  5. 基于哈希表，数据插入和查找的时间复杂度很低，几乎是常数时间，而代价是消耗比较多的内存。底层实现上，使用一个下标范围比较大的数组来存储元素，形成很多的桶，利用hash函数对key进行映射到不同区域进行保存。
  6. 标准库的unordered_map，底层实现是基于hashtable的，其避免冲突的方法是使用开链（seperate chaining）法，这种做法是在每一个表格元素中维护一个list，每个表格元素称之为buket（桶）
                       | map              | unordered_map
---------------------------------------------------------
element ordering       | strict weak      | n/a 
                       |                  |
common implementation  | balanced tree    | hash table
                       | or red-black tree|  
                       |                  |
search time            | log(n)           | O(1) if there are no hash collisions
                       |                  | Up to O(n) if there are hash collisions 
                       |                  | O(n) when hash is the same for any key
                       |                  |     
Insertion time         | log(n)+rebalance | Same as search
                       |                  | 
Deletion time          | log(n)+rebalance | Same as search
                       |                  | 
needs comparators      | only operator <  | only operator ==
                       |                  |
needs hash function    | no               | yes
                       |                  |
common use case        | when good hash is| In most other cases. 
                       | not possible or  | 
                       | too slow. Or when|
                       | order is required|

map初始化

//c++11以上
map<string,int> m3 = {
    {"string",1}, {"sec",2}, {"trd",3}
    };

map<string,string> m4 = {
{"first","second"}, {"third","fourth"},
{"fifth","sixth"}, {"begin","end"}
};

unordered_map 哈希表

unordered_map<int, int> umap;
umap[a + b]++;

map的value是int，默认为0。可以直接++

unordered_map<int, int> cnt;
++cnt[num];
// c++17 支持
for (auto &[num, c] : cnt) {
}
// 否则
for (auto it = cnt.begin(); it != cnt.end(); ++it) {
    auto& key = it->first;
    auto& value = it->second;
    // 使用 key 和 i 进行操作
}
for (auto &[x, _] : cnt) {
    //sth
}
cnt.at(num) //unordered_map 类模板中，还提供有 at() 成员方法，和使用 [ ] 运算符一样，at() 成员方法也需要根据指定的键，才能从容器中找到该键对应的值；不同之处在于，如果在当前容器中查找失败，该方法不会向容器中添加新的键值对，而是直接抛出out_of_range异常。

插入元素

// insert 不能覆盖元素，已经存在会失败
mapStudent.insert(map<int, string>::value_type (1, "student_one"));
// 数组方式可以覆盖
mapStudent[1] = "student_one";

可以用pair来获得是否insert成功，程序如下

pair<map<int, string>::iterator, bool> Insert_Pair;

Insert_Pair = mapStudent.insert(map<int, string>::value_type (1, "student_one"));

我们通过pair的第二个变量来知道是否插入成功，它的第一个变量返回的是一个map的迭代器，如果插入成功的话Insert_Pair.second应该是true的，否则为false。

查找是否存在 count

用count函数来判定关键字是否出现，其缺点是无法定位数据出现位置,由于map的特性，一对一的映射关系，就决定了count函数的返回值只有两个，要么是0，要么是1，出现的情况，当然是返回1了

查找是否存在 find

通过 find() 方法得到的是一个正向迭代器，该迭代器的指向分以下 2 种情况：

  1. 当 find() 方法成功找到以指定元素作为键的键值对时，其返回的迭代器就指向该键值对；
  2. 当 find() 方法查找失败时，其返回的迭代器和 end() 方法返回的迭代器一样，指向容器中最后一个键值对之后的位置。
//查找成功
unordered_map<string, string>::iterator iter = umap.find("Python教程");
cout << iter->first << " " << iter->second << endl;
//查找失败
unordered_map<string, string>::iterator iter2 = umap.find("GO教程");
if (iter2 == umap.end()) {
    cout << "当前容器中没有以\"GO教程\"为键的键值对";
}

删除

mymap.erase ('c');               // erasing by key

set

  1. 按关键字有序保存元素：
  2. set(关键字即值，即只保存关键字的容器)；
  3. multiset(关键字可重复出现的set)；
  4. 无序集合：
  5. unordered_set(用哈希函数组织的set)；
  6. unordered_multiset(哈希组织的set，关键字可以重复出现)。

set就是关键字的简单集合。当只是想知道一个值是否存在时，set是最有用的。

在set中每个元素的值都唯一，而且系统能根据元素的值自动进行排序。set中元素的值不能直接被改变。set内部采用的是一种非常高效的平衡检索二叉树：红黑树，也称为RB树(Red-Black Tree)。RB树的统计性能要好于一般平衡二叉树。

set具备的两个特点：

  • set中的元素都是排序好的
  • set中的元素都是唯一的，没有重复的

常用函数

定义的参数compare可见，为了确定唯一性，需要有个值唯一表示存储的复杂类型

template < class T,                             // set::key_type/value_type
           class Compare = less<T>,        // set::key_compare/value_compare
           class Alloc = allocator<T>         // set::allocator_type
           > class set;

//初始化
set<char> vowel {'a','e','i','o','u'};

insert()–在集合中插入元素
emplace() 最大的作用是避免产生不必要的临时变量
erase()–删除集合中的元素
//删除 set 容器中值为 val 的元素
size_type erase (const value_type& val);
//删除 position 迭代器指向的元素
iterator  erase (const_iterator position);
//删除 [first,last) 区间内的所有元素
iterator  erase (const_iterator first, const_iterator last);
//第 1 种格式的 erase() 方法，其返回值为一个整数，表示成功删除的元素个数；
//后 2 种格式的 erase() 方法，返回值都是迭代器，其指向的是 set 容器中删除元素之后的第一个元素。

find()–返回一个指向被查找到元素的迭代器。返回值：该函数返回一个迭代器，该迭代器指向在集合容器中搜索的元素。如果找不到该元素，则迭代器将指向集合中最后一个元素之后的位置end
count()- 查找的bool结果
size()–集合中元素的数目

begin();            // 返回指向第一个元素的迭代器
end();              // 返回指向迭代器的最末尾处（即最后一个元素的下一个位置）
clear();            // 清除所有元素
count();            // 返回某个值元素的个数

swap()–交换两个集合变量

template <class T, class Compare, class Alloc>
  bool operator== ( const set<T,Compare,Alloc>& lhs,
                    const set<T,Compare,Alloc>& rhs ); // 和map类似的，重载相等判断

set::lower_bound(key)

參數：該函數接受單個強製性參數鍵，該鍵指定要返回其lower_bound的元素。

返回值：該函數返回一個指向容器中元素的迭代器，該迭代器等效於在參數中傳遞的k。如果set容器中不存在k，則該函數返回一個迭代器，該迭代器指向剛好大於k的下一個元素。如果參數中傳遞的鍵超過了容器中的最大值，則返回的迭代器等效於s.end()(特殊的迭代器指向最後一個元素)。

find example

//set.find(key)!=set.end() 的判断一般会比count快
auto p = points.find({x, y});
if (p != points.end()) {
 points.erase(p);
 ……
}

// 检查键30是否存在
if (mp.count(30))
 cout << "键30存在\n";
else
 cout << "键30不存在\n";

unordered_set

auto hash_p = [](const pair<int, int> &p) -> size_t {
  static hash<long long> hash_ll;
  return hash_ll(p.first + (static_cast<long long>(p.second) << 32));
 };
unordered_set<pair<int, int>, decltype(hash_p)> points(0, hash_p); //(0,hash_p)分别为迭代器的开始和结束的标记（数组多为数据源）
//多用于数组 set<int> iset(arr,arr+sizeof(arr)/sizeof(*arr));

类似的例子

auto hash = [](const std::pair<int, int>& p){ return p.first * 31 + p.second; };
std::unordered_set<std::pair<int, int>, decltype(hash)> u_edge_(8, hash);

上面的不是用lambda expression隐函数，而是定义函数的写法

struct pair_hash {
    inline std::size_t operator()(const std::pair<int,int> & v) const {
        return v.first*31+v.second;
    }
};
std::unordered_set< std::pair<int, int>,  pair_hash> u_edge_;

How to use unordered_set with custom types?

https://stackoverflow.com/questions/9729390/how-to-use-unordered-set-with-custom-types/9729747#9729747

set map 的区别

map和set都是C++的关联容器，其底层实现都是红黑树（RB-Tree）。由于 map 和set所开放的各种操作接口，RB-tree 也都提供了，所以几乎所有的 map 和set的操作行为，都只是转调 RB-tree 的操作行为。 map和set区别在于：

（1）map中的元素是key-value（关键字—值）对：关键字起到索引的作用，值则表示与索引相关联的数据；Set与之相对就是关键字的简单集合，set中每个元素只包含一个关键字。

（2）set的迭代器是const的，不允许修改元素的值；map允许修改value，但不允许修改key其原因是因为map和set是根据关键字排序来保证其有序性的，如果允许修改key的话，那么首先需要删除该键，然后调节平衡，再插入修改后的键值，调节平衡，如此一来，严重破坏了map和set的结构，导致iterator失效，不知道应该指向改变前的位置，还是指向改变后的位置。所以STL中将set的迭代器设置成const，不允许修改迭代器的值；而map的迭代器则不允许修改key值，允许修改value值。

（3）map支持下标操作，set不支持下标操作。map可以用key做下标，map的下标运算符[ ]将关键码作为下标去执行查找，如果关键码不存在，则插入一个具有该关键码和mapped_type类型默认值的元素至map中，因此下标运算符[ ]在map应用中需要慎用，const_map不能用，只希望确定某一个关键值是否存在而不希望插入元素时也不应该使用，mapped_type类型没有默认值也不应该使用。如果find能解决需要，尽可能用find。

map和multimap的区别

map不允许相同key值存在，multimap则允许相同的key值存在。

set/map 后insert 先输出

由于是有序的，对于int这种能比大小的，默认是输出是从小到大，可以改变。

  • set中存放的为数（整数，浮点数......），在set中会按从小到大排列这些数
  • 存放指针，都会按照地址排序
  • set 中存放的为string，存入的string会按字母表顺序排列
  • 至于存放类的话，还可以自己定义排列规则
  • 存放结构体？没定义大小关系的类？
  • *it 递增的顺序，存储的是指向某元素的指针，则是指针地址递增的顺序。

并差集

核心是

  1. 同一个并查集内的元素会指向同一个parent
  2. 可以维护并查集总个数Rank
  3. 和每个并查集的子集合元素个数
  4. 数据结构用数组和map都行

例子是LeetCode 1020

class UnionFind {
public:
    // 初始化未union的数组
    UnionFind(const vector<vector<int>> & grid) {//初始化遍历
        int m = grid.size(), n = grid[0].size();
        this->parent = vector<int>(m * n);
        //this->onEdge = vector<bool>(m * n, false);
        this->rank = vector<int>(m * n, 0);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    int index = i * n + j;
                    parent[index] = index;
                    if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                        //onEdge[index] = true;
                    }
                }
            }
        }
    }

    int find(int i) {
        // 原始版本
        return (parent[i] == i)? i : find(parent[i]);
        // “路径压缩”。在执行Find的过程中，将路径上的所有节点都直接连接到根节点上。
        return (parent[i] == i)? i : (parent[i] = find(parent[i]));
    }

    void uni(int x, int y) {
        int rootx = find(x);
        int rooty = find(y);
        if (rootx != rooty) {
            // "按秩合并"。实际上就是在合并两棵树时，将高度较小的树合并到高度较大的树上。
            if (rank[rootx] > rank[rooty]) {
                parent[rooty] = rootx;
            } else if (rank[rootx] < rank[rooty]) {
                parent[rootx] = rooty;
            } else {
                parent[rooty] = rootx;
                rank[rootx]++;
            }
        }
    }

private:
    vector<int> parent;
    vector<int> rank;  
    // 如果带合并的元素表示有负数表示，或者不是连续表示的。可以使用map
    map<int, int> parent;//定义一个并查集
    map<int, int> ranks;//定义树的深
};

对于不确定元素个数来初始化的

class DisjointSet {
  public:
    std::unordered_map<BBLID, BBLID> parent;

    BBLID Find(BBLID l) {
        auto it = parent.find(l);
        if (it == parent.end()) {
            parent[l] = l;
        }
        else {
            while (parent[l] != l) {
                // 路径压缩部分
                parent[l] = parent[parent[l]];
                l = parent[l];
            }
        }
        return l;
    }

    void Union(BBLID m, BBLID n) {
        BBLID x = Find(m);
        BBLID y = Find(n);
        parent[x] = y;
    }
};

emplace VS push

push() adds a copy of an already constructed object into the queue as a parameter, it takes an object of the queue's element type.

emplace() constructs a new object in-place at the end of the queue. It takes as parameters the parameters that the queue's element types constructor takes.

If your usage pattern is one where you create a new object and add it to the container, you shortcut a few steps(creation of a temporary object and copying it) by using emplace().

数组

int array[2][3] = {
  {0, 1, 2},
  {3, 4, 5}
    };

数组初始化为0

//直接初始化为0
int a[SIZE]={0};

#include<string.h>
int a[SIZE];
memset(a, 0, sizeof(a));
memset(a, 0, sizeof(int)*1000);//这里的1000是数组大小，需要多少替换下就可以了。

注意 memset是按照字节进行赋值，即对每一个字节赋相同值。除开0和-1，其他值都是不安全的，不会赋值期望的值。比如int是四个字节。

  • memset（a，127，sizeof（a）），全部初始化为int的较大值，即2139062143(int 最大值为2147483647)；
  • memset（a，128，sizeof（a）），全部初始化为一个很小的数，比int最小值略大，为-2139062144。

calloc & malloc 

//区分
//calloc() 函数是动态申请内存函数之一，相当于用malloc函数申请并且初始化一样，calloc函数会将申请的内存全部初始化为0。
int *res = (int*)calloc(numsSize, sizeof(int)); 
//方法二：
int *res = (int*)malloc(numsSize * sizeof(int));
memset(res, 0, numsSize * sizeof(int));
//错误写法： memset(res, 0, sizeof(res)); res是指针变量，不管 res 指向什么类型的变量，sizeof( res ) 的值都是 4。

new

int *p = new int();//此时p指向内存的单变量被初始化为0
int *p = new int (5);//此时p指向内存的单变量被初始化为5
int *p = new int[100]()//此时p指向数组首元素，且数组元素被初始化为0
//c++11 允许列表初始化，因此也有了以下几种形式形式
int *p = new int{}//p指向的单变量被初始化为0
int *p = new int{8}//p指向变量被初始化为8
int *p = new int[100]{}//p指向的数组被初始化为0
int *p = new int[100]{1,2,3}//p指向数组的前三个元素被初始化为1，2，3，后边97个元素初始化为0；

new 三维数组

建议老实用vector 

int ***array;
// 假定数组第一维为 m， 第二维为 n， 第三维为h
// 动态分配空间
array = new int **[m];
for( int i=0; i<m; i++ )
{
    array[i] = new int *[n];
    for( int j=0; j<n; j++ )
    {
        array[i][j] = new int [h];
    }
}
//释放
for( int i=0; i<m; i++ )
{
    for( int j=0; j<n; j++ )
    {
        delete[] array[i][j];
    }
    delete[] array[i];
}
delete[] array;

Leetcode support VLA

  • The C++ standard does not officially support Variable Length Arrays (VLA), but some compilers, such as g++ and Clang++, may accept it as valid syntax as an extension to the language.
  • leetcode uses g++ 5.4.0 compiler for C++ compilation. It supports variable length array definitions. After ISO C99 specification, arrays with variable length declarations are allowed.
  • The storage is allocated at the point of declaration and deallocated when the block scope containing the declaration exits.
  • And memory consumption differ significantly.
class Solution {
public:
    int minimizeConcatenatedLength(vector<string>& words) {
        int n = words.size();
        int f[n][26][26];

pair

pair<T1, T2> p1;            //创建一个空的pair对象（使用默认构造），它的两个元素分别是T1和T2类型，采用值初始化。
pair<T1, T2> p1(v1, v2);    //创建一个pair对象，它的两个元素分别是T1和T2类型，其中first成员初始化为v1，second成员初始化为v2。
make_pair(v1, v2);          // 以v1和v2的值创建一个新的pair对象，其元素类型分别是v1和v2的类型。
p1 < p2;                    // 两个pair对象间的小于运算，其定义遵循字典次序：如 p1.first < p2.first 或者 !(p2.first < p1.first) && (p1.second < p2.second) 则返回true。
p1 == p2；                  // 如果两个对象的first和second依次相等，则这两个对象相等；该运算使用元素的==操作符。
p1.first;                   // 返回对象p1中名为first的公有数据成员
p1.second;                 // 返回对象p1中名为second的公有数据成员

array

array也位于名称空间std中,与数组同样,array对象的长度也是固定的,也使用栈(静态内存分配),而不是自由存储区,所以其效率与数组相同,但更方便,更安全.

array<typeName, nElem> arr;

# include <array>
using namespace std;
array<int, 5> ai;
array<double, 4> ad = {1.1,1.2,1.2,1.3};

//通过如下创建 array 容器的方式，可以将所有的元素初始化为 0 或者和默认元素类型等效的值：
std::array<double, 10> values {};
//使用该语句，容器中所有的元素都会被初始化为 0.0。

//二维
std::array<std::array<int, 2>, 3> m = { {1, 2}, {3, 4}, {5, 6} };

单链表 （自定义）

// 单链表
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};

ListNode* head = new ListNode(5);

或者
ListNode* head = new ListNode();
head->val = 5;

while(result != nullptr && result->val == val){
 //多使用nullptr 
 ListNode* tmp_free = result;
 result = result->next;
 delete tmp_free; // 注意释放空间
}

nullptr是一个关键字，可以在所有期望为NULL的地方使用。

  • 与NULL一样，可与任何指针类型相比较。
  • 与NULL不同，只能被赋值给指针类型，它不能隐式转换，也不能与整型相比较。与NULL通常被定义为整数0的宏定义 之间来区分。

list 双向链表

STL list 容器，又称双向链表容器，即该容器的底层是以双向链表的形式实现的。

  • 特点：
  • 可以看到，list 容器中各个元素的前后顺序是靠指针来维系的，每个元素都配备了 2 个指针，分别指向它的前一个元素和后一个元素。其中第一个元素的前向指针总为 null，因为它前面没有元素；同样，尾部元素的后向指针也总为 null。
  • vector是连续的容器，而list是非连续的容器，即vector将元素存储在连续的存储器中，而list存储在不连续的存储器中。
  • 优点
  • list 容器具有一些其它容器（array、vector 和 deque）所不具备的优势，
  • 可以在序列已知的任何位置快速插入或删除元素（时间复杂度为O(1)）。
  • 并且在 list 容器中移动元素，也比其它容器的效率高。
  • 缺点
  • 不能像 array 和 vector 那样，通过位置直接访问元素。
    • 举个例子，如果要访问 list 容器中的第 6 个元素，它不支持容器对象名[6]这种语法格式，正确的做法是从容器中第一个元素或最后一个元素开始遍历容器，直到找到该位置。
  • 应用场景：需要对序列进行大量添加或删除元素的操作，而直接访问元素的需求却很少，这种情况建议使用 list 容器存储序列。
list<pair<unordered_set<string>, int>> lst;
unordered_map<string, list<pair<unordered_set<string>, int>>::iterator> nodes;

auto cur = nodes[key], nxt = next(cur); //对迭代器使用next
nodes[key] = lst.emplace(nxt, s, cur->second + 1);

*lst.rbegin()->first.begin(); //链表最后元素的first也就是unordered_set<string>的第一个

emplace & emplace_front

C ++ List emplace()函数在指定位置插入新元素，并且列表的大小增加一。

语法 iterator emplace(iterator pos, value_type val); 参数

pos：它定义了要插入新元素的位置。

val：要在指定位置插入的新值。

返回值

它返回指向新构造元素的迭代器。

vector

构造函数

vector(int nSize)   //创建一个vector,元素个数为nSize

//指定值初始化，ilist5被初始化为包含7个值为3的int
vector(int nSize,const t& t)//创建一个vector，元素个数为nSize,且值均为t
vector<int> ilist5(7,3);
//区分列表初始化, 包含7 和 3两个元素
vector<int> ilist5{7,3};

//改变大小
vals.reserve(cnt.size());

二维vector, 两个维度的长度都未知时：

vector<vector<bool>> name (xSize, vector<bool>(ySize, false));
//leetcode假如写在函数外，class public下，第二维度为空
vector<vector<int>> alphaIndexList{26, vector<int>(0)}; 
//指针使用
vector<int>* todo;
todo= &alphaIndexList[i];
int n = todo->size(); // (*todo).size();
for(auto &x: *todo)

二维vector, 已知某一个维度的大小:

vector<int> alphaIndexList[26];
alphaIndexList[i].push_back(x);

返回表示

vector<int> func() {
    //sth
    return {it->second, i}; //no []
    //or
    return {};
}

元素排序

如果需要元素有序，考虑stable_sort

//默认是从低到高，加入std::greater<int>() 变成从高到低排序
sort(nums.begin(),nums.end(),std::greater<int>());

//vector of pair
vector<pair<int, char>> arr = {{a, 'a'}, {b, 'b'}, {c, 'c'}};

//c++14 
std::sort(v.begin(), v.end(), [](auto &left, auto &right) {
    return left.second < right.second;
});

//C++11 using lambdas
sort(arr.begin(), arr.end(), 
 [](const pair<int, char> & p1, const pair<int, char> & p2) {
  return p1.first > p2.first;
 }
);

//origin 
struct sort_pred {
    bool operator()(const std::pair<int,int> &left, const std::pair<int,int> &right) {
        return left.second < right.second;
    }
};
std::sort(v.begin(), v.end(), sort_pred());

增加函数

void push_back(const T& x)      :向量尾部增加一个元素X
void emplace_back(const T& x)
iterator insert(iterator it,const T& x)   :向量中迭代器指向元素前增加一个元素x
result.insert(result.begin()+p,x);     :在result的index为p的位置插入元素
iterator insert(iterator it,int n,const T& x) :向量中迭代器指向元素前增加n个相同的元素x
iterator insert(iterator it,const_iterator first,const_iterator last):向量中迭代器指向元素前插入另一个相同类型向量的[first,last)间的数据

删除函数

iterator erase(iterator it)     :删除向量中迭代器指向元素
iterator erase(iterator first,iterator last):删除向量中[first,last)中元素
void pop_back()        :删除向量中最后一个元素
void clear()        :清空向量中所有元素

遍历查找函数

reference at(int pos)  :返回pos位置元素的引用
reference front()   :返回首元素的引用
reference back()   :返回尾元素的引用
iterator begin()   :返回向量头指针，指向第一个元素
iterator end()    :返回向量尾指针，指向向量最后一个元素的下一个位置
reverse_iterator rbegin() :反向迭代器，指向最后一个元素
reverse_iterator rend()  :反向迭代器，指向第一个元素之前的位置

upper_bound(prefix_sum.begin(),prefix_sum.end(),a) : 查找满足prefix_sum[i]<=a的最大i

判断函数

bool empty() const   :判断向量是否为空，若为空，则向量中无元素

大小函数

int size() const  :返回向量中元素的个数
int capacity() const :返回当前向量所能容纳的最大元素值
int max_size() const :返回最大可允许的vector元素数量值

#include <algorithm> 
// C++ vector 容器裡使用 std::max_element 找最大值（或者min_element）的範例，std::max_element 會回傳一個迭代器，這個迭代器會指向該容器範圍內最大值的元素，
vector<int>::iterator result = std::max_element(v.begin(), v.end());
int index = result - v.begin();
int value = (*result)

片段的截取

vector<int> Arrs {1,2,3,4,5,6,7,8,9}; // 假设有这么个数组,要截取中间第二个元素到第四个元素：2，3，4
vector<int>::const_iterator First = Arrs.begin() + 1; // 找到第二个迭代器
vector<int>::const_iterator Second = Arrs.begin() + 3; // 找到第三个迭代器
vector<int> Arrs2(First, Second); // 将值直接初始化到Arrs2

迭代器是指可在容器对象上遍访的对象

或者assign()功能函数实现截取

assign() 功能函数是vector容器的成员函数。原型：

1:void assign(const_iterator first,const_iterator last);//两个指针，分别指向开始和结束的地方 2:void assign(size_type n,const T& x = T()); //n指要构造的vector成员的个数， x指成员的数值，他的类型必须与vector类型一致！

vector<int> Arrs {1,2,3,4,5,6,7,8,9}; // 假设有这么个数组,要截取中间第二个元素到第四个元素：2，3，4
vector<int>::const_iterator First = Arrs.begin() + 1; // 找到第二个迭代器
vector<int>::const_iterator Second = Arrs.begin() + 3; // 找到第三个迭代器
vector<int> Arr2;
Arr2.assign(First,Second); //使用assign() 成员函数将Arrs对应位置的值存入Arrs2数组中

迭代器的使用

#include <algorithm> 
double max = *max_element(vector.begin(), vector.end());
cout<<"Max value: "<<max<<endl;

vector<int>::iterator i;  //定义正向迭代器
for (i = v.begin(); i != v.end(); ++i) {  //用迭代器遍历容器
    cout << *i << " ";  //*i 就是迭代器i指向的元素
    *i *= 2;  //每个元素变为原来的2倍
}
cout << endl;
//用反向迭代器遍历容器
for (vector<int>::reverse_iterator j = v.rbegin(); j != v.rend(); ++j)
    cout << *j << " ";

迭代器之间的减法是被允许的，两个迭代器相减返回是它们之间的距离，这个距离是一个符号类整型（signed），意味着两个迭代器之间相减可能是正数、零或者负数。

其他赋值函数

void swap(vector&)    :交换两个同类型向量的数据
void assign(int n,const T& x) :设置向量中前n个元素的值为x
void assign(const_iterator first,const_iterator last):向量中[first,last)中元素设置成当前向量元素

#include <algorithm> //或者#include <bits/stdc++.h>
reverse(a.begin(), a.end());
std::reverse(a,a+5);  //转换0～5下标的元素

fill(ForwardIt first, ForwardIt last, const T& value) //fill函数的作用是：将一个区间的元素都赋予val值。函数参数：fill(first,last,val);//first为容器的首迭代器，last为容器的末迭代器，val为将要替换的值。
fill_n(OutputIt first, Size count, const T& value) //fill_n函数的作用是：给你一个起始点，然后再给你一个数值count和val。把从起始点开始依次赋予count个元素val的值。

vector具体实现

（1）扩容

vector的底层数据结构是数组。

当vector中的可用空间耗尽时，就要动态第扩大内部数组的容量。直接在原有物理空间的基础上追加空间？这不现实。数组特定的地址方式要求，物理空间必须地址连续，而我们无法保证其尾部总是预留了足够空间可供拓展。一种方法是，申请一个容量更大的数组，并将原数组中的成员都搬迁至新空间，再在其后方进行插入操作。新数组的地址由OS分配，与原数据区没有直接的关系。新数组的容量总是取作原数组的两倍。

（2）插入和删除

插入给定值的过程是，先找到要插入的位置，然后将这个位置（包括这个位置）的元素向后整体移动一位，然后将该位置的元素复制为给定值。删除过程则是将该位置以后的所有元素整体前移一位。

（2）vector的size和capacity

size指vector容器当前拥有的元素个数，capacity指容器在必须分配新存储空间之前可以存储的元素总数，capacity总是大于或等于size的。

size() – 返回目前存在的元素数。即： 元素个数
capacity() – 返回容器能存储 数据的个数。 即：容器容量
reserve() --设置 capacity 大小
resize() --设置 size ，重新指定有效元素的个数 ，区别与reserve()指定 容量的大小
clear() --清空所有元素，把size设置成0，capacity不变

针对capacity这个属性，STL中的其他容器，如list map set deque，由于这些容器的内存是散列分布的，因此不会发生类似realloc()的调用情况，因此我们可以认为capacity属性针对这些容器是没有意义的，因此设计时这些容器没有该属性。

在STL中，拥有capacity属性的容器只有vector和string。

为何map和set的插入删除效率比用其他序列容器高？

因为对于关联容器来说，不需要做内存拷贝和内存移动。说对了，确实如此。map和set容器内所有元素都是以节点的方式来存储，其节点结构和链表差不多，指向父节点和子节点。

插入的时候只需要稍做变换，把节点的指针指向新的节点就可以了。删除的时候类似，稍做变换后把指向删除节点的指针指向其他节点就OK了。这里的一切操作就是指针换来换去，和内存移动没有关系。

std::map的优势: 内存池的管理

自己实现的map需要自己去new一些节点，当节点特别多， 而且进行频繁的删除和插入的时候，内存碎片就会存在，而STL采用自己的Allocator分配内存，以内存池的方式来管理这些内存，会大大减少内存碎片，从而会提升系统的整体性能。

为什么有时unordered_map, 性能比map差

注意到很多代码使用 std::unordered_map 因为“哈希表更快”。但是对于小map，具有很高的内存开销。

网上有许多map和unorderd_map的比较，但是都是大例子。

下载一个，比较N比较小时的速度。前面是插入，后面是读取时间。编译g++ -std=c++11 -O3 map.cpp -o main

$ ./main
insert N=15,cost=               9e-06 sec
[] N=15,cost=                   5e-06 sec
insert N=15,cost=               3e-06 sec
getall find not N=15,cost=      1.2e-05 sec
getall find N=15,cost=          1.4e-05 sec
getall find not N=15,cost=      1e-05 sec
getall cout N=15,cost=          1.3e-05 sec
getall cout not N=15,cost=      1.3e-05 sec

insert N=15,cost=               6e-06 sec
[] N=15,cost=                   2e-06 sec
insert N=15,cost=               3e-06 sec
getall find not N=15,cost=      1.9e-05 sec
getall find N=15,cost=          2e-05 sec
getall find not N=15,cost=      1.9e-05 sec
getall cout N=15,cost=          3.7e-05 sec
getall cout not N=15,cost=      2e-05 sec

insert N=15,cost=               3e-06 sec
[] N=15,cost=                   2e-06 sec
insert N=15,cost=               1e-06 sec
getall find not N=15,cost=      2e-05 sec
getall find N=15,cost=          1.8e-05 sec
getall find not N=15,cost=      1.9e-05 sec
getall cout N=15,cost=          1.8e-05 sec
getall cout not N=15,cost=      1.9e-05 sec

insert N=15,cost=               5e-06 sec
[] N=15,cost=                   1e-06 sec
insert N=15,cost=               2e-06 sec
getall find not N=15,cost=      7e-06 sec
getall find N=15,cost=          8e-06 sec
getall find not N=15,cost=      7e-06 sec
getall cout N=15,cost=          8e-06 sec
getall cout not N=15,cost=      1e-05 sec

可见创建 unorderd_map快于map。

map find没命中会很快，差不多unorderd_map。

但是map命中会慢很多。1.2e-05 >> 2e-06

array,vector与数组的区别

共同点

（1.）都和数组相似，都可以使用标准数组的表示方法来访问每个元素（array和vector都对下标运算符[ ]进行了重载）

（2.）三者的存储都是连续的，可以进行随机访问

不同点

（0.）数组是不安全的，array和vector是比较安全的（有效的避免越界等问题）

（1.）array对象和数组存储在相同的内存区域（栈）中，vector对象存储在自由存储区（堆）malloc和new的空间也是在堆上，原因是栈的空间在编译代码的时候就要确定好，堆空间可以运行时分配。

（2.）array可以将一个对象赋值给另一个array对象，但是数组不行

（3.）vector属于变长的容器，即可以根据数据的插入和删除重新构造容器容量；但是array和数组属于定长容器

（4.）vector和array提供了更好的数据访问机制，即可以使用front()和back()以及at()（at()可以避免a[-1]访问越界的问题）访问方式，使得访问更加安全。而数组只能通过下标访问，在写程序中很容易出现越界的错误

（5.）vector和array提供了更好的遍历机制，即有正向迭代器和反向迭代器

（6.）vector和array提供了size()和Empty()，而数组只能通过sizeof()/strlen()以及遍历计数来获取大小和是否为空

（7.）vector和array提供了两个容器对象的内容交换，即swap()的机制，而数组对于交换只能通过遍历的方式逐个交换元素

（8.）array提供了初始化所有成员的方法fill（）

（9.）由于vector的动态内存变化的机制，在插入和删除时，需要考虑迭代的是否有效问题

（10.）vector和array在声明变量后，在声明周期完成后，会自动地释放其所占用的内存。对于数组如果用new[ ]/malloc申请的空间，必须用对应的delete[ ]和free来释放内存

vector 存储可变大小类型

  • vector是变长的连续存储，
  • 对于简单的类型，是直接存储
  • 对于复杂的类，存储的是，该元素的信息（比如新构造元素的begin地址,end地址,capacity信息)
vector<vector<int>> v2d(3,vector<int>(0));      // 间隔 6 个int
// vector<set<int>> v2d(3);                     // 间隔 12 个int 
// vector<unordered_set<int>> v2d(3);           // 间隔 14 个int 
// vector<map<int,int>> v2d(3);                 // 间隔 12 个int 
// vector<unordered_map<int,int>> v2d(3);       // 间隔 14 个int 

const int STEP = 6;
for(int i = 0; i<v2d.size(); i++){
    cout << " " << &v2d[i] << endl;
    for(int j=0; j<STEP; j++)
        cout << " " << hex << *(int *)((void *)(&v2d[i])+j*4);
    cout << endl;
}

// add elements to v2d[0]
const int ADDNUM = 10;
for(int i = 0; i<ADDNUM; i++){
    v2d[0].emplace_back(2);
    // v2d[0].insert(i);
    // v2d[0][i]=i*i;
}

// check the space change
cout << "Ele[0] size : " << v2d[0].size() << endl;
for(int i = 0; i<v2d.size(); i++){
    cout << " " << &v2d[i] << endl;
}

//check ele[0] location
cout << endl;
for(int i = 0; i<ADDNUM; i++){
    cout << " " << &v2d[0][i];
}

hash

哈希

#include<functional> 
auto hash_p = [](const pair<int, int> &p) -> size_t {
            static hash<long long> hash_ll;
            return hash_ll(p.first + (static_cast<long long>(p.second) << 32));//64位高低一半存储x和y
        };

static_cast 用于良性类型转换，一般不会导致意外发生，风险很低。

hash <K> 模板专用的算法取决于实现，但是如果它们遵循 C++14 标准的话，需要满足一些具体的要求。这些要求如下：

  • 不能拋出异常
  • 对于相等的键必须产生相等的哈希值
  • 对于不相等的键产生碰撞的可能性必须最小接近 size_t 最大值的倒数

C++11技巧

https://shaojiemike.notion.site/C-11-a94be53ca5a94d34b8c6972339e7538a

map VS unordered_map 时间比较

/**
比较map、hash_map和unordered_map的执行效率以及内存占用情况
**/
#include "parallel-hashmap/parallel_hashmap/phmap.h"
#include <sys/types.h>
#include <unistd.h>
#include <sys/time.h> 
#include <iostream>
#include <fstream>
#include <string>
#include <map>
// #include <ext/hash_map>
#include <tr1/unordered_map>
#include <unordered_map>

#include <cstring>

using namespace std;

// using namespace __gnu_cxx;

using namespace std::tr1;

#define N 15  //分别测试N=100,000、N=1,000,000、N=10,000,000以及N=100,000,000
#define LOOP 50

//分别定义MapKey=map<int,int>、hash_map<int,int>、unordered_map<int,int>
typedef map<int,int> MapKey;          //采用map
//typedef hash_map<int,int> MapKey;     //采用hash_map
typedef std::unordered_map<int,int> MapKey1;  //采用unordered_map
typedef tr1::unordered_map<int,int> MapKey2;  //采用unordered_map
typedef phmap::flat_hash_map<int,int> MapKey3;  //采用unordered_map





int GetPidMem(pid_t pid,string& memsize)
{
 char filename[1024];

 snprintf(filename,sizeof(filename),"/proc/%d/status",pid);

 ifstream fin;

 fin.open(filename,ios::in);
 if (! fin.is_open())
 {
  cout<<"open "<<filename<<" error!"<<endl;
  return (-1);
 }

 char buf[1024];
 char size[100];
 char unit[100];

 while(fin.getline(buf,sizeof(buf)-1))
 {
  if (0 != strncmp(buf,"VmRSS:",6))
   continue;

  sscanf(buf+6,"%s%s",size,unit);

  memsize = string(size)+string(unit);
 }

 fin.close();

 return 0;
}


template<typename T>
void testMap(T MyMap){
 struct timeval begin;

 struct timeval end;
 gettimeofday(&begin,NULL);

 for(int i=0;i<N;++i){
  MyMap.insert(make_pair(i,i));
 }

 gettimeofday(&end,NULL);

 cout<<"insert N="<<N<<",cost=\t\t"<<end.tv_sec-begin.tv_sec + float(end.tv_usec-begin.tv_usec)/1000000<<" sec"<<endl;

 MyMap.clear();

 gettimeofday(&begin,NULL);

 for(int i=0;i<N;++i){
  MyMap[i]=i;
 }

 gettimeofday(&end,NULL);

 cout<<"[] N="<<N<<",cost=\t\t\t"<<end.tv_sec-begin.tv_sec + float(end.tv_usec-begin.tv_usec)/1000000<<" sec"<<endl;

 MyMap.clear();

 gettimeofday(&begin,NULL);

 for(int i=0;i<N;++i){
  MyMap.insert(make_pair(i,i));
 }

 gettimeofday(&end,NULL);

 cout<<"insert N="<<N<<",cost=\t\t"<<end.tv_sec-begin.tv_sec + float(end.tv_usec-begin.tv_usec)/1000000<<" sec"<<endl;

 gettimeofday(&begin,NULL);

 for(int t=0; t<LOOP; t++)
 for(int i=N;i<2*N;++i){
  MyMap.find(i);
 }

 gettimeofday(&end,NULL);

 cout<<"getall find not N="<<N<<",cost=\t"<<end.tv_sec-begin.tv_sec + float(end.tv_usec-begin.tv_usec)/1000000<<" sec"<<endl;


 gettimeofday(&begin,NULL);

 for(int t=0; t<LOOP; t++)
 for(int i=0;i<N;++i){
  MyMap.find(i);
 }

 gettimeofday(&end,NULL);

 cout<<"getall find N="<<N<<",cost=\t\t"<<end.tv_sec-begin.tv_sec + float(end.tv_usec-begin.tv_usec)/1000000<<" sec"<<endl;

 gettimeofday(&begin,NULL);

 for(int t=0; t<LOOP; t++)
 for(int i=N;i<2*N;++i){
  MyMap.find(i);
 }

 gettimeofday(&end,NULL);

 cout<<"getall find not N="<<N<<",cost=\t"<<end.tv_sec-begin.tv_sec + float(end.tv_usec-begin.tv_usec)/1000000<<" sec"<<endl;

 gettimeofday(&begin,NULL);

 for(int t=0; t<LOOP; t++)
 for(int i=0;i<N;++i){
  MyMap.count(i);
 }

 gettimeofday(&end,NULL);

 cout<<"getall cout N="<<N<<",cost=\t\t"<<end.tv_sec-begin.tv_sec + float(end.tv_usec-begin.tv_usec)/1000000<<" sec"<<endl;

 gettimeofday(&begin,NULL);

 for(int t=0; t<LOOP; t++)
 for(int i=N;i<2*N;++i){
  MyMap.count(i);
 }

 gettimeofday(&end,NULL);

 cout<<"getall cout not N="<<N<<",cost=\t"<<end.tv_sec-begin.tv_sec + float(end.tv_usec-begin.tv_usec)/1000000<<" sec"<<endl;

 cout<<endl;

}

int main(int argc, char *argv[])
{

 MapKey map;
 MapKey1 map1;
 MapKey2 map2;

 MapKey3 map3;

 testMap<MapKey>(map);
 testMap<MapKey1>(map1);
 testMap<MapKey2>(map2);
 testMap<MapKey3>(map3);


 string memsize;

 GetPidMem(getpid(),memsize);

 cout<<memsize<<endl;

 return 0;
}

需要进一步的研究学习

暂无

遇到的问题

暂无

开题缘由、总结、反思、吐槽~~

参考文献

https://www.runoob.com/w3cnote/cpp-vector-container-analysis.html

【C++容器】数组和vector、array三者区别和联系 https://blog.51cto.com/liangchaoxi/4056308

https://blog.csdn.net/y601500359/article/details/105297918

———————————————— 版权声明：本文为CSDN博主「stitching」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/qq_40250056/article/details/114681940

———————————————— 版权声明：本文为CSDN博主「FishBear_move_on」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/haluoluo211/article/details/80877558

———————————————— 版权声明：本文为CSDN博主「SOC罗三炮」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/luolaihua2018/article/details/109406092

———————————————— 版权声明：本文为CSDN博主「鱼思故渊」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/yusiguyuan/article/details/40950735

  • 分类于 Tutorials
  • 需要 9 分钟阅读时间

MPI

简介

  • Message Passing Interface (消息传递接口 MPI) is a standardized and portable message-passing standard designed to function on parallel computing architectures.[1]
  • The MPI standard defines the syntax 语法 and semantics 语意 of library routines that are useful to a wide range of users writing portable message-passing programs in C, C++, and Fortran.
  • There are several open-source MPI implementations （MPICH，Open MPI）, which fostered the development of a parallel software industry, and encouraged development of portable and scalable large-scale parallel applications.

历史

  • 1994.6 MPI-1
  • 主要的MPI-1模型没有共享内存的概念，
  • point-to-point send/recieve, gather/reduce, synchronous, asynchronous,
  • MPI-2只有一个有限的分布式共享内存的概念。尽管如此，MPI程序通常在共享内存计算机上运行，MPICH和Open MPI都可以使用共享内存进行消息传输（如果可用的话）。
  • 围绕MPI模型（与显式共享内存模型相反）设计程序在NUMA体系结构上运行时具有优势，因为MPI鼓励内存局部性。显式共享内存编程是在MPI-3中引入的。

实现原理简介

虽然MPI属于OSI参考模型的第5层和更高层，但实现可以覆盖大多数层，其中在传输层中使用套接字和传输控制协议（TCP）。

与RDMA的区别

MPI hardware research focuses on implementing MPI directly in hardware, for example via processor-in-memory, building MPI operations into the microcircuitry of the RAM chips in each node. By implication, this approach is independent of language, operating system, and CPU, but cannot be readily updated or removed. MPI硬件研究的重点是直接在硬件中实现MPI，例如通过内存处理器，将MPI操作构建到每个节点中的RAM芯片的微电路中。通过暗示，这种方法独立于语言、操作系统和CPU，但是不能容易地更新或删除。

Another approach has been to add hardware acceleration to one or more parts of the operation, including hardware processing of MPI queues and using RDMA to directly transfer data between memory and the network interface controller（NIC 网卡） without CPU or OS kernel intervention. 另一种方法是将硬件加速添加到操作的一个或多个部分，包括MPI队列的硬件处理以及使用RDMA在存储器和网络接口控制器之间直接传输数据，而无需CPU或OS内核干预。

与管道的区别

进程间通信都是Inter-process communication（IPC）的一种。常见有如下几种：

  1. 文件，进程写文件到磁盘，其余进程能并行读取。
  2. Memory-mapped file 存储在内存里的文件
  3. signal，多为控制信号
  4. 信号量(计数器)
  5. Network Socket
  6. Message queue 消息队列（没用过
  7. 管道
  8. Anonymous pipe 匿名管道（命令行的结果传递|
    1. 可用于单向进程间通信（IPC）的单FIFO通信通道
    2. A unidirectional data channel using standard input and output.
  9. named pipe 有名管道
    1. 持久化，mkfifo,具有p的文件属性
    2. cat tail的例子说明，不建立写读连接会阻塞。
  10. Shared memory 共享内存（OpenMP
  11. Message passing 消息传递（类似MPI

与OpenMP的关系

线程共享存储器编程模型（如Pthreads和OpenMP）和消息传递编程（MPI/PVM）可以被认为是互补的，并且有时在具有多个大型共享存储器节点的服务器中一起使用。

基本概念

后四个是MPI-2独有的

  1. Communicator 进程组
  2. Point-to-point basics 点对点同步异步通信
  3. Collective basics 集体通信（eg. alltoall
  4. Derived data types 派生数据类型（自定义传输数据结构
  5. One-sided communication
  6. MPI-2定义了三个单边通信操作，分别是对远程存储器的写入、从远程存储器的读取以及跨多个任务对同一存储器的归约操作。
  7. Dynamic process management 类似进程池？没用过
  8. 并行文件IO

编程

C++ 查看在哪个节点

#include <unistd.h>
char hostname[100];
gethostname(hostname,sizeof(hostname));
printf( "Hello world from process %d of %d: host: %s\n", rank, size, hostname);

运行命令

输出X个当前机器hostname

mpirun -np 6 -machinefile ./machinelist ./a.out 即可多节点执行。

问题

MPI_Finalize()之后 ,MPI_Init()之前 https://www.open-mpi.org/doc/v4.0/man3/MPI_Init.3.php

不同的进程是怎么处理串行的部分的？都执行（重复执行？）。执行if(rank=num),那岂不是还要同步MPI_Barrier()。

而且写同一个文件怎么办？

对等模式和主从模式

MPI的两种最基本的并行程序设计模式 即对等模式和主从模式。

对等模式：各个部分地位相同，功能和代码基本一致，只不过是处理的数据或对象不同，也容易用同样的程序来实现。

主从模式：分为主进程和从进程，程序通信进程之间的一种主从或依赖关系 。MPI程序包括两套代码，主进程运行其中一套代码，从进程运行另一套代码。

程序并行可行性分析

圈收缩(cycle shrinking)－此变换技术一般用于依赖距离大于1的循环中，它将一个串行循环分成两个紧嵌套循环，其中外层依然串行执行，而内层则是并行执行（一般粒度较小）

https://shaojiemike.notion.site/41b9f62c4b054a2bb379316f27da5836

MPI消息

预定义类型消息——特殊MPI_PACKED

MPI_PACKED预定义数据类型被用来实现传输地址空间不连续的数据项 。 

int MPI_Pack(const void *inbuf,
             int incount,
             MPI_Datatype datatype, void *outbuf, int outsize, int *position, MPI_Comm comm)
int MPI_Unpack(const void *inbuf, int insize, int *position,
               void *outbuf, int outcount, MPI_Datatype datatype, MPI_Comm comm)
The input value of position is the first location in the output buffer to be used for packing. position is incremented by the size of the packed message,

and the output value of position is the first location in the output buffer following the locations occupied by the packed message. The comm argument is the communicator that will be subsequently used for sending the packed message.

//Returns the upper bound on the amount of space needed to pack a message
int MPI_Pack_size(int incount, MPI_Datatype datatype, MPI_Comm comm, int *size)
例子： 这里的A+i*j应该写成A+i*2吧？？？

派生数据类型(Derived Data Type)

来定义由数据类型不同且地址空间不连续的数据项组成的消息。 

//启用与弃用数据类型
int MPI_Type_commit(MPI_Datatype * datatype)
int MPI_Type_free(MPI_Datatype * datatype)
//相同数据类型
int MPI_Type_contiguous(int count, MPI_Datatype oldtype, MPI_Datatype * newtype)
//成块的相同元素组成的类型，块之间具有相同间隔
int MPI_Type_vector(int count,
                    int blocklength, int stride, MPI_Datatype oldtype, MPI_Datatype * newtype)


//成块的相同元素组成的类型，块长度和偏移由参数指定
int MPI_Type_indexed(int count,
                     const int *array_of_blocklengths,
                     const int *array_of_displacements,
                     MPI_Datatype oldtype, MPI_Datatype * newtype)


//由不同数据类型的元素组成的类型, 块长度和偏移(肯定也不一样)由参数指定
int MPI_Type_struct(int count,
                    int *array_of_blocklengths,
                    MPI_Aint * array_of_displacements,
                    MPI_Datatype * array_of_types, MPI_Datatype * newtype)

通讯域映射为网格表示

MPI_Cart_create 确定了虚拟网络每一维度的大小后，需要为这种拓扑建立通信域。组函数MPI_Cart_create可以完成此任务，其声明如下： 

// Makes a new communicator to which topology拓扑 information has been attached
int MPI_Cart_create(
    MPI_Comm old_comm,//旧的通信域。这个通讯域中的所有进程都要调用该函数
    int dims,//网格维数 number of dimensions of cartesian grid (integer)
    int* size,//长度为dims的数组，size[j]是第j维的进程数, integer array of size ndims specifying the number of processes in each dimension
    int* periodic,//长度为dims的数组，如果第j维有周期性，那么periodic[j]=1，否则为0
    int reorder,//进程是否能重新被编号，如果为0则进程在新的通信域中仍保留在旧通信域的标号
    MPI_Comm* cart_comm//该函数返回后，此变量将指向新的笛卡尔通信域
);

int MPI_Cart_rank(MPI_Comm comm, const int coords[], int *rank)
//Determines process rank in communicator given Cartesian location
//该函数的作用是通过进程在网格中的坐标获得它的进程号

int MPI_Cart_coords(MPI_Comm comm, int rank, int maxdims, int coords[])
//Determines process coords in cartesian topology given rank in group
//该函数的作用是确定某个线程在虚拟网格中的坐标

通信域划分

int MPI_Comm_create(MPI_Comm comm, MPI_Group group, MPI_Comm * newcomm)
//Creates a new communicator

int MPI_Comm_split(MPI_Comm comm, int color, int key, MPI_Comm * newcomm)
将某个通信域进一步划分为几组

组间通信域

点对点通信

特殊的函数 

int MPI_Sendrecv(const void *sendbuf, int sendcount, MPI_Datatype sendtype,
                 int dest, int sendtag,
                 void *recvbuf, int recvcount, MPI_Datatype recvtype,
                 int source, int recvtag, MPI_Comm comm, MPI_Status * status)
int MPI_Sendrecv_replace(void *buf, int count, MPI_Datatype datatype,
                         int dest, int sendtag, int source, int recvtag,
                         MPI_Comm comm, MPI_Status * status)
特别适用于在进程链（环）中进行“移位”操作，而避免在通讯为阻塞方式时出现死锁。

There is also another error. The MPI standard requires that the send and the receive buffers be disjoint不相交 (i.e. they should not overlap重叠), which is not the case with your code. Your send and receive buffers not only overlap but they are one and the same buffer. If you want to perform the swap in the same buffer, MPI provides the MPI_Sendrecv_replace operation. 

//MPI标准阻塞通信函数,没发出去就不会结束该命令。
MPI_Send(sb, buf_size, MPI_INT, other, 1, MPI_COMM_WORLD);
                /*其中sb为发送缓冲区首地址, 
                  buf_size为发送数据量, 
                  MPI_INT 为发送数据的类型,
                  other为发送目标进程,(发送给other)
                  1的位置为tag,
                  MPI_COMM_WORLD为通信子*/
MPI_Recv(rb, buf_size, MPI_INT, other, 1, MPI_COMM_WORLD, &status);
                /*与发送类似,从other接收消息,status见下面*/

是否会导致死锁

可能大家会想到这会死锁，如下图：

但是实际情况可能并不会死锁，这与调用的MPI库的底层实现有关。

MPI_Send将阻塞，直到发送方可以重用发送方缓冲区为止。当缓冲区已发送到较低的通信层时，某些实现将返回给调用方。当另一端有匹配的MPI_Recv()时，其他一些将返回到呼叫者。

但是为了避免这种情况，可以调换Send与Recv的顺序，或者使用MPI_Isend()或MPI_Issend()代替非阻塞发送，从而避免死锁。

梯形积分

/*
        梯形积分法，计算y=sin x 在[0,pi]上的积分
        @ trap 梯形积分串行程序
        @total_inte 最终积分结果
        */
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include<math.h>
#include "mpi.h"
using namespace std;

const double a = 0.0;
const double b = 3.1415926;
int n = 100;
double h = (b - a) / n;

double trap(double a, double b, int n, double h)
{
    double*x = new double[n + 1];
    double*f = new double[n + 1];
    double inte = (sin(a) + sin(b)) / 2;
    for (int i = 1; i<n + 1; i++) {
        x[i] = x[i - 1] + h;   /*x_0=a,x_n=b*/
        f[i] = sin(x[i]);
        inte += f[i];
    }
    inte = inte*h;    /* inte=h*[f(a)/2+f(x_1)+...f(x_{n-1})+f(b)/2]*/
    return inte;
}

int main(int argc, char * argv[])
{
    int myid, nprocs;
    int local_n;
    double local_a;
    double local_b;
    double total_inte;

    MPI_Init(&argc, &argv);
    MPI_Comm_rank(MPI_COMM_WORLD, &myid);   /* get current process id */
    MPI_Comm_size(MPI_COMM_WORLD, &nprocs); /* get number of processes */

    local_n = n / nprocs; //任务划分
    local_a = a + myid*local_n*h;
    local_b = local_a + local_n*h;
    double local_inte = trap(local_a, local_b, local_n, h);

    if (myid != 0) //通信结果
    {
        MPI_Send(&local_inte, 1, MPI_DOUBLE, 0, 0, MPI_COMM_WORLD);
    }
    else
    {
        total_inte = local_inte;
        for (int i = 1; i<nprocs; i++)
        {
            MPI_Recv(&local_inte, 1, MPI_DOUBLE, i, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
            total_inte += local_inte;
        }
    }
    if (myid == 0)
    {
        printf("integral output is %d", total_inte);
    }
    MPI_Finalize();

    return 0;
}

群集通讯

一个进程组中的所有进程都参加的全局通信操作。

实现三个功能：通信、聚集和同步。 1. 通信功能主要完成组内数据的传输 2. 聚集功能在通信的基础上对给定的数据完成一定的操作 3. 同步功能实现组内所有进程在执行进度上取得一致

常见的通讯

//将一个进程中得数据发送到所有进程中的广播函数
MPI_Bcast(void* data_p,int count,MPI_Datatype datatype, int scr_process,MPI_Comm comm);
注意data_p在root 或者scr_process进程里是发送缓存也是接收缓存，但是在其余进程里是接收缓存。 MPI_Scatter?

区别

  1. MPI_Scatter与MPI_Bcast非常相似，都是一对多的通信方式，不同的是后者的0号进程将相同的信息发送给所有的进程，而前者则是将一段array的不同部分发送给所有的进程，其区别可以用下图概括：
  3. MPI_Gather，作用是从所有的进程中将每个进程的数据集中到根进程中，同样根据进程的编号对array元素排序，
  5. 接收缓冲由三元组标识，发送缓冲由三元组标识，所有非Root进程忽略接收缓冲。
  6. MPI_Allgather 当数据分布在所有的进程中时，MPI_Allgather将所有的数据聚合到每个进程中。
  8. Allgather操作相当于每个进程都作为ROOT进程执行了一次Gather调用，即每一个进程都按照Gather的方式收集来自所有进程(包括自己)的数据。
  9. MPI_GATHERV扩展了功能,提供新的参数disp,是一个整数数组，包含存放从每个进程接收的数据相对于recvbuf的偏移地址
  10. MPI_alltoall()
  12. 等价于每个进程作为Root进程执行了一次MPI_Scatter散播操作。 
    int MPI_Allgather(void * sendbuff, int sendcount, MPI_Datatype sendtype, 
                  void * recvbuf, int recvcount, MPI_Datatype recvtype, 
                  MPI_Comm comm)
int MPI_Allgatherv(void * sendbuff, int sendcount, MPI_Datatype sendtype, 
                   void * recvbuf, int * recvcounts, int * displs, 
                   MPI_Datatype recvtype, MPI_Comm comm)
    recvcount gather和allgather是一样的

number of elements received from any process (integer)

注意

  1. 通信域中的所有进程必须调用群集通信函数。如果只有通信域中的一部分成员调用了群集通信函数而其它没有调用，则是错误的。
  2. 除MPI_Barrier以外，每个群集通信函数使用类似于点对点通信中的标准、阻塞的通信模式。也就是说，一个进程一旦结束了它所参与的群集操作就从群集函数中返回，但是并不保证其它进程执行该群集函数已经完成。
  3. 一个群集通信操作是不是同步操作取决于实现。MPI要求用户负责保证他的代码无论实现是否同步都必须是正确的。 ???与后面矛盾了 mpich官网说明的。
  4. 关于同步最后一个要注意的地方是：始终记得每一个你调用的集体通信方法都是同步的。
  5. https://mpitutorial.com/tutorials/mpi-broadcast-and-collective-communication/zh_cn/
  6. 在MPI-3.0之前MPI中的所有集合操作都是阻塞的,这意味着在返回之后使用传递给它们的所有缓冲区是安全的.特别是,这意味着当其中一个函数返回时,会收到所有数据.(但是,它并不意味着所有数据都已发送!)因此,如果所有缓冲区都已有效,则在集合操作之前/之后MPI_Barrier不是必需的(或非常有用).
  7. 对用户的建议:为保证程序正确性而依赖于集合操作中同步的副作用是很危险的作法.例如,即便一个特定的实现策略可以提供一个带有同步副作用的广播通信例程, 但标准却不支持它,因此依赖于此副作用的程序将不可移植.从另一方面讲,一个正确的、可移植的程序必须能容忍集合操作可能带来同步这样 一个事实.尽管一个程序可以丝毫不依赖于这种同步的副作用,编程时也必须这样做.这个问题在4.12节中还将进一步讨论(对用户的建议结尾) https://scc.ustc.edu.cn/zlsc/cxyy/200910/MPICH/mpi41.htm
  8. 关于不同的进程运行同一句Bcast的效果
  9. 当根节点(在我们的例子是节点0)调用 MPI_Bcast 函数的时候，data 变量里的值会被发送到其他的节点上。当其他的节点调用 MPI_Bcast 的时候，data 变量会被赋值成从根节点接受到的数据。
  10. 所以如果有进程无法到达该语句Bcast，同步的性质会导致到达Bcast的命令需要等待。

聚合

MPI聚合的功能分三步实现 * 首先是通信的功能，即消息根据要求发送到目标进程，目标进程也已经收到了各自需要的消息； * 然后是对消息的处理，即执行计算功能； * 最后把处理结果放入指定的接收缓冲区。

MPI提供了两种类型的聚合操作: 归约和扫描。

聚合——归约

int MPI_Reduce(
    void *input_data, /*指向发送消息的内存块的指针 */
    void *output_data, /*指向接收（输出）消息的内存块的指针 */
    int count，/*数据量*/
    MPI_Datatype datatype,/*数据类型*/
    MPI_Op operator,/*规约操作*/
    int dest，/*要接收（输出）消息的进程的进程号*/
    MPI_Comm comm);/*通信器，指定通信范围*/
// operator可以有：求最大值 MPI_MAX 最小值 求累加和 累乘积 逻辑操作  

// 求和语句
MPI_Reduce(&local_int,&total_int,1,MPI_DOUBLE,MPI_SUM,0,MPI_COMM_WORLD);

//另外有时候需要将得到的结果放入所有的线程中
MPI_Allreduce(void* input_data_p,void*output_data_p, int count,MPI_Datatype datatype,MPI_Op operator, MPI_Comm comm);

//每一个进程都对排在它前面的进程进行归约操作。
MPI_scan(SendAddress, RecvAddress, Count, Datatype, Op, Comm)

自定义归约操作

int MPI_Op_create(MPI_User_function *function, int commute, MPI_Op *op)

//function    用户自定义的函数(函数)
//commute   如果commute=ture， 则此操作同时也是可交换的。如果commute=false,则此操作不满足交换律。
            else 按进程号升序进行Op操作
//op              自定义归约操作名

int  MPI_Op_free(MPI_Op *op) //将用户自定义的归约操作撤销， 将op设置成MPI_OP_NULL。
用户自定义函数 function
typedef void MPI_User_function(void *invec, void *inoutvec, int *len, MPI_Datatype *datatype) 
for(i=0;i<*len;i++)  {
    *inoutvec = *invec USER_OP *inoutvec;
    inoutvec++;  invec++;
}
必须具备四个参数： 1. invec 和 inoutvec 分别指出将要被归约的数据所在的缓冲区的首地址， 2. len指出将要归约的元素的个数, datatype 指出归约对象的数据类型

也可以认为invec和inoutvec 是函数中长度为len的数组， 归约的结果重写了inoutvec 的值。

梯形积分(MPI_Reduce)
 /*
@local_inte：send buffer;
@total_inte:receive buffer;
@MPI_SUM:MPI_Op;
@dest=0,rank of the process obtaining the result.
*/ 中间改成这个

MPI_Reduce(&local_inte, &total_inte, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD);

注意事项

  1. 除了#include "mpi.h"

需要进一步的研究学习

MPI_Group https://www.rookiehpc.com/mpi/docs/mpi_group.php

并行IO文件

1997年推出了MPI的最新版本MPI-2

MPI-2加入了许多新特性，主要包括 * 动态进程(Dynamic Process) * 远程存储访问(Remote Memory Access) * 并行I/O访问(Parallel I/O Access) * MPI-1没有对并行文件I/O给出任何定义，原因在于并行I/O过于复杂，很难找到一个统一的标准。 more

遇到的问题

数据发送和收集

开题缘由、总结、反思、吐槽~~

参考文献

https://blog.csdn.net/susan_wang1/article/details/50033823

https://blog.csdn.net/u012417189/article/details/25798705

是否死锁： https://stackoverflow.com/questions/20448283/deadlock-with-mpi

https://mpitutorial.com/tutorials/

http://staff.ustc.edu.cn/~qlzheng/pp11/ 第5讲写得特别详细

https://www.mpich.org/static/docs/latest/www3/

  • 分类于 tips
  • 需要 1 分钟阅读时间

URLs

导言

frequently-used out-of-work urls

  • 分类于 network
  • 需要 3 分钟阅读时间

VPN

VPN原理

vpn：英文全称是“Virtual Private Network”，翻译过来就是“虚拟专用网络”。vpn通常拿来做2个事情:

  • 一个是可以让世界上任意2台机器进入一个虚拟的局域网中（当然这个局域网的数据通讯是加密的，很安全，用起来和一个家庭局域网没有区别），
  • 一个是可以用来翻墙。

VPN与SS的区别

  • SS全称shadowsocks，SSR全称shadowsocks-R
  • VPN是为了保证通信的安全性、私密性，不是专门为“科学上网”制定的技术
  • 而SS/SSR则是为了转发客户端流量，绕过防火墙的检测，从而达到“科学上网”的真实意图，但是没有保证数据传输的安全性。
  • vpn比ss更加底层，它通过操作系统的接口直接虚拟出一张网卡，后续整个操作系统的网络通讯都将通过这张虚拟的网卡进行收发。
  • 这和任何一个代理的实现思路都差不多，应用层并不知道网卡是虚拟的，这样vpn虚拟网卡将以中间人的身份对数据进行加工，从而实现各种神奇的效果。具体来说，vpn是通过编写一套网卡驱动并注册到操作系统实现的虚拟网卡，这样数据只要经过网卡收发就可以进行拦截处理。

一句话，vpn在IP层工作，而ss在TCP层工作。

内网访问举例

  • 普通用户无法访问公司内网服务器
  • 开启VPN以后，如果他想打开公司ERP，他的电脑就不再直接连接公司ERP网站，而是去连接VPN服务器，并给VPN服务器发一条指令——“我要访问公司ERP”。
  • VPN服务器接到指令后，VPN服务器自己去访问公司ERP，收到公司ERP网页的内容，再把内容回传给员工，这样使用VPN的员工最终就能看到公司ERP网站的内容了。
  • 也就是说，使用VPN时，这个员工的所有网上访问都通过VPN服务器代理完成的。

IP packet 如何被传输

理解 VPN 路由（以及任何网络路由）配置的关键是认识到一个 IP packet 如何被传输，以下描述的是极度简化后的单向传输过程：

  1. 机器 A (192.168.0.2) 发送了一个目标地址为 172.29.1.4 的 IP packet.
  2. 根据本地路由规则，172.29.1.0/24 的下一跳是虚拟网卡 tun0, 由 VPN 客户端接管。
  3. VPN 客户端将这个 packet 的来源地址从 192.168.0.2 改为 10.8.0.123, 转发给 VPN 服务端。
  4. VPN 服务端收到 packet. 根据本地路由规则，172.29.1.0/24 的下一跳是默认网关 172.29.1.1.
  5. 默认网关找到在同一个局域网内的机器 B (172.29.1.4).

客户端 -> 内网

为什么机器 A 的本地路由表里会有 172.29.1.0/24 这个网段的路由规则？通常情况下，这是 OpenVPN 服务端推送给客户端，由客户端在建立 VPN 连接时自动添加的。也可以由服务端自定义，比如wireguard

内网 -> 客户端

这个时候，如果机器 B 想要回复 A（比如发个 ACK），就会出问题，因为 packet 的来源地址还是 10.8.0.123, 而 10.8.0.0/24 网段并不属于当前局域网，是 VPN 服务端私有的——机器 B 往 10.8.0.123 发送的 ACK 会在某个位置（比如默认网关）遇到 "host unreachable" 而被丢弃。对于机器 A 来说，表面现象可能是连接超时或 ping 不通。

解决方法是，在 packet 离开 VPN 服务端时，将其「伪装」成来自 172.29.0.3（举例VPN 服务端的局域网地址），这样机器 B 发送的 ACK 就能顺利回到 VPN 服务端，然后发给机器 A. 这就是所谓的 SNAT。

  • SNAT: Source Network Address Translation，是修改网络包源ip地址的。
  • DNAT: Destination Network Address Translation,是修改网络包目的ip地址的。

在 Linux 系统中由 iptables 来管理，具体命令是：

iptables -t nat -A POSTROUTING -s 10.8.0.0/24 -o eth0 -j MASQUERADE.

客户端 -> 另一个客户端的内网

连接 OpenVPN 的两个 client 之间可以互相通信，这是因为服务端推送的路由里包含了对应的网段。但是想从 Client A 到达 Client B 所在局域网的其他机器，还需要额外的配置。因为 OpenVPN 服务端缺少 Client B 局域网相关的路由规则。

# server.conf
push "route 172.29.0.0 255.255.0.0" # client -> Client B 给客户端推送 172.29.0.0/16 网段的路由(即这个网段的IP的信息都经过VPN)

route 172.29.0.0 255.255.0.0 #在 OpenVPN Server 上添加 172.29.0.0/16 网段的路由，具体下一跳是哪里，由 client-config 里的 iroute 指定

# 启用 client-config, 目录里的文件名对应 client.crt 的 Common Name
client-config-dir /etc/openvpn/ccd

# /etc/openvpn/ccd/client-b
iroute 172.29.0.0 255.255.0.0 # 告诉 OpenVPN Server, 172.29.0.0/16 的下一跳应该是 client-b (根据名字来)

内网与内网互访

在前两节所给的配置基础上，只需要再加一点配置，就能实现 OpenVPN 服务端所在局域网与客户端所在局域网的互访。配置内容是，在各自局域网的默认网关上添加路由，将对方局域网网段的下一跳设为 OpenVPN 服务端 / 客户端所在机器，同时用 iptables 配置相应的 SNAT 规则。

机场购买链接推荐

Based on the info in clashio, we select some cheap vpns to try.

name 每月价格(￥/GB/off on holiday) 每月单价(GB/￥) 每年单价(GB/￥) 节点数与稳定性 使用速度感觉
fastlink 2019 20/100/-30% 5 100+, 节点速度高达5Gbps 峰值 5Gbps (1)
totoro 2023 15/100/-20%(2) 6.6 ??? ???
冲浪猫 2022 16/200/-12%(3) 12.5 ??? 峰值 1Gbps
奈云机场 2021 10.6/168/-30%(4) 15.8 230624购买，240109几天全面掉线 峰值 5Gbps (6)
FatCat 2023 6/60/-20% 10 ??? 峰值 xx Gbps

detail info in table

  1. up to 6MB/s off-peak period
  2. 年付8折 + 优惠码8折 \(15*12*0.8*0.8=115.2\)
  3. 年付 150￥*0.88
  4. 年付+优惠码 128*0.7 = 89.6￥
  5. 年费+优惠码 128G每月，：46.99￥/128G or 76.36￥/256G。单价最低时间最短买法：256G,按季度买
  6. 新注册用户运行一周内测试5GB: up to 6MB/s in real download

My Choice: 单价，大小，速度，优惠码有效期

  1. 优惠码(春节 中秋 双十一)
  2. fastlink 用了两年了，还是x3很快的。但是相当于一个月只有30GB, 不够用。
  3. 奈云机场(可靠性暂时不行)，冲浪猫 平衡比较好。

现在组合：奈云机场(2) + fastlink。 等fastlink过期了(1)，看要不要转成 冲浪猫。

  1. 240624
  2. 241105 配置：复制订阅，订阅地址后面加 &flag=clash下载config.yaml
slow and expensive I had try

Nyacloud 喵云：只有10个节点 8￥/40GB/0.03Gbps or 17￥/128GB/0.2Gbps 平均 5GB/￥

BGP: Border Gateway Protocol

边界网关协议（Border Gateway Protocol，BGP）就是互联网的邮政服务。当有人把一封信投进邮筒时，邮政服务就会处理这封邮件，并选择一条快速、高效的路线将这封信投递给收件人。同样地，当有人通过互联网提交数据时，BGP 负责寻找数据能传播的所有可用路径，并选择最佳的路由，这通常意味着在自治系统之间跳跃。1

BGP不仅能够解决速度问题，还可以解决绕过线路故障:

IPLC: International Private Leased Circuit

中文翻译是国际私用出租线路，是指用户专用的跨国的数据、话音等综合信息业务的通信线路。通俗地说，也就是指传统的跨境专线。

延迟更低40ms、速度更快, 但是价格贵1 元 / GB。

Anycast

Anycast 是一种网络寻址和路由方法，可以将传入请求路由到各种不同的位置或“节点”。在 CDN 的上下文中，Anycast 通常会将传入的流量路由到距离最近并且能够有效处理请求的数据中心。选择性路由使 Anycast 网络能够应对高流量、网络拥塞和 DDoS 攻击。

SJF 稳定翻墙VPS

brook vpn+ Amazon American node

各种设备翻墙

教程

参考文献

OpenVPN 路由详解

  1. BGP 漫谈 ↩↩↩

  • 分类于 Programming
  • 需要 2 分钟阅读时间

Java

java运行的特点

JVM(java虚拟机)

Just-In-Time (JIT) 编译器

  • JIT编译器是一种动态编译技术，它将程序的一部分或者全部源代码或更常见的字节码在运行时编译成机器码，然后将编译后的代码替换原来的代码。
  • 字节码（英语：Bytecode）通常指的是已经经过编译，但与特定机器代码无关，需要解释器转译后才能成为机器代码的中间代码(多为虚拟机代码)。典型应用为Java虚拟机里的Java bytecode。
  • 主要优点是可以在运行时根据程序的运行情况进行优化，从而提高程序的执行效率。
  • 字节码编译是跨平台的，便于移植的。
  • 主要缺点是编译字节码导致的延迟和空间开销较大，因此只有在程序运行时间较长的情况下才能体现出优势。
  • 是提前编译（AOT）和字节码解释器(python的实现)的结合体，它的执行效率介于两者之间。

区别

  1. Java Virtual Machine (JVM) is an abstract computing machine.
  2. Java Runtime Environment (JRE) is an implementation of the JVM.
  3. Java Development Kit (JDK) contains JRE along with various development tools like Java libraries, Java source compilers, Java debuggers, bundling and deployment tools.
  4. Java SE: Java™ Platform Standard Edition 21 Development Kit - JDK™ 21
  5. Just In Time compiler (JIT) is runs after the program has started executing, on the fly. It has access to runtime information and makes optimizations of the code for better performance.

Install

Intall for topcoder

chinese ref

  1. download from website
  2. But the first download choice java 21 SDK seems not contain Java Control Panel (javacpl.exe), you need to install Java SE Development Kit 8u381 which include JDK 1.8 and JRE 1.8
  3. config Java Control Panel, add https://www.topcoder.com to allowed website (Attention: https)
  4. open ContestAppletProd.jnlp
  5. need 127.0.0.1 proxy and HTTP TUNE 1 to connect to server

需要进一步的研究学习

暂无

遇到的问题

暂无

开题缘由、总结、反思、吐槽~~

参考文献

无

  • 分类于 Tutorials
  • 需要 1 分钟阅读时间

Keyboard

It's a fucking crazy thing when you reuse a Bluetooth device, because forget how to make pair.

logitech K780

My keyboard encounter Poor contact of keyboard keys, esepeacially the ctrl

change Win/Mac/IOS configurations

iOS fn + i

Mac OS X fn + o

Windows fn + p

LEOPOLO FC980M

Bluetooth pair

Read more: official ref and ref_photo

It seems that just

  1. Open the battery cover
  2. insert AAA battery and Set the power switch to the ON position.

you can Turn on the Bluetooth.

Answer from TAOBAO

连接蓝牙方法：（我们键盘没有送蓝牙适配器）需要您电脑有蓝牙功能，

  1. 第一步背后大开关打到on，
  2. 第二步用取卡针捅一下大开关下面的孔、进入配对环节，
  3. 第三步打开电脑蓝牙搜蓝牙键盘的型号按提示连接就行。参考

Windows weird option 输入 FC980MBT 的PIN，也可以选择关闭，尤其是鼠标也需要输入时：

  1. type 00000 using original keyboard，click confirm.
  2. type 00000 using new keyboard, enter.

需要进一步的研究学习

暂无

遇到的问题

暂无

开题缘由、总结、反思、吐槽~~

参考文献

上面回答部分来自ChatGPT-3.5，没有进行正确性的交叉校验。

无