Archived

This topic is now archived and is closed to further replies.

Finding advanced STL container information

This topic is 5236 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
The way STL containers work is up to individual implementers.
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

Share this post


Link to post
Share on other sites