Standard Out and Input

STL also includes classes for printing to the standard output streams. Like standard C++ the classes are cout and wcout. To use them in a console application include the file iostream. As an example:

Collapse Copy Code

    
      #include
    
    
      
        <
      
      
        iostream
      
      
        >
      
    
    
      void
    
     main ()
{
	
    
      char
    
     ch;
     
	cin 
    
      >
    
    
      >
    
     ch;
	cout 
    
      <
    
    
      <
    
     &#8220;This is the output terminal 
    
      for
    
     STL&#8221; 
    
      <
    
    
      <
    
     endl;
}

  

Vector and Deque add and remove methods

We want to look briefly at adding/removing elements from the vector and deque collections. These collections are represented as an array, and to add an element we use the push methods with back or front depending on if we are adding at the front (start) or back (end) of an array.

The general methods are:

As an example, suppose we want to build a message processing system based on a message class:

Collapse Copy Code

    Class Msg
{
	
    
      int
    
     _type;
	
    
      int
    
     _priority;
	
    
      string
    
     _message;
	
	
    
      public
    
    :

	Msg ( 
    
      int
    
     type, 
    
      int
    
     priority, 
    
      string
    
     & msg )
    { _type = type; priority = priority; _msg = msg; }
          
	Msg ( 
    
      int
    
     type, 
    
      int
    
     priority, 
    
      char
    
     * msg )
	{ _type = type; priority = priority; _msg = msg; }
          
	
    
      int
    
     getType () { 
    
      return
    
     _type; }
	
    
      int
    
     getPriority () { reutrn _priority; }
	
    
      string
    
     & getMsg () {
    
      return
    
     _msg; }
};
  

To store the messages we would need a first in first out based collection, such as deque: typedef deque<Msg> MsgList;

To send a message we might do the following:

Collapse Copy Code

         Msg message( 
    
      0
    
    , 
    
      0
    
    , 
    
      "
    
    
      My Message"
    
     );
     msgList.push_back(msg);
  

And to process message we could would do the following:

Collapse Copy Code

    
      void
    
     process_msgs ()
{
	
    
      bool
    
     done = 
    
      false
    
    ;
	
    
      while
    
     ( !done )
	{
		
    
      //
    
    
       if no messages stop

    
    
      if
    
     ( msgList.size() == 
    
      0
    
     )
		{ done == 
    
      true
    
    ; 
    
      continue
    
    ;}
		
    
      //
    
    
       get msg and process

    
    		Msg & msg = msgList.front();
		
		
    
      switch
    
     ( msg.getType() )
		{ 
    
      //
    
    
       process messages }

    
    
      //
    
    
       remove msg from que

    
    		msgList.pop_front();
	}
}
  

With just a few lines of code we have created a general messaging system, if we wanted an entire system we could create a simple COM server that exposed a mail interface, and that stored the messages using a message list.

Operator []

For vector, map, deque, string and wstring collections, elements are normally added using:

Collapse Copy Code

    
      operator
    
     []
  

Access an element at a position, and for map, string and wstring supports insert of element.

A simple example of using this operator would be to decalre a list using map:

Collapse Copy Code

    
      typedef
    
     map
    
      <
    
    
      int
    
    , 
    
      string
    
    
      >
    
     StringList
StringList strings;
stringstream strStr

    
      for
    
     ( 
    
      long
    
     i=0; i
    
      <
    
    
      10
    
    ; i++ )
{
	stringstream strStr;
	strStr 
    
      <
    
    
      <
    
    
      "
    
    
      String "
    
    
      <
    
    
      <
    
     i;
	strings[i] = strStr.str();
}

    
      for
    
     ( 
    
      long
    
     i=0; i
    
      <
    
    
      10
    
    ; i++ )
{
	
    
      string
    
     str = strings[
    
      5
    
    ];
	cout 
    
      <
    
    
      <
    
     str.c_str() 
    
      <
    
    
      <
    
     endl;
}
  

We have created a map, whose key is an integer, and that stores strings.

Iterators

Iterators support the access of elements in a collection. They are used throughout the STL to access and list elements in a container. The iterators for a particular collection are defined in the collection class definition. Below we list three types of iterators, iterator, reverse_iterator, and random access. Random access iterators are simply iterators that can go both forward and backward through a collection with any step value. For example using vector we could do the following:

Collapse Copy Code

    vector
    
      <
    
    
      int
    
    
      >
    
        myVec;
vector
    
      <
    
    
      int
    
    
      >
    
    ::iterator    first, last;

    
      for
    
     ( 
    
      long
    
     i=0; i
    
      <
    
    
      10
    
    ; i++ )
	myVec.push_back(i);
