How to handle correctly/efficiently pointers to std::vector elements?

Question

Let say we have:

std::vector<Segment*> segments;
...
Segment* dd = new Segment;
segments.emplace_back(dd);
Owner*   owner = getOwner();
owner->setSegmentPointer(&(segments.back());

This will not work because of Iterator invalidation rules.

Any subsequent element addition to the vector segments will render invalid the pointers stored in owner. How to circumvent this problem keeping the access time of std::vector<>? (Assuming that we can't use vector.resize in advance). Is to use std::map<> the only solution?

Thanks in advance

What genius came up with that Iterator Invalidation Rules page? — Lightness Races in Orbit, Mar 20 '18 at 12:43
@LightnessRacesinOrbit It doesn't make sense. Otherwise the `Owner` should own the pointer, not the vector address. — llllllllll, Mar 20 '18 at 12:44
@liliscent Mmm yeah I suppose. Weird that they're owning a `Segment**`. I am guessing that was a mistake. — Lightness Races in Orbit, Mar 20 '18 at 12:45
Sorry: the example is a bit convoluted. The idea is that all the Segments are handled by a "common" object. It passes a double pointer to the owner component. — vpuente, Mar 20 '18 at 12:56
@vpuente Why the double pointer? The double pointer can get invalidated, if re-allocation occurs in the vector. If you pass the pointer to the segment directly, you avoid the mess... — Aconcagua, Mar 20 '18 at 12:59
@Aconcagua Yep is a bit of non-sense. Each owner can use that pointer to access other elements in the vector. I know, combine pointer arithmetic and C++ is "very" bad idea :-) — vpuente, Mar 20 '18 at 13:02
@vpuente Would certainly be a better idea to make the vector available to the owners directly by some means. If you want to access the other elements via the pointer, how do you make sure that you do not exceed the vector's inner array's bounds??? — Aconcagua, Mar 20 '18 at 13:05
@vpuente This design questionable. If you provide more information about what you actually want to achieve, we might come up with a better design... — Aconcagua, Mar 20 '18 at 13:41

Aconcagua · Accepted Answer · 2018-03-20T15:02:47.697

2

Each owner can use that pointer to access other elements in the vector.

Apart from being a horrible idea, you could realise it with a std::list, though:

First, every owner instance gets an iterator to the list, not a pointer to a segment. std::list has the advantage of not invalidating iterators on insertion/deletion, unless you delete the element an iterator points to.

Via this iterator, you can find the other elements in the list. One problem remains, though: you need to detect safely the begin and end of the list. So you need sentinel values at begin and end, which could be e. g. null pointers, if these do not occur in the list.

One important note: If you need to remove a segment from the list, although an owner still has an iterator to it, you need to find a way to inform the owner about iterator invalidation. There are no means available to get this done automatically!

edited Mar 20 '18 at 15:02

answered Mar 20 '18 at 13:29

Aconcagua

24,880
4
34
59

My comment was posterior. For the particular problem I have I think is enough. Yep, I'm aware that there is a lot of ugliness in my design, but the desired flexibility requires this. – vpuente Mar 20 '18 at 14:47
@vpuente Dropped the corresponding paragraph - you cannot do pointer arithmetics on std::deque safely due to non-contiguous memory, but you can use iterators, as long as not invalidating them as described by Nathan. You still need sentinels to discover begin and end of data! And you need a safe way to notify the owners about their segment being deleted, if this can occur, otherwise trouble ahead again... – Aconcagua Mar 20 '18 at 15:08
1

@vpuente Still, I am pretty sure there are better options still offering the same flexibility. Might be an option or not, but have you thought about adding the owners to the vector instead of the segments? If the segment manager is a single resource, it might be a singleton every owner accesses. The owners might have an ordinary pointer and in addition a link to the responsible segment manager - or the segments themselves have such a link. The segment manager stores the segments in the vector *by value*, the owners maintain a link to the SM and instead of the pointer an index. TBC... – Aconcagua Mar 20 '18 at 15:20
That might be a good approach. I'll think about it. Thanks again for your help. – vpuente Mar 20 '18 at 17:37

score 1 · Answer 2 · answered Mar 20 '18 at 12:44

If you need random access but you need the container to grow without invalidating pointers/references/iterators to the elements then you can use a std::deque. This will let you grow/shrink from the front or back. If you insert/erase from the middle though that can still invalidate iterators.

How to handle correctly/efficiently pointers to std::vector elements?

2 Answers2