0

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

paseena
  • 4,207
  • 6
  • 32
  • 51
  • Re .NET, you may be confusing a regular queue implemented with a *circular buffer* with a deque – Marc Gravell Apr 05 '11 at 22:53
  • According to the first comment in the class template definition in the VC++ deque header, it's a `// circular queue of pointers to blocks`. After that, it's all in Greek. – Benjamin Lindley Apr 05 '11 at 22:55

4 Answers4

8

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.

Jerry Coffin
  • 476,176
  • 80
  • 629
  • 1,111
6

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

Mark Ransom
  • 299,747
  • 42
  • 398
  • 622
  • I interpreted the OP to mean a circular array, not a circular linked list. A circular buffer is contiguous, but the data can start in the middle of the buffer, and wrap around to the front of it. Nevertheless, std::deque can not be a circular array either. – Howard Hinnant Apr 05 '11 at 23:58
  • @Howard, the "linked list" designation is in the title. – Mark Ransom Apr 06 '11 at 01:09
2

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).

Oliver Charlesworth
  • 267,707
  • 33
  • 569
  • 680
2

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.

Paul Groke
  • 6,259
  • 2
  • 31
  • 32
  • IIRC, the C++ standard is actually expressed in terms of complexity on the contained type, not time. Else resizing the outer vector of a `std::vector >` could be an O(N*N) operation. But since complexity is counted in terms of lists, not ints or milliseconds, it's still O(N). And resizing the ring-buffer here doesn't touch the deque elements. – MSalters Apr 06 '11 at 12:37
  • Resizing an `std::vector >` would be O(N + M) where M is the total number of elements in all lists. Or simply O(N) if we assume the cost of copying an element (in this case a list) to be constant. IMO specifying *constant time* for `deque::push_back()` etc. just doesn't make sense. Growing the index isn't possible in constant time, only amortized constant time, so that's what the complexity spec. should say. Otherwise we could also say that random access in a `std::list` is O(1), because it involves no operations on the elements. Doesn't make sense to me. – Paul Groke Apr 06 '11 at 15:05
  • Er. O(N + M) is incorrect, it's really just O(max(N, M)) with N = number of lists and M = number of elements in all lists. Anyway, doesn't invalidate my point. – Paul Groke Apr 06 '11 at 15:14