first = myVec.begin();
last = myVec.begin() + 
    
      5
    
    ;

    
      if
    
     ( last 
    
      >
    
    = myVec.end() )
	
    
      return
    
    ;
myVec.erase( first, last );

  

This code will erase the first five elements of the vector. Note, we are setting the last iterator to one past the last element we of interest, and we test this element against the return value of end (which give an iterator one past the last valid item in a collection). Always remember when using STL, to mark the end of an operation use an iterator that points to the next element after the last valid element in the operation.

The three types of iterators are:

iterator (forward iterator through collection)

Allows a collection to be traversed in the forward direction. To use the iterator

Collapse Copy Code

        
          for
        
         ( iterator element = begin(); element 
        
          <
        
         end(); element++ ) 
	t = (*element);
      

Forward iterators support the following operations:

Collapse Copy Code

        a++, ++a, *a, a = b, a == b, a != b
      

reverse_iterator (reverse iterator through collection)

Allows a collection to be traversed in the reverse direction. As an example:

Collapse Copy Code

        
          for
        
         ( reverse_iterator element = rbegin(); element 
        
          <
        
         rend(); element++ ) 
	t = (*element);
      

All of the collections support forward iterators. Reverse iterators support the following operations:

Collapse Copy Code

        a++, ++a, *a, a = b, a == b, a != b
      

random access ( used by vector declared as forward and reverse_iterator)

Allows a collection to be traversed in either direction, and with any step value. An example would be:

Collapse Copy Code

        
          for
        
         ( iterator element = begin(); element 
        
          <
        
         end(); element+=2 ) 
	t = (*element);
      

The vector collection supports random access iterators. Iterators are the most used type of access to the collections of STL, and they are also used to remove elements from collections. Look at the following:

Collapse Copy Code

        iterator element = begin(); erase(element);
      

This will set an iterator to the first element of the collection and then remove it from the collection. If we were using a vector we could do the following

Collapse Copy Code

        iterator firstElement = begin();
          iterator lastElement = begin() + 
        
          5
        
        ;
          erase(firstElement,lastElement);
   
   
        

          
          
             Collapse
          
          
          
             Copy Code
          
        
        
          

            to remove the first five elements of a collection.
          Random access iterators support the following:
          
          
          
          

            
            
               Collapse
            
            
            
               Copy Code
            
          
          
            a++, ++a, a--, --a, a += n, a -= n, a – n, a + n*a, a[n],
a = b, a == b, a != b, a 
            
              <
            
             b, a 
            
              <
            
            = b, a 
            
              >
            
             b, a 
            
              >
            
            = b 
          
        
      

It is important to remember, when you get an iterator to a collection do not modify the collection and then expect to use the iterator. Once a collection has been modified an iterator in most cases will become invalid.

Declaring collections

Each collection uses it’s template paramters to determine what elements the collection will store. Shown below is a list of the collections we are discussing and beside each is the template pamaters. In the parameters T denotes the element type to store in the collection, A denotes the allocator (which allocates elements), Key denotes the key for the element, and Pred denotes how the collection will be sorted.

Collapse Copy Code

    
      template
    
    
      <
    
    
      class
    
     T, 
    
      class
    
     A = allocator
    
      <
    
    T
    
      >
    
    
      >
    
    
      class
    
     vector

    
      template
    
    
      <
    
    
      class
    
     T, 
    
      class
    
     A = allocator
    
      <
    
    T
    
      >
    
    
      >
    
    
      class
    
     list

    
      template
    
    
      <
    
    
      class
    
     T, 
    
      class
    
     A = allocator
    
      <
    
    T
    
      >
    
    
      >
    
    
      class
    
     deque

    
      template
    
    
      <
    
    
      class
    
     Key, 
    
      class
    
     T, 
    
      class
    
     Pred = less
    
      <
    
    Key
    
      >
    
    , 
    
      class
    
     A = allocator
    
      <
    
    T
    
      >
    
    
      >
    
    
      class
    
     map

    
      template
    
    
      <
    
    
      class
    
     Key, 
    
      class
    
     Pred = less
    
      <
    
    Key
    
      >
    
    , 
    
      class
    
     A = allocator
    
      <
    
    Key
    
      >
    
    
      >
    
    
      class
    
     set

    
      template
    
    
      <
    
    
      class
    
     Key, 
    
      class
    
     T, 
    
      class
    
     Pred = less
    
      <
    
    Key
    
      >
    
    , 
    
      class
    
     A = allocator
    
      <
    
    T
    
      >
    
    
      >
    
    
      class
    
     multimap

    
      template
    
    
      <
    
    
      class
    
     Key, 
    
      class
    
     Pred = less
    
      <
    
    Key
    
      >
    
    , 
    
      class
    
     A = allocator
    
      <
    
    Key
    
      >
    
    
      >
    
    
      class
    
     multiset
  

