将函数返回值分配给 std::vector 元素: C++14 中的行为与 C++17 中的行为不同

Assign a function return-value to std::vector element: Different behavior in C++14 than in C++17

提问人:HuyAT 提问时间:10/30/2023 最后编辑:AmitHuyAT 更新时间:10/31/2023 访问量:135

问:

断言失败且具有未定义的行为

#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

--

有谁知道为什么?

C++ 向量 17 C++14 标准

评论

8赞 Wyck 10/30/2023
请参阅为什么不应 #include < bits/stdc++.h>?
0赞 463035818_is_not_an_ai 10/30/2023
失败的断言不是(必然)未定义的行为。
0赞 463035818_is_not_an_ai 10/30/2023
如果它存在,则对向量中最后一个元素的引用是 。使用索引看起来很复杂st.back()cur

答:

5赞 Jarod42 10/30/2023 #1

在 C++17 之前,分配的评估顺序(链接为 19)是无序的:

st[cur].left = update(l,mid,pos,val,st[oldId].left);

所以我们可以之前评估。由于以某种方式(容量变化)进行修改,所有迭代器/引用(实际上)都可能变得无效,从而导致 UB。st[cur].leftupdatestst[cur]

在 C++17 中,保证在 之前进行评估,所以一切都很好。updatest[cur].left

评论

0赞 Marek R 10/30/2023
使用也可以解决此问题:godbolt.org/z/aax83ehafstd::vector::reserve