Department of Engineering

CUED Talk: C++ and the STL (Standard Template Library)

Contents

• Introduction
• Classes and Templates
• The Standard Template Library
  • Containers and algorithms
  • Iterators
  • Adaptors and Function Objects
• Why strings and vectors are better than arrays
• Examples
  • simple vector use
  • removing spaces in a string
  • stack of integers
  • stack of complex numbers
  • copying vectors
  • boolean vectors
  • sorting and deleting items from vectors
  • transforming all elements of vectors
  • Writing results into an empty vector
  • adding vectors
  • queue
  • miscellaneous
  • set
  • another set
  • look-up table using multimap
• Matters arising from the examples
• More features
• References

Introduction

C++ was designed to support object-orientated programming. It also supports "polymorphism", allowing routines to be written without needing to worry at a high level about the type of the data, thus allowing "generic" programming. This is useful, not least because it is often as easy to write a general (and reusable) solution to a problem as it is to tackle a particular case.

However, this support hasn't always been easy to use. Templates (which were introduced into C++ in 1989) helped. In 1995 the Standard Template Library (STL) was developed, which uses templates to provide users with easy access to powerful generic routines. The STL is now part of the C++ Standard, subsumed within the "Standard Library". With it, programmers can express concepts in a more natural way, and at a higher level of abstraction, without losing the efficiency and power of C. Furthermore, by reducing the need for loops and the "switch" keyword the STL helps make code more sequential, so that it's simpler as well as more powerful.

The STL isn't just some more functions that you can call. It's almost like a sub-language within C++ with its own concepts and approach. Fortunately the design is fairly logical, and it can be mixed with O-O and procedural code.

Classes and Templates

In C, user-defined data types can be aliased/created using "typedef" and "struct". In Pascal, the RECORD mechanism does a similar thing. C++'s class mechanism is an extention of this, providing extra features that allow data plus associated functions to be encapsulated into objects.

C++'s Templates are parameterized types. They support generic programming by obviating the need for explicit switch statements to deal with various data types. Let's look at an example. The following code swaps 2 integers in the usual C++ way

Here the "T" name is arbitrary (like a formal parameter in a function definition). Note that the function is written much as before. When the compiler is now given the following code

it will create a version ("instantiation") of swapping for each type required.

So when you see "< ... >" being used, don't panic - it just means that templates are being used. Note that this generality is achieved without the loss of type-checking - if you tried swapping a string and an integer, the compiler would complain because the 2 items need to be of the same (or very similar) type.

The Standard Template Library

Templates help reduce the amount of code you need to write. Imagine software components as a three-dimensional space. One dimension represents the data types (int, double, char, ...), the second dimension represents the way these types can be collected (array, linked-list, ...) and the third dimension represents the algorithms (sort, merge, search, ...). To deal with all cases in C would require i*j*k routines. Use of templates collapses 1st dimension - the type doesn't matter. The Standard Template Library (STL) reduces the number of routines further, providing algorithms that can operate on various types of collections. Almost every component in the STL is a template.

The STL consists of five main types of components, 3 of which we'll concentrate on first

• Container: an object that is able to keep and administer objects. Several containers are available - list, set, etc - but as far as possible they have the same member function names. For example, size(), empty(), begin(), end() and swap usually work whatever the container
• Algorithm: a computational procedure that is able to work on different containers
• Iterator: abstraction of "pointer" or "index" - a means to access the appropriate element.

Containers and algorithms

The STL includes container classes: classes whose purpose is to contain other objects. There are classes for vectors, lists, etc. Each of these classes is a template, and can be instantiated to contain any type of object. You can, for example, use a vector<int> in much the same way as you would use an ordinary C array of ints.

The payoff comes when you use the large collection of algorithms that manipulate the data stored in containers - reverse, insert, unique, transform etc. Note that these operations act on the elements without explicit use of loops, but you do need to know about iterators.

Iterators