This list looks somewhat daunting but it provides a quick reference for the collections. In most cases you will use the default arguments and your only concern will be what you are storing and how it is stored. T refers to what you will store, and for collections that support a key; Key shows how the elements will be associated.

From previous experience the vector, map and deque classes are the most often used so we can use them as an example for declaring a collection:

Using typedef to declare the collection:

Collapse Copy Code

    
      typedef
    
     vector
    
      <
    
    
      int
    
    
      >
    
     myVector

    
      typedef
    
     map
    
      <
    
    
      string
    
    , 
    
      int
    
    
      >
    
     myMap

    
      typedef
    
     deque
    
      <
    
    
      string
    
    
      >
    
     myQue
  

The first declaration declares a vector of integers, the second declares a collection of integers, which have a key of type string, and the last declares a queue (or stack) of strings.

Another way to declare a collection is to derive a collection from an STL collection as in the following:

Collapse Copy Code

    
      class
    
     myVector : 
    
      public
    
     vector
    
      <
    
    
      int
    
    
      >
    
     {};
  

Either method is useful, it a matter of preference. Another important consideration is declaring the iterators supported by the collection as separate types. If we use the above example we would declare:

Collapse Copy Code

    
      typedef
    
     myVector::iterator vectorIterator

    
      typedef
    
     myVector::reverse_iterator revVectorIterator
  

This gives the user of the collection direct access to the iterator without being forced to use the following syntax:

Collapse Copy Code

    myVector coll;

    
      for
    
     ( myVector::iterator element = coll.begin(); element 
    
      <
    
     coll.end(); element++ )
  

The resolution operator can be cumbersome.

Algorithms

Up to this point we have discussed how to use STL at a bare minimum, now we need to delve into the most important part of the collections. How do we manipulate a collection? For example, if we had list of strings, what would we need to sort the list in alphabetical order, or if we wanted to search a collection for a set of elements that matched a given criterion. This is where STL algorithms are used. In your visual studio installation, under include directory, you will find an include file, algorithm. In algorithm a set of template based functions are declared. These functions can be used to manipulate STL collections. The functions can be categorized in the following: sequence, sorting and numeric. Using these categories, we can list all of the methods of algorithms:

Sequence

count, count_if, find, find_if, adjacent_find, for_each, mismatch, equal, search copy, copy_backward, swap, iter_swap, swap_ranges, fill, fill_n, generate, generate_n, replace, replace_if, transform, remove, remove_if, remove_copy, remove_copy_if, unique, unique_copy, reverse, reverse_copy, rotate, rotate_copy, random_shuffle, partition, stable_partition

Sorting

Sort, stable_sort, partial_sort, partial_sort_copy, nth_element, binary_search, lower_bound, upper_bound, equal_range, merge, inplace_merge, includes, set_union, set_intersection, set_difference, set_symmetric_difference, make_heap, push_heap, pop_heap, sort_heap, min, max, min_element, max_element, lexographical_compare, next_permutation, prev_permutation

Numeric

Accumulate, inner_product, partial_sum, adjacent_difference

Since this is an extensive list, we will only examine a few of the methods in the algorithms. It is very important to note that the methods here are templated so we are not required to use the STL containers to use the methods. For example, we could have a list of ints and to sort this list then we could do:

Collapse Copy Code

    
      #include
    
    
      
        <
      
      
        vector
      
      
        >
      
    
    
      #include
    
    
      
        <
      
      
        algorithm
      
      
        >
      
    
    
      #include
    
    
      
        <
      
      
        iostream
      
      
        >
      
    
         
vector
    
      <
    
    
      int
    
    
      >
    
                  myVec;
vector
    
      <
    
    
      int
    
    
      >
    
    ::iterator    item;
ostream_iterator
    
      <
    
    
      int
    
    
      >
    
        out(cout,
    
      "
    
    
       "
    
    );

    
      //
    
    
       generate array

    
    
      for
    
     ( 
    
      long
    
     i=0; i
    
      <
    
    
      10
    
    ; i++ )
    myVec.push_back(i);

    
      //
    
    
       shuffle the array

    
    random_shuffle( myVec.begin(), myVec.end() );
copy( myVec.begin(), myVec.end(), out );

    
      //
    
    
       sort the array in ascending order

    
    sort( myVec.begin(), myVec.end() );
copy( myVec.begin(), myVec.end(), out );

  

This example shows how declare the vector and then sort it, using STL containers. We could do the same without using containers:

