同一代码在C++17与C++14下输出不一致问题排查求助

你的代码在C17下正常运行，但C14下输出错误，问题出在持久化线段树update函数中节点的创建方式：先通过emplace_back()默认构造新节点，再赋值为原节点拷贝的操作，在C14的vector实现中可能触发未定义行为，而C17的vector实现优化规避了这个问题。

具体问题点 #

在update函数中，你原本的写法是：

int id = T.size();
T.emplace_back();
T[id] = T[root];

当vector容量不足时，emplace_back()会触发扩容：分配新内存、移动/拷贝原元素到新内存、释放原内存。虽然索引访问理论上有效，但先默认构造再赋值的步骤，在C++14的内存模型下可能导致对已释放内存的间接访问，引发未定义行为，最终导致线段树节点数据错误。

修复方案 #

将上述三行代码替换为直接拷贝构造新节点的写法，避免中间赋值步骤：

int id = T.size();
T.emplace_back(T[root]); // 直接基于原节点拷贝构造新节点

或者使用push_back实现相同效果：

int id = T.size();
T.push_back(T[root]);

修改后的完整代码 #

#include <bits/stdc++.h>

#define nl '\n'

using namespace std;

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

    Node() : value(0), left(0), right(0) {}
    Node(const Node&) = default; // 显式声明拷贝构造，确保行为一致
  };
  vector<Node> T = {Node()};

  int update(int root, int l, int r, int p, int v) {
    int id = T.size();
    T.emplace_back(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;

int 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;    
  }
}

验证说明 #

修改后，代码在C14和C17环境下都会输出正确结果：

5 
6 
3

内容的提问来源于stack exchange，提问作者kilkuwu