A container can be treated as a single entity, but you sometimes need a way to access individual items. Iterators are generalised pointers. They are needed as arguments to the algorithms mentioned above. For a container "v", v.begin() returns an iterator pointing to the first element and v.end() "points" to one beyond the last, so

would reverse the whole of the above vector. It's possible to iterate through the values in much the way as one would do in C, though iterator definitions can look scary - here's one of the simplest -

A file can have the properties necessary to be treated like a container (it can be treated as a sequence of items of the same type), so perhaps it's not too surprising that the following is another way to print the integer elements of a vector.

(don't worry about trying to understand this - it's introduced now to shorten the examples. A 'for' loop can be used instead to print the values out). If you wanted, you could stop reading at this point and use the ideas so far presented to do sorting, finding, etc in your programs, introducing these new ideas bit by bit until you feel comfortable with them. Even simple uses offer great benefits and you can replace as much (or little) of your old C-style C++ code as you want.

Adaptors and Function Objects

For the sake of completeness I'll mention the other 2 STL component types now. They're used sometimes in the examples but don't worry about them; you can get a long way without them, and you can use them without understanding them.

• Function Object (or Functor): an object of a class that has the function-call operator (operator() ) defined (e.g. "set")
• Adaptor: encapsulates a component to provide another interface (e.g. make a stack out of a list, or make an existing class look like an STL collection)

Why strings and vectors are better than arrays

The previous section became a little technical so let's first take a very simple example to show how the mechanisms described above needn't be visible to the user, and how C programmers can migrate gradually to using these C++ features.

string is easy to use and replaces C's character arrays -

This code does the same as the first fragment does but is less readable and contains a bug - the s array is only big enough to contain 10 characters. So C++'s more recent features are not only easier to use than the old methods, they're safer!

vector is easy to use too, and replaces C's arrays. The advantages of vector include

• They can expand (using the push_back() member function, for example)
• You can stop going off the end of an array - the at member function can throw an exception that you can trap. Try this code
  #include <vector> using namespace std; int main() { vector<int> v(3); v.at(3)=7; }
  When I run it I get

    terminate called after throwing an instance of 'std::out_of_range'
      what():  vector::_M_range_check
    Aborted
  

• A vector knows its own size, which is useful if it's passed to a function

See "Why should I use container classes rather than simple arrays?" if you're not convinced.

Examples

The following examples demonstrate some further features. Some of the details are dealt with in the next section. On linux-based systems, use "g++" to compile them.

1. Simple vector use

   #include <vector> // needed for vector 
   #include <algorithm> // needed for reverse 
   using namespace std; 
   
   int main() { 
      vector<int> v(3); // Declare a vector of 3 ints 
      v[0] = 7; 
      v[1] = v[0] + 3; 
      v[2] = v[0] + v[1]; 
      reverse(v.begin(), v.end()); 
   }
   
   

2. Remove spaces in a string. Note that the remove command doesn't remove elements, it just shunts them to the end of the string, returning a pointer to the first of the moved elements. In this example, that pointer is given to erase, which removes the unwanted elements

   #include <iostream>
   #include <string>
   #include <algorithm>
   using namespace std;
   
   int main() {
     string s="spaces in text";
     cout << s << endl;
     s.erase(remove(s.begin(), s.end(), ' ' ), s.end() ) ;
   
     cout << s << endl;
   }
   

3. Create a stack of integers

   #include <stack>
   #include <iostream>
   using namespace std;
   
   int main() {
     stack<int> S;
     S.push(1);
     S.push(2);
     S.push(3);
     S.pop();
     cout << "Top element is " <<  S.top()  <<endl;
   
     S.pop();
     S.pop();
     cout << "Number of elements is now " << S.size() <<endl;
   }
   

