Practical Guide to STL By Jeff Bogan

Introduction

STL (Standard Template Library) is a good skill for anyone programming C++ in the modern day. I must say that it takes some getting used to, i.e. there is a fairly steep learning curve, and some of the names that are used are not very intuitive (perhaps because all of the good names had been used up). The upside is once learned they will save you headaches down the road. Compared to MFC containers, they are more flexible and powerful.

Listed advantages:

• Can sort and search easily
• They are safer and easier to debug
• You can understand code written by the UNIX crowd.
• It is another acronym to add to your resume

Background

This guide has been written so that the reader can get a running start at this challenging part of computer science, without having to wade through the endless mass of jargon and stifling exactitude that STL'er have created for their own amusement.

Using the Code

The code here is mainly instructive on the practical ways to use STL.

Definitions

• Template - A macro for classes (and structures and data types and functions). Sometimes called a cookie cutter. Also formally known as generic - a template of a class is called a generic class. A template of a function is called, wait for it, a generic function.
• STL - Standard Template Library, templates written by a bunch of smart people, now used by everyone part of the C++ standard language.
• Container - A class that holds data. STL examples are vectors, sets, maps, multimaps, and deques.
• Vector - Your basic array template. It is a container.
• Iterator - A fancy word for a pointer to an element inside an STL container. It does other stuff too.

Hello World Program

I always wanted to write one and here is my golden 24 karet opportunity: a hello world program. This transfers a char string into a vector of characters and then displays the string one character at a time. A vector is your basic garden variety array-like template. Probably, about half of all STL containers are vectors, so if you grasp this program, you are half way to a complete understanding of STL.

Collapse Copy Code

// Program: Vector Demo 1
// Purpose: To demonstrate STL vectors

// #include "stdafx.h" - include if you use pre compiled headers
#include 
 
    // STL vector header. There is no ".h"
#include 
  
  
     // for cout
using namespace std;  // Ensure that the namespace is set to std

char* szHW = "Hello World";  
// This is - as we all know - a character array, 
// terminated with a null character

