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
  • 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.

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.

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 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, except that vector eliminates the chore of managing dynamic memory allocation by hand.

The STL also includes a 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 -

Adaptors and Function Objects

• 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 too! Moreover, C++ strings are "near containers", so they behave much like vector. In particular you can use the standard algorithms in the usual way: sort(s.begin(),s.end()); works.

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; }
• 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 element, 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(V.begin(),V.end(), V.begin(), square); copy(V.begin(),V.end(), ostream_iterator<int>(cout, " ")); cout <<endl; }
9. 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(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; }
10. 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); }
11. 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; }
12. 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"; }
13. 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); }
14. 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

• 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.
• 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.
• 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

• 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.

• 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
• The Standard Template Library Tutorial (Johannes Weidl) - a long and detailed guide, including an example of How to create a generic algorithm
• Engineering Department users can find examples of STL (Standard Template Library) programs in /export/Examples/C++/libstdc++/ on the Teaching System.