Vector of pointers undefined behaviour-CodePudding

I'm trying to make a vector of pointers whose elements are pointing to vector of int elements. (I'm solving a competitive programming-like problem, that's why it sounds kinda nonsense).

but here's the code:

#include <bits/stdc  .h>

using namespace std;

int ct = 0;

vector<int> vec;

vector<int*> rf;

void addRef(int n){
    vec.push_back(n);
    rf.push_back(&vec[ct]);
    ct  ;
}


int main(){
    addRef(1);
    addRef(2);
    addRef(5);
    for(int i = 0; i < ct; i  ){
        cout << *rf[i] << ' ';
    }
    cout << endl;
    for(int i = 0; i < ct; i  ){
        cout << vec[i] << ' ';  
    }
}

When I execute the code, it's showing weird behaviour that I don't understand. The first element of rf (vector<int*>) seems not pointing to the vec's (vector<int>) element, where the rest of the elements are pointing to it.

here's the output when I run it on Dev-C :

1579600 2 5
1 2 5

When I tried to run the code here, the output is even weirder:

1197743856 0 5 
1 2 5

The code is intended to have same output between the first line and the second.

Can you guys explain why it happens? Is there any mistake in my implementation?

thanks

CodePudding user response：

Adding elements to a std::vector with push_back or similar may invalidate all iterators and references to its elements. See https://en.cppreference.com/w/cpp/container/vector/push_back.

The idea is that in order to grow the vector, it may not have enough free memory to expand into, and thus may have to move the whole array to some other location in memory, freeing the old block. That means in particular that your pointers now point to memory that has been freed, or reused for something else.

If you want to keep this approach, you will need to resize() or reserve() a sufficient number of elements in vec before starting. Which of course defeats the whole purpose of a std::vector, and you might as well use an array instead.

CodePudding user response：

The vector is changing sizes and the addresses you are saving might not be those you want. You can preallocate memory using reserve() and the vector will not resize.

  vec.reserve(3);
  addRef(1);
  addRef(2);
  addRef(5);

CodePudding user response：

The problem occurs when you call vec.push_back(n) and vec’s internal array is already full. When that happens, the std::vector::push_back() method allocates a larger array, copies the contents of the full array over to the new array, then frees the old/full array and keeps the new one.

Usually that’s all you need, but your program is keeping pointers to elements of the old array inside (rf), and these pointers all become dangling/invalid when the reallocation occurs, hence the funny (undefined) behavior.

An easy fix would be to call vec.reserve(100) (or similar) at the top of your program (so that no further reallocations are necessary). Or alternatively you could postpone the adding of pointers to (rf) until after you’ve finished adding all the values to (vec).

CodePudding user response：

Just do not take pointer from a vector that may change soon. vector will copy the elements to a new space when it enlarges its capacity.

Use an array to store the ints instead.