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

Question

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.

Pacesetter

A circular buffer places some upper limit on the size of the deque. As specified, deque does not have an upper limit on its size. – Gossoon

What do you expect as a concise and definitve answer here? Stack Overflow isn't a discussion forum. – Lail

What happens when your circular buffer is full and you push another element? – Spates

@TartanLlama, How about reallocation, like vector does? – Pacesetter

@Pacesetter then you invalidate all iterators and have to copy/move all existing elements. – Spates

One key property of a std::deque is that you never invalidate iterators and references when adding or removing elements from either end. That would not be the case with a circular buffer. – Thevenot

Oh, I see. that's the requirement I miss~ thank you guys. – Pacesetter

Altough I think @Pacesetter has some point there; I don't see why deque couldn't use vector of rings. That wouldn't be much harder to implement than vector of vectors and it would allow the container to never allocate memory if total number of elements never exceeds ring size. – Greed

@AndreyTurkin, I think when deque is full , head and tail are probably in the same ring. you can't move them to insert a new chunk. and by the way, a chunk is small, so I think they won't worry if a chunk is not full. – Pacesetter

Hence "vector of rings". Once a ring is full, allocate another one and start using it; same as it is done now with vector. Rings should give some gain if number of elements stored in deque is small but rate of insersion/deletion is high (think FIFO) because it won't need to allocate new vectors every N insertions. – Greed

@AndreyTurkin, Oh i see. but I think one disadvantage is it needs additional storage and procedure to handle all these heads(tails)~, and I think this also increases the possibility of cache miss, because head data and tail data are stored in the same ring, data is quite fragmented. – Pacesetter

Agreed on some overhead. Don't see how it could increase cache misses though; it is almost as contiguous and sequential as vector is. If anything it could improve cache locality in some cases (again, FIFO with small number of elements). Anyway, let's close this discussion since it is kinda pointless :). Some (I hope) much smarter people than me had to put a lot of work to designing deque implementations and they had to have come to similar idea, tested it (hopefully) and rejected it. – Greed

Answer 1

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 "smart list" of vectors rather (i.e. fast push_front(), but probably a bit faster random access).

Animator

I believe dequeue is actually closer to vector<array<T, N>> – Nowadays

except it has a O(1) push_front. Might be two vector<array> where the first is handled as reversed, so adding to end of that one actually adds to front of deque. – Animator

True. It's more of a ring_buffer<unique_ptr<array<T,N>>> (I forgot the pointer the first time) – Nowadays