title: C++ std::deque implementation: why not use circular buffer?
body: <p>I did some search on the implementation of deque. According to <a href="https://stackoverflow.com/questions/6292332/what-really-is-a-deque-in-stl">this post</a>, 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?</p>
  
  <p>I also found the <a href="http://www.boost.org/doc/libs/1_53_0/libs/circular_buffer/doc/circular_buffer.html" rel="noreferrer">boost circular buffer</a>. How it compares to deque?</p>
  
  <hr>
  
  <p>Edit:
       Ok, so it has something to do with the <a href="http://kera.name/articles/2011/06/iterator-invalidation-rules-c0x/" rel="noreferrer">Iterator Invalidation Rules</a>.It states:</p>
  
  <blockquote>
    <p>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)</p>
  </blockquote>
  
  <p>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.</p>