STL Introduction

This library of components uses C++ templates to implement a standardised extensible and reusable code base for the development of complex software applications. STL aims to encourage the programmer to build code that is solid, robust and reusable. STL is extensible, allowing the programmer to add their own containers and algorithms. All C++ library entities are declared or defined in one or more standard headers. To make use of a library entity in a program, write an include directive that names the relevant standard header, out of the 50 available.

As discussed before you can include the contents of a standard header by naming it in an include directive. For example:

	#include <iostream>   // include I/O facilities

All names other than operator delete and operator new in the C++ library headers are defined in the std namespace, or in a namespace nested within the std namespace. You refer to the name cin, for example, as std::cin. Alternatively, you can write the declaration:

	using namespace std;

which brings all library names into the current namespace. If you write this declaration immediately after all include directives, you hoist the names into the global namespace. Unless specifically indicated otherwise, you may not define names in the std namespace, or in a namespace nested within the std namespace.

STL can be described and categorised as follows:

STL Containers

In previous exercises we have examined the use of an array for the storage of objects. The array discussed is a container, but one that lacks advanced memory management capabilities. For example, if we had an array of 10 elements and the middle one needed to be removed, how would the array be altered to fill this gap, remember this gap, remove this gap? How could we extend it if we needed to add 12 elements? Well, more than likely, the programmer would have to write the logic for these memory management routines.

Containers are data structures that contain memory managment capabilities. There are two categories of containers, sequential containers and associative containers. Some examples of sequential containers are:

  • vector: A flexible array of elements.

  • deque: A dynamic array that can grow at both ends.

  • list: A doubly linked list.

STL vectors are a good solution to the array problem just discussed. They are as easy to declare as an array and are automatically dynamically resized during program execution.

Associative containers associate a value with a name and some examples are:

  • map: A collection of name-value pairs, sorted by the keys value.

  • set: A collection of elements sorted by their own value.

  • multimap: Same as a map, only duplicates are permitted.

  • multiset: Same as a set, only duplicates are permitted.

STL Iterators

The container "contains" the elements together, and the iterator provides a mechanism for traversing the different types of those containers. Even though each container may have a completely different data structure, the iterator can provide the level of abstraction necessary to build a generic interface to traverse any type of container.

  • Input iterators

  • Output iterators

  • Forward iterators

  • Bidirectional iterators

  • Random iterators

Figure 6.1. STL Iterator Categories

STL Iterator Categories

Iterators are abstract, requiring a class that implements the methods for use as the iterator. Input and Output iterators are the simplest form of iterators (being simple iterator interfaces to the iostream classes, with the random access iterator being the most complex, and by definition, it has implemented the other iterator categories.

STL Algorithms

Algorithms provide a means of accessing and manipulating the data in containers using the iterator interface. The algorithms even implement a for_each loop.

The algorithms can be classified as:

  • Non-modifying algorithms: e.g. for_each, count, search ...

  • Modifying algorithms: for_each, copy, transform ...

  • Removing algorithms: remove, remove_if, ...

  • Mutating algorithms: reverse, rotate, ...

  • Sorting algorithms: sort, partial_sort, ...

  • Sorted range algorithms: binary_search, merge ...

  • Numeric algorithms: accumulate, partial_sum ...

A for_each example

The for_each loop condenses the for loop into a single line. This single line iterates through the vector and executes a function at every element within the vector. The function outputFunction receives the element type the vector was specialized with at compile time. The function can do anything, but in this case, it simply prints to the standard output.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
 
// declare a simple function that outputs an int
void outputFunction(int x)
{       
	cout << x << endl;
}
 
int main(void)
{
      int x;                                                                               
      vector<int> vect;  // declare a vector container of ints
                                                              
      cout << "Please enter a list of numbers:" << endl;      
      while(cin >> x)                 
      {
      	vect.push_back(x); 
      }
            
      sort(vect.begin(), vect.end());   // sort the array                             
      
      cout << endl << "Sorted output of numbers:" << endl;
             
      // loop through vector with for_each loop and execute 
      // outputFunction() for each element       
      
      for_each(vect.begin(), vect.end(), outputFunction);
}

This can be applied to an object of our own type - an example is listed in for_each_fish.cpp. This is a basic example of the use of vectors with your own type. If you wish to use STL algorithms then your type must provide certain additional functionality to allow you to define the behaviour of your type with certain operations, in particular '<' and '=='. an example is given in for_each_fish_with_sort.cpp that demonstrates the use of the required overloaded operators. Note that the const after a method declaration states that this method can be called on a constant object, as it bans the method from modifiying the state of Fish through compiler checks (".... in read-only structure" error).

Functors etc.

You may have heard of these things called functors in C++. So what is a functor, or function object? Essentially, it is a class declared with the () operator overloaded. First, we declare a class. Next, we overload the () operator with as many parameters as we want, and then we simply instantiate it. Why would we do something so complicated? Bjarne Stroustrup, the creator of C++, says that, "Function objects often execute faster." Since C++ was developed with robustness and efficiency in mind, the creators of STL felt that the use of functors would be an ideal way to maintain the performance for the algorithms implemented.

Implementing the previous example using functors:

  #include <iostream>
  #include <vector>
  #include <algorithm>
  using namespace std;
  
  // declare a function object using a struct
  struct func
  {
    void operator()(int x)      
    {              
      cout << x << endl;       
    }
  };
  
  int main(void)
  {
    int x;                                                                              
    vector<int> vect;  // declare a vector container of ints
    
    cout << "Please enter a list of numbers:" << endl;     
    while(cin >> x)                 
    {
      vect.push_back(x); 
    }
    sort(vect.begin(), vect.end());   // sort the array                             
    
    cout << endl << "Sorted output of numbers:" << endl;
	
	// loop through vector with for_each loop and execute the function 
	//  object for each element      
	for_each(vect.begin(), vect.end(), func());
  }

So in this example the function object funct() was passed to the for_each() just like an object! This is a very useful facility in C++ as we can use the same for_each() method for an unlimited number of applications.

Implementing the previous example using functors and templates:

  #include <iostream>
  #include <vector>
  #include <algorithm>
  using namespace std;
  
  // declare a function object using a template
  template<class T> class func
  {
    public:       
      void operator()(T x)      
      {
        cout << x << endl;      
      }
  };

  int main(void)
  {
    int x;                                                                               
    vector<int> vect;  // declare a vector container of ints
    
    cout << "Please enter a list of numbers:" << endl;      
    while(cin >> x)                 
    {
      vect.push_back(x); 
    }
	            
    sort(vect.begin(), vect.end());   // sort the array                             
	      
    cout << endl << "Sorted output of numbers:" << endl;
	       
    // loop through vector with for_each loop and execute the function 
    // object for each element        
		  
    for_each(vect.begin(), vect.end(), func<int>());
  }