Finding advanced STL container information
Author
I am looking for some more advanced information about the various STL containers. I want to find out more about how they each work internally for looking at the source is just confusing: there are so many typedefs and stuff to keep track of with no commenting. The other thing I want to know is the speed of accessing and adding variables in the containers and how it changes over time.
Thanks.
There''s a very detailed description of how they work, what they do, how fast they do it, in the book ''The C++ Programming Language'' by Bjarne Stroustrup.
The way STL containers work is up to individual implementers.
The C++ standard mandates performance guarantees, not specific implementations.
However, here are typical implementations :
Book :
Nicolai M. Josuttis
The C++ Standard Library - A Tutorial and Reference
Addison-Wesley U.S.A., 1999
ISBN 0-201-37926-0
The C++ standard mandates performance guarantees, not specific implementations.
However, here are typical implementations :
- vector
Dynamically-allocated (new) array.
Access is O(1)
Traversal is O(n)
Insertion/deletion at the end is amortized O(1)
Insertion/deletion anywhere else is O(n) - deque
Dynamic array of pointers to fixed-size arrays.
Access is O(1) - a simple computation is done to find out in which array a given index falls.
Traversal is O(n)
Insertion/deletion at the beginning and end is amortized O(1)
Insertion/deletion anywhere else is O(n) - list
Doubly linked list
Access is O(n)
Traversal is O(n)
Insertion/deletion anywhere is O(1) but requires an iterator. - Associative containers ( map, set, multimap, multiset )
Binary tree - the specific tree type and balancing scheme vary, red-black trees are popular.
Access is O(log n)
Traversal is O(n)
Insertion/deletion is O(log n) anywhere - Adaptors (queue, stack, priority_queue)
Wrappers around other containers, a deque by default.
Book :
Nicolai M. Josuttis
The C++ Standard Library - A Tutorial and Reference
Addison-Wesley U.S.A., 1999
ISBN 0-201-37926-0
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
