C++ std::deque implementation: why not use circular buffer?

c++ stl deque circular-buffer
sunnior picture sunnior · Oct 27, 2016 · Viewed 8.8k times · Source

I did some search on the implementation of deque. According to this post, deque uses vector of vectors. I know pushing at the begin and end should be both in constant time, and also random access is required. I think circular buffer meets all these requirements, and is much simpler. So why not use circular buffer?

I also found the boost circular buffer. How it compares to deque?

Edit: Ok, so it has something to do with the Iterator Invalidation Rules.It states:

all iterators and references are invalidated, unless the inserted member is at an end (front or back) of the deque (in which case all iterators are invalidated, but references to elements are unaffected)

My understanding is to overload operator like iter++, the iterators has to own a pointer to the node map and a pointer to the chunk, so if the node map is reallocated, the iterator is invalidated. But since the data never moves, the references are still valid.

Answer

Macke picture Macke · Mar 26, 2019

A circular buffer cannot be expanded indefinitely. Eventually, you need to allocate a new one and copy all items over.

Deque can simply allocate a new vector in front of the previous ones and add a "middle" element there. I think of it as a a list of vectors rather.

Related questions

What really is a deque in STL?

I was looking at STL containers and trying to figure what they really are (i.e. the data structure used), and the deque stopped me: I thought at first that it was a double linked list, which would allow insertion …

Read More
What's the difference between deque and list STL containers?

What is the difference between the two? I mean the methods are all the same. So, for a user, they work identically. Is that correct??

Read More
Why would I prefer using vector to deque

Since they are both contiguous memory containers; feature wise, deque has almost everything vector has but more, since it is more efficient to insert in the front. Why whould anyone prefer std::vector to std::deque?

Read More