Hi,
Just out of curiosity, can anyone outline how you would implement a std::deque?
Hi,
Just out of curiosity, can anyone outline how you would implement a std::deque?
All the buzzt!
CornedBee
"There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
- Flon's Law
Linked list, and pointers to both ends.
MagosX.com
Give a man a fish and you feed him for a day.
Teach a man to fish and you feed him for a lifetime.
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.
All the buzzt!
CornedBee
"There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
- Flon's Law
http://www.cs.duke.edu/~ola/courses/...l96/deque.html
That page has a suggestion on how to get constant-time access.
GNU standard library does it the same way.
Which is funny, because without this disclaimer:
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.All of the complexity requirements in this clause are stated solely in terms of the number of operations on the contained objects.
All the buzzt!
CornedBee
"There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
- Flon's Law
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.Originally Posted by CornedBee
MagosX.com
Give a man a fish and you feed him for a day.
Teach a man to fish and you feed him for a lifetime.
The requirement on constant-time random access is very well hidden.
The 1997 draft:
Deque:
Iterators: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.
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.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.
All the buzzt!
CornedBee
"There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
- Flon's Law