How do deques work?

This is a discussion on How do deques work? within the C++ Programming forums, part of the General Programming Boards category; Originally Posted by alphaoide Hmm, all I know is that, with Dequeue, accessing first item is guaranteed to be as ...

  1. #16
    Registered User
    Join Date
    Apr 2006
    Posts
    2,053
    Quote Originally Posted by alphaoide
    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?
    Professional C++ by N. A. Solter and S.J.Kleper.
    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. #17
    unleashed alphaoide's Avatar
    Join Date
    Sep 2003
    Posts
    696
    Quote Originally Posted by King Mir
    Professional C++ by N. A. Solter and S.J.Kleper.
    Well, make sure you understand what you read.

    I have this source
    A deque [1] is very much like a vector: like vector, it is a sequence that supports random access to elements, constant time insertion and removal of elements at the end of the sequence, and linear time insertion and removal of elements in the middle.

    http://www.sgi.com/tech/stl/Deque.html
    source: compsci textbooks, cboard.cprogramming.com, world wide web, common sense

  3. #18
    Registered User
    Join Date
    Apr 2006
    Posts
    2,053
    Quote Originally Posted by alphaoide
    Well, make sure you understand what you read.

    I have this source
    Linear time insetrions and deleations. Constant time access.

    Me and the link are in compleate agreement, so to speak . . .
    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. #19
    semi-colon generator ChaosEngine's Avatar
    Join Date
    Sep 2005
    Location
    Chch, NZ
    Posts
    597
    Quote Originally Posted by King Mir
    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.
    the difference is defined in the standard. the difference is in the specified interface, and that is comprised of the methods it must support.

    Of course the method interfaces define more than just a function signature. They define complexity (linear, constant, etc), pre and post conditions and error handling. In reality, this narrows down the implementation fairly sharply

    e.g. vector::front() returns a reference to the start of a contiguous block of memory and it's subscript operator is constant time. This pretty much means array implementation. but, technically a vendor is free to implement vector as a linked list and copy the contents to a memory block whenever front is called or cache an array of pointers to the objects to provide constant time random access. It would be a slow crap implementation, but it would be standard-compliant.

    edit: in fact, the standard library isn't really that standard at all. vendors are allowed to add extra parameters to methods and templates! http://www.gotw.ca/gotw/064.htm
    Last edited by ChaosEngine; 05-08-2006 at 12:13 AM.
    "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?

  5. #20
    Registered User
    Join Date
    Apr 2006
    Posts
    2,053
    Quote Originally Posted by ChaosEngine
    the difference is defined in the standard. the difference is in the specified interface, and that is comprised of the methods it must support.

    Of course the method interfaces define more than just a function signature. They define complexity (linear, constant, etc), pre and post conditions and error handling. In reality, this narrows down the implementation fairly sharply

    e.g. vector::front() returns a reference to the start of a contiguous block of memory and it's subscript operator is constant time. This pretty much means array implementation. but, technically a vendor is free to implement vector as a linked list and copy the contents to a memory block whenever front is called or cache an array of pointers to the objects to provide constant time random access. It would be a slow crap implementation, but it would be standard-compliant.
    Not only that, it would not have the same complexity, nor would it follow the results given by this nice experiment page.

    So clearly your proposed meathod (of coping a linked list over) is not the answer I'm looking for.
    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.

  6. #21
    unleashed alphaoide's Avatar
    Join Date
    Sep 2003
    Posts
    696
    Quote Originally Posted by King Mir
    Linear time insetrions and deleations. Constant time access.

    Me and the link are in compleate agreement, so to speak . . .
    Though my source doesn't say about complexity in accessing item, it says about insertion and deletion.
    Code:
    Deletion operation = Accessing item + Deleting the item
    O(N)                       = O(N)                 + O(1)
    Similarly, for insertion. Anyway, I'll let someone else put another view on this tomorrow.
    source: compsci textbooks, cboard.cprogramming.com, world wide web, common sense

  7. #22
    semi-colon generator ChaosEngine's Avatar
    Join Date
    Sep 2005
    Location
    Chch, NZ
    Posts
    597
    Quote Originally Posted by King Mir
    Not only that, it would not have the same complexity, nor would it follow the results given by this nice experiment page.

    So clearly your proposed meathod (of coping a linked list over) is not the answer I'm looking for.
    I wasn't really suggesting that! that was just a "lets take the most ridiculous implementation possible and torture it into meeting the requirements" exercise.

    My point was that, as long as you match the given specifications for complexity (which, fair enough, my example failed to do) and interface the internals are up to the vendor. To take a much more realistic example, a vector can cache it's size or calculate it on calls to size().
    "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?

  8. #23
    Registered User
    Join Date
    Feb 2006
    Posts
    312
    I would imagine a deque is a wrapper for an array (as someone else said - a bit like an overloaded vector) - since appending to the 'front' of an array would use exactly the same process as appending to the 'back'. Maybe this site will help: http://www.sgi.com/tech/stl/Deque.html

  9. #24
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,806
    Due to the way templated code is handled by most compilers, the code is probably not hidden in any sort of precompiled library. Just open up the deque header file and look at it, it's there for you to see in all its wondrous glory. It will show you everything you want to know in excrutiating detail. It's then just a matter of translating that into English (...or whatever language you speak) which may be quite difficult depending on your level of expertice in the matter.

    P.S. Don't ask me for any translation, I don't care, that's the beauty of the STL; as long as it works correctly and efficiently the internal workings don't matter. It's just that if you really want to know how it is implemented then the code is right there in front of you to look at.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  10. #25
    Registered User
    Join Date
    Dec 2004
    Location
    UK
    Posts
    109
    Quote Originally Posted by alphaoide
    A deque [1] is very much like a vector: like vector, it is a sequence that supports random access to elements, constant time insertion and removal of elements at the end of the sequence, and linear time insertion and removal of elements in the middle.

    http://www.sgi.com/tech/stl/Deque.html
    I'm pretty sure random access iterators have to guarantee constant time for access, otherwise why wouldn't a linked list implement them?

  11. #26
    Registered User
    Join Date
    Feb 2006
    Posts
    312
    Quote Originally Posted by sigfriedmcwild
    I'm pretty sure random access iterators have to guarantee constant time for access, otherwise why wouldn't a linked list implement them?
    That's not the same thing. iterators are abstractions of pointers - the random access refers to the ability to access elements by index : ie, You can access an vector/deque directly by using an index, eg
    Code:
    std::vector<int> foo;
    foo.push_back(5);
    foo.push_back(6);
    foo.push_back(8);
    int a = foo.at(1);
    However, linked lists do not have this ability, because there are no indexes in linked lists.

  12. #27
    Registered User
    Join Date
    Dec 2004
    Location
    UK
    Posts
    109
    Again from the SGI STL reference (http://www.sgi.com/tech/stl/ )

    All operations on Random Access Iterators are amortized constant time
    and for Random access containers (those that provide random access iterators)

    The run-time complexity of element access is amortized constant time
    Quote Originally Posted by Bench82
    That's not the same thing. iterators are abstractions of pointers - the random access refers to the ability to access elements by index : ie, You can access an vector/deque directly by using an index, eg
    A list is an ordered container, thus all elements have an index which is their position in their container. If the only requirement for random access was the ability to access elements by index a list could do so by iterating over the elements the right number of times.
    Last edited by sigfriedmcwild; 05-08-2006 at 10:23 AM.

  13. #28
    Registered User
    Join Date
    Feb 2006
    Posts
    312
    Quote Originally Posted by sigfriedmcwild
    A list is an ordered container, thus all elements have an index which is their position in their container. If the only requirement for random access was the ability ot access elements by index a list could do so by iterating over the elements the right number of times.
    That isn't access in constant time - because the further into the list, the longer it takes to iterate through and find that element in the list. On the other hand, a vector or deque takes the same amount of time to access any element by index regardless of its position, because you can jump straight to it, and not have to iterate through the rest of the container.

  14. #29
    Registered User
    Join Date
    Dec 2004
    Location
    UK
    Posts
    109
    Which is exactly what I was saying isn't it?

  15. #30
    Registered User
    Join Date
    Feb 2006
    Posts
    312
    Sorry, I think I might have lost track of "who said what" in this thread

Page 2 of 3 FirstFirst 123 LastLast
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, 11: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, 11: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, 05:36 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21