C++ - Deleting a vector element that is referenced by a pointer

Question

Hi all! Well, I don't know if it is possible, but the thing would be:

struct stPiece
{
  /* some stuff */
  stPiece *mother; // pointer to the piece that created this one
};

vector<stPiece> pieces;

Is it possible to erase the piece referenced by 'mother' from pieces, having just that pointer as a reference? How?

Would it mess with the other references? (i.e. if it is not the last element in the vector, by shifting the next elements to other memory positions, while the other '*mothers' remain constant). Of course, I assuming that all the child pieces will be deleted (so I won't need to update any pointer that goes to the same mother).

Thanks!

Answer 1

Yes, you can erase the piece referenced by mother.

If you delete the piece referenced by 'mother', the mother pointer in all its children will become dangling, you'll have to take care of this.

About the shifting of elements in the vector, you need not do it, its taken care by the vector class.

Answer 2

If your mother pointers point directly to elements of the pieces vector you will get in all kinds of trouble.

Deleting an element from pieces will shift all the positions of the elements at higher indexes. Even inserting elements can make all the pointers invalid, since the vector might need to reallocate it's internal array which might transfer all the elements to new positions in memory.

To answer your main question: You can't delete the element you have the pointer to directly, you would first need search through the vector to find it, or calculate it's index in the vector.

Not storing pointers into pieces as mother but instead the indexes of the elements would make it a bit more robust, so that at least inserting new elements could not break the existing mothers. But deleting from pieces would still shift elements to new indexes.

Using a std::list for pieces and storing iterators into that as mother might be a solution. Iterators of std::list are not invalidated if other elements are of that list are removed/added. If different elements can have the same mother you still have a problem finding out when to remove the mother elements, than maybe using boost::shared_ptr would be simpler.

Answer 3

Short answer: no.

The pieces are stored in the vector by value. A vector iterator is therefore a pointer to a piece. This means, then, that a pointer to the mother piece is the same as the vector's iterator at the mother. Vector iterators are invalidated on insertion (all iterators) and erasure (all iterators past the erased iterator), which means memory locations will change and it will be nearly impossible to keep all the pointers updated.

You could store dynamically allocated pieces in the vector, i.e.:

vector<stPiece*> pieces

The mother pointers won't change as pieces are added/removed to/from the vector. The downsides are:

• you now have to manage memory (new/delete each piece)
• it uses more memory per piece (the pointers in pieces)
• it may be slower because you lose spatial locality (cache efficiency) because it is no longer a contiguous array of stPiece objects

The latter two points may or may not be important in your application.

Answer 4

What you have coded is a singly-linked tree. You probably don't want an object to contain all your stPieces, because that would get in the way of implementing creation and deletion semantics.

I'm guessing that you want to delete mother after all the children are gone.

set< stPiece * > all_pieces;

struct stPiece {
    boost::shared_ptr< stPiece > const mother;
    stPiece( boost::shared_ptr< stPiece > &in_mother )
     : mother( in_mother ) {
        all_pieces.insert( this );
    }
    ~stPiece() {
        all_pieces.erase( this );
    }
};

The key point is that there's a difference between containing some objects and merely being able to iterate over them. If using the most obvious way to create and delete the objects isn't using the container, they probably shouldn't be in it.

Answer 5

It is not exactly clear how the entire data structure is organized and what the consequences are going to be, but it is perfectly possible to erase an element from the vector by having a pointer to that element and the vector itself. You just need to convert the pointer to an iterator first. For example, having a vector

vector<stPiece> pieces; 

and a pointer into that vector

stPiece *mother;

you can convert the pointer to an index

vector<stPiece>::size_type i = mother - &pieces[0];
assert(i < pieces.size());

then convert the index to an iterator

vector<stPiece>::iterator it = pieces.begin() + i;

then erase the element

pieces.erase(it);

and that's it.

However, it appears that in your data structure you might have multiple long-lived pointers pointing into the same vector. Any attempts to erase elements from such vector will immediately invalidate all these pointers. It theoretically is possible to "restore" their validity, if you do everything carefully, but this is going to a major PITA.

I'm not sure I understand what you mean by "assuming that all the child pieces will be deleted".