相同的代码在使用不同版本的C++时会产生不同的输出。

huangapple
go评论142阅读模式
英文:

The same code gives different output when using different versions of C++

问题

这是关于C++版本之间不同行为的问题，当使用C++17时，代码输出正确，但当切换到C++14时，输出完全不同。编译器是g++ (x86_64-posix-seh-rev1, Built by MinGW-Builds project) 13.1.0。如果有人能指出发生了什么事情，我将不胜感激。

以下是我对该问题的解决方案：

  1. #include <bits/stdc++.h>
  3. #define nl '\n'
  5. using namespace std;
  7. using i64 = long long;
  9. struct PersistentSegmentTree {
  10.   struct Node {
  11.     int value, left, right;
  13.     Node() : value(0), left(0), right(0) {}
  14.   };
  15.   vector<Node> T = {Node()};
  17.   int update(int root, int l, int r, int p, int v) {
  18.     int id = T.size();
  19.     T.emplace_back();
  20.     T[id] = T[root];
  21.     if (l == r) {
  22.       T[id].value += v;
  23.       return id;
  24.     }
  25.     
  26.     int mid = (l + r) / 2;
  27.     if (p <= mid) {
  28.       T[id].left = update(T[root].left, l, mid, p, v);
  29.     } else {
  30.       T[id].right = update(T[root].right, mid + 1, r, p, v);
  31.     }
  32.     
  33.     T[id].value = T[T[id].left].value + T[T[id].right].value;
  34.     return id;
  35.   }
  37.   int query(int from, int to, int l, int r, int k) {
  38.     if (l == r) {
  39.       return l;
  40.     }
  41.     int mid = (l + r) / 2;
  42.     int left_count = T[T[to].left].value - T[T[from].left].value;
  43.     if (left_count >= k) {
  44.       return query(T[from].left, T[to].left, l, mid, k);
  45.     } else {
  46.       return query(T[from].right, T[to].right, mid + 1, r, k - left_count);
  47.     }
  48.   }
  49. } tree;
  51. signed main() {
  52.   cin.tie(0), ios::sync_with_stdio(0);
  54.   int n, q;
  55.   cin >> n >> q;
  56.   vector<int> a(n);
  57.   for (int i = 0; i < n; i++) {
  58.     cin >> a[i]; 
  59.   }
  61.   vector<int> roots;
  62.   roots.push_back(0);
  63.   
  64.   auto vals = a;
  65.   sort(vals.begin(), vals.end());
  66.   vals.erase(unique(vals.begin(), vals.end()), vals.end());
  68.   for (int i = 0; i < n; i++) {
  69.     a[i] = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin();
  70.     roots.push_back(tree.update(roots.back(), 0, vals.size() - 1, a[i], 1));
  71.   }
  73.   for (int qi = 0; qi < q; qi++) {
  74.     int l, r, k;
  75.     cin >> l >> r >> k;
  76.     cout << vals[tree.query(roots[l - 1], roots[r], 0, vals.size() - 1, k)] << nl;    
  77.   }
  78. }

测试用例如下：

  1. 7 3
  2. 1 5 2 6 3 7 4
  3. 2 5 3
  4. 4 4 1
  5. 1 7 3

C++17 输出（正确）：

  1. 5 
  2. 6 
  3. 3

C++14 输出（不正确）：

  1. 7
  2. 7
  3. 4

提前感谢您的帮助。

英文:

I was solving this problem and then I encounter this weird behaviour between different versions of C++. When I use C++17, the code gives correct output, but when I switch to C++14, the output changes completely. I was compiling with g++ (x86_64-posix-seh-rev1, Built by MinGW-Builds project) 13.1.0. I would appreciate it if someone would point out what is happening.

