Thread: Deque Implementation

Hi,

Just out of curiosity, can anyone outline how you would implement a std::deque?

Linked list, and pointers to both ends.

That would hardly yield constant-time random access, which it has.

The standard places these requirements on deque:

Constant-time insertion and removal at both ends of the sequence.
Linear-time insertion and removal in the middle of the sequence.
Constant-time random access.

GNU standard library does it the same way.
Which is funny, because without this disclaimer:

All of the complexity requirements in this clause are stated solely in terms of the number of operations on the contained objects.

the complexity of insertion with this method is actually O(n) where n is the size of the container divided by the node size (512 in the GNU library). That's because, if the pointer field needs to be reallocated, the pointers need to be copied, which is a linear-time operation.

Originally Posted by CornedBee

That would hardly yield constant-time random access, which it has.

I haven't read any official deque requirements, but I assumed a deque (double ended queue) used basic queue push n pop instrucitons at both ends, in which a list ould be the most efficient implementation.

The requirement on constant-time random access is very well hidden.

The 1997 draft:
Deque:

1 A deque is a kind of sequence that, like a vector (_lib.vector_), sup-
ports random access iterators. In addition, it supports constant time
insert and erase operations at the beginning or the end; insert and
erase in the middle take linear time. That is, a deque is especially
optimized for pushing and popping elements at the beginning and end.
As with vectors, storage management is handled automatically.

Iterators:

8 All the categories of iterators require only those functions that are
realizable for a given category in constant time (amortized). There-
fore, requirement tables for the iterators do not have a complexity
column.

So deque must supply random access iterators. Those iterators' addition must be amortized constant time. Since [n] can be implemented as *(begin()+n), this implies that [] is constant time as well.