Thread: How do deques work?

  1. #1
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149

    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?
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  2. #2
    unleashed alphaoide's Avatar
    Join Date
    Sep 2003
    Posts
    696
    Quote Originally Posted by King Mir
    But can somebody explain to me how deques work?
    You meant Queues? or Double-ended Queues?
    source: compsci textbooks, cboard.cprogramming.com, world wide web, common sense

  3. #3
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    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.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  4. #4
    unleashed alphaoide's Avatar
    Join Date
    Sep 2003
    Posts
    696
    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.
    source: compsci textbooks, cboard.cprogramming.com, world wide web, common sense

  5. #5
    semi-colon generator ChaosEngine's Avatar
    Join Date
    Sep 2005
    Location
    Chch, NZ
    Posts
    597
    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.
    "I saw a sign that said 'Drink Canada Dry', so I started"
    -- Brendan Behan

    Free Compiler: Visual C++ 2005 Express
    If you program in C++, you need Boost. You should also know how to use the Standard Library (STL). Want to make games? After reading this, I don't like WxWidgets anymore. Want to add some scripting to your App?

  6. #6
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    Quote 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. . .
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  7. #7
    unleashed alphaoide's Avatar
    Join Date
    Sep 2003
    Posts
    696
    Quote 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.
    source: compsci textbooks, cboard.cprogramming.com, world wide web, common sense

  8. #8
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Actually, everyone is completely wrong. Prelude wrote something on this.

  9. #9
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    Quote 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.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  10. #10
    semi-colon generator ChaosEngine's Avatar
    Join Date
    Sep 2005
    Location
    Chch, NZ
    Posts
    597
    Quote 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
    "I saw a sign that said 'Drink Canada Dry', so I started"
    -- Brendan Behan

    Free Compiler: Visual C++ 2005 Express
    If you program in C++, you need Boost. You should also know how to use the Standard Library (STL). Want to make games? After reading this, I don't like WxWidgets anymore. Want to add some scripting to your App?

  11. #11
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    Quote 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.
    Last edited by King Mir; 05-07-2006 at 10:54 PM.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  12. #12
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    Quote 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.
    Last edited by King Mir; 05-07-2006 at 10:38 PM.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  13. #13
    semi-colon generator ChaosEngine's Avatar
    Join Date
    Sep 2005
    Location
    Chch, NZ
    Posts
    597
    Quote 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.
    "I saw a sign that said 'Drink Canada Dry', so I started"
    -- Brendan Behan

    Free Compiler: Visual C++ 2005 Express
    If you program in C++, you need Boost. You should also know how to use the Standard Library (STL). Want to make games? After reading this, I don't like WxWidgets anymore. Want to add some scripting to your App?

  14. #14
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    Quote 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?
    Last edited by King Mir; 05-07-2006 at 10:51 PM.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  15. #15
    unleashed alphaoide's Avatar
    Join Date
    Sep 2003
    Posts
    696
    Quote 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?
    source: compsci textbooks, cboard.cprogramming.com, world wide web, common sense

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. getline() don't want to work anymore...
    By mikahell in forum C++ Programming
    Replies: 7
    Last Post: 07-31-2006, 10:50 AM
  2. Why don't the tutorials on this site work on my computer?
    By jsrig88 in forum C++ Programming
    Replies: 3
    Last Post: 05-15-2006, 10:39 PM
  3. help getting program to work
    By jlmac2001 in forum C Programming
    Replies: 2
    Last Post: 11-13-2002, 11:04 PM
  4. fopen();
    By GanglyLamb in forum C Programming
    Replies: 8
    Last Post: 11-03-2002, 12:39 PM
  5. DLL __cdecl doesnt seem to work?
    By Xei in forum C++ Programming
    Replies: 6
    Last Post: 08-21-2002, 04:36 PM