Deque Implementation

This is a discussion on Deque Implementation within the C++ Programming forums, part of the General Programming Boards category; Hi, Just out of curiosity, can anyone outline how you would implement a std::deque?...

  1. #1
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,892

    Deque Implementation

    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

  2. #2
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    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.

  3. #3
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,892
    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

  4. #4
    Senior Member joshdick's Avatar
    Join Date
    Nov 2002
    Location
    Phildelphia, PA
    Posts
    1,146
    http://www.cs.duke.edu/~ola/courses/...l96/deque.html

    That page has a suggestion on how to get constant-time access.

  5. #5
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,892
    GNU standard library does it the same way.
    Which is funny, because without this disclaimer:
    All of the complexity requirements in this clause are stated solely in terms of the number of operations on the contained objects.
    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 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

  6. #6
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    Quote Originally Posted by CornedBee
    That would hardly yield constant-time random access, which it has.
    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.
    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.

  7. #7
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,892
    The requirement on constant-time random access is very well hidden.

    The 1997 draft:
    Deque:
    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.
    Iterators:
    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.
    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.
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

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

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