Container Classes

• Up to now, the data structures we've used:  linked-lists, stacks, and queues, are those we've built ourselves.  If these structures are so useful---and they are---why are they not part of the language?

  1. They are implementations, not language constructs

  2. They have many variants.  For example, consider the different kinds of queues:

     1. In type:

        1. Queue of characters

        2. Queue of integers

        3. Queue of __________

     2. In characteristics:

        1. Simple queue

        2. Priority queue (w/multiple priority schemes)

        3. Double-ended queue

• However, the usefulness of common data structures has encouraged a standardization for these data structures in the C++ Standard Template Library (or STL).

• The STL provides many common data structures for managing (or containing) objects, including:  vectors, lists, stacks, queues, priority queues, sets, and maps.

• STL data structures are templates, meaning they are incomplete implementations until a C++ object type is provided by the programmer to indicate the objects which they operate upon.

  • Example:  lists are sequences of objects, so if we want a sequence of float objects, we specify:  list<float>.  If we want a list of complex_number then we specify:  list<complex_number>.  Get it?

• Template implementations are very powerful.  They have some limitations and some special rules, but we can ignore that for now (we'll look at them in depth more later) and just take advantage of them.

• Here are the STL data structures we'll look at (in this order):

  • vector:  provides dynamic resizing and random access to a collection of like objects.

  • list:  provides dynamic resizing, combining, and sorting of the list(s).

  • stack:  provides the LIFO behavior of adding to and removing from the stack.

  • queue:  provides the FIFO behavior of adding to and removing from the queue.