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

Question

Assertion failed and has undefined behavior

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

• I know that these lines of code look like a bunch of messy stuff but don't mind all the other functions.

• The code does not require input.

--

C++14 : On run, assertion fails

a.out: main.cpp:39: int PersistentSegmentTree::update(int, int, int, int, int): Assertion `st[cur].left != 0' failed

Demo: https://www.onlinegdb.com/FZhhhDjwgc

--

C++17 and C++20 : On run, ok

Demo: https://www.onlinegdb.com/2pxv_lRq7

--

Does anyone know why ?

Answer 1

Before C++17, evaluation order of assignation (19 for the link) is unordered:

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

so we might evaluate st[cur].left before. As update modifies st in a way (capacity changes) that all iterators/references (st[cur] actually) might become invalid, leading to UB.

In C++17, it is guaranteed that update is evaluated before st[cur].left, so all is fine.