Frank's blogs

二叉树的非递归遍历

• 通过在遍历过一次的节点前面加入一个NULL指针，提示下一个节点遍历过一次了

  前序遍历

  class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> result; stack<TreeNode*> st; if (root != NULL) st.push(root); while (!st.empty()) { TreeNode* node = st.top(); if (node != NULL) { st.pop(); if (node->right) st.push(node->right); // 右 if (node->left) st.push(node->left); // 左 st.push(node); // 中 st.push(NULL); } else { st.pop(); node = st.top(); st.pop(); result.push_back(node->val); } } return result; } };

• 遍历过一次的节点第二次直接输出

  中序遍历

  class Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector<int> result; stack<TreeNode*> st; if (root != NULL) st.push(root); while (!st.empty()) { TreeNode* node = st.top(); if (node != NULL) { st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中 if (node->right) st.push(node->right); // 添加右节点（空节点不入栈） st.push(node); // 添加中节点 st.push(NULL); // 中节点访问过，但是还没有处理，加入空节点做为标记。 if (node->left) st.push(node->left); // 添加左节点（空节点不入栈） } else { // 只有遇到空节点的时候，才将下一个节点放进结果集 st.pop(); // 将空节点弹出 node = st.top(); // 重新取出栈中元素 st.pop(); result.push_back(node->val); // 加入到结果集 } } return result; } };

• 针对没访问过的节点，先把他的左孩子入栈，再把NULL和自身入栈，再入栈右孩子

  后序遍历

  class Solution { public: vector<int> postorderTraversal(TreeNode* root) { vector<int> result; stack<TreeNode*> st; if (root != NULL) st.push(root); while (!st.empty()) { TreeNode* node = st.top(); if (node != NULL) { st.pop(); st.push(node); // 中 st.push(NULL); if (node->right) st.push(node->right); // 右 if (node->left) st.push(node->left); // 左 } else { st.pop(); node = st.top(); st.pop(); result.push_back(node->val); } } return result; } };

• 针对没访问过的节点，先把自己和NULL入栈，再把右孩子入栈，再把左孩子入栈

• 参考

  ucontext.h上下文切换

• 上下文结构体定义
• mcontext_t类型与机器相关，并且不透明.ucontext_t结构体则至少拥有以下几个域:

  typedef struct ucontext { struct ucontext *uc_link; sigset_t uc_sigmask; stack_t uc_stack; mcontext_t uc_mcontext; ... } ucontext_t;

• 当当前上下文(如使用makecontext创建的上下文）运行终止时系统会恢复uc_link指向的上下文；uc_sigmask为该上下文中的阻塞信号集合；uc_stack为该上下文中使用的栈；uc_mcontext保存的上下文的特定机器表示，包括调用线程的特定寄存器等

  四个操作函数

• int getcontext(ucontext_t *ucp);
  • 初始化ucp结构体，将当前的上下文保存到ucp中
• int setcontext(const ucontext_t *ucp);
  • 设置当前的上下文为ucp，setcontext的上下文ucp应该通过getcontext或者makecontext取得，如果调用成功则不返回。
  • 如果上下文是通过调用getcontext()取得,程序会继续执行这个调用。如果上下文是通过调用makecontext取得,程序会调用makecontext函数的第二个参数指向的函数，如果func函数返回,则恢复makecontext第一个参数指向的上下文第一个参数指向的上下文context_t中指向的uc_link
  • 如果uc_link为NULL,则线程退出。
• void makecontext(ucontext_t *ucp, void (*func)(), int argc, ...);
  • makecontext修改通过getcontext取得的上下文ucp(这意味着调用makecontext前必须先调用getcontext)。然后给该上下文指定一个栈空间ucp->stack，设置后继的上下文ucp->uc_link.
  • 当上下文通过setcontext或者swapcontext激活后，执行func函数，argc为func的参数个数，后面是func的参数序列。当func执行返回后，继承的上下文被激活，如果继承上下文为NULL时，线程退出
• int swapcontext(ucontext_t *oucp, ucontext_t *ucp);
  • 保存当前上下文到oucp结构体中，然后激活upc上下文。
• 如果执行成功，getcontext返回0，setcontext和swapcontext不返回；如果执行失败，getcontext,setcontext,swapcontext返回-1，并设置对于的errno.

• 例子

  #include <stdio.h> #include <ucontext.h> #include <unistd.h> int main(int argc, const char *argv[]){ ucontext_t context; getcontext(&context); puts("Hello world"); sleep(1); setcontext(&context); return 0; }

• 上述函数会不断重复输出Hello World，因为getcontext将上下文设置在了输出之前，setcontext每次都把整个执行流返回到输出的位置

更换为执行时间最短先服务逻辑的调度器版本

• 参考的原版
• 我改进代码的github仓库
• 使用了优先级队列重写携程选择逻辑，切换的时候会选择当前已经运行时间最短的携程上处理机执行
• 运行结果
  • 
  • 四个线程的优先级分别是4，3，2，1，可见是符合设置的

    1月12日修改

• 修改为了多线程版本，分别调度，分别设置优先级
• 
• 

注意事项

• C/C++文件编译的时候每个源文件都是独立编译的，这样会导致即使头文件使用了ifndef之类的保护，仍然可能在整个项目中被不同的文件引用多次
  • 因此如果头文件中出现了函数或者是变量的定义的话，这个变量在整个项目中会被定义多次
  • 因此头文件中只能声明，变量使用extern关键字声明
  • 必须定义的函数用inline
• 注意类的静态static成员变量必须在某个源文件中定义，才能在其他源文件中使用类名和作用域运算符::访问
• C++可以使用宏__FILE__判断自己所处的文件名称
• makecontext的第二个参数无论传入的是什么函数，都要将其转换为void(*)(void)类型的函数指针，然后再给出参数
• 执行流路径

  -----------调度器或main中----------------- 创建协程(create)--> 获取互斥锁 使用makecontext生成开始执行协程函数的上下文 令目标函数的上下文的后继位置时刻指向调度器schedule的上下文main 释放互斥锁 切换到协程(resume)--> 将当前的上下文保存在调度器schedule.main中，切换到目标函数的上下文 -----------协程函数中---------------- 切换回main(yield)--> 获取锁 将协程当前的上下文保存在ctx中 释放锁 切换回之前指向的main上下文 -----------------main中----------------- ...

• 因为添加协程create函数与协程调度器不在一个线程中，可能会有竞争关系，因此添加了互斥锁防止冲突

<setjmp.h>实现切换

setjmp 函数：

• setjmp 用于保存当前程序的执行状态，并返回一个整数值。

• 当首次调用 setjmp 时，它返回0，表示保存了当前执行状态。

• 当从 longjmp 调用返回时，setjmp 返回一个非零值，通常用于区分正常返回和通过 longjmp 返回。

  longjmp函数

• longjmp 用于恢复之前由 setjmp 保存的执行状态。

• 它接受两个参数：保存的执行状态（由 setjmp 返回的值）和一个非零的返回值。

• 调用 longjmp 会导致程序跳转到相应 setjmp 处，并且 setjmp 返回的值为 longjmp 的返回值。

  一个例子

• 参考

  #include <stdio.h> #include <stdlib.h> #include <setjmp.h> jmp_buf env; int my_func(int a, int b) { if (b == 0) { printf("do not allow division by 0\n"); longjmp(env, 1); } return a / b; } int main(int argc, char const *argv[]) { int res = setjmp(env); if (res == 0) { printf("return from setjmp\n"); my_func(10, 0); } else { printf("return from longjmp: %d\n", res); } return 0; }

  C++语言的锁机制

  unique_lock

• #include <mutex>和#include <thread>

  std::unique_lock<std::mutex> lock(myMutex); // 构造 unique_lock，并锁定互斥量

• 构造就是加锁

• 析构就是解锁

  lock.lock(); // 手动锁定互斥量 // 锁定期间的其他操作... lock.unlock(); // 手动释放锁 // 在 unique_lock 离开作用域时，会自动释放锁

• 同样支持手动操作，加锁和解锁

Leetcode 49. 字母异位词分组

• 此题除了使用哈希或者类似哈希的方式之外，还有一个简单的方式
• 就是将字符串直接按字母排序，相同的就是字母异位词

  class Solution { public: vector<vector<string>> groupAnagrams(vector<string>& strs) { map<string, vector<string>> m; for(auto& s : strs) { string tmp = s; sort(tmp.begin(), tmp.end()); m[tmp].push_back(s); } vector<vector<string>> ret; for(auto& i : m) { ret.push_back(i.second); } return ret; } };

  Leetcode 299. 猜数字游戏

• 遍历两个字符串，假如相同的话就加一个公牛，假如不同的话就对各自的char做数量统计（0, 1, 2, …, 9）各有多少个
• 最终母牛的结果是每个类型的char中谜底和猜测中较小的一个

  class Solution { public: string getHint(string secret, string guess) { int bulls = 0; vector<int> cntS(10), cntG(10); for (int i = 0; i < secret.length(); ++i) { if (secret[i] == guess[i]) { ++bulls; } else { ++cntS[secret[i] - '0']; ++cntG[guess[i] - '0']; } } int cows = 0; for (int i = 0; i < 10; ++i) { cows += min(cntS[i], cntG[i]); } return to_string(bulls) + "A" + to_string(cows) + "B"; } };

Leetcode 316. 去除重复字母

• 对已经入栈的字符而言，只要后面还出现而且字典顺序大于当前字符的一律弹出，将标记重新设置为0
• 然后加入当前字符，并且设置已经过标记为1
• 意义就是将较大而且后面还出现的字符的出现尽量推迟靠后

  class Solution { public: string removeDuplicateLetters(string s) { vector<int> vis(26), num(26); for (char ch : s) { num[ch - 'a']++; } string stk; // 对已经入栈的字符而言，只要后面还出现而且字典顺序大于当前字符的一律弹出，将标记重新设置为0 // 然后加入当前字符，并且设置已经过标记为1 // 意义就是将较大而且后面还出现的字符的出现尽量推迟靠后 for (char ch : s) { if (!vis[ch - 'a']) { while (!stk.empty() && stk.back() > ch) { if (num[stk.back() - 'a'] > 0) { vis[stk.back() - 'a'] = 0; stk.pop_back(); } else { break; } } vis[ch - 'a'] = 1; stk.push_back(ch); } num[ch - 'a'] -= 1; } return stk; } };

Leetcode 343. 整数拆分

• 此题也是使用动态规划，主要是分两种情况讨论
  • 将一个数字拆成a和b，b使用之前拆分的最大乘积
  • b不拆分，直接相乘

    class Solution { public: int integerBreak(int n) { vector<int> maxArr(n+1); maxArr[1] = 0; maxArr[2] = 1; for(int i = 3; i<=n; ++i) { for(int j = 1; j<i; ++j) { maxArr[i] = max(j*maxArr[i-j], maxArr[i]); // 拆分 maxArr[i] = max(j*(i-j), maxArr[i]); // 不拆分，就两个数字算 } } return maxArr[n]; } };

    Leetcode 718. 最长重复子数组

• 递推，使用上一个位置的连续长度加上这个位置是否相等递推出这个位置的
• 如果相等，就是到i-1,j-1位置为止的连续长度+1

  class Solution { public: int findLength(vector<int>& nums1, vector<int>& nums2) { vector<vector<int>> map(nums1.size(), vector<int>(nums2.size(), 0)); int maxLen = 0; for(int i = 0; i<nums1.size(); ++i) { for(int j = 0; j<nums2.size(); ++j) { if(nums1[i] == nums2[j]){ if(i == 0 || j == 0) { map[i][j] = 1; } else { map[i][j] = map[i-1][j-1]+1; } maxLen = max(map[i][j], maxLen); } } } return maxLen; } };

Leetcode 115. 不同的子序列

• 因为是从s中找t，所以递归的主要顺序是t找到了哪个位置
• 假如s的i位置与t的j相等，那么该位置的子字符串种类就是i-1和j-1位置位置+t到j位置时之前的种类之和
• 不等的话，就继承s字符串在之前位置，j字符串在当前位置的种类数量

  class Solution { public: int numDistinct(string s, string t) { vector<vector<int>> map(s.size()+1, vector<int>(t.size()+1, 0)); for(int i = 0; i<=s.size(); ++i) { map[i][0] = 1; } for(int i = 1; i<=s.size(); ++i) { for(int j = 1; j<=t.size(); ++j) { if(s[i-1] == t[j-1]) { map[i][j]=(map[i-1][j-1]+map[i-1][j])%((int)1e9+7); // 此处就是求和t字符串到j位置的所有可能性（包括s字符串之前的可能性） } else { map[i][j] = map[i-1][j]; } } } return map[s.size()][t.size()]; } };

Leetcode 583. 两个字符串的删除操作

• 从i-1和j-1递推i和j

• 当word1[i - 1] 与 word2[j - 1]相同的时候，dp[i][j] = dp[i - 1][j - 1]

• 当word1[i - 1] 与 word2[j - 1]不相同的时候，有三种情况：

  • 情况一：删word1[i - 1]，最少操作次数为dp[i - 1][j] + 1

  • 情况二：删word2[j - 1]，最少操作次数为dp[i][j - 1] + 1

  • 情况三：同时删word1[i - 1]和word2[j - 1]，操作的最少次数为dp[i - 1][j - 1] + 2

• 那最后当然是取最小值，所以当word1[i - 1] 与 word2[j - 1]不相同的时候，递推公式：dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});

• 因为 dp[i][j - 1] + 1 = dp[i - 1][j - 1] + 2，所以递推公式可简化为：dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);

  • 因为对于dp[i][j-1]而言，就是第一个字符串到i-1位置和第二个字符串到j-2位置，第一个字符串增加一步删除就可以到i-2和j-2的位置，因此二者只差一步

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1));
        for (int i = 0; i <= word1.size(); i++) dp[i][0] = i;
        for (int j = 0; j <= word2.size(); j++) dp[0][j] = j;
        for (int i = 1; i <= word1.size(); i++) {
            for (int j = 1; j <= word2.size(); j++) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
                }
            }
        }
        return dp[word1.size()][word2.size()];
    }
};

Leetcode 72. 编辑距离

• 此题遇上一个类似，只是增加了几个操作

  class Solution { public: int minDistance(string word1, string word2) { vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0)); for (int i = 0; i <= word1.size(); i++) dp[i][0] = i; for (int j = 0; j <= word2.size(); j++) dp[0][j] = j; for (int i = 1; i <= word1.size(); i++) { for (int j = 1; j <= word2.size(); j++) { if (word1[i - 1] == word2[j - 1]) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1; } } } return dp[word1.size()][word2.size()]; } };

Leetcode 1035. 不相交的线

• 此题同样是类似的动态规划
• 利用i-1和j-1推导i和j位置的值
• 如果当前位置相等，此时则是在i-1和j-1位置的基础上+1
• 因为递推的上一级是i-1和j-1，这就导致之前的连线最多只涉及之前的数字，不会于新加入的相交，从而防止了相交

  class Solution { public: int maxUncrossedLines(vector<int>& A, vector<int>& B) { vector<vector<int>> dp(A.size() + 1, vector<int>(B.size() + 1, 0)); for (int i = 1; i <= A.size(); i++) { for (int j = 1; j <= B.size(); j++) { if (A[i - 1] == B[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[A.size()][B.size()]; } };

Leetcode 1143. 最长公共子序列

• 暴力递归方法（或者动态规划）
• 每次两个字符串往前走一个位置（比如到达i, j），假如两个字符串在这个位置的值相同，那么就以(i-1, j-1)位置的最长子串的长度+1作为当前位置的值
• 否则，就从两个字符串分别到（i-1，j）和（i，j-1）位置选择一个较大的作为结果
  • 这么做的关键原因（也就是遇上一题的区别）就是因为这个不必须是连续的

    class Solution { public: int longestCommonSubsequence(string text1, string text2) { int m = text1.length(), n = text2.length(); vector<vector<int>> dp(m + 1, vector<int>(n + 1)); for (int i = 1; i <= m; i++) { char c1 = text1.at(i - 1); for (int j = 1; j <= n; j++) { char c2 = text2.at(j - 1); if (c1 == c2) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[m][n]; } };

LeetCode 72. 编辑距离

• 创建一个二维数组，一个维度是第一个字符串的长度，另一个是第二个字符串的长度
• 当 word1[i] == word2[j]，dp[i][j] = dp[i-1][j-1]
• 当 word1[i] != word2[j]，dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
• 其中，dp[i-1][j-1] 表示替换操作，dp[i-1][j] 表示删除操作，dp[i][j-1] 表示插入操作。

  class Solution { public: int minDistance(string word1, string word2) { int m = word1.length(); int n = word2.length(); vector<vector<int>> map(m+1, vector<int>(n+1, INT_MAX)); map[0][0] = 0; for(int i = 0; i<=m; ++i) { for(int j = 0; j<=n; ++j) { if(i == 0&& j > 0) { map[i][j] = map[i][j-1]+1; } else if(i > 0&& j == 0) { map[i][j] = map[i-1][j]+1; } else if(i == 0 && j == 0)continue; else if(word1[i-1] == word2[j-1]) { map[i][j] = map[i-1][j-1]; } else { map[i][j] = min(map[i-1][j], min(map[i][j-1], map[i-1][j-1]))+1; } } } return map[m][n]; } };

647. 回文子串

• 注意循环顺序，从中间到两边，所以要从末端开始

  class Solution { public: int countSubstrings(string s) { vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false)); int result = 0; for (int i = s.size() - 1; i >= 0; i--) { // 注意遍历顺序 for (int j = i; j < s.size(); j++) { if (s[i] == s[j]) { if (j - i <= 1) { // 情况一 和 情况二 result++; dp[i][j] = true; } else if (dp[i + 1][j - 1]) { // 情况三 result++; dp[i][j] = true; } } } } return result; } };

最长回文子序列

• 此题大体与上面类似，唯一的区别是不需连续
• 因此需要在条件不成立的时候使用dp[i][j] = max(dp[i+1][j], dp[i][j-1]);保存结果递推

  class Solution { public: int longestPalindromeSubseq(string s) { vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0)); int result = INT_MIN; for (int i = s.size() - 1; i >= 0; i--) { // 注意遍历顺序 for (int j = i; j < s.size(); j++) { if (s[i] == s[j]) { if (j - i <= 1) { // 情况一 和 情况二 dp[i][j] = j-i+1; result = max(result, dp[i][j]); } else { dp[i][j] = dp[i+1][j-1]+2; result = max(result, dp[i][j]); } } else { dp[i][j] = max(dp[i+1][j], dp[i][j-1]); } } } return result; } };

Leetcode 673. 最长递增子序列的个数

• 链接
• 这道题目我们要一起维护两个数组。
• dp[i]：i之前（包括i）最长递增子序列的长度为dp[i]
• count[i]：以nums[i]为结尾的字符串，最长递增子序列的个数为count[i]
• 那么在nums[i] > nums[j]前提下，如果在[0, i-1]的范围内，找到了j，使得dp[j] + 1 > dp[i]，说明找到了一个更长的递增子序列。
• 那么以j为结尾的子串的最长递增子序列的个数，就是最新的以i为结尾的子串的最长递增子序列的个数，即：count[i] = count[j]。
• 在nums[i] > nums[j]前提下，如果在[0, i-1]的范围内，找到了j，使得dp[j] + 1 == dp[i]，说明找到了两个相同长度的递增子序列。
• 那么以i为结尾的子串的最长递增子序列的个数 就应该加上以j为结尾的子串的最长递增子序列的个数，即：count[i] += count[j];
• 注意初始化为1

  class Solution { public: int findNumberOfLIS(vector<int>& nums) { if (nums.size() <= 1) return nums.size(); vector<int> dp(nums.size(), 1); vector<int> count(nums.size(), 1); int maxCount = 0; for (int i = 1; i < nums.size(); i++) { for (int j = 0; j < i; j++) { if (nums[i] > nums[j]) { if (dp[j] + 1 > dp[i]) { dp[i] = dp[j] + 1; count[i] = count[j]; } else if (dp[j] + 1 == dp[i]) { count[i] += count[j]; } } if (dp[i] > maxCount) maxCount = dp[i]; } } int result = 0; for (int i = 0; i < nums.size(); i++) { if (maxCount == dp[i]) result += count[i]; } return result; } };

小总结

• 从大序列中找小序列的问题，假如是连续序列的话，不满足对应的条件的时候可以不处理
• 但是假如不是连续序列的话，往往需要类似于dp[i][j] = max(dp[i+1][j], dp[i][j-1]);的操作来保存递推结果

Leetcode 486. 预测赢家

• 此题使用起始和结束位置作为两个坐标的二维数组动态规划
• 记忆化搜索的递归(原题)

  #include <iostream> #include <vector> #include <cstdlib> using namespace std; vector<vector<int>> res; int traversal(vector<int>& arr, int beg, int end) { // cout<<'!'; if(beg>end || beg>=arr.size() || end<0)return 0; else if(beg == end)return arr[beg]; if(res[beg][end]>=0)return res[beg][end]; int ret = max(arr[beg]+min(traversal(arr, beg+1, end-1), traversal(arr, beg+2, end)), arr[end]+min(traversal(arr, beg+1, end-1), traversal(arr, beg, end-2))); res[beg][end] = ret; return ret; } int main() { int cnt; cin>>cnt; res = vector<vector<int>>(cnt, vector<int>(cnt, -1)); int sum = 0; vector<int> arr(cnt, 0); for(int i = 0; i<cnt; ++i) { cin>>arr[i]; sum+=arr[i]; } for(int i = 0; i<cnt; ++i) { res[i][i] = arr[i]; } cout<<max(first, sum-first)<<endl; }

• 动态规划的答案
• dp[i][j] 表示两个玩家在数组 i 到 j 区间内游戏能赢对方的差值（i <= j）

  class Solution { public: bool PredictTheWinner(vector<int>& nums) { // dp[i][j] 表示两个玩家在数组 i 到 j 区间内游戏能赢对方的差值（i <= j） int dp[22][22] = {0}; // 当i == j的时候，nums[i]就是dp[i][j] for (int i = 0; i < nums.size(); i++) { dp[i][i] = nums[i]; } for(int i = nums.size() - 2; i >= 0; i--) { for (int j = i + 1; j < nums.size(); j++) { dp[i][j] = max((nums[i] - dp[i + 1][j]), (nums[j] - dp[i][j - 1])); } } return dp[0][nums.size() - 1] >= 0; } };

Leetcode 283. 移动零

• 此题是使用双指针法
  • 一个指针是依次向前的
  • 另一个是指向非0区的左边界
  • 每次遇到一个非0的数字，就把他跟左边界位置的数字互换然后将左边界右移一位

    class Solution { public: void moveZeroes(vector<int>& nums) { int nonZero = 0; for(int i = 0; i<nums.size(); ++i) { if(nums[i] != 0) { swap(nums[i], nums[nonZero]); ++nonZero; } } } void swap(int& a, int& b) { int tmp = a; a = b; b = tmp; } };

Leetcode 560.和为k的子数组

• 循环一次，每次寻找每个位置的前缀和
• 然后寻找字典中是否存在pre-k
• 假如存在的话，意味着从pre-k的结束位置开始，到当前的位置结束的一段数组的和是k
  • map中pre-k有多少个，增加多少个到结果中

    class Solution { public: int subarraySum(vector<int>& nums, int k) { unordered_map<int, int> mp; mp[0] = 1; int count = 0, pre = 0; for (auto& x:nums) { pre += x; // 这一步是前缀和 if (mp.find(pre - k) != mp.end()) { count += mp[pre - k]; // 可行的计数加上这个计数 } mp[pre]++; // 添加上当前计算的前缀和到字典 } return count; } };

Leetcode 33. 搜索旋转排序数组

• 此题是针对一个向后平移过的有序数组进行操作
• 如果数组的第一个元素小于当前元素，则当前元素位于数组的前半部分，否则是后半部分
• 然后在自己的区间内二分即可，与数组的最左侧和最右侧元素比较

  class Solution { public: int search(vector<int>& nums, int target) { int n = (int)nums.size(); if (!n) { return -1; } if (n == 1) { return nums[0] == target ? 0 : -1; } int l = 0, r = n - 1; while (l <= r) { int mid = (l + r) / 2; if (nums[mid] == target) return mid; if (nums[0] <= nums[mid]) { if (nums[0] <= target && target < nums[mid]) { r = mid - 1; } else { l = mid + 1; } } else { if (nums[mid] < target && target <= nums[n - 1]) { l = mid + 1; } else { r = mid - 1; } } } return -1; } };

  Leetcode 977. 有序数组的平方

• 此题因为是针对一个已经排序的数组，所以最大值不是在数组的头部就是在数组的尾部，因此每次只要从后往前依次插入当前首部和尾部平方值较大的一个元素即可
• 注意插入是倒序的

  class Solution { public: vector<int> sortedSquares(vector<int>& nums) { vector<int> ret(nums.size(), 0); int begin = 0, end = nums.size()-1; int k = nums.size()-1; while(k>=0) { if(nums[begin]*nums[begin]<nums[end]*nums[end]) { ret[k--] = nums[end]*nums[end]; --end; } else { ret[k--] = nums[begin]*nums[begin]; ++begin; } } return ret; } };

LeetCode 153. 寻找旋转排序数组中的最小值

• 我们考虑数组中的最后一个元素x：在最小值右侧的元素（不包括最后一个元素本身），它们的值一定都严格小于x；而在最小值左侧的元素，它们的值一定都严格大于x。因此，我们可以根据这一条性质，通过二分查找的方法找出最小值。

  class Solution { public: int findMin(vector<int>& nums) { int low = 0; int high = nums.size() - 1; while (low < high) { int pivot = low + (high - low) / 2; if (nums[pivot] < nums[high]) { high = pivot; } else { low = pivot + 1; } } return nums[low]; } };

  Leetcode 4. 寻找两个正序数组的中位数

• 此题较为复杂，建议查看题解

  class Solution { public: int getKthElement(const vector<int>& nums1, const vector<int>& nums2, int k) { /* 主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较 * 这里的 "/" 表示整除 * nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个 * nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个 * 取 pivot = min(pivot1, pivot2)，两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个 * 这样 pivot 本身最大也只能是第 k-1 小的元素 * 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums1 数组 * 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums2 数组 * 由于我们 "删除" 了一些元素（这些元素都比第 k 小的元素要小），因此需要修改 k 的值，减去删除的数的个数 */ int m = nums1.size(); int n = nums2.size(); int index1 = 0, index2 = 0; while (true) { // 边界情况 if (index1 == m) { return nums2[index2 + k - 1]; } if (index2 == n) { return nums1[index1 + k - 1]; } if (k == 1) { return min(nums1[index1], nums2[index2]); } // 正常情况 int newIndex1 = min(index1 + k / 2 - 1, m - 1); int newIndex2 = min(index2 + k / 2 - 1, n - 1); int pivot1 = nums1[newIndex1]; int pivot2 = nums2[newIndex2]; if (pivot1 <= pivot2) { k -= newIndex1 - index1 + 1; index1 = newIndex1 + 1; } else { k -= newIndex2 - index2 + 1; index2 = newIndex2 + 1; } } } double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int totalLength = nums1.size() + nums2.size(); if (totalLength % 2 == 1) { return getKthElement(nums1, nums2, (totalLength + 1) / 2); } else { return (getKthElement(nums1, nums2, totalLength / 2) + getKthElement(nums1, nums2, totalLength / 2 + 1)) / 2.0; } } };

Leetcode 136. 只出现一次的数字

• 对整个数组元素挨个求异或，最后剩下的一个就是只出现一次的那个
• 因为出现过两次的会因为自己异或自己而变为0

  class Solution { public: int singleNumber(vector<int>& nums) { int sum = nums[0]; for(int i = 1; i<nums.size(); ++i) { sum^=nums[i]; } return sum; } };

LeetCode 31. 下一个排列

• 参考
• 从后向前 查找第一个 相邻升序 的元素对 (i,j)，满足 A[i] < A[j]。此时 [j,end) 必然是降序
• 在 [j,end) 从后向前 查找第一个满足 A[i] < A[k] 的 k。A[i]、A[k] 分别就是上文所说的「小数」、「大数」
• 将 A[i] 与 A[k] 交换
• 可以断定这时 [j,end) 必然是降序，逆置 [j,end)，使其升序
• 如果在步骤 1 找不到符合的相邻元素对，说明当前 [begin,end) 为一个降序顺序，则直接跳到步骤 4

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int l=nums.size(),i=l-2;
        while(i>=0&&nums[i]>=nums[i+1]){
            i--;
        }
        if(i>=0){
            int j=l-1;
            //找出nums[i]后面大于nums[i]的最小数的下标
            while(nums[j]<=nums[i]){
                j--;
            }
            swap(nums[i],nums[j]);
            reverse(nums.begin()+i+1,nums.end());//交换完后对nums[i]后面的数字进行从小到大排列
            //因为此时nums.begin()+i+1到nums.end()一定是降序排列,所以只需reverse就是从小到大排列了
        }else{//说明是最大排列,下一个应该是最小排列
            reverse(nums.begin(),nums.end());
        }
        return;
    }
};

Leetcode 452. 用最少数量的箭引爆气球

• 按照区间的右端点排序，取右端点的值，直到目前的区间的右端点的值小于下一个区间的左端点的值的时候就说明没有重叠部分了，需要增加新的区间

  class Solution { public: int findMinArrowShots(vector<vector<int>>& points) { if (points.empty()) { return 0; } sort(points.begin(), points.end(), [](const vector<int>& u, const vector<int>& v) { return u[1] < v[1]; }); int pos = points[0][1]; int ans = 1; for (const vector<int>& balloon: points) { if (balloon[0] > pos) { pos = balloon[1]; ++ans; } } return ans; } };

图的拓扑排序

广度优先搜索（Leetcode 207.课程表）

• 用一个数组记录每个节点的进入边的数量
• 开始的时候将所有入度为0的点加入队列
• 依次从队列中弹出点，将从这个点出发指向的所有点的入度-1，然后将跟这个点相关的路径全部删除
  • 假如此时遇到点的入度是0的话，将这个点加入队列
• 将队列中弹出的点加入输出序列中
• 假如最后图上的所有点都在输出序列中，说明无环，否则有环

  class Solution { public: bool canFinish(int numCourses, vector<vector<int>>& prerequisites) { vector<vector<int>> vMap(numCourses); vector<int> inCnt(numCourses, 0); vector<int> ans; for(int i = 0; i<prerequisites.size(); i++) { vMap[prerequisites[i][1]].push_back(prerequisites[i][0]); ++inCnt[prerequisites[i][0]]; } queue<int> q; for(int i = 0; i<numCourses; i++) { if(inCnt[i] == 0) { q.push(i); } } while(q.size()) { auto temp = q.front(); q.pop(); for(auto& i:vMap[temp]) { --inCnt[i]; if(inCnt[i] == 0)q.push(i); } vMap[temp] = vector<int>(); ans.push_back(temp); } if(ans.size()<numCourses)return false; else return true; } };

深度优先搜索

• 遍历所有节点，先标记自己被遍历过了
• 每个节点递归的遍历自己所有边指向的没有被打上遍历过的标签的节点
• 回溯的时候（也就是之后的节点都遍历结束之后）将自己添加到拓扑顺序的栈中
• 依次弹出栈中元素，得到顺序

  #include <iostream> #include <vector> #include <stack> using namespace std; class Graph { public: int vertices; vector<vector<int>> adjList; Graph(int V) : vertices(V), adjList(V) {} void addEdge(int u, int v) { adjList[u].push_back(v); } void topologicalSortUtil(int v, vector<bool>& visited, stack<int>& result) { visited[v] = true; for (int neighbor : adjList[v]) { if (!visited[neighbor]) { topologicalSortUtil(neighbor, visited, result); } } result.push(v); } void topologicalSort() { stack<int> result; vector<bool> visited(vertices, false); for (int i = 0; i < vertices; ++i) { if (!visited[i]) { topologicalSortUtil(i, visited, result); } } cout << "Topological Sort: "; while (!result.empty()) { cout << result.top() << " "; result.pop(); } } }; int main() { Graph g(6); g.addEdge(5, 2); g.addEdge(5, 0); g.addEdge(4, 0); g.addEdge(4, 1); g.addEdge(2, 3); g.addEdge(3, 1); g.topologicalSort(); return 0; }

  417. 太平洋大西洋水流问问题

• 此题主要是使用逆向搜索
• 也就是从海边往上倒溯看能到达哪个位置，减少遍历的次数

  class Solution { public: vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) { vector<vector<bool>> passed(heights.size(), vector<bool>(heights[0].size(), false)); vector<vector<bool>> passedR(heights.size(), vector<bool>(heights[0].size(), false)); int m = heights.size(), n = heights[0].size(); vector<vector<int>> ret; vector<vector<bool>> visited(heights.size(), vector<bool>(heights[0].size(), false)); for(int i = 0; i<m; ++i) { if(passed[i][0])continue; queue<pair<int, int>> q; passed[i][0] = true; q.push(make_pair(i, 0)); while(q.size()) { auto t = q.front(); q.pop(); int curH = heights[t.first][t.second]; visited[t.first][t.second] = true; if(t.first-1>=0 && !visited[t.first-1][t.second] && heights[t.first-1][t.second]>=curH && !passed[t.first-1][t.second]) { passed[t.first-1][t.second] = true; q.push(make_pair(t.first-1, t.second)); } if(t.second-1>=0 && !visited[t.first][t.second-1] && heights[t.first][t.second-1]>=curH && !passed[t.first][t.second-1]) { passed[t.first][t.second-1] = true; q.push(make_pair(t.first, t.second-1)); } if(t.first+1<m && !visited[t.first+1][t.second] && heights[t.first+1][t.second]>=curH && !passed[t.first+1][t.second]) { passed[t.first+1][t.second] = true; q.push(make_pair(t.first+1, t.second)); } if(t.second+1<n && !visited[t.first][t.second+1] && heights[t.first][t.second+1]>=curH && !passed[t.first][t.second+1]) { passed[t.first][t.second+1] = true; q.push(make_pair(t.first, t.second+1)); } } } for(auto& i : visited) { fill(i.begin(), i.end(), false); } // cout<<'!'<<endl; for(int i = 0; i<n; ++i) { if(passed[0][i])continue; queue<pair<int, int>> q; passed[0][i] = true; q.push(make_pair(0, i)); while(q.size()) { auto t = q.front(); q.pop(); int curH = heights[t.first][t.second]; visited[t.first][t.second] = true; if(t.first-1>=0 && !visited[t.first-1][t.second] && heights[t.first-1][t.second]>=curH && !passed[t.first-1][t.second]) { passed[t.first-1][t.second] = true; q.push(make_pair(t.first-1, t.second)); } if(t.second-1>=0 && !visited[t.first][t.second-1] && heights[t.first][t.second-1]>=curH && !passed[t.first][t.second-1]) { passed[t.first][t.second-1] = true; q.push(make_pair(t.first, t.second-1)); } if(t.first+1<m && !visited[t.first+1][t.second] && heights[t.first+1][t.second]>=curH && !passed[t.first+1][t.second]) { passed[t.first+1][t.second] = true; q.push(make_pair(t.first+1, t.second)); } if(t.second+1<n && !visited[t.first][t.second+1] && heights[t.first][t.second+1]>=curH && !passed[t.first][t.second+1]) { passed[t.first][t.second+1] = true; q.push(make_pair(t.first, t.second+1)); } } } for(auto& i : visited) { fill(i.begin(), i.end(), false); } for(int i = 0; i<m; ++i) { if(passedR[i][n-1])continue; queue<pair<int, int>> q; passedR[i][n-1] = true; q.push(make_pair(i, n-1)); while(q.size()) { auto t = q.front(); q.pop(); int curH = heights[t.first][t.second]; visited[t.first][t.second] = true; if(passed[t.first][t.second])ret.push_back({t.first, t.second}); if(t.first-1>=0 && !visited[t.first-1][t.second] && heights[t.first-1][t.second]>=curH && !passedR[t.first-1][t.second]) { passedR[t.first-1][t.second] = true; q.push(make_pair(t.first-1, t.second)); } if(t.second-1>=0 && !visited[t.first][t.second-1] && heights[t.first][t.second-1]>=curH && !passedR[t.first][t.second-1]) { passedR[t.first][t.second-1] = true; q.push(make_pair(t.first, t.second-1)); } if(t.first+1<m && !visited[t.first+1][t.second] && heights[t.first+1][t.second]>=curH && !passedR[t.first+1][t.second]) { passedR[t.first+1][t.second] = true; q.push(make_pair(t.first+1, t.second)); } if(t.second+1<n && !visited[t.first][t.second+1] && heights[t.first][t.second+1]>=curH && !passedR[t.first][t.second+1]) { passedR[t.first][t.second+1] = true; q.push(make_pair(t.first, t.second+1)); } } } for(auto& i : visited) { fill(i.begin(), i.end(), false); } for(int i = 0; i<n; ++i) { if(passedR[m-1][i])continue; queue<pair<int, int>> q; passedR[m-1][i] = true; q.push(make_pair(m-1, i)); while(q.size()) { auto t = q.front(); q.pop(); int curH = heights[t.first][t.second]; visited[t.first][t.second] = true; if(passed[t.first][t.second])ret.push_back({t.first, t.second}); if(t.first-1>=0 && !visited[t.first-1][t.second] && heights[t.first-1][t.second]>=curH && !passedR[t.first-1][t.second]) { passedR[t.first-1][t.second] = true; q.push(make_pair(t.first-1, t.second)); } if(t.second-1>=0 && !visited[t.first][t.second-1] && heights[t.first][t.second-1]>=curH && !passedR[t.first][t.second-1]) { passedR[t.first][t.second-1] = true; q.push(make_pair(t.first, t.second-1)); } if(t.first+1<m && !visited[t.first+1][t.second] && heights[t.first+1][t.second]>=curH && !passedR[t.first+1][t.second]) { passedR[t.first+1][t.second] = true; q.push(make_pair(t.first+1, t.second)); } if(t.second+1<n && !visited[t.first][t.second+1] && heights[t.first][t.second+1]>=curH && !passedR[t.first][t.second+1]) { passedR[t.first][t.second+1] = true; q.push(make_pair(t.first, t.second+1)); } } } return ret; } };

Leetcode 827. 最大人工岛

• 此题关键是要使用grid本身的空间在岛屿的每个位置上存储本身的大小方便计算
• 要额外维护一张表，将同一个岛屿的点编号为同样的，不同的岛屿编为不同的，防止最后求和的时候比如某个0的位置被同一个岛屿的多个点包围导致同一个岛屿累加了多次的重复

  class Solution { public: int largestIsland(vector<vector<int>>& grid) { vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false)); vector<vector<int>> identity(grid.size(), vector<int>(grid[0].size(), 0)); vector<pair<int, int>> visQue; int m = grid.size(), n = grid[0].size(); int id = 0; for(int i = 0; i<grid.size(); ++i) { for(int j = 0; j<grid[0].size(); ++j) { int cnt = 0; if(visited[i][j] || grid[i][j] == 0)continue; queue<pair<int, int>> q; visited[i][j] = true; q.push(make_pair(i, j)); while(q.size()) { auto tmp = q.front(); // cout<<tmp.first<<'|'<<tmp.second<<endl; q.pop(); visQue.push_back(tmp); ++cnt; if(tmp.first-1>=0 && !visited[tmp.first-1][tmp.second] && grid[tmp.first-1][tmp.second] == 1) { q.push(make_pair(tmp.first-1, tmp.second)); visited[tmp.first-1][tmp.second] = true; } if(tmp.second-1>=0 && !visited[tmp.first][tmp.second-1] && grid[tmp.first][tmp.second-1] == 1) { q.push(make_pair(tmp.first, tmp.second-1)); visited[tmp.first][tmp.second-1] = true; } if(tmp.first+1<m && !visited[tmp.first+1][tmp.second] && grid[tmp.first+1][tmp.second] == 1) { q.push(make_pair(tmp.first+1, tmp.second)); visited[tmp.first+1][tmp.second] = true; } if(tmp.second+1<m && !visited[tmp.first][tmp.second+1] && grid[tmp.first][tmp.second+1] == 1) { q.push(make_pair(tmp.first, tmp.second+1)); visited[tmp.first][tmp.second+1] = true; } } for(auto& k : visQue) { grid[k.first][k.second] = cnt; identity[k.first][k.second] = id; } id++; visQue.clear(); } } unordered_set<int> ids; int maxS = 0; for(int i = 0; i<m; ++i) { for(int j = 0; j<n; ++j) { maxS = max(maxS, grid[i][j]); if(grid[i][j]>0)continue; int sum = 0; if(i>0 && grid[i-1][j]>0 && ids.count(identity[i-1][j]) == 0) { ids.insert(identity[i-1][j]); sum+=grid[i-1][j]; } if(j>0 && grid[i][j-1]>0 && ids.count(identity[i][j-1]) == 0) { ids.insert(identity[i][j-1]); sum+=grid[i][j-1]; } if(i<m-1 && grid[i+1][j]>0 && ids.count(identity[i+1][j]) == 0) { ids.insert(identity[i+1][j]); sum+=grid[i+1][j]; } if(j<n-1 && grid[i][j+1]>0 && ids.count(identity[i][j+1]) == 0) { ids.insert(identity[i][j+1]); sum+=grid[i][j+1]; } maxS = max(maxS, sum+1); ids.clear(); } } return maxS; } };

Leetcode 127. 单词接龙

• 此题是讲字母相邻的单词组织成一张图
• 实际上是求图上两个点的最近距离
• 题解
• 广度优先搜索法
  • 每循环一次，找一个没有接触过的位置，将其距离更新为接触过的位置+1，然后也放入队列遍历
  • 注意，只考虑之前没有加入过的点，防止环的影响
  • 广搜到的第一条路一定是最近的，因为广搜会一次遍历所有可能的路径

    class Solution { public: unordered_map<int, vector<int>> edges; int getdistence(string& s1, string& s2) { int cnt = 0; for(int m = 0; m<s1.size(); ++m) { if(s1[m]!=s2[m])++cnt; } return cnt; } int ladderLength(string beginWord, string endWord, vector<string>& wordList) { // if(wordList.find(endWord) == wordList.end())return 0; vector<bool> visited(wordList.size(), false); vector<int> toBegin; queue<int> q; int endIndex = -1; for(int i = 0; i<wordList.size(); ++i) { if(wordList[i] == endWord)endIndex = i; if(getdistence(wordList[i], beginWord) == 1) { // toBegin.push_back(i); q.push(i); visited[i] = true; } for(int j = i+1; j<wordList.size(); ++j) { int cnt = getdistence(wordList[i], wordList[j]); if(cnt == 1) { edges[i].push_back(j); edges[j].push_back(i); } } } if(endIndex == -1)return 0; int cnt = 1; while(q.size()) { int s = q.size(); ++cnt; for(int i = 0; i<s; ++i) { auto tmp = q.front(); // cout<<wordList[tmp]<<' '; if(wordList[tmp] == endWord) { return cnt; } q.pop(); if(!edges.count(tmp)) { continue; } for(auto& f : edges[tmp]) { if(visited[f])continue; q.push(f); visited[f] = true; } } // cout<<endl; } return 0; } };

Leetcode 463. 岛屿的周长

• 这道题不需要使用搜索
• 只使用遍历即可，招每个节点左和上的相邻节点，减去内部边界
• 不找右和下是因为怕重复

  class Solution { public: int islandPerimeter(vector<vector<int>>& grid) { int sum = 0; // 陆地数量 int cover = 0; // 相邻数量 for (int i = 0; i < grid.size(); i++) { for (int j = 0; j < grid[0].size(); j++) { if (grid[i][j] == 1) { sum++; // 统计上边相邻陆地 if(i - 1 >= 0 && grid[i - 1][j] == 1) cover++; // 统计左边相邻陆地 if(j - 1 >= 0 && grid[i][j - 1] == 1) cover++; // 为什么没统计下边和右边？ 因为避免重复计算 } } } return sum * 4 - cover * 2; } };

STL相关

• 注意vector<>.size()返回的是无符号整数，unsigned与同样大小类型的有符号整数相加的时候会将这个有符号整数类型转换为无符号的，导致表示的意思出现区别

• 对无符号数字给负值的时候，实际的到的值是给的数字+该类型能表达的最大数字

  initializer_list<>

• 用于不定参数个数的函数的传参

• 只能传递同一个类型的参数

• 复制的时候是浅拷贝

  algorithm

  函数|功能
  |—|—|
  find(begin, end, val)|在begin和end（不包括）之间找val，找不到返回end，找到返回位置迭代器，是线性查找
  stable_sort(begin, end, compare)|是稳定排序算法，会保证相等元素的顺序

• 其他

bind函数

• 用于包装函数改变其参数列表

  auto newCallable = bind (callable, arg_list);

• 将可调用对象和参数绑定成一个新的可调用对象，可以延迟调用或者传递给其他函数使用。
• 将多元（参数个数大于1）的可调用对象转换成一元或者少元的可调用对象，即只绑定部分参数，剩下的参数在调用时传入。

  struct A { void print(int x, int y) { cout << x << " " << y << endl; } }; // 将print函数和一个参数绑定成一个新的可调用对象，另一个参数用占位符表示 auto f2 = bind(print, placeholders::_1, 2); f2(1); // 输出 1 2 f2(3); // 输出 3 2

• 注意bind后的函数传参是按照placeholder从小到大传参的，可以人为颠倒顺序

ref

• 将拷贝的参数转换为引用
• ref(val)

  hash哈希函数

• hash<key_type>()函数为内置类型，指针，string和智能指针提供了哈希函数

智能指针shared_ptr和unique_ptr

• shared_ptr允许多个指针指向同一个对象
• unique_ptr独占所指向的对象

  用法

• 对指针可以直接做条件判断，true就是非空，否则是空
• 最好不要用将自己申请的动态内存转化为智能指针的方式创建智能指针，可能会泄露
• p.get()返回指针指向的对象
  • 注意，如果智能指针被释放，那么使用get返回的指针指向的对象也会被释放
• shared_ptr比较是否相等时候，比较的是指向的对象是否相等，因此可以用来在STL中find()等等
• shared_ptr基本用法

  #include <iostream> #include <memory> int main() { // 创建 shared_ptr，并分配一个整数 std::shared_ptr<int> sharedInt = std::make_shared<int>(42); // 使用 shared_ptr std::cout << "Value: " << *sharedInt << std::endl; // 获取引用计数 std::cout << "Reference count: " << sharedInt.use_count() << std::endl; // 创建另一个 shared_ptr，共享相同的整数 std::shared_ptr<int> anotherSharedInt = sharedInt; // 引用计数增加 std::cout << "Reference count: " << sharedInt.use_count() << std::endl; return 0; }

• 另一种初始化
• shared_ptr<int> p(new int(1024));可以用动态对象初始化指针
• 但是必须显式的调用，不能隐式类型转换
• 不要使用shared_ptr的get方法为另一个智能指针赋值，会导致内存管理混乱
  • 比如另一个位置的shared_ptr析构，可能使得另一侧的引用计数为0，导致指向的对象直接被析构，但是这一侧的shated_ptr并不知情，再访问会导致段错误
• unique_ptr基本用法

  #include <iostream> #include <memory> int main() { // 创建 unique_ptr，并分配一个整数 std::unique_ptr<int> uniqueInt = std::make_unique<int>(42); // 使用 unique_ptr std::cout << "Value: " << *uniqueInt << std::endl; // unique_ptr 不能被拷贝，这会导致编译错误 // std::unique_ptr<int> anotherUniqueInt = uniqueInt; // 错误！ return 0; }

• 可以用release或者reset转移指针的所有权
  • reset会释放本身指向的内存，将目标转移到函数传入的新地址上
  • release会返回自己指向的内存地址，同时放弃对这个位置的控制权（不会释放内存）
• unique_ptr只有在即将被销毁（比如函数返回）或者是临时对象的时候可以被拷贝，接手自己的内存区域

  weak_ptr

• 可以绑定到shared_ptr但是不影响引用计数
• lock方法用于获取对应的shared_ptr，不存在则是空的指针对象
• expired可以看当前是不是还有shared_ptr在指向空间

  Blob

• 与vector类似，但是其中数据在拷贝的时候是公用的，不是像vector是复制的
• 管理机制与共享指针类似，最后一个被释放之后存储的数据才会删除

tuple

• 多种不同类型的组合
• 注意make_tuple可以不显式的声明类型

  #include <tuple> std::tuple<int, float, std::string> myTuple(42, 3.14, "Hello"); // 或者 auto myTuple = std::make_tuple(42, 3.14, "Hello"); //访问 std::cout << "First element: " << std::get<0>(myTuple) << std::endl; std::cout << "Second element: " << std::get<1>(myTuple) << std::endl; std::cout << "Third element: " << std::get<2>(myTuple) << std::endl; // 解包为多个变量 int intValue; double doubleValue; std::string stringValue; std::tie(intValue, doubleValue, stringValue) = myTuple; // 使用 std::tuple_size 获取 tuple 大小 std::cout << "Tuple size: " << std::tuple_size<decltype(myTuple)>::value << std::endl;

bitset

• 用于位运算的类

  #include <bitset> // 创建一个有 8 位的 bitset，初始值为 0 std::bitset<8> myBitset1; // 用整数值初始化 bitset std::bitset<8> myBitset2(42); // 使用二进制表示为 00101010 // 用字符串初始化 bitset std::bitset<8> myBitset3("10101010"); // 访问位 std::cout << "Bit at position 3: " << myBitset[3] << std::endl; // 修改位 myBitset.set(1, true); // 将第 1 位设置为 1 // set不给参数的话会默认为1 // reset会把指定的位设置为0 myBitset.flip(4); // 反转第 4 位 // 位与 std::bitset<8> resultAnd = bitset1 & bitset2; // 位或 std::bitset<8> resultOr = bitset1 | bitset2; // 位异或 std::bitset<8> resultXor = bitset1 ^ bitset2; // 获取 bitset 的大小 std::cout << "Size of myBitset: " << myBitset.size() << std::endl; // 检查是否所有位都是 0 std::cout << "All zeros? " << myBitset.none() << std::endl; // 检查是否有任意位是 1 std::cout << "Any ones? " << myBitset.any() << std::endl; // 检查是否所有位都是 1 std::cout << "All ones? " << myBitset.all() << std::endl;

lambda表达式

[capture list] (parameters) -> <return type>{};

• 返回类型可以省略
• 捕获的作用是比如函数作为谓词的时候，只能传递两个互相比较的参数，此时需要外部的参数就只能用捕获传入。
  • 全局变量不需要捕获也能使用
  • 可以捕获引用[&var]即可
  • 支持隐式捕获，也就是编译器自己推断捕获什么不捕获什么
  • [=, other vals]等号表示值捕获方式，可以与显式捕获混合使用
  • [&, other vals]引用符号表示引用捕获方式
  • 不同种类的捕获可以互相混用
  • 通过值捕获的变量一般不允许修改，除非在函数体之前加一个mutable关键字
• lambda是函数类型，不是函数指针

函数对象

• 包装器
• 可以将任何可以调用的对象存入，能使用()的就可以，包装为一个函数

  #include <iostream> #include <functional> // 一个普通函数 int Add(int a, int b) { return a + b; } // 一个函数对象 struct Multiply { int operator()(int a, int b) { return a * b; } }; int main() { // 使用 std::function 包装普通函数 std::function<int(int, int)> addFunction = Add; std::cout << "Add Function Result: " << addFunction(3, 4) << std::endl; // 使用 std::function 包装函数对象 std::function<int(int, int)> multiplyFunction = Multiply(); std::cout << "Multiply Function Result: " << multiplyFunction(3, 4) << std::endl; // 使用 Lambda 表达式 std::function<int(int, int)> lambdaFunction = [](int a, int b) { return a / b; }; std::cout << "Lambda Function Result: " << lambdaFunction(8, 2) << std::endl; return 0; }

迭代器

反向迭代器

• 倒序排序

  sort(vec.begin(), vec.end()); sort(vec.rbegin(), vec.rend()); // 倒序

  iostream迭代器

• 连续输入使用
• 不初始化的话就是尾后迭代器

  istream_iterator<int> in_iter(cin); // 创建一个表示istream尾后位置的istream_iterator istream_iterator<int> eof; // 创建一个int类型的vector，并用in_iter和eof初始化 vector<int> vec(in_iter, eof); // 读入一个元素并且赋值 in_iter++; int y = *in_iter;

• 输出流迭代器

  // 创建一个输出流迭代器，绑定到cout，数据类型为int，分隔符为"," ostream_iterator<int> out_it(cout, ","); // 向输出流迭代器写入一个数据 *out_it = 10; // 创建一个vector容器，存储一些int数据 vector<int> vec = {1, 2, 3, 4, 5}; // 使用copy算法，将vector中的数据复制到输出流迭代器中 copy(vec.begin(), vec.end(), out_it);

• 向输出流迭代器写入数据就是输出
• 初始化的时候加的是每个数据之后的分隔符
• *, ++等运算符对他没什么意义

  语法相关

• 使用三目运算符?:的时候最好外加括号，否则会因为计算顺序的原因报错

  管理内存

• new和delete是运算符一个分配动态对象一个删除动态对象

for_each

• 作用是对一个区间内的变量每个都执行指定的操作（函数）

  #include <iostream> #include <vector> #include <algorithm> // 一个函数，用于在 for_each 中作为操作 void PrintSquare(int x) { std::cout << x * x << " "; } int main() { // 创建一个向量 std::vector<int> numbers = {1, 2, 3, 4, 5}; // 使用 for_each 遍历向量并应用操作 std::for_each(numbers.begin(), numbers.end(), PrintSquare); // 输出结果：1 4 9 16 25 return 0; }

函数返回值

• 不要返回局部对象的引用类型，否则会因为局部对象生命周期结束而失效
• 返回指向某个数组的指针的函数

  int (*func(int i))[10];// 看的时候从里往外看，先返回的是指针，指针指向的是int[10] // 或者 typedef int arr[10]; arr* func(int i); // 或者 auto func(int i) -> int(*)[10]

• 也可以直接在返回值的位置使用decltype标出类型

Cpp函数重载

• 函数重载只有在同一个级别的作用域才行
  • 假如在某个函数内部声明了一个与外部函数同名的函数，会导致外部同名函数被屏蔽
• 假如有一组参数传入导致系统无法区分具体调用哪个的话会导致编译出错
• 类型转换的分类

Cpp函数内联

• 编译器可以选择忽略内联函数请求，也可以自动优化内联函数

是否是开发状态

• 定义NDEBUG
• 如果定义了就不能使用assert等debug用的工具
• 也可以自己用#ifndef NDEBUG来控制自己写的代码哪些用在调试阶段

  调试输出

• 可以用__func__打印当前函数的名字
• __FILE__文件名
• __LINE__行号
• __TIME__编译时间
• __DATE__编译日期

  backtrace和backtrace_symbols函数

  #include <execinfo.h> int backtrace(void **buffer, int size);

• backtrace函数是一个用于获取调用栈信息的函数，通常在调试或错误处理中使用。它在标准的C库中，头文件是#include <execinfo.h>
• 使用backtrace_symbols函数将backtrace信息转换成字符串
• char **bt_strings = backtrace_symbols(bt_buffer, bt_size);

  #include <execinfo.h> #include <stdio.h> #include <stdlib.h> void printStackTrace() { const int max_frames = 16; void *addrlist[max_frames + 1]; int addrlen = backtrace(addrlist, sizeof(addrlist) / sizeof(void *)); if (addrlen == 0) { fprintf(stderr, "No stack trace available.\n"); return; } char **symbolList = backtrace_symbols(addrlist, addrlen); if (symbolList == NULL) { perror("backtrace_symbols"); exit(EXIT_FAILURE); } printf("Stack trace:\n"); for (int i = 0; i < addrlen; i++) { printf("%s\n", symbolList[i]); } free(symbolList); } void foo() { printStackTrace(); } void bar() { foo(); } int main() { bar(); return 0; }

• backtrace函数在编译时需要开启调试信息。如果使用gcc编译，可以添加-g
• 传入的需要是一个指针数组或者是使用addrlist = (void **)malloc((sizeof(void *) * addrlen));分配好内存的空间

  函数指针

• 给函数指针赋值的时候加不加取地址符号都一样

  <return type> (*func name)(<para> parameters);

• 不同种类的函数指针之间无法转换，即使形参列表能转换，也就是说必须是返回类型和形参列表与自身完全一样的函数才可以赋值给函数指针
• 但是调用的时候可以发生类型转换
• 返回的时候不能返回函数，因为函数不能拷贝，只能返回函数指针

  如何返回函数指针

• int (*f1(int))(int, int);返回的是一个int(*)(int, int)类型的函数指针
• 或者写auto f(int) -> int(*)(int, int)

动态内存管理

动态数组

• int*a = new int[10];是未初始化的
• int*a = new int[10]();是已经值初始化为0的
• int* a = new int[3]{0, 1, 2};是显式初始化列表的
• 创建长度为0的动态数组可以，但不能解引用
• 释放的时候必须用delete [] ptr

allocator类申请内存

#include <iostream>
#include <memory>

int main() {
    // 使用 std::allocator 分配一块内存来存储 int 类型的元素
    std::allocator<int> allocator;

    // 分配内存以存储一个 int
    int* ptr = allocator.allocate(1);

    // 在分配的内存上构造 int 对象
    allocator.construct(ptr, 42);

    // 使用构造的对象
    std::cout << "Value: " << *ptr << std::endl;

    // 销毁对象并释放内存
    allocator.destroy(ptr);
    allocator.deallocate(ptr, 1);

    return 0;
}

• alloccate仅仅是分配内存
• construct才构造对象
• 删除的时候先destroy
• 然后再解除内存占用deallocate
• 使用allocator构造内存的时候可以像使用指针一样对指针做加减，只要不超出构造的范围即可

  一次初始化多个元素

• `std::uninitialized_fill(intPtr, intPtr + 3, 1);
  • 注意，uninitialized_fill的第二个参数类似于尾后迭代器，不会真的被赋值

面向对象

成员函数

• 常量成员函数<return type> func() const {}

  • 不修改类对象的函数
  • 对这个类的const实例的时候会调用const的成员函数
  • 但是假如某个成员有mutable关键字，那么也可以修改

    访问说明符

• public和private可以反复出现多次

  友元

• 类内声明

• friend <return type> func();

• 即使这个类被内嵌在一个子类中，也可以访问相应部分的成员

  不同类别的继承

• private继承会把所有从基类继承的成员都作为private对象

• protected会把所有的作为protected

• public则不改变权限

• 可以手动在public、protected或者private后面使用using 基类名:: 基类成员手动变更访问权限

• 继承的时候子类的同名成员会覆盖基类的，无论是变量还是成员函数

  作用域运算符::

• 访问全局作用域中的变量直接用::<variable>即可

• 访问类的就用<class name>::<var>

  构造函数

• 子类在构造的时候必须在初始化列表中显式的调用基类的构造函数构造基类的部分

• 派生类构造函数只能通过初始化列表或构造函数的成员初始化列表来调用基类构造函数，而在函数体中是无法再次调用的

  类成员初始化

• 无论初始化列表里怎么写，类成员的初始化顺序是按照他们在类中定义的顺序的

  委托构造函数

• 类的多个构造函数中一个构造函数借用类的其他功能强大的构造函数构造对象

  class test { string data; public: test(string s):data(s){} test():test("Hello World"){} // 这里是委托带参数的构造函数test(string s)构造对象 }

• 调用默认构造函数（无参数）的时候不能加括号，否则编译器会认为你想声明一个函数

  className obj();// 看起来就是声明一个叫obj的函数

  拷贝构造函数

• className(const className& cName){};

• 第一个参数必须是自身的引用

• 其他参数必须有默认值

• 注意形如<className> val = valOld;的是拷贝初始化

  移动构造函数

• 移动语义的目的是在避免不必要的数据复制的同时，更高效地管理资源。

• 在 C++11 引入右值引用之前，对象的拷贝构造函数是唯一的构造函数，用于复制对象。然而，对于临时对象或即将销毁的对象，进行深拷贝可能是不必要的开销。移动构造函数通过使用右值引用，允许在不复制底层资源的情况下将资源从一个对象“移动”到另一个对象。

• 必须是noexcept标明的

• 传入的参数是一个右值引用

• 有不具备移动构造功能的成员，自身也不能移动构造

  #include <iostream> #include <string> class MyString { public: // 移动构造函数 MyString(MyString&& other) noexcept : data(other.data), length(other.length) { std::cout << "Move Constructor" << std::endl; // 移动构造函数中，将原对象的资源指针置为空，避免资源被析构 other.data = nullptr; other.length = 0; } // 构造函数 MyString(const char* str) : data(strdup(str)), length(strlen(str)) { std::cout << "Constructor" << std::endl; } // 析构函数 ~MyString() { std::cout << "Destructor" << std::endl; // 释放资源 free(data); } private: char* data; std::size_t length; }; int main() { // 创建一个对象 MyString source("Hello, World!"); // 调用移动构造函数，将资源从 source 移动到 target MyString target = std::move(source); // 输出结果 std::cout << "Source String: " << (source.GetData() ? source.GetData() : "nullptr") << std::endl; std::cout << "Target String: " << (target.GetData() ? target.GetData() : "nullptr") << std::endl; return 0; }

  运算符重载

• 可以是成员函数也可以直接是函数

• 如果运算符是某个类的成员函数那么左侧的操作数必须是这个类的对象

• 重载输入输出运算符的时候必须不是成员函数

• 下标运算符必须是成员函数

• 赋值运算符必须是成员函数

  自增自减运算符

• className& operator++();前置

• className& operator(int); 后置，参数无用，用于与前置区分

• 一般是成员函数

重载->运算符

• 返回值必须是指针（可以是某个成员函数类型的指针）

  #include <iostream> class MyClass { public: void Display() const { std::cout << "Displaying MyClass" << std::endl; } // 重载 -> 运算符 MyClass* operator->() { return this; } }; int main() { MyClass myObject; // 使用重载的 -> 运算符 myObject->Display(); return 0; }

等号运算符

• className& operator=(const className&);
• 控制等号的行为
• return *this;即可
• 注意处理等号左右是同一个变量的情况

要求系统合成一个默认的构造/析构函数

• ClassName() = default;
• =default;

  禁止一个构造/复制函数被调用

• ClassName &operator=(const ClassName&) = delete;
• =delete;
• 可以对于任何函数使用
• 删除析构函数的类型，不能定义该类型的变量或者释放该类型动态对象的指针

类型转换

• 如果类具有只接受一个参数的构造函数，那么编译器可以将这个参数类型的对象自动转换为这个类的对象
  • 给构造函数增加一个explicit参数可以禁止这种转换
  • 但是static_cast可以调用explicit的构造函数

重载类型转换运算符

• 类型转换运算符通常不显式声明返回类型，因为它们没有返回类型

  #include <iostream> class Distance { private: int feet; float inches; public: Distance(int ft, float in) : feet(ft), inches(in) {} // 类型转换运算符，将 Distance 转换为 float operator float() const { return static_cast<float>(feet) + inches / 12.0f; } }; int main() { Distance d(5, 9.0); // 使用类型转换运算符将 Distance 转换为 float float totalInches = static_cast<float>(d); std::cout << "Total Inches: " << totalInches << std::endl; return 0; }

• 注意防止类型转换运算符与某些具有隐式类型转换功能的构造函数出现二义性
• 只要有多个用户自定义的类型转换都能达到目的，编译器就认为出线了二义性

override

• override的主要作用是在子类中表明某个函数是覆盖基类的虚函数的，方便检查是否真的覆盖了

动态绑定

• 使用一个基类的指针调用一个虚函数
• 根据不同的子类对虚函数的继承，产生不同的结果
• 使用基类的指针调用子类的时候，必须基类也有这个函数才行
• 使用智能指针也能实现这些功能

多态和虚函数

• 使用基类的指针（或引用）不能直接访问子类中定义了但是基类中没定义的成员函数和变量
  • 需要使用类型转换才能访问
• 但是可以访问子类中重载了的基类的虚函数
• 虚函数继承的时候必须函数头完全一致才行，这样才能实现多态
  • 不一样的话会直接覆盖基类的虚函数，不会产生多态，用基类的指针的时候还是会调用基类的函数
• 可以使用类名和作用域运算符手动指定通过指针调用的是哪个函数，从而防止运行时才知道是哪个
• 基类的构造函数中无法访问子类重载的虚函数，因为这个虚函数表是之后才被构建出来的

  析构函数

• 基类的析构函数最好写成虚函数，方便多态调用的时候析构掉整个的，否则析构基类的动态对象的时候会只析构基类的部分导致内存泄漏
• 具有手动析构函数的类，编译器一般不会自动合成移动构造函数、拷贝构造函数、等号运算符重载等，需要的话最好手动指出
  • 否则会因此导致继承他的子类因为父类没有这些函数而无法复制构造

    基类的拷贝构造函数和移动构造函数

• 必须显式的子类的相应函数中的初始化列表中调用基类的拷贝构造函数或者移动构造函数
  • 

基类和派生类的=赋值运算符

• 需要在派生类的=赋值运算符函数体中手动调用基类的赋值运算符

构造函数虚函数的情况

• 在派生类的构造函数初始化列表中调用基类的构造函数的时候最好手动通过类名::的形式指定需要调用的函数，防止因为多态导致调用了继承的构造函数

智能指针的情况

• 涉及智能指针的情况也可以实现多态
• make_shared或者其他构造一个子类对象即可

抽象类和纯虚函数

• 在一个成员函数后面加上=0;即可实现
• 类不能被实例化
• 纯虚函数的定义必须在外部

集成的时候的构造函数

• 基类的数据成员必须调用基类的构造函数构造（在初始化列表直接调用）
• 然后再按声明的顺序构造自身的对象

不能被继承的类

• 类声明之后加一个final

private和protected

• protected是继承的类能拿到但是别的类拿不到
• private继承的类也拿不到
• 派生类的友元对基类的保护对象访问没有任何特权，无法访问protected

聚合类

• 所有成员public
• 没有构造函数
• 类内没给初始值
• 没有基类和虚函数
• 可以用花括号直接初始化，类似于struct

  字面值类

• 数据成员必须都是字面值类型
• 至少有一个常量表达式的构造函数
• 析构函数必须是默认的
• 内置类型必须是常量表达式，类调用自己的常量构造函数
• constexpr的构造函数的函数体必须是空的
• 此时可以在构造的时候加一个constexpr

  静态成员

• static
• 对象的内存不包含静态对象
• static函数不含有this指针，不能处理非static成员
• 可以使用类作用域直接调用，也可以用对象的.调用
• static关键字只出现在类内声明的场合，定义的时候不出现
• 初始化
  • 只有是constexpr的情况下可以在类内声明，但是无法在外部使用
  • int <class name>:: var = blabla;
• 可以在一个类还没被初始化完的时候就声明它的静态对象
• 类的（不一定是静态）成员函数操作静态成员的时候可以直接操作，不需要加作用域运算符

IO流对象

• iostream, fstream, sstream
• 不能修改，赋值
• 输出endl是刷新缓冲区附带一个回车，输出flush则只刷新缓冲区，输出ends刷新缓冲区的同时附带一个空格
• 输入和输出流可以绑定，多个输入可以绑定到一个输出
  • 用.tie(<some stream>)函数
  • 输入与输出绑定的时候，调用输入流的时候自动刷新输出缓冲区
• fstream可以用open或者close打开或者关闭文件
• 析构的时候会自动close文件

  打开方式

  open函数flag|功能
  |—|—|
  in|读
  out|写
  app|追加(每次操作都从末尾开始)
  ate|打开的时候定位到结尾
  trunc|如果存在，丢弃内容
  binary|二进制
• 只有app和in方式可以保留原来的内容
• 不指定的话是out和trunc

  sstream

• 自身就是个string
• 可以初始化也可以不初始化

  #include <iostream> #include <string> #include <sstream> using namespace std; int main() { // 将一个整数转换为string int n = 123; stringstream ss1; ss1 << n; // 向stringstream写入整数 string s1 = ss1.str(); // 获取stringstream内部的string cout << "s1 = " << s1 << endl; // 输出s1 // 将一个string分割为单词 string s2 = "Hello world!"; stringstream ss2(s2); // 用string初始化stringstream string word; while (ss2 >> word) // 从stringstream读取单词 { cout << "word = " << word << endl; // 输出单词 } return 0; }

std::istringstream

• 一个字符串输入流，允许你从字符串中读取数据，就像从标准输入流中读取数据一样

  #include <iostream> #include <sstream> #include <string> int main() { std::string inputString = "123 4.56 Hello"; // 创建 istringstream 对象，并将字符串传入 std::istringstream iss(inputString); int intValue; float floatValue; std::string stringValue; // 从字符串流中读取数据 iss >> intValue >> floatValue >> stringValue; // 输出读取到的数据 std::cout << "Int: " << intValue << ", Float: " << floatValue << ", String: " << stringValue << std::endl; return 0; }

  std::ostringstream

• 一个字符串输出流，允许你将数据写入字符串，就像写入标准输出流一样

  #include <iostream> #include <sstream> #include <string> int main() { int intValue = 42; float floatValue = 3.14; std::string stringValue = "Hello, World!"; // 创建 ostringstream 对象 std::ostringstream oss; // 将数据写入字符串流 oss << "Int: " << intValue << ", Float: " << floatValue << ", String: " << stringValue; // 获取字符串 std::string resultString = oss.str(); // 输出写入的字符串 std::cout << resultString << std::endl; return 0; }

iostream格式化

int num = 42;
// 进制
std::cout << "Default: " << num << std::endl;
std::cout << "Hexadecimal: " << std::hex << num << std::endl;
std::cout << "Octal: " << std::oct << num << std::endl;
std::cout << "Decimal: " << std::dec << num << std::endl;
//填充字符
std::cout << "Default fill: " << std::setw(10) << num << std::endl;
std::cout << "Fill with '*': " << std::setfill('*') << std::setw(10) << num << std::endl;
//对齐
 std::cout << "Default alignment: " << std::setw(10) << num << std::endl;
std::cout << "Left alignment: " << std::left << std::setw(10) << num << std::endl;
std::cout << "Right alignment: " << std::right << std::setw(10) << num << std::endl;
std::cout << "Internal alignment: " << std::internal << std::setw(10) << -num << std::endl;
// 精度
double pi = 3.141592653589793;
std::cout << "Default precision: " << pi << std::endl;
std::cout << "Precision 4: " << std::setprecision(4) << pi << std::endl;
// 设置宽度
std::cout << "Width 10: " << std::setw(10) << num << std::endl;

iostream其他用法

• cin.get

  int cin.get(); istream& cin.get(char& var); istream& get ( char* s, streamsize n ); istream& get ( char* s, streamsize n, char delim )。

• cin.getline

  istream& getline(char* s, streamsize count); //默认以换行符结束 istream& getline(char* s, streamsize count, char delim);

• gets
• gets是C中的库函数，在<stdio.h>申明，从标准输入设备读字符串，可以无限读取
• 不会判断上限，以回车结束或者EOF时停止读取

  #include <iostream> using namespace std; int main() { char array[20]={NULL}; gets(array); cout<<array<<endl; system("pause"); return 0; }

  模板

• 声明模板类型
• template<typename T>或者template<typename T, class U>
• class和typename相同，都可以， 但每个类型钱都必须有这二者之一

声明未定大小的数组

• template<unsigned N, unsigned M>其中N和M是未定的大小，比如用于

  template<unsigned N, unsigned M> int compare(const char (&p1)[N], const char (&p2)[M]);

  类模板和类模板的成员函数

  #include <iostream> // 类模板定义 template <typename T> class SimpleTemplate { private: T data; public: // 构造函数 SimpleTemplate(T value) : data(value) {} // 成员函数 void display() { std::cout << "Data: " << data << std::endl; } // Getter 函数 T getData() const { return data; } // Setter 函数 void setData(T value) { data = value; } };

• 在类外定义类的成员函数注意也要写模板参数

  #include <iostream> // 类模板的声明 template <typename T> class MyClass { private: T data; public: // 构造函数的声明 MyClass(T value); // 成员函数的声明 void display() const; }; // 构造函数的定义 template <typename T> MyClass<T>::MyClass(T value) : data(value) {} // 成员函数的定义 template <typename T> void MyClass<T>::display() const { std::cout << "Data: " << data << std::endl; }

• 一个模板类的成员函数在用到的时候才被实例化
• 在一个类模板的作用域内，不必在类名之后带<T>

  template <typename T> retType className<T>::func(val) { // 这里使用类的时候直接用className就行 }

  类模板的友元函数

• 只有实例化为同一种类型才成立的友元

  #include <iostream> // 前置声明 template <typename T> class MyClass; // 友元类模板的特例化 template <typename T> class FriendClass { public: // 友元函数模板的特例化 friend void FriendFunction(const MyClass<T>& obj); }; // 类模板的声明 template <typename T> class MyClass { private: T data; public: // 构造函数 MyClass(T value) : data(value) {} // 友元声明 friend class FriendClass<T>; // 成员函数 void display() const { std::cout << "Data: " << data << std::endl; } };

• 可以通过在friend函数前面独立增加一个template <typename X>来打破友元必须与类实例化为相同的类型才能成为友元的要求，从而使得所有情况下友元都成立

  模板类型别名

  template <typename T> using twin = pair<T, T>; twin<string> authors; // 相当于`pair<string, string>`