Posts

coverity 的 WRAPPER_ESCAPE 告警 const char* Foo() { std::string str_msg("test"); return str_msg.c_str(); } int main() { const char *p_msg = Foo(); printf("%s\n", p_msg); return 0; } // output:（为空，或乱码） D? 上面代码中的 Foo 函数会被 coverity 报告 WRAPPER_ESCAPE，详细说明是： Wrapper object use after free (WRAPPER_ESCAPE) 1. escape: The internal representation of local strMsg escapes, but is destroyed when it exits scope 大意是局部变量 str_msg 在离开函数 Foo 的时候会被释放（因为 str_msg 是分配在栈上的变量），而通过函数 std::string::c_str() 获取的指向 str_msg 头部的指针会因此变为一个悬空指针，将这个悬空指针返回给函数调用者使用将会发生不可预知的行为。 而 c_str() 本身返回的是一个 const char *p，虽然我们无法直接修改指针 p 所指向的数据，但我们可以通过修改 str_msg 来达到修改 p 所指向内存的效果，例如如下的代码： ...

C++ 协程（1）：函数和协程 这篇文章的目的是探究 C++ 中协程的机制和用法，以及怎样利用协程的特性来构建上层的库和应用。 1. 栈帧和函数 栈帧是一个函数执行的环境，包括函数参数、函数返回地址、局部变量等信息。操作系统每次调用一个函数，都会为其分配一个新的栈帧，相关的概念有： ESP：栈指针寄存器（Extended Stack Pointer），其内存中存放一个始终指向系统栈最顶部栈帧栈顶的指针 EBP：基址指针寄存器（Extended Base Pointer），其内存中存放一个始终指向系统最顶部栈帧栈底的指针 函数栈帧：ESP和EBP之间的内存空间为当前栈帧，EBP标识了当前栈帧的底部，ESP标识了当前栈帧的顶部 对于普通的函数来说，一般我们可以对其进行两种操作：call（调用）和 return（返回）。为了方便对比，此处不讨论 throw exception 的情况。在运行一个 C++ 程序时，编译器会先执行 C++ runtime，然后会调用 main 函数，再由 main 函数调用其他的函数。 call 操作一般包含以下几个步骤： 参数入栈：参数从右向左依次入栈 返回地址入栈：将当前代码区的下一条待执行的指令入栈，以便在函数 return 之后执行 代码区跳转：处理器跳转到被调函数的入口 栈帧调整，包括： 保存当前栈帧状态值，EBP 入栈 从当前栈帧切换到新的栈帧，更新 EBP，将 EBP 的值设置为 ESP 的值 给新的栈帧分配内存空间，更新 ESP，将 ESP 的值减去所需空间的大小 当一个函数通过 return 语句返回时，执行的步骤与调用时相反： 2. 协程 协程由程序所控制，即在用户态执行，而不是像线程一样由操作系统内核管理，使用协程时，不需要如线程一般频繁地进行上下文切换，性能能够得到很大的提升，因此协程的开销远远小于线程的开销。一般来说协程有三种特性： suspend 悬停：暂停当前协程的执行，将执行权交还给调用者，但是保留当前栈帧。和函数的 return 类似，协程的 suspend 只能由协程自身发起 resume 恢复：继续执行已经 suspend 的协程，重新激活协程的栈帧 destroy 销毁：销毁协程的栈帧和其对应的内存 可以看到，协程可以在不清除栈帧的情况下被挂起而不被销毁，因此我们不能够使用调用栈这样的数据结构来严格保证活动栈帧的生命周期，我们可以把协程存储在堆中。我们可以把协程的栈帧分为两部分，一部分是执行栈帧，这部分仅在当前协程执行期间存在，在执行结束，即协程 suspend 的时候被释放；另一部分是数据栈帧，这部分即使在协程 suspend 的时候依然存在。 ...

LeetCode 树（3） 题目 4. 递归求解 617 合并二叉树 合并两个二叉树。 判断各个节点是否存在，全部合并到一棵树上即可。 class Solution { public: TreeNode *mergeTrees(TreeNode *t1, TreeNode *t2) { if (!t1 && !t2) return nullptr; else if (!t1) return t2; else if (!t2) return t1; t1->val += t2->val; t1->left = mergeTrees(t1->left, t2->left); t1->right = mergeTrees(t1->right, t2->right); return t1; } }; 226 翻转二叉树 翻转一个二叉树。 先将左右子树分别翻转，再交换两者的位置。 class Solution { public: TreeNode *invertTree(TreeNode *root) { if (!root) return nullptr; TreeNode *left = invertTree(root->left), *right = invertTree(root->right); root->right = left; root->left = right; return root; } }; 104 二叉树的最大深度 找出一个二叉树的最大深度。 ...

LeetCode 排序 题目 56 合并区间 按照间隔的起始进行排序，判断下一个间隔的起始是否大于前一个间隔的末尾，如果大于的话就把之前的间隔加入结果数组，否则继续扩展当前的间隔。 class Solution { public: vector<vector<int>> merge(vector<vector<int>> &intervals) { vector<vector<int>> res; int n = intervals.size(); if (n == 0) return res; sort(intervals.begin(), intervals.end(), [](vector<int> const &v1, vector<int> const &v2) { return v1[0] < v2[0]; }); int start = intervals[0][0], end = intervals[0][1]; for (int i = 1; i < n; ++i) { if (intervals[i][0] > end) { res.push_back(vector<int>{start, end}); start = intervals[i][0]; } end = max(end, intervals[i][1]); } res.push_back(vector<int>{start, end}); return res; } }; 179 最大数 先把数字转换为字符串，然后自定义类似于字典序的排序规则 s1 + s2 > s2 + s1 进行排序。 ...

LeetCode 堆 题目 215 数组中的第 K 个最大元素 最简单的堆的应用。 class Solution { public: int findKthLargest(vector<int> &nums, int k) { priority_queue<int, vector<int>, greater<>> heap; for (auto &m:nums) { if (heap.size() < k || m > heap.top()) heap.push(m); if (heap.size() > k) heap.pop(); } return heap.top(); } }; 347 前 K 个高频元素 先遍历一次统计出数组中各个元素出现的次数，再用一个大根堆将前 k 个高频元素保存下来，最后再将这些元素依次 pop 出来存入结果数组。时间复杂度是 O(n)，空间复杂度是 O(n)。 class Solution { public: vector<int> topKFrequent(vector<int> &nums, int k) { priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> freq; unordered_map<int, int> count; vector<int> res(k, 0); for (auto &m:nums) ++count[m]; for (auto &c:count) { freq.push(pair<int, int>(c.second, c.first)); if (freq.size() > k) freq.pop(); } for (int i = 0; i < k; ++i) { pair<int, int> p = freq.top(); freq.pop(); res[i] = p.second; } return res; } }; 451 根据字符出现频率排序 用一个大根堆保存每个字符出现的频率，然后依次将原字符串覆盖即可。 ...