英文:
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
。如果有人能指出发生了什么,我将不胜感激。
这是我对该问题的解决方案。
#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
提前感谢。
英文:
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.
#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;
}
}
The test case is:
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3
C++17 output (correct):
5
6
3
C++14 output (incorrect):
7
7
4
Thanks in advance.
答案1
得分: 3
你在所有的作业中都有问题,比如T.at(id).left = update(...
。
在C++17之前,对赋值语句的左右两边的求值顺序是未指定的。T.at(id).left
似乎首先被求值,其结果类型是Node&
。然后调用update()
函数,该函数向向量T.emplace_back()
添加一个新元素,这会使所有引用失效,因此首先求值的引用T.at(id).left
现在是一个指向堆中已释放内存的悬空引用。在update()
完成后,将结果值赋给悬空指针会导致堆使用已释放内存的问题。
修复方法非常简单:
const auto left = update(T.at(root).left, l, mid, p, v);
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&
. 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:
const auto left = update(T.at(root).left, l, mid, p, v);
T.at(id).left = left;
I hope you will fix the other assignment yourself.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论