CODEWITHSUNDEEP
c++dictionaryvectorstlcontainers
Adrian
Adrian

Reputation: 121

Using map<int, Foo> instead of vector<Foo> to avoid pointer invalidation

Say I have a class Foo, and a container vector<Foo> Foos. The algorithms I use rely heavily on pointers to the elements of Foos, and I also need to add Foos dynamically and to access elements of the container. The problem is that if I add too many elements to the vector, it may need to reallocate the elements, hence invalidating all the pointers to these elements. Would it make sense then to use something like map<int, Foo> instead of vector<Foo>?

Upvotes: 1

Views: 94

Answers (4)

cmaster - reinstate monica
cmaster - reinstate monica

Reputation: 40665

You have four possibilities:

  • You use a non-invalidating container. That's your suggestion.

  • You reserve sufficient space in the vector beforehand (El Professor's answer). This only works when you know the maximum amount of Foos in advance.

  • You use a vector of (smart) pointers (Michael Chourdakis' answer). This works as long as you do not need to use the pointers as iterators.

  • You make no change to your vector<Foo>, but instead of pointers, you make your algorithm work with indices. This allows you to look at the element before and after (after checking the vector bounds), and the indices won't be invalidated by reallocations.

Upvotes: 2

jfMR
jfMR

Reputation: 24788

This answer focuses on how to prevent pointer invalidation from happening, while still sticking to std::vector.

Preallocating

If you know beforehand the maximum number of Foo objects that the vector can contain, you can simply reallocate the vector's buffer with the std::vector::reserve() member function. This way, a reallocation of the objects won't happen and therefore the pointers to the Foo objects won't be invalidated.

Using a vector of pointers

Alternatively, you can use std::vector<std::unique_ptr<Foo>> instead of std::vector<Foo>. This way, even if the vector reallocates its elements, the address of the pointed Foo objects won't change since it will be the std:unique_ptr<Foo> objects the ones that will be reallocated, not the Foo objects. Therefore, the pointers to the Foo objects will still be valid.

The latter approach introduces an additional layer of indirection, and it is, therefore, less efficient than the former one.

Upvotes: 2

Marshall Clow
Marshall Clow

Reputation: 16690

std::deque has similar performance (and random-access) to vector, but does not invalidate pointers upon insertion.

It does invalidate pointers on deletion, though.

Upvotes: 3

Michael Chourdakis
Michael Chourdakis

Reputation: 11178

I would use std::vector<std::shared_ptr<Foo>>, so I still have a vector and I still have valid pointers wherever I need them no matter how they are positioned inside the vector.

Upvotes: 2

Related Questions