int main(int argc, char* argv[])
{
  vector 
   
   
     vec;  // A vector (STL array) of characters

  // Define an iterator for a vector of characters - this is always 
  // scoped to within the template
  vector 
    
    
     ::iterator vi;

  // Initialize the character vector, loop through the string, 
  // placing the data in the vector character by character until 
  // the terminating NULL is reached
  char* cptr = szHW;  // Start a pointer on the Hello World string
  while (*cptr != '/0')
  {  vec.push_back(*cptr);  cptr++;  }
  // push_back places the data on the back of the vector 
  // (otherwise known as the end of the vector)

  // Print each character now stored in the STL array to the console
  for (vi=vec.begin(); vi!=vec.end(); vi++)  
  // This is your standard STL for loop - usually "!=" 
  // is used in stead of "


     
     
push_back is the standard function for putting data into a vector or deque. insert is a similar function and does much the same, and works with all containers, but is more complicated. The end() is actually the end plus one, to allow the loop to operate properly - it actually points to the point just beyond the limits of the data. Just like in a regular loop in which you say for (i=0; i - ar[6] does not exist, but it is never reached in the loop so it does not matter.


     
     
STL Annoyance #1:


     
     
One of the first annoyances of STL makes itself known. To initialize it with data is more difficult than is the case in C/C++ arrays. You basically must do it element by element, or first initialize an array and then transfer it. People are working on this I understand.


     
     
 Collapse Copy Code


     
     
// Program: Initialization Demo
// Purpose: To demonstrate initialization of STL vectors

#include 
      
         // same as 
       
       
        
#include 
        
        
         
using namespace std;

int ar[10] = {  12, 45, 234, 64, 12, 35, 63, 23, 12, 55  };
char* str = "Hello World";

int main(int argc, char* argv[])
{
  vector 
         
         
           vec1(ar, ar+10);
  vector 
          
          
            vec2(str, str+strlen(str));
  return 0;
}
          
          
         
         
        
        
       
       
      
      


     
     
In programming, there are many ways of doing the same task. Another way to fill a vector is to use the more familiar square brackets, like so:


     
     
 Collapse Copy Code


     
     
// Program: Vector Demo 2
// Purpose: To demonstrate STL vectors with
// counters and square brackets

#include 
      
       
#include 
       
       
        
#include 
        
        
         
using namespace std;

char* szHW = "Hello World";
int main(int argc, char* argv[])
{
  vector 
         
         
           vec(strlen(sHW)); 
  // The argument initializes the memory footprint
  int i, k = 0;
  char* cptr = szHW;
  while (*cptr != '/0')
  {  vec[k] = *cptr;  cptr++;  k++;  }
  for (i=0; i
          
          
           
           
This example is cleaner, but allows you less control of the iterator, and has an extra integer counter, and you must explicitly set the memory footprint.


           
           
Namespaces


           
           
Hand in hand with STL is the concept of Namespaces. STL is defined within the std namespace. There are 3 ways to specify it:


           
           
 
            
USE that namespace, near the top of all files, but below headers. 
 Collapse Copy Code
 
using namespace std;
 
This is the simplest and best for simple projects, limits you to the std namespace, anything you add is improperly put in the std namespace (I think you go to heck for doing this).
 
            
Specify each and every template before use (like prototyping) 
 Collapse Copy Code
 
using std::cout;
using std::endl;
using std::flush;
using std::set;
using std::inserter;
 
This is slightly more tedious, although a good mnemonic for the functions that will be used, and you can interlace other namespaces easily.
 
            
EVERY time you use a template from the std namespace, use the std scope specifier. 
 Collapse Copy Code
 
typedef std::vector<:string> VEC_STR;
              
 
This is tedious but the best way if you are mixing and matching lots of namespaces. Some STL zealots will always use this and call anyone evil who does not. Some people will create macros to simplify matters.
 
           

           
           
In addition, you can put using namespace std within any scope, for example, at the top of a function or within a control loop.


           
           
Some Tips


           
           
To avoid an annoying error code in debug mode, use the following compiler pragma:


           
           
 Collapse Copy Code


           
           
#pragma warning(disable: 4786)


           
           
Another gotcha is: you must make sure that the spaces are placed between your angle brackets and the name. This is because >> is the bit shift operator, so:


           
           
 Collapse Copy Code


           
           
vector 
            
             > veclis;
            
            


           
           
will give an error. Instead, write it:


           
           
 Collapse Copy Code


           
           
vector 
            
              > veclis;
            
            


           
           
to avoid compilation errors.


           
           
Another Container - The set


           
           
This is the explanation lifted from the MS help file of the set: "The template class describes an object that controls a varying-length sequence of elements of type const Key. Each element serves as both a sort key and a value. The sequence is represented in a way that permits lookup, insertion, and removal of an arbitrary element with a number of operations proportional to the logarithm of the number of elements in the sequence (logarithmic time). Moreover, inserting an element invalidates no iterators, and removing an element invalidates only those iterators that point at the removed element."


           
           
An alternate, more practical, definition is: A set is a container that contains all unique values. This is useful for cases in which you are required to collect the occurrence of value. It is sorted in an order that is specified at the instantiation of the set. If you need to store data with a key/value pair, then a map is a better choice. A set is organized as a linked list, is faster than a vector on insertion and removal, but slightly slower on search and addition to end.


           
           
An example program would be:


           
           
 Collapse Copy Code


           
           
// Program: Set Demo
// Purpose: To demonstrate STL sets

#include 
            
             
#include 
             
             
              
#include 
              
              
               
using namespace std;

int main(int argc, char* argv[])
{
  set 
               
               
                 strset;
  set 
                
                
                 ::iterator si;
  strset.insert("cantaloupes");
  strset.insert("apple");
  strset.insert("orange");
  strset.insert("banana");
  strset.insert("grapes");
  strset.insert("grapes");  
   // This one overwrites the previous occurrence
  for (si=strset.begin(); si!=strset.end(); si++)  
  {  cout 


                 
                 
If you want to become an STL fanatic, you can also replace the output loop in the program with the following lines.


                 
                 
 Collapse Copy Code


                 
                 
copy(strset.begin(), strset.end(), ostream_iterator
                  
                   (cout, " "));
                  
                  


                 
                 
While instructive, I find this personally less clear and prone to error. If you see it, now you know what it does.


                 
                 
All the STL Containers


                 
                 
Containers pre-date templates and are computer science concepts that have been incorporated into STL. The following are the seven containers implemented in STL.


                 
                 
 
                  
vector - Your standard safe array. It is expanded in the "front" direction only.
 
                  
deque - Functionally the same as a vector. Internally, it is different. It can be expanded in both the front and back.
 
                  
list - Can only be traversed one step at time. If you are already familiar with the concept of a list, an STL list is doubly linked (contains pointer to both the previous and next value).
 
                  
set - contains unique values that are sorted.
 
                  
map - sorted set of paired values, one of which is the key on which sorts and searches occur, and the value which is retrieved from the container. E.g. instead of ar[43] = "overripe", a map lets you do this ar["banana"] = "overripe". So if you wanted to draw up a bit of information keyed on full name is easily done.
 
                  
multiset - same as a set, but does not necessarily have unique values.
 
                  
multimap - same as a map, but does not necessarily have unique keys.
 
                 

                 
                 
Note: If you are reading the MFC help then you will also come across the efficiency statement of each container. I.E. (log n * n) insertion time. Unless you are dealing with very large number of values, you should ignore this. If you start to get a noticeable lag or are dealing with time critical stuff then you should learn more about the proper efficiency of various containers.


                 
                 
How to Use a Map with some Class


                 
                 
The map is a template that uses a key to obtain a value.


                 
                 
Another issue is that you will want to use your own classes instead of data types, like int that has been used up to now. To create a class that is "template-ready", you must be ensure that the class contains certain member functions and operators. The basics are:


                 
                 
 
                  
default constructor (empty, usually)
 
                  
copy constructor
 
                  
overload "="
 
                 

                 
                 
You would overload more operators as required in a specific template, for example, if you plan to have a class that is a key in a map you would have to overload relational operators. But that is another story.


                 
                 
 Collapse Copy Code


                 
                 
// Program: Map Own Class
// Purpose: To demonstrate a map of classes

#include 
                  
                   
#include 
                   
                   
                    
#include 
                    
                    
                     
#include