0

I'm looking for a container that preserves it's contained objects' positions in memory (it's pointers remain valid)

The container will grow and shrink constantly. Elements in the middle may be erased, but there's no insertions in the middle; all elements are pushed onto the back of the container. Iterator validity isn't important in this case, my only concern is that the pointers remain valid.

Is std::deque a safe and efficient option in this situation? I was previously using list, but it is allocating far too many times to be useful in this instance.

Anne Quinn
  • 12,609
  • 8
  • 54
  • 101
  • 2
    does http://stackoverflow.com/questions/6438086/iterator-invalidation-rules answer your question? (it doesn't just cover the iterators, it also lists reference/pointer invalidation rules) – Cubbi Nov 11 '14 at 05:28
  • @Cubbi - It does it does! That's handy to have in one place finally, thank you! – Anne Quinn Nov 11 '14 at 05:33
  • 2
    Unfortunately I don't think there's a container other than `std::list` that guarantees valid pointers when you remove from the middle. Edit: I take that back, I think `std::set` and `std::map` do also but you need to accept an ordered container and all that implies. – Mark Ransom Nov 11 '14 at 05:50

3 Answers3

5

Inserting or removing elements in the middle invalidates all iterators and references.

Inserting elements at the beginning/end invalidates iterators, but does not affect references.

Removing elements at the beginning/end does not affect iterators or references, except ones pointing to the removed element, and possibly the past-the-end iterator.

http://en.cppreference.com/w/cpp/container/deque/erase

All iterators and references are invalidated, unless the erased elements are at the end or the beginning of the container, in which case only the iterators and references to the erased elements are invalidated.

http://en.cppreference.com/w/cpp/container/deque/push_back

All iterators, including the past-the-end iterator, are invalidated. No references are invalidated.

(other methods that operate on front or back elements have similar notes).

riv
  • 6,846
  • 2
  • 34
  • 63
4

No. std::deque is necessarily implemented using chunks. Erasing in the middle of a chunk would at the very least invalidate the addresses of all subsequent elements in that chunk.

Note that iterator invalidation and pointer invalidation are generally closely connected. An iterator often is a pointer to the (node holding the) element, with proper iteration semantics added. Such iterators get invalidated because the pointer they contain is invalidated.

MSalters
  • 173,980
  • 10
  • 155
  • 350
  • Have you tried? At least on gcc 5.4. I created dequeue, check a specific element in the container, erased and then inserted some random number of elements in front the specific element does NOT invalid the specific element's pointer. – r0n9 Jan 11 '18 at 04:00
  • But you are right, we should not depend on the vender's effort and just follow the documents. – r0n9 Jan 11 '18 at 04:22
-1

NO ! As opposed to std::vector, the elements of a deque are not stored contiguously: typical implementations use a sequence of individually allocated fixed-size arrays. The storage of a deque is automatically expanded and contracted as needed. Expansion of a deque is cheaper than the expansion of a std::vector because it does not involve copying of the existing elements to a new memory location

tinyfiledialogs
  • 1,111
  • 9
  • 18