# Thread: How do deques work?

1. ## How do deques work?

I have implemented my own linked lists before, so I understand how lists work.
And I can understand how a vector works; it just allocates a heap array and realocates it when it gets full, kind of like realloc, but with constructors and destructors. Right?

But can somebody explain to me how deques work?

2. Originally Posted by King Mir
But can somebody explain to me how deques work?
You meant Queues? or Double-ended Queues?

3. The deques as found in the STL. I want the algorithim, not how it's used.

But yes deque does stand for Double-ended Queue.

4. Dequeue is implemented as doubly linked list http://en.wikipedia.org/wiki/Linked_...ly-linked_list, which is similar to singly linked list, except that each node has pointers to previous and next node, instead of only to next one. The way the member methods are implemented are obvious by looking at the list structure. If not, then tell us, which method you want to know the implementation.

5. I don't think deques are required to be implemented in any specific fashion by the standard, so each implementation may vary. I'd suggest having a look at your <deque> header.

In the general case, I'd imagine they're implemented as an over-allocated vector, but I could be wrong.

6. Originally Posted by alphaoide
Dequeue is implemented as doubly linked list http://en.wikipedia.org/wiki/Linked_...ly-linked_list, which is similar to singly linked list, except that each node has pointers to previous and next node, instead of only to next one. The way the member methods are implemented are obvious by looking at the list structure. If not, then tell us, which method you want to know the implementation.
That cannot be right becouse that's how list is implemented. Nor would it work for random access. No, The FAQ said something about having small segments of ordered data. . .

7. Originally Posted by King Mir
That cannot be right becouse that's how list is implemented.
What a reasoning??

Nor would it work for random access.
Yes, it would. Say you want item at index 4, you'd start from the head and hope 4 nodes.

But, ChaosEngine is right. What makes a Dequeue is not the implementation, but instead, the methods it provides. You could implement a Dequeue with a simple array if you want to.

8. Actually, everyone is completely wrong. Prelude wrote something on this.

9. Originally Posted by alphaoide
What a reasoning??
Huh? the list container is a doublely linked list. It supports quick deleation and insertion anywhere at constant complexity and linear complexity lookup. This is not true of deque.

Yes, it would. Say you want item at index 4, you'd start from the head and hope 4 nodes.
Thus the linear complexity. The higher ther index, the slower the lookup.

But, ChaosEngine is right. What makes a Dequeue is not the implementation, but instead, the methods it provides. You could implement a Dequeue with a simple array if you want to.
Which would compleatly defeate the purpose of the STL. But Ok, what is the simplest way to implement deque functionality found with STL's deque? This is esentially what I'm asking anyway.

10. Originally Posted by alphaoide

>> Nor would it work for random access.

Yes, it would. Say you want item at index 4, you'd start from the head and hope 4 nodes.
how would that would provide constant time access? in a deque, I thought accessing d[0] should take the same time as accessing d[1000]

have a look at http://www.codeproject.com/vcpp/stl/vector_vs_deque.asp for more than you ever wanted to know about deques

11. Originally Posted by citizen
Actually, everyone is completely wrong. Prelude wrote something on this.
Yea, I read that. It just compairs vectors and deques, and preaches the use of either one. I still don't get how deques work.

12. Originally Posted by ChaosEngine
how would that would provide constant time access? in a deque, I thought accessing d[0] should take the same time as accessing d[1000]
Yes. That's the definiotion of constant complexity.

have a look at http://www.codeproject.com/vcpp/stl/vector_vs_deque.asp for more than you ever wanted to know about deques
Thanks, that looks like exactly what I wanted.

Edit: No that's still just a comparison of proformance. It does not tell me why the results are as they are. I'm really curious how it works.

13. Originally Posted by King Mir
Which would compleatly defeate the purpose of the STL.
agree with everything else you said, but why would that defeat the purpose of the stl? The standard library defines interfaces and operational complexity, if you match those guarentees you can implement the containers in anyway you see fit. This is a good thing as it allows compiler/library writers to optimise their implementations for their platform, but maintain a common interface.

For example, if on some weird quantum computing platform, an std::list is more efficently implemented as a BST , they can do that. It's not likely, but it's allowed.

14. Originally Posted by ChaosEngine
agree with everything else you said, but why would that defeat the purpose of the stl? The standard library defines interfaces and operational complexity, if you match those guarentees you can implement the containers in anyway you see fit. This is a good thing as it allows compiler/library writers to optimise their implementations for their platform, but maintain a common interface.

For example, if on some weird quantum computing platform, an std::list is more efficently implemented as a BST , they can do that. It's not likely, but it's allowed.
You misunderstood me. For the sake of not clairifing, I agree with you.

However, there needs to be some difference between deque, list, and vector. That difference should be defined somewhere. And ofcourse it cannot be only the meathods it uses. For example list is most definately defined as a doubly linked list.

Thus my question, how is a deque usually implemented? What model generates the results of the experiments in the above provided link?

Or most simmply, how do I write my own implementation of deque?
As I said, I could write an implementation of a vector and a list that provides similar functionality, but How do I implement a deque?

15. Originally Posted by ChaosEngine
how would that would provide constant time access? in a deque, I thought accessing d[0] should take the same time as accessing d[1000]
Hmm, all I know is that, with Dequeue, accessing first item is guaranteed to be as fast as accessing last item, which is also true for doubly linked linked. Where did you get the requirement for complexity of access operations?