4. Create a stack of complex numbers that have integer components

   #include <stack>
   #include <complex>
   #include <iostream>
   using namespace std;
   
   int main() {
     stack<complex<int> > S; // the space between the '>' signs matters
     complex<int> a(1,2), b(4,7);
     S.push(a);
     S.push(b);
     S.push(a);
     S.pop();
     cout << "Top element is " <<  S.top()  <<endl;
   
     S.pop();
     S.pop();
     cout << "Number of elements is now " << S.size() <<endl;
     
     cout << "Stack empty? (1 means yes) " << S.empty() <<endl;
   }
   

5. Create a vector of integers. Copy it into a list, reversing as you do so, then copy selected items into another vector

   #include <vector>
   #include <list>
   #include <algorithm>
   #include <iostream>
   #include <iterator>
   using namespace std;
   
   int main()
   {
   vector<int> V;
   V.push_back(0);
   V.push_back(1);
   V.push_back(2);
   copy(V.begin(), V.end(), ostream_iterator<int>(cout, " "));
                   // Output: 0 1 2 
   cout <<endl;
   list<int> L(V.size());
   reverse_copy(V.begin(), V.end(), L.begin());
   copy(L.begin(), L.end(), ostream_iterator<int>(cout, " "));
                   // Output: 2 1 0 
   cout <<endl;
   
   vector<int> V2;
   //copy the elements from V that are not <1 into V2
   remove_copy_if(V.begin(), V.end(), back_inserter(V2), 
                  bind2nd(less<int>(), 1));
   copy(V2.begin(), V2.end(), ostream_iterator<int>(cout, " "));
   cout <<endl;
   exit(0);
   }
   

6. Create a Boolean vector of bits. Flip the values

   #include <vector>
   #include <iostream>
   #include <iterator>
   using namespace std;
   
   void print(vector<bool>&v) {
     for (vector<bool> ::iterator it = v.begin(); it != v.end(); it++)
       cout << *it << " ";
     cout << endl;
   }
   
   int main() {
        vector<bool> V;
        V.push_back(0);
        V.push_back(1);
        V.push_back(0);
        print(V);
        V.flip();  // only available for boolean vectors 
        V.insert(V.begin()+1, 5,1); // insert 5 'true' values
        copy (V.begin(),V.end(), ostream_iterator<bool>(cout," "));
        cout << endl;
   }
   
   

7. Create a vector. Use count_if, remove_if and sort on it. This example uses bind2nd, which you'll have to take on trust as a 'trick' that works (more details later)

   #include <vector>
   #include <algorithm>
   #include <functional>
   #include <iostream>
   #include <iterator>
   using namespace std;
   
   int main()
   {
   int sum=0;
   vector<int> V;
   V.push_back(1);
   V.push_back(4);
   V.push_back(2);
   V.push_back(8);
   V.push_back(5);
   V.push_back(7);
   
   copy(V.begin(), V.end(), ostream_iterator<int>(cout, " "));
   
   count_if (V.begin(), V.end(), bind2nd(greater<int>(),5), sum);
   cout << endl << "There are " << sum << " number(s) greater than 5" << endl;
   
   // "remove" all the elements less than 4
   vector<int>::iterator new_end = 
           remove_if(V.begin(), V.end(), bind2nd(less<int>(), 4));
   
   // remove_if doesn't actually remove elements. It moves the unwanted
   // elements to the end and returns an iterator pointing to the first 
   // of these unwanted elements. It works this way because
   // it's a generic routine and it doesn't "know" whether the size of
   // the underlying data structure can be changed.
   // But V.erase "knows" about vectors.
   V.erase(new_end, V.end());
   
   copy(V.begin(), V.end(), ostream_iterator<int>(cout, " "));
   cout << endl << "Elements less than 4 removed" << endl;
   
   sort(V.begin(), V.end());
   copy(V.begin(), V.end(), ostream_iterator<int>(cout, " "));
   cout << endl << "Elements sorted" << endl;
   }
   