This is my solution to that problem.

  1. #include &lt;bits/stdc++.h&gt;
  3. #define nl &#39;\n&#39;
  5. using namespace std;
  7. using i64 = long long;
  9. struct PersistentSegmentTree {
  10.   struct Node {
  11.     int value, left, right;
  13.     Node() : value(0), left(0), right(0) {}
  14.   };
  15.   vector&lt;Node&gt; T = {Node()};
  17.   int update(int root, int l, int r, int p, int v) {
  18.     int id = T.size();
  19.     T.emplace_back();
  20.     T[id] = T[root];
  21.     if (l == r) {
  22.       T[id].value += v;
  23.       return id;
  24.     }
  25.     
  26.     int mid = (l + r) / 2;
  27.     if (p &lt;= mid) {
  28.       T[id].left = update(T[root].left, l, mid, p, v);
  29.     } else {
  30.       T[id].right = update(T[root].right, mid + 1, r, p, v);
  31.     }
  32.     
  33.     T[id].value = T[T[id].left].value + T[T[id].right].value;
  34.     return id;
  35.   }
  37.   int query(int from, int to, int l, int r, int k) {
  38.     if (l == r) {
  39.       return l;
  40.     }
  41.     int mid = (l + r) / 2;
  42.     int left_count = T[T[to].left].value - T[T[from].left].value;
  43.     if (left_count &gt;= k) {
  44.       return query(T[from].left, T[to].left, l, mid, k);
  45.     } else {
  46.       return query(T[from].right, T[to].right, mid + 1, r, k - left_count);
  47.     }
  48.   }
  49. } tree;
  51. signed main() {
  52.   cin.tie(0), ios::sync_with_stdio(0);
  54.   int n, q;
  55.   cin &gt;&gt; n &gt;&gt; q;
  56.   vector&lt;int&gt; a(n);
  57.   for (int i = 0; i &lt; n; i++) {
  58.     cin &gt;&gt; a[i]; 
  59.   }
  61.   vector&lt;int&gt; roots;
  62.   roots.push_back(0);
  63.   
  64.   auto vals = a;
  65.   sort(vals.begin(), vals.end());
  66.   vals.erase(unique(vals.begin(), vals.end()), vals.end());
  68.   for (int i = 0; i &lt; n; i++) {
  69.     a[i] = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin();
  70.     roots.push_back(tree.update(roots.back(), 0, vals.size() - 1, a[i], 1));
  71.   }
  73.   for (int qi = 0; qi &lt; q; qi++) {
  74.     int l, r, k;
  75.     cin &gt;&gt; l &gt;&gt; r &gt;&gt; k;
  76.     cout &lt;&lt; vals[tree.query(roots[l - 1], roots[r], 0, vals.size() - 1, k)] &lt;&lt; nl;    
  77.   }
  78. }

The test case is:

  1. 7 3
  2. 1 5 2 6 3 7 4
  3. 2 5 3
  4. 4 4 1
  5. 1 7 3

C++17 output (correct):

  1. 5 
  2. 6 
  3. 3

C++14 output (incorrect):

  1. 7
  2. 7
  3. 4

Thanks in advance.

答案1

得分: 3

在所有的作业中都存在问题，比如 T.at(id).left = update(...。

在C++17之前，赋值语句的左边和右边的求值顺序是未指定的。T.at(id).left 似乎首先被求值，其结果类型是 Node&amp;。然后调用了 update()，它向向量 T.emplace_back() 添加了一个新元素 - 这会使所有引用失效，因此首先求值的引用 T.at(id).left 现在是对堆中释放的内存的悬挂引用。在 update() 完成后，将结果值分配给悬挂指针会导致堆上使用已释放内存。

修复方法非常简单：

  1.   const auto left = update(T.at(root).left, l, mid, p, v);
  2. T.at(id).left = left;

希望你能自己修复其他的赋值。

英文:

You have issues in all assignments like T.at(id).left = update(....

The evaluation of the left and right sides of the assignment is unspecified until C++17. T.at(id).left seems to be evaluated first, its result type is Node&amp;. Then update() is called, that adds a new element to the vector T.emplace_back() - this invalidates all references, thus the first evaluated reference T.at(id).left is now a dangling reference to a freed memory in the heap. After uppdate() has finished, the assignent of the result value to the dangling pointer results in the heap-use-after-free.

The fix is quite trivial:

  1.   const auto left = update(T.at(root).left, l, mid, p, v);
  2. T.at(id).left = left;

I hope you will fix the other assignment yourself.

huangapple
  • 本文由 发表于 2023年8月9日 10:40:39
  • 转载请务必保留本文链接：https://go.coder-hub.com/76864237-2.html
  • c++
  • c++14
  • c++17
  • g++
  • gcc
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定