Pointer to vector of objects losing their value

Question

I have a project I've been developing for my master's thesis. In this project, I have a parent class called node and some other children classes, for example, the class AND. And I also have a class called graph where nodes are stored using std::map. I came to the conclusion I don't need to use std::map. Using std::vector I would have quicker access to the nodes inside the graph.

The AND class has two vectors: one for its inputs and another for its outputs. I have two methods to add a pointer of a node to one of these two vectors.

When I changed from map to vector in the graph class, some of the pointers inside the AND nodes are losing their value.

I did some research on pointers, and it seems to me I am doing nothing wrong. I am lost here.

class node{
protected:
    unsigned int id;
public:
    virtual void pushOutput(node* param){}
    virtual void pushInput(node* param,bool param_polarity){}
}

class AND : public node{
    vector <node*> inputs;
    vector <node*> outputs;
public:
   void pushOutput(node* param) override;
   void pushInput(node* param,bool param_polarity) override;
}

void AND::pushOutput(node* param){
    this->outputs.push_back(param);
}

//AND::pushInput is omitted, but it is pretty similar to AND::pushOutput except with a bunch of ifs.

class graph {
protected:
//    map<unsigned int,AND> all_ANDS;
    vector<AND> all_ANDS;
public:
    AND* pushAnd(unsigned int index,AND AND_obj); 
    AND* findAnd(unsigned int);
}

AND* graph::pushAnd(unsigned int index, AND AND_obj){
//    std::pair<std::map<unsigned int,AND>::iterator,bool> ret;
//    ret=this->all_ANDS.insert(pair<unsigned int,AND>(index,AND_obj));
    all_ANDS.push_back(AND_obj);
    return &all_ANDS.back();
}

AND* graph::findAnd(unsigned int param){
//    return &this->all_ANDS.find(param)->second;
    return &all_ANDS[param];
}

Please notice the commented lines are the version the code used to work properly.

Using the methods to read from a file (some things were omitted):

bool polar;
AND* AND_ptr;
unsigned int rhs0;
for(int l=0;l<A;l++)
{
    and_index++;
    AND AND_obj(and_index*2);
    AND_ptr=this->pushAnd(and_index*2,AND_obj);
//reading info from file here and putting on rhs0 and polar.
    AND_ptr->pushInput(findAnd(rhs0),polar);
    findAnd(rhs0)->pushOutput(findAnd(and_index*2));
    findAny(rhs0)->printNode();
}

If I use the method graph::findAnd() to get a node address to push it inside another node's vector: inputs or outputs the address saved on these vectors point to some junk, but only after some processing time, it points to the proper place at first, as the AND::printNode() shows.

In other words, graph::findAnd() is returning an invalid pointer, although with the std::map version it was working just fine.

I am pretty sure my issue is due to some lack of knowledge on pointers. Although when I check other similar issues like this one Vector of object pointers returns odd values. My code seems ok to me.

get a [good c++ book](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list), seems you need to get some basic understanding of memory managment — skeller, May 21 '19 at 19:21
I understand very little of your code, but what could be a reason is that `std::vector` needs to reallocate when you push more elements, ie pointers to elements get invalid. This is not the case for `std::map` — 463035818_is_not_an_ai, May 21 '19 at 19:23
Interesting point with the push on vector. I thought it wouldn't happen cause it is always at the end of the vector. Would I have another option? — gudé, May 21 '19 at 19:32

score 2 · Accepted Answer · answered May 21 '19 at 20:22

You have to consider iterator invalidation. From cppreference on std::vector::push_back:

If the new size() is greater than capacity() then all iterators and references (including the past-the-end iterator) are invalidated. Otherwise only the past-the-end iterator is invalidated.

Here "references" is used in the wider sense, ie pointers to elements also get invalidated. The reason is that std::vector guarantess to keep its data in a contiguous block of memory, hence previous elements may have to move around when you push new ones.

I understand too little of your code to give any more advice. Just note that std::list does not invalidate iterators when new elements are added (same goes for std::map). However, that comes at a price that is usually not worth to pay (no data locality with std::list is the killer). On the other hand, if the whole purpose of the container is to enable referencing elements without getting invalidated it might be a valid choice.

YES. This was the problem. I thought it was my understanding of pointers that was wrong, but it was actually because I was pushing back on the vector and messing up everything. I solved by first pushing back the number of nodes I needed with blank nodes than modifying them while I read the file. Thanks a lot for the attention! — gudé, May 21 '19 at 20:40

score -1 · Answer 2 · answered May 21 '19 at 19:47

Don't keep pointers to objects that are stored in vectors. The vector structure keeps all its members in contiguous memory blocks and so may need to allocate a new block when the vector gets larger, invalidating all pointers to objects in the vector.

I would also strongly suggest not using a vector of raw pointers. This is bad practice that makes it very difficult to manage the lifetime of the object, which is exactly went wrong here.

You could, for example, use a vector of std::shared_ptrs to objects. Then you can store additional shared_ptrs to those objects in other collections.

Objects are allocated on heap. Those are not pointers inside vectors, they are vector elements themselves, so reallocation cannot harm them in any way (provided this particular STL implementation does it correct.) — bipll, May 22 '19 at 06:29

Pointer to vector of objects losing their value

2 Answers2