8. Create a routine to operate on all the elements of a container using transform.

   #include <vector>
   #include <algorithm>
   #include <iostream>
   #include <iterator>
   using namespace std;
   
   int square(int i) { return i * i; }
   
   int main()
        {
        vector<int> V;
        V.push_back(0);
        V.push_back(1);
        V.push_back(2);
   
        // transform all the elements of V, putting the answers back in V
        transform(V.begin(),V.end(), V.begin(), square);
        copy(V.begin(),V.end(), ostream_iterator<int>(cout, " "));           
        cout <<endl;
   }
   

9. Writing results into an empty vector. In the previous example, the results were put into the V vector, which was big enough to contain all the answers. It's also possible to write the results into a vector that will grow on demand.

   #include <vector>
   #include <algorithm>
   #include <iostream>
   #include <iterator>
   using namespace std;
   
   int square(int i) { return i * i; }
   
   int main()
        {
        vector<int> V,V2;
        V.push_back(0);
        V.push_back(1);
        V.push_back(2);
   
        // transform all the elements of V, putting the answers in V2
        transform(V.begin(),V.end(), back_inserter(V2), square);
        copy(V2.begin(),V2.end(), ostream_iterator<int>(cout, " "));           
        cout <<endl;
   }
   

10. Add vectors using transform and plus

    #include <iostream> 
    #include <vector> 
    #include <algorithm> 
    #include <numeric> 
    #include <iterator>
    using namespace std; 
    
    int main() { 
    vector<int> V1(10), V2(10); 
      fill(V1.begin(), V1.end(), 1);
      partial_sum(V1.begin(), V1.end(),V1.begin() );
      random_shuffle(V1.begin(), V1.end());
      fill(V2.begin(), V2.end(), 2);
      partial_sum(V2.begin(), V2.end(),V2.begin() );
      random_shuffle(V2.begin(), V2.end());
      copy(V1.begin(),V1.end(), ostream_iterator<int>(cout, " ")); 
      cout << endl;
      copy(V2.begin(),V2.end(), ostream_iterator<int>(cout, " ")); 
      // transform all the elements of V1, using all the elements of V2
      // as operands, putting the answers in V2
      transform(V1.begin(), V1.end(), V2.begin(), V2.begin(),
                       plus<int>());
      cout << endl;
      cout << endl;copy(V2.begin(),V2.end(), ostream_iterator<int>(cout, " ")); 
    
      cout <<endl; 
    }
    

11. Create a queue (adapted from Silicon Graphics)

    #include <deque>
    #include <algorithm>
    #include <iostream>
    #include <iterator>
    using namespace std;
    
    int main()
    {
    deque<int> Q; // pronounced "deck" - double-ended queue
    Q.push_back(3);
    Q.push_front(1);
    Q.insert(Q.begin() + 1, 2);
    Q[2] = 0;
    copy(Q.begin(), Q.end(), ostream_iterator<int>(cout, " "));
    // The values that are printed are 1 2 0
    cout <<endl;
    exit(0);
    }
    

12. Miscellaneous - this avoids explicit "for" loops without becoming too unreadable, using 6 algorithms

    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <numeric>
    
    using namespace std;
    
    bool multiple_of_three(int num) {return ! (num%3);}
    void print_remainder(int num) {cout << num%3 << " ";}
    int add1(int num) {return num+1;}
    
    int main()
    {
    // create a vector big enough to hold 10 ints
    vector<int> v(10);
      fill(v.begin(), v.end(), 1);
      partial_sum(v.begin(), v.end(),v.begin() );
      // v now contains 1....10
    
      // Use transform to change values
      transform(v.begin(), v.end(), v.begin(),add1);
    
      // Use for_each if you're not changing values
      cout << "Print remainders when dividing 2...11 by 3" << endl;
      for_each(v.begin(), v.end(), print_remainder);
      cout << endl;
    
      // Random shuffle
      random_shuffle(v.begin(), v.end());
    
      cout << "Remainders again, having shuffled" << endl;
      for_each(v.begin(), v.end(), print_remainder);
      cout << endl;
    
      // Use count_if to count how many elements have a particular property
      cout << count_if(v.begin(), v.end(), multiple_of_three) 
           << " elements are a multiple of 3" << endl;
    }
    

