[Effective-cpp] Item 1: Choose Your Containers With Care

[Paul Grenyer]

                Item 1: Choose Your Containers With Care


In this item Scott starts off by listing and categorising the various
contains provided by the C++ Standard and those that are found in common
implementations:


Standard STL Sequence Containers


      * vector
        
      * string
        
      * deque
        
      * list
        
        

Standard STL Associative Containers


      * set
        
      * multiset
        
      * map
        
      * multimap
        
      * 
Non-Standard Sequence Containers


      * slist – a singly linked list
        
      * rope – a heavy duty string
        
        

Non-Standard Associative Containers (hash-table-based containers)


      * has_set
        
      * hash_multiset
        
      * hash_map
        
      * hash_mulitmap
        
        

Also mentioned is the fact that vector<char> can be used as a
replacement for string, that there are many times when a vector can
out-perform the associative containers in terms of time and space and
that non-STL containers such as arrays, bitset, valarray, stack, queue
and priority queue are also available, but not covered by the book. 


Scott goes on to highlight the fact that most discussions of STL
containers fail to cover a lot of the issues concerned with selecting
the right container for the right job. To help readdress the balance he
divides the containers into two distinct groups:



Contiguous Memory Containers 


Contiguous Memory Containers store their elements in one or more
dynamically allocated chunks of memory. Inserting or removing elements
can cause the other elements to be reshuffled in order to maintain the
contiguous arrangement. vector, string and deque are all Contiguous
Memory Containers.


Node-based Containers.


Node based containers store only a single element per chunk of
dynamically allocated memory. Inserting or deleting elements is much
faster (especially in the middle of the container) because only the
pointers to the contents of the nodes need to be moved. list, slist, the
associative containers (set, multiset, map and multimap) and the various
non-standard has containers are all node based containers.


Scott finishes the item with a list of questions aimed to help choose
the appropriate container. I think this could have been presented better
as a tree diagram where one question leads on from the next depending on
how it is answered and all branches lead finally to a container. I've
often thought this would be a good exercise for the Linux \ STL project.
If I get chance I'll knock up a diagram and a small application which
helps choose containers in this way.

-- 


Regards
Paul

Paul Grenyer
Email: pjgrenyer at iee.org
Web: www.paulgrenyer.co.uk

EvanScence: http://www.evanescence.com