Collapse Copy Code

    ostream_iterator
    
      <
    
    
      int
    
    
      >
    
      out(cout,
    
      "
    
    
       "
    
    );

    
      //
    
    
       generate array (note: one extra element, end in STL is one element past last valid)

    
    
      int
    
     myVec[
    
      11
    
    ];

    
      for
    
     ( 
    
      long
    
     i=0; i
    
      <
    
    
      10
    
    ; i++ )
    myVec[i] = i;

    
      int
    
     * begin = &myVec[
    
      0
    
    ];

    
      int
    
     * end = &myVec[
    
      10
    
    ];

    
      //
    
    
       shuffle the array

    
    random_shuffle( begin, end );
copy( begin, end, out );

    
      //
    
    
       sort the array in ascending order

    
    sort( begin, end );
copy( begin, end, out );
  

How you use the algorithms is largely up to you, but they provide a rich set of methods for manipulating containers.

Multithreading Issues

STL is not thread protected, so you must provide locks on your collections if they will be used in multithreaded environment. The standard locking mechanisms of Mutexes, Semaphores and Critical Sections can be used. One simple mechanism for providing locking is to declare a lock class. In this class the constructor creates the lock, and the destructor destroys the lock. Then provide lock() and unlock() methods. For example:

Collapse Copy Code

    
      class
    
     Lock
{

    
      public
    
    :
	HANDLE    _hMutex;            
    
      //
    
    
       used to lock/unlock object

    
         
	Lock() : _hMutex(NULL)
	{ _hMutex = ::CreateMutex( NULL, 
    
      false
    
    ,NULL) ); }
     
	
    
      virtual
    
     ~Lock() { ::CloseHandle( _hMutex ); }
     
	
    
      bool
    
     lock ()
	{
		
    
      if
    
     ( _hMutex == NULL )
			
    
      return
    
    
      false
    
    ;
		WaitForSingleObject( _hMutex, INFINITE );
		
    
      return
    
    
      true
    
    ;
	}
     
	
    
      void
    
     unlock () { ReleaseMutex(_hMutex);      }
     
};
  

Then declare a class that is derived from one of the STL collections, and in the class override the access methods to the collection that might cause an insertion or deletion of an element. For example a general vector class would be:

Collapse Copy Code

    
      template
    
    
      <
    
    
      class
    
     T
    
      >
    
    
      class
    
     LockVector : vector
    
      <
    
    T
    
      >
    
    , Lock
{

    
      public
    
    :
	LockVector () : vector
    
      <
    
    T
    
      >
    
    (), Lock()
	{}
	
    
      virtual
    
     LockVector ()
	{}
     
	
    
      void
    
     insert ( T & obj )
	{
		
    
      if
    
     ( !lock())
			
    
      return
    
    ;
		vector
    
      <
    
    T
    
      >
    
    ::push_back (obj);
		unlock();
	}
};
  

Conclusion

Hopefully I’ve given you a good tutorial on how to use STL. If not then please try some of the web sites listed below or drop by your local bookstore or amazon.com and purchase one of the many books on the subject. I believe STL can provide many benefits and I hope you will to.

Other STL Web sites

• The Rensselaer STL site by David Musser
• The Renssalaer STL online reference
• The STL tutorial at Technical University Vienna
• Port of the SGI STL to other compilers, by Boris Fomitchev.
• The STL Newbie Guide by Mumit Khan
• A Tiny STL Primer by David Harvey
• A Very Modest STL Tutorial by Jak Kirman
• The Dinkum Standard Template Library Reference by P. J. Plauger.
• Overview of the STL by G. Bowden Wise
• Ian Burrell's STL page
• Cay Horstmann's "Safe STL"
• The STL Resource List by Warren Young
• The Standard Template Library Overview by Rob Kremer
• Alexander Stepanov's Byte Magazine's article
• Dr. Dobb's Journal interview with Alexander Stepanov

Direct Links:

• http://www.cs.brown.edu/people/jak/proglang/cpp/stltut/tut.html
• http://www.cs.brown.edu/people/jak/proglang/cpp/stltut/
• http://www.roy.org/docs/stl

Books about the STL and generic programmng

STL for C++ Programmers, by Leen Ammeraal.
John Wiley, 1996.ISBN 0-471-97181-2.

Designing Components with the C++ STL, by Ulrich Breymann.
Addison Wesley Longman, 1998. ISBN 0-201-17816-8.

STL Tutorial and Reference Guide, by David Musser and Atul Saini.
Addison-Wesley, 1996. ISBN 0-201-63398-1.

C++ Programmer’s Guide to the Standard Template Library, by Mark Nelson.
IDG Books, 1995. ISBN 1-56884-314-3.

License

An Introductory STL tutorial