13. Set -

    #include <set>
    #include <iostream>
    #include <iterator>
    using namespace std;
    
    int A[3]= {1, 2, 3};
    
    set<int> setA(A, A+3); 
    
    int main() {
      set<int>::iterator it1=  find(setA.begin(), setA.end(),9);
      if (it1 == setA.end())
        cout << "9 not found\n";
      else
        cout << "9  found\n";
      setA.insert(9);
      cout << setA.size() << " elements in the set" << endl;
      it1=  find(setA.begin(), setA.end(),9);
      if (it1 == setA.end())
        cout << "9 not found\n";
      else
        cout << "9  found\n";
    }
    

14. Another Set - (adapted from Silicon Graphics)

    #include <set>
    #include <algorithm>
    #include <iostream>
    using namespace std;
    
    // define how the items are to be tested for equality
    struct ltstr
    {
      bool operator()(const char* s1, const char* s2) const
      {
        return strcmp(s1, s2) < 0;
      }
    };
    
    int main()
    {
      const int N = 6;
      const char* a[N] = {"isomer", "ephemeral", "prosaic", 
                          "nugatory", "artichoke", "serif"};
      const char* b[N] = {"flat", "this", "artichoke",
                          "frigate", "prosaic", "isomer"};
    
      set<const char*, ltstr> A(a, a + N);
      set<const char*, ltstr> B(b, b + N);
      set<const char*, ltstr> C;
    
      cout << "Set A: ";
      copy(A.begin(), A.end(), ostream_iterator<const char*>(cout, " "));
      cout << endl;
      cout << "Set B: ";
      copy(B.begin(), B.end(), ostream_iterator<const char*>(cout, " "));   
      cout << endl;
    
      cout << "Union: ";
      set_union(A.begin(), A.end(), B.begin(), B.end(),
                ostream_iterator<const char*>(cout, " "),
                ltstr());   
      cout << endl;
      exit(0);
    }
    

15. Multimaps - This example of a look-up table uses some non-trivial C++ to make the main routine simpler.

    #include <string>
    #include <map>
    #include <iostream>
    #include <iterator>
    using namespace std;
    
     typedef multimap <string, string, less<string> > names_type;
    
     // Print out a pair
    // Note: with gcc version 4.0.2 this needs to go onto the std namespace
    namespace std {
     template <class First, class Second>
     ostream& operator<<(ostream& out, 
                         const pair<First,Second>& p)
     {
       cout << p.first << " belongs to the " << p.second << " family";
       return out;
     }
    
     // Print out a multimap
     ostream& operator<<(ostream& out, names_type l)
     {
       copy(l.begin(),l.end(), ostream_iterator
                    <names_type::value_type>(cout,"\n"));
       return out;
     }
    } // End of the namespace std insertion
    
     int main(void)
     {
       // create a multimap of names
       names_type names;
       typedef names_type::value_type value_type;
      
       // Put the names in the multimap
       names.insert(value_type(string("Sue"), string("Smith")));
       names.insert(value_type(string("Jane"), string("Smith")));
       names.insert(value_type(string("Kay"), string("Smith")));
       names.insert(value_type(string("Kurt"), string("Jones")));
       names.insert(value_type(string("Sue"), string("Jones")));
       names.insert(value_type(string("John"), string("Jones")));
       names.insert(value_type(string("Sophie"), string("Mackay")));
       names.insert(value_type(string("Steve"), string("Mackay")));
       names.insert(value_type(string("Sue"), string("Mackay")));
    
       // print out the names
       cout << "All the names" << endl << names << endl;
       // Find the people called Sue
       pair<names_type::iterator,names_type::iterator> p = 
              names.equal_range("Sue");
       // print them out 
       cout << endl << "People called Sue" << endl;
       copy(p.first,p.second,
            ostream_iterator<value_type>(cout,"\n"));
      
       return 0;
     }
    

