Is STL deque implemented as a circular linked list?

I am not able to find internals of how deque is implemented in C++ STL.

I read it somewhere earlier that in C# it is implemented as a circular list. is it true of the C++ STL too? Also, can you please explain why it is so?

EDIT : by C++ STL, I mean the STL library that ships with Visual studio C开发者_开发技巧++ 2010, and also the one which ships along with gcc

No. There's some variation allowed in how it could be implemented, but a circular linked list definitely would not qualify.

In most implementations (including VC++ and probably gcc as well) it's basically an array of pointers to blocks of data. When you add data, it normally just adds it to an existing block of data. When the existing blocks get full, it allocates a new one, adds it to the end of the array where you're inserting, and then adds your data to it. When/if the base array runs out of space, it allocates a new one and copies the pointers there.

The C++ standard requires that a deque have a constant random lookup time. A circular linked list would not meet the requirement.

STL is a specification, not an implementation. The specification places no requirements on how the behaviour must be implemented (so long as it obeys the defined interface).

An implementation of a deque must provide

1. constant time random access to it's elements
2. constant time insertion and removal at the end
3. constant time insertion and removal at the beginning

(1) rules out any kind of linked list, including circular lists

(2) & (3) rule out a simple chunk of memory where the elements are stored.

NOTE: the current standard ('03) really says constant time and not amortized constant time for (2) & (3) (see 23.2.1/1), however I think that's an oversight. I wouldn't know how to do all three in constant time. If it's only constant time for (1) and amortized constant time for (2) and (3) then it's rather easy.

AFAIK the MSVC deque uses a ring-buffer of pointers to pages of elements. Think of the ring-buffer as an array (vector) with an offset + wrap-around. And a page contains a small number of elements (IIRC no more than 8), depending on sizeof(element). The ring-buffer grows just like a std::vector if more space is needed (and this is where you need amortized constant time instead of constant time).

I think other implementations (GCC, ...) will be quite similar.

BTW: There is also a clause in the standard that makes it impossible to use just one big ring-buffer of elements, without the "pointer index". 23.2.1.3/1 says that an insertion at the beginning or the end does not invalidate references to elements in the deque. Clearly that's not possible if the structure that holds the elements itself must be reallocated when it grows beyond the reserved space. A plain ring-buffer would require that, so it cannot be used.