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:

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:

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.

Figure 6.1. 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.

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:

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

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>());
  }