10

Hi I need an stl container which can be indexed like a vector but does not move old elements in the memory like a vector would do with resize or reserve (Unless I call reserve once at the beginning with a capacity enough for all elements, which is not good for me). (Note I do address binding to the elements so I expect the address of these elements to never change). So I've found this deque. Do you think it is good for this purpose? Important: I need only pushback but I need to grow the container on demand in small chunks.

ThinkingStiff
  • 64,767
  • 30
  • 146
  • 239
user1132655
  • 243
  • 4
  • 14

2 Answers2

13

std::deque "never invalidates pointers or references to the rest of the elements" when adding or removing elements at its back or front, so yes, when you only push_back the elements stay in place.

Fred Foo
  • 355,277
  • 75
  • 744
  • 836
  • Thanks! Can I use pushback without resize? Since it sais resize may move elements. – user1132655 Nov 05 '12 at 15:55
  • @user1132655: sure, just `push_back`. Why do you think you'd need `resize`? That sounds like premature optimization to me. – Fred Foo Nov 05 '12 at 15:57
  • Sorry, I wanted to ask Should, not Can, just with resize it seems optimization may alter my elements, so shouldnt use it in this case. – user1132655 Nov 05 '12 at 16:04
  • @user1132655: if I read [cppreference.com](http://en.cppreference.com/w/cpp/container/deque/resize) correctly, `resize` *appends* elements, so there should be no problem with it, but honestly I'm too lazy to look it up in the Standard right now. – Fred Foo Nov 05 '12 at 16:08
  • unfortunately I will need resize to inser several elements (with default values) to the end, but for resize it sais: Notice that this function changes the actual content of the container by inserting or erasing elements from it. Not sure though if this is a bad news... – user1132655 Nov 05 '12 at 16:32
  • 1
    @user1132655: the Standard says `resize(sz)` for `sz > size()` is equivalent to repeat `insert(end(), T())`. If cppreference.com is correct, that should still not invalidate pointers or references. – Fred Foo Nov 05 '12 at 16:43
5

A careful reading of the documentation seems to indicate that so long as you insert at the beginning or the end it will not invalidate pointers, and invalidating pointers is a sign that the data is being copied or moved.

The way it's constructed is not quite like a linked list, where each element is allocated individually, but as a set of linked arrays presumably for performance reasons. Altering the order of elements in the middle will necessitate moving data around.

tadman
  • 208,517
  • 23
  • 234
  • 262
  • 2
    More like an array of arrays. A linked array offers much better traversal than a linked list but no random access. – Puppy Nov 05 '12 at 15:45