C++里一个简单的 ::std::sort 怎么就能造成堆溢出呢？

C++ 里怎么一个简单的个简 ::std::sort 就能堆溢出呢?

BV1Z64y1a7P1 坑神截图

这周力扣周赛照例去凑热闹。

前两道题很快写完了，单的堆溢T3T4读了题...嗯，造成不憋了，个简等坑神的单的堆溢题解吧。

午时十二点，造成令我十分意外地发现坑神T2竟然罚时了好多次?个简

T2不就是重载一下 sort 的比较函数吗?看坑神的b站录象[1]，再看看评论，单的堆溢才知道 C++ 中的造成一个惊天大坑。得益于4个月来对 y 总高质量代码风格与良好书写习惯的个简阅读与模仿，我在考试时“幸运”地避开了这个坑。单的堆溢

但还是造成很有必要记录一下。

题目：找出数组中的个简第 K 大整数

给你一个字符串数组 nums 和一个整数 k 。nums 中的单的堆溢每个字符串都表示一个不含前导零的整数。

返回 nums 中表示第 k 大整数的造成字符串。高防服务器

注意：重复的数字在统计时会视为不同元素考虑。例如，如果 nums 是 ["1","2","2"]，那么 "2" 是最大的整数，"2" 是第二大的整数，"1" 是第三大的整数。

示例 1：

输入：nums = ["3","6","7","10"], k = 4 输出："3" 解释： nums 中的数字按非递减顺序排列为 ["3","6","7","10"] 其中第 4 大整数是 "3" 

示例 2：

输入：nums = ["2","21","12","1"], k = 3 输出："2" 解释： nums 中的数字按非递减顺序排列为 ["1","2","12","21"] 其中第 3 大整数是 "2" 

示例 3：

输入：nums = ["0","0"], k = 2 输出："0" 解释： nums 中的数字按非递减顺序排列为 ["0","0"] 其中第 2 大整数是 "0" 

提示：

1 <= k <= nums.length <= 1 <= nums[i].length <= 100 nums[i] 仅由数字组成 nums[i] 不含任何前导零

我的临场作答

struct Num {      string a;     bool operator< (const Num& t) const     {          if (a.size() != t.a.size()) return a.size() < t.a.size();         for (int i = 0; i < a.size(); ++ i)         {              if (a[i] != t.a[i]) return a[i] < t.a[i];         }         return false;     } }; class Solution {  public:     string kthLargestNumber(vector<string>& nums, int k) {          vector<Num> S;         for (auto&& t: nums)         {              S.push_back({ t});         }         sort(S.begin(), S.end());         return S[S.size() - k].a;     } }; 

经验：

重载 sort 中，在 operator < 或者 cmp 中 a == b 时一定也得返回 false !如果不返回 false 而是 true 将造成堆栈溢出!

“主要是因为如果a==b时return true的话，那么我们在a和b相等的时候，问a “原来，STL中的sort并非只是网站模板普通的快速排序，除了对普通的快速排序进行优化，它还结合了插入排序和堆排序。根据不同的数量级别以及不同情况，能自动选用合适的排序方法。当数据量较大时采用快速排序，分段递归。一旦分段后的数据量小于某个阀值，为避免递归调用带来过大的额外负荷，便会改用插入排序。而如果递归层次过深，有出现最坏情况的倾向，还会改用堆排序。” 坑神掉进了这个坑：【算法实况】又血崩了，这种题目完全没经验乌乌 - 力扣周赛 - LeetCode Weekly 256[2]

此外，一些关于重载效率的对比如下：

我的题解性能(struct重载operator<)：执行用时 236ms 内存消耗 76.9MB 力扣官方题解性能(lambda重载sort)：执行用时 132ms 内存消耗 53.8MB 巨佬墨染空[3]题解性能(重载sort)：执行用时 592ms 内存消耗 341.7MB

代码如下。这让我感觉很费解。

// 力扣官方题解 class Solution {  public:     string kthLargestNumber(vector<string>& nums, int k) {          nth_element(nums.begin(), nums.begin() + k - 1, nums.end(), [](const string& u, const string& v "") {              return u.size() > v.size() || (u.size() == v.size() && u > v);         });         return nums[k - 1];     } }; // 巨佬墨染空题解 bool inline cmp(string x, string y) {   if (x.size() != y.size()) return x.size() > y.size();  return x > y; } class Solution {  public:     string kthLargestNumber(vector<string>& a, int k) {       vector<string> s = a;  // 我将此赋值去掉，也没有提升性能      sort(s.begin(), s.end(), cmp);      return s[k - 1];     } }; 

参考资料

[1]坑神的b站录象: https://www.bilibili.com/video/BV1Z64y1a7P1

[2]【算法实况】又血崩了，这种题目完全没经验乌乌 - 力扣周赛 - LeetCode Weekly 256: https://www.bilibili.com/video/BV1Z64y1a7P1?p=1

[3]墨染空: https://leetcode-cn.com/u/mo-ran-kong/