Alternatives to std::vector due to reallocation that invalidates pointers to elements

Question

this might be a newb question (i am) but i've searched as much as i could to find a solution to the following problem

I have the following scenario (heavily distilled of course):

class Container
{
std::vector<Object> obj;
};

class Pointers
{
std::vector<Object*> obj_ptr;
};

I have a routine that pushes back an element of type Object to the vector obj in Container then pushes back the pointer to that same element to obj_ptr.

the overall idea is that obj_ptr[i] == &obj[i] throughout the life of the program.

The problem I run into is that whenever the capacity of obj needs to increase all the pointers are invalidated, making the obj_ptr completely useless. I have tried both obj.reserve() using the maximum expected size (around 10^7) and initializing the vector with that same size. Problem still persists.

Not sure if it's important, but I'm using VS 2015 Com.

Thanks!

This sounds like a design problem on your side / XY problem. Why would you ever want to have such a second vector in the first place? E.g if you need a way to iterate over the pointers of yonder objects, implement a custom iterator. If want to implement an interface which exposes the objects as pointer, directly access the vector in the implementation of your interface. — Sebastian Hoffmann, Feb 28 '16 at 14:32
Hi Sebastian. It was a distilled version of the following problem The container in this case is a **mesh** that has **points**, **edges**, and **faces** basically, every point, edge and face need to know which **mesh** it belongs to, and which are its adjacent **point**, **edge**, **face** elements, so that some sort of algorithm can be applied to modify the geometry. so to avoid duplicates, only the **mesh** contains **vector>**, **vector**, and **vector**. for each of the other types the adjacency lists are stored in vector of pointers. — Adl A, Feb 28 '16 at 15:54
Simply use indices instead of pointers and your problem vanishes. — Walter, Jan 16 '17 at 09:07

score 8 · Accepted Answer · edited Feb 28 '16 at 18:50

8

The common alternative is using smart pointers like

class Container {
    std::vector<std::unique_ptr<Object>> obj;
};

or

class Container {
    std::vector<std::shared_ptr<Object>> obj;
};

Depends on your use case (semantically).

edited Feb 28 '16 at 18:50

Pete Becker

74,985
8
76
165

answered Feb 28 '16 at 14:25

πάντα ῥεῖ

1
13
116
190

1

Um, no, even a smart pointer isn't smart to know that the original vector was reallocated. – Pete Becker Feb 28 '16 at 14:55
2

@PeteBecker: But `obj[i]->get() == obj_ptr[i]` will still be true after reallocation. I think that was the point of the answer. – Christian Hackl Feb 28 '16 at 15:23
Thanks. **shared_ptr – Adl A Feb 28 '16 at 16:32
Oh, I see: you put a smart pointer into the other container. Sigh. Too complicated for me... – Pete Becker Feb 28 '16 at 18:49
2

Sorry about the stupid edit; I had to do that to unlock the question so I could cancel my downvote. – Pete Becker Feb 28 '16 at 18:52

ysdx · Answer 2 · 2017-01-16T08:21:58.563

4

Boost stable vector is designed for this. It is a vector (access in O(1), etc.) which does not invalidate its values. It is complying to the standard C++ container API/semantic.

It is similar to a std::vector<std::unique_ptr<T>> but hides the smart pointer from you.

edited Jan 16 '17 at 08:21

answered Feb 28 '16 at 14:31

ysdx

8,889
1
38
51

Thanks for the suggestion. The major drawback is that it is not standard. – Adl A Feb 28 '16 at 16:43
@AdlA, well its not in the standard library, yes. If you don't want to depend on thirs party libs, you can roll you own implementation by wrapping std::vector>. – ysdx Feb 28 '16 at 21:08
wrapping `std::vector>` is an interesting option, simply for the option of making it slightly less verbose. Also, i only need to add and read elements (no popping, deleting) so it might be "safer". cheers! – Adl A Feb 29 '16 at 08:08

Christian Hackl · Answer 3 · 2016-02-28T14:30:07.133

2

You can use std::list or std::forward_list in Container, so that the pointers are not invalidated.

class Container
{
std::forward_list<Object> obj;
};

class Pointers
{
std::vector<Object*> obj_ptr;
};

Pay attention to the process of deleting elements from obj, though. Deleting an element from obj does invalidate the corresponding pointer in obj_ptr.

edited Feb 28 '16 at 14:30

answered Feb 28 '16 at 14:28

Christian Hackl

27,051
3
32
62

2

of course, a lot of care must still be taken this way – M.M Feb 28 '16 at 14:28
@M.M: Well... yes :) – Christian Hackl Feb 28 '16 at 14:29

score 2 · Answer 4 · answered Feb 28 '16 at 19:32

You have a number of choices

Use a data structure like std::list or std::deque where adding elements does not invalidate pointers to previsouly added elements.
keep indexes instead of pointers in your second array
have only vectors of pointers -- perhaps a std::vector<std::unique_ptr<Object>> for the first array and std::vector<Object *> for the others, or perhaps std::vector<std::shared_ptr<Object>> for all the arrays.

Which makes the most sense depends on what it is you are actually trying to do.

Thanks, all those suggestions seem to be valid. In my case, I think the best is the `std::vector>`. Cheers! — Adl A, Feb 29 '16 at 08:04

Alternatives to std::vector due to reallocation that invalidates pointers to elements

4 Answers4

Linked