page 464 stroustrup''s the C++ Programming language list STL op times. thats what i was using.
It list O(n) for Stacks "list" operation. Which was intersting cause in review your right it doesnt support any of the list operations. (insert,erase,clear). lol

btw vectors times make alot more sense in light of the no push front. i dont tend to think in terms of sub script access so i dont use it much.

Lohrno:

I think you would really enjoy a book on the standard library. There are so many things in it. You''ll find that once you know iterators a whole new world opens up. I recommend The C++ Standard Library by Nicolai M. Josuttis. It''s the book I have, it''s good. It is both a tutorial and reference, so it is the only book you''ll need on the standard library. So if you have the money buy, or wait until a birthday or something.

Hah! Thanks guys! =D Actually, speed and memory are kinda important, but I guess it all depends on what I will be doing with it. Like, if I were to do some simple lightweight stuff, but wanted speed, and speedy insertion, I guess I should use Vector. But if I''m always going to be going through the whole thing one element at a time, maybe a list is better. And to be honest, I''m confused as to really what a deque is. STL docs online say it''s something like a vector, except you can insert in the beginning, and it doesn''t allocate memory?

Hmmm I think I''ll look for a book like AP says. It seems like a nice set of libraries that can do a lot provided you know what exactly you need, and what would accoplish it best. =D

-=Lohrno

quote: Original post by Lohrno
And to be honest, I''m confused as to really what a deque is.

Double-Ended Queue.

A queue is a FIFO (First In, First Out) data structure (stack, OTOH, is LIFO). It supports push, pop and front operations; push inserts an element from the tail, pop removes one from the head and front returns the element at the head. A double-ended queue supports push_front, push_back, pop_front, pop_back, front and back operations which do exactly what their names suggest. Interestingly, since the functionality of a deque encompasses and exceeds that of a queue, STL queues are actually internally deques with an adaptor to constrain operations on the controlled sequence. I''ve heard that there are only three actual STL data structures: deque, vector and set (probably multiset, though) and all other data structures are actually adaptors on them. I haven''t had the time to assess the validity or correctness of that statement, but it''s interesting nonetheless.

[ GDNet Start Here | GDNet Search Tool | GDNet FAQ ]
[ MS RTFM [MSDN] | SGI STL Docs | Boost ]
[ Google! | Asking Smart Questions | Jargon File ]
Thanks to Kylotan for the idea!

The internal container for the associative containers is a tree, ocasionally seen as _Tree (implementation dependent name, I assume, from the _Uppercase) in error messages.

Lists are doubly-linked list, either a type of its own, or adapted form _Tree, but I suspect the former. Specializing the classes based on whether they can have duplicates or not is easy with a traits class (such as _Tset_traits).

stack, queue and priority queue are adaptors that use deque as the underlying container by default.

According to Josuttis, deque are usually implemented as arrays of arrays, which is why it is easier for them to insert at the beginning (just create a new array).

[Questions (STFW) | GDNet Start Here | GDNet Search | Forum FAQ | Google | Asking Smart Questions ]
[Docs (RTFM) | MSDN | SGI''s STL | OpenGL | File formats]
[C++ Must Haves (RTFS) | MinGW | Boost | Loki | FLTK | SDL ]

Stolen from Magmai Kai Holmlor, who held it from Oluseyi, who was inspired by Kylotan...