5

As far as I know std::deque stores its elements in pieces of chunks (although its implementation-dependent, but this is what I read in most of the sources) as opposed to std::vector which in most of the cases uses a single block of memory.

So, it's pretty reasonable for std::vector to encounter reallocation as part of insertion. However, I can't relate any situation where there would be need for re-allocation for std::deque since it just starts over with new chunk of memory when the current is blown up.

Can anyone provide me a case where std::deque needs reallocation as a consequence of some operations performed on it?

edmz
  • 8,220
  • 2
  • 26
  • 45
ravi
  • 10,994
  • 1
  • 18
  • 36
  • Have a look here: http://stackoverflow.com/questions/10373985/c-deque-when-iterators-are-invalidated – filmor Dec 20 '14 at 12:56
  • I don´t think the C++ standard required how deque does it´s internal things. In theory, it could use a vector for some things... – deviantfan Dec 20 '14 at 12:56
  • Herb Sutter says `std::deque` doesn't reallocate(http://www.gotw.ca/gotw/054.htm): `A deque uses memory in a more operating system-friendly way, particularly on systems without virtual memory. For example, a 10-megabyte vector uses a single 10-megabyte block of memory, which is usually less efficient in practice than a 10-megabyte deque that can fit in a series of smaller blocks of memory.` – w.b Dec 20 '14 at 13:01
  • @w.b "std::deque doesn't reallocate"...I have already gone through that article and Sutter never made a firm argument in support of this statement. – ravi Dec 20 '14 at 13:03
  • 2
    It is more often stated in terms of iterator invalidation. – Marc Glisse Dec 20 '14 at 13:05
  • 1
    But ravi´s point is still standing. What HS thinks how it should be is not necessarily what standard-abiding implementations are. – deviantfan Dec 20 '14 at 14:11
  • 1
    @deviantfan: The standard specifically states that inserting/deleting at either end does not cause invalidation of references/pointers. – kec Dec 20 '14 at 15:41

2 Answers2

5

Can anyone provide me with case where std::deque needs reallocation as a consequence of some operations performed on it.

In a typical scenario, never. While the precise implementation details of a deque are unspecified, to preserve the iterator/pointer/reference invalidation* and algorithmic requirements would find ill practical use for any scenario which calls for reallocating an existing block of memory to a larger or smaller one.

[Especially focus on pointer/reference invalidation, since that tells us more about what has to go on in memory. Iterators can make some exceptions that detach their validity from the memory representation of deque].

Try putting yourself in the implementor's shoes. How do you implement functions like push_front, push_back, and expanding resize in a way that doesn't invalidate any existing pointers to the deque if you were ever tempted to reallocate memory blocks?

And likewise to preserve similar requirements for pop_front and pop_back and shrinking resize (invalidating only pointers to the elements that were removed) if you were ever tempted to reallocate an existing memory block to a smaller size?

The gotcha part, and the one place where you might find the remotest possibility of a reallocation, is inserting to the middle of the deque. That's the one place where all pointers to the deque can be invalidated, and there it might be possible to reallocate the deque's contents (possible, not necessarily practical). It is only in this particular case, as deque implementors, where we can invalidate pointers to elements that still exist where we even have the freedom to reallocate any existing memory blocks. But it's unlikely that this will happen, since an efficient insert implementation will typically just want to shuffle and move elements around, not actually reallocate the memory blocks in which they reside.

All these requirements combine to constrain the implementation to the type that Sutter describes, even if he kind of got sloppy there and glossed over the theoretical part. It's kind of like how C++03 code often took for granted that std::vector was always contiguous even though it was unspecified, since the algorithmic and iterator requirements for std::vector made a contiguous representation pretty much the only practical choice.

So in theory, it is possible that someone might sneak a reallocation somewhere, somehow, while conforming to these requirements. But in practice, it's almost impossible, and definitely impractical, so you would be hard-pressed to ever find such a deque implementation.

1

The one thing that comes to my mind is what happens when you do an insertion on a deque and the page the insertion needs to go to is full? cplusplus.com states on the insertion function about deques

If the insertion happens at the beginning or the end of the sequence, all iterators 
related to this container are invalidated, but pointers and references remain valid, 
referring to the same elements they were referring to before the call. If the 
insertion happens anywhere else in the deque, all iterators, pointers and references 
related to this container are invalidated.

The part that really catches my eye is that everything is invalidated is the insertion is in the middle which to me sounds like something is going on with the underlying data structure. I am not sure if it is a reallocation but it is at least a shift-copy-insert.

NathanOliver
  • 171,901
  • 28
  • 288
  • 402