Matters arising from the examples

The examples gloss over a few details

• Errors - The code might do a lot in a few lines, but if you make a coding mistaking the error codes can reveal all the complexity that C++ tries to hide. On my machine, the following code

  #include <iostream>
  using namespace std;
  int main() {
    cin >> endl;
  }
  

  gives me an error message that's helpful (error: no match for 'operator>>' in 'std::cin >> std::endl') then about 20 lines like the following, which is scary.

  /usr/include/c++/4.1.2/istream:131: note: candidates are: std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(std::basic_istream<_CharT, _Traits>& (*)(std::basic_istream<_CharT, _Traits>&)) [with _CharT = char, _Traits = std::char_traits<char>]
  
  

• Iterators - Note that end() returns an Iterator value that points past the last element of the corresponding container. This value is called the past-the-end value. This value is also returned if a find() can't find a match. NULL isn't used.
• Many of these algorithms can be used with different numbers of parameters. For example, in

        transform(v.begin(), v.end(), v.begin(),add1);
  

  transform takes 4 parameters. The 1st 2 parameters determine the inputs, the 3rd one determines where the results will go. However, it's also possible to supply 5 parameters

        transform(V1.begin(), V1.end(), V2.begin(), V2.begin(), plus<int>());
  

  In this situation the 1st 2 parameters determine the first range of inputs, the 3rd one determines the start of the 2nd range of inputs, and the 4th determines where the results will go. Here the operation needs 2 operands, so 2 vectors of inputs are required.
• Function objects - Because so many functions provided by the standard library take other functions as arguments, the library includes classes that let you build new function objects out of old ones. bind2nd takes as arguments a binary function object and a value to be used as the 2nd argument of the function. So "bind2nd(greater<int> (),3)" is true when an integer is greater than 3. bind1st exists too. For a list of alternatives to greater, see the C++ bind1st and bind2nd page in the local documentation.
• Performance - you may be thinking that all this extra power must come at the expense of speed, but one reason that templates were chosen for the STL is that the resulting code should be fast. Indeed, the templated version of the swap routine introduced at the start might even generate the same code as the hand-crafted version. However, compilers have to be good to generate code that is both small and fast, and some ANSI C++ compilers are rather raw.
  Note that although the generic nature of the algorithms means that you don't have to worry about whether you're using vectors or lists, performance is affected by the choice of container - for example, inserting an item in the middle of a vector is going to be slower than inserting an item into a list. The C++ specification includes performance guarantees for common operations - e.g. the complexity of a list's sort should be O(nlog₂n).

More features

Once you've mastered the programs above, you should be able to use other components of the STL without too much trouble

• More containers - bit_vector, multiset, hash_set, hash_multiset, hash_map, and hash_multimap
• More algorithms - for_each, random_shuffle, partial_sort , partition, etc.
• More types of iterators - ones designed to go backwards though a container, etc.

Because of the generic approach,

• SL algorithms are able to work on user-built containers
• user-built algorithms can work on STL containers

References

• libstdc++ Modules (from GNU)
• STL Programmer's Guide (Silicon Graphics) - a useful reference guide with many examples. Note that the programs have lines like "#include <algo.h>" rather than the more recent "#include <algorithm>".
• C++ Containers Cheat Sheet
• Introduction to the Standard Template Library (Silicon Graphics) - gets deep quickly
• Engineering Department users can find examples of STL (Standard Template Library) programs in /export/Examples/C++/libstdc++/ on the Teaching System.

The newest editions of Stroustrup's "The C++ programming language" (the 3rd edition) and Deitel & Deitel's "C++: how to program" (7th edition) cover the STL as part of the Standard Library, but earlier editions are less complete. Books devoted to the STL library are beginning to appear in bookshops. The one I see mentioned most often is The C++ Standard Library by Josuttis.