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)
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)
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?
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?
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).
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
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.
Quoted more than 1000 times (I hope).Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.