Thread: STL deque wrappers

  1. #1
    ...and never returned. StainedBlue's Avatar
    Join Date
    Aug 2009
    Posts
    168

    STL deque wrappers

    Just out of curiosity,

    what was the reason behind queues and stacks being implemented as wrappers around deques in the STL? (Besides the obvious allowing for container copies)

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Probably the fact that a queue Just Plain Is a special case of a deque. So if you've already got a deque, why make a completely new thing?

  3. #3
    ...and never returned. StainedBlue's Avatar
    Join Date
    Aug 2009
    Posts
    168
    So ease of implementation eh?

    I don't remember if singly-linked-lists will be part of the new standard, but if they make the cut, you think they'll simply wrap around the existing STL list?

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    I would be extremely surprised if it was anything else (performance is the whole point of the STL, and so there's no reason to make implementors try and create something new -- as though they wouldn't just cut and paste anyway -- when they can use what's already been fine-tuned).

  5. #5
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Stacks and queues are templates; they are wrappers around a generic container. They just default to using deque, because it's most efficient in the general case. (Actually, priority_queue defaults to vector.)
    So you can use std::list for std::stack and std::queue, or std::vector for std::stack, or std::deque for std::priority_queue.
    You can't use C++0x std::forward_list for any of the adapters, actually, because it doesn't support push_back, which is a requirement of all of them. However, you could easily write an adapter for forward_list that "inverts" the list, i.e. provides push_back(), pop_back() and back(), and implements them in terms of the *front() versions. Then you use that adapter instead of the list.
    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
    The larch
    Join Date
    May 2006
    Posts
    3,573
    stack and queue are not containers but container adaptors. They wrap a deque by default, but they can just as well use a std::list or a user-defined container with a suitable interface (the container type is given with a template parameter).

    I'm not sure if there are any plans for singly-linked list, but if so it would be a container.
    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).

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Confusion with a Deque program
    By Bluefish in forum C++ Programming
    Replies: 0
    Last Post: 05-20-2006, 03:13 PM
  2. costum grow() not working
    By Opel_Corsa in forum C++ Programming
    Replies: 2
    Last Post: 02-17-2006, 10:11 PM
  3. im extreamly new help
    By rigo305 in forum C++ Programming
    Replies: 27
    Last Post: 04-23-2004, 11:22 PM
  4. Prime Number Generator... Help !?!!
    By Halo in forum C++ Programming
    Replies: 9
    Last Post: 10-20-2003, 07:26 PM
  5. include question
    By Wanted420 in forum C++ Programming
    Replies: 8
    Last Post: 10-17-2003, 03:49 AM