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

Question

我正在解决这个问题，然后我在不同版本的 C++ 之间遇到了这种奇怪的行为。当我使用 C++17 时，代码给出正确的输出，但当我切换到 C++14 时，输出完全改变。我正在用

g++ (x86_64-posix-seh-rev1, Built by MinGW-Builds project) 13.1.0

进行编译。如果有人能指出发生了什么，我将不胜感激。

这是我解决这个问题的方法。

#include <bits/stdc++.h>

#define nl '\n'

using namespace std;

using i64 = long long;

struct PersistentSegmentTree {
  struct Node {
    int value, left, right;

    Node() : value(0), left(0), right(0) {}
  };
  vector<Node> T = {Node()};

  int update(int root, int l, int r, int p, int v) {
    int id = T.size();
    T.emplace_back();
    T[id] = T[root];
    if (l == r) {
      T[id].value += v;
      return id;
    }
    
    int mid = (l + r) / 2;
    if (p <= mid) {
      T[id].left = update(T[root].left, l, mid, p, v);
    } else {
      T[id].right = update(T[root].right, mid + 1, r, p, v);
    }
    
    T[id].value = T[T[id].left].value + T[T[id].right].value;
    return id;
  }

  int query(int from, int to, int l, int r, int k) {
    if (l == r) {
      return l;
    }
    int mid = (l + r) / 2;
    int left_count = T[T[to].left].value - T[T[from].left].value;
    if (left_count >= k) {
      return query(T[from].left, T[to].left, l, mid, k);
    } else {
      return query(T[from].right, T[to].right, mid + 1, r, k - left_count);
    }
  }
} tree;

signed main() {
  cin.tie(0), ios::sync_with_stdio(0);

  int n, q;
  cin >> n >> q;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i]; 
  }

  vector<int> roots;
  roots.push_back(0);
  
  auto vals = a;
  sort(vals.begin(), vals.end());
  vals.erase(unique(vals.begin(), vals.end()), vals.end());

  for (int i = 0; i < n; i++) {
    a[i] = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin();
    roots.push_back(tree.update(roots.back(), 0, vals.size() - 1, a[i], 1));
  }

  for (int qi = 0; qi < q; qi++) {
    int l, r, k;
    cin >> l >> r >> k;
    cout << vals[tree.query(roots[l - 1], roots[r], 0, vals.size() - 1, k)] << nl;    
  }
}

测试用例是：

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

C++17 输出（正确）：

5 
6 
3

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

7
7
4

提前致谢。

Answer 1

您在所有作业中都遇到问题，例如

T.at(id).left = update(...

。

在 C++17 之前，赋值左侧和右侧的计算是未指定的。

T.at(id).left

似乎首先被评估，其结果类型是

Node&

。然后调用

update()

，向向量

T.emplace_back()

添加一个新元素 - 这会使所有引用无效，因此第一个评估的引用

T.at(id).left

现在是对堆中已释放内存的悬空引用。

uppdate()

完成后，将结果值分配给悬空指针会导致heap-use-after-free。

修复非常简单：

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

我希望你能自己解决其他作业。