提问人:HuyAT 提问时间:10/30/2023 最后编辑:AmitHuyAT 更新时间:10/31/2023 访问量:135
将函数返回值分配给 std::vector 元素: C++14 中的行为与 C++17 中的行为不同
Assign a function return-value to std::vector element: Different behavior in C++14 than in C++17
问:
断言失败且具有未定义的行为
#include<bits/stdc++.h>
const int MaxN = 1e5 + 10;
struct Node{
long long sum;
int left,right;
Node() :sum(0),left(0),right(0){
}
Node(long long sum,int left,int right) :sum(sum),left(left),right(right){
}
};
struct PersistentSegmentTree{
std::vector<Node> st;
std::vector<int> ver;
int n;
PersistentSegmentTree(int n) :n(n){
ver.push_back(0);
st.push_back(Node());
}
int update(int l,int r,int pos,int val,int oldId){
std::cerr << l << " " << r << "\n";
st.push_back(Node());
if(l == r){
st.back() = Node(val,0,0);
assert((int)st.size() - 1 != 0);
return (int)st.size() - 1;
}
int cur = (int)st.size() - 1;
std::cerr << cur << "\n";
int mid = (l + r) >> 1;
if(pos <= mid){
st[cur].left = update(l,mid,pos,val,st[oldId].left); // <---- C++14 / C++17 : DIFFERENT BEHAVIOR ?
// this code below does the same but somehow they works
// int t = update(l,mid,pos,val,st[oldId].left);
// st[cur].left = t;
assert(st[cur].left != 0); // <---- ON C++14 ASSERTION FAILS HERE
st[cur].right = st[oldId].right;
}else{
st[cur].left = st[oldId].left;
st[cur].right = update(mid + 1,r,pos,val,st[oldId].right);
}
st[cur].sum = st[st[cur].left].sum + st[st[cur].right].sum;
assert(cur != 0);
return cur;
}
long long getSum(int l,int r,int u,int v,int id){
if(l > v || r < u){
return 0;
}
if(u <= l && r <= v){
return st[id].sum;
}
int mid = (l + r) >> 1;
return getSum(l,mid,u,v,st[id].left) + getSum(mid + 1,r,u,v,st[id].right);
}
void updateArray(int arrayIndex,int pos,int val){
ver[arrayIndex] = update(1,n,pos,val,ver[arrayIndex]);
std::cerr << arrayIndex << " " << ver[arrayIndex] << " " << st[ver[arrayIndex]].left << "\n";
}
void copyArray(int arrayIndex){
ver.push_back(ver[arrayIndex]);
}
long long sumQuery(int arrayIndex,int l,int r){
return getSum(1,n,l,r,ver[arrayIndex]);
}
};
int a[MaxN + 1],n;
void readData(){
std::cin >> n;
for(int i = 1;i <= n;++i){
std::cin >> a[i];
}
}
void query(){
PersistentSegmentTree tree(n);
tree.copyArray(0);
for(int i = 1;i <= n;++i){
tree.updateArray(1,i,a[i]);
}
std::cout << tree.sumQuery(1,1,1);
}
int main(){
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);std::cout.tie(nullptr);
PersistentSegmentTree tree(3);
tree.copyArray(0);
tree.updateArray(1,1,2);
std::cout << tree.sumQuery(1,1,1);
return 0;
}
我知道这些代码行看起来像一堆乱七八糟的东西,但并不介意所有其他功能。
该代码不需要输入。
--
C++14:运行时,断言失败
a.out: main.cpp:39: int PersistentSegmentTree::update(int, int, int, int, int): 断言 'st[cur].left != 0' 失败
演示:https://www.onlinegdb.com/FZhhhDjwgc
--
C++17 和 C++20:运行时,正常
演示:https://www.onlinegdb.com/2pxv_lRq7
--
有谁知道为什么?
答:
5赞
Jarod42
10/30/2023
#1
在 C++17 之前,分配的评估顺序(链接为 19)是无序的:
st[cur].left = update(l,mid,pos,val,st[oldId].left);
所以我们可以之前评估。由于以某种方式(容量变化)进行修改,所有迭代器/引用(实际上)都可能变得无效,从而导致 UB。st[cur].left
update
st
st[cur]
在 C++17 中,保证在 之前进行评估,所以一切都很好。update
st[cur].left
评论
st.back()
cur