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

12,205

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.

Share:
12,205
sunnior
Author by

sunnior

Updated on June 08, 2022

Comments

  • sunnior
    sunnior almost 2 years

    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.