Thread: Deque implementation

  1. #1
    Registered User
    Join Date
    Aug 2005
    Posts
    96

    Deque implementation

    How are Deques implemented? I've read that they use arrays of arrays. Is that right?


    Maybe something like this?

    Code:
    Block<T> base[8];
    
    template<typename T>
    struct Block
    {
       T* data;
    
       int size;
    };

  2. #2
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    There's no defined way of implementing a deque, but yes, an array of fixed-sized arrays is often how it's done. That way any individual index can be determined by some quick arithmetic and constant time array access. In your example the Block size is not fixed, but in most implementations I would imagine the block size is fixed and the array of blocks is dynamic.

  3. #3
    Registered User
    Join Date
    Aug 2005
    Posts
    96
    Ok. Thanks.

    Is there any default size for a block (I'm thinking eight)?

  4. #4
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    It depends on the implementation. I'm not sure if there is a commonly used size. I would imagine the blocks would be much larger than 8, though. You can try to look through your standard library's source code to see (the documentation might also mention it, but that's not likely). You could also probably figure it out with some code that outputs the memory location of elements in a deque.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    You can implement a deque however you like, it's an abstract data type. I used a linked-list for a deque last time I had to implement one myself.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    >> I used a linked-list for a deque last time I had to implement one myself.

    You're referring to a double-ended queue in general rather than the deque interface specified by the standard, right?

  7. #7
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Does the standard say ANYTHING about how it should be implemented [other than the interface it must follow]?

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  8. #8
    The larch
    Join Date
    May 2006
    Posts
    3,573
    If I'm not wrong it needs constant-time random access, something that would be impossible to achieve with nothing more than a linked list.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Does the standard say ANYTHING about how it should be implemented [other than the interface it must follow]?
    There are complexity guarantees; with a linked list random access does not seem possible.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #10
    Registered User
    Join Date
    Aug 2005
    Posts
    96
    Quote Originally Posted by Daved View Post
    It depends on the implementation. I'm not sure if there is a commonly used size. I would imagine the blocks would be much larger than 8, though. You can try to look through your standard library's source code to see (the documentation might also mention it, but that's not likely). You could also probably figure it out with some code that outputs the memory location of elements in a deque.
    Thanks.

    Quote Originally Posted by Daved View Post
    >> I used a linked-list for a deque last time I had to implement one myself.

    You're referring to a double-ended queue in general rather than the deque interface specified by the standard, right?
    Yes.

    Quote Originally Posted by laserlight View Post
    There are complexity guarantees; with a linked list random access does not seem possible.
    Yeah that is what I'm thinking too.

  11. #11
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    >> You're referring to a double-ended queue in general rather than the deque interface specified by the standard, right?

    FYI, when I said that, I was actually asking iMalc who mentioned implementing a deque with a linked list.

  12. #12
    Registered User
    Join Date
    Aug 2005
    Posts
    96
    Quote Originally Posted by Daved View Post
    >> You're referring to a double-ended queue in general rather than the deque interface specified by the standard, right?

    FYI, when I said that, I was actually asking iMalc who mentioned implementing a deque with a linked list.
    Oh heh. Sorry.

  13. #13
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by Daved View Post
    >> I used a linked-list for a deque last time I had to implement one myself.

    You're referring to a double-ended queue in general rather than the deque interface specified by the standard, right?
    Oh certainly, yes. I always thought that the only reason they allow random access in a std::deque is because it is implmenented in such as way that makes that possible in constant time, so they figured what the heck someone will use it.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. deque best practices
    By George2 in forum C++ Programming
    Replies: 10
    Last Post: 03-02-2008, 08:11 PM
  2. Confusion with a Deque program
    By Bluefish in forum C++ Programming
    Replies: 0
    Last Post: 05-20-2006, 03:13 PM
  3. costum grow() not working
    By Opel_Corsa in forum C++ Programming
    Replies: 2
    Last Post: 02-17-2006, 10:11 PM
  4. Very slow processing of vectors?
    By Blackroot in forum C++ Programming
    Replies: 35
    Last Post: 02-06-2006, 06:36 PM
  5. Deque Implementation
    By CornedBee in forum C++ Programming
    Replies: 6
    Last Post: 04-06-2005, 04:19 PM