Course Notes‎ > ‎

Chapter 4 - C++ Standard Libraries




Introduction

In this section we will look at the use of the C++ standard libraries in more detail, including a brief discussion on templates and the use of the Standard Template Library (STL).

What are templates?

C++ templates are functions that can handle different data types without requiring that we write separate code for each of them. To perform a similar operation on several kinds of data types, a programmer need not write different versions by overloading a function. Instead the programmer can write a C++ template based function that will work with all data types.

There are two types of templates in C++, function templates and class templates. First off we will examine function templates.

Function Templates

There are many occasions where we might need to write the same functions for different data types. A simple example can be the addition of two variables, for example, of the intfloat or double types. The function requirement will be to return the summed value with the correct return type that is based on the type of the input variables. If we start writing one function for each of the data types, then we will end up with 4 to 5 different functions, that all contain very similar code. This goes against everything we have learned so far in OOP.

C++ templates are a useful facility in these situations. When we use C++ function templates, only one function "signature" needs to be created. The C++ compiler will automatically generate the required functions for handling the individual data types. This makes programming much easier - Here is an example:

Example: Here is a short example of an add() function. If the requirement is to use this add() function for both int and float types, then two functions are to be created, one for each of the data types (over-loading).

  int add(int a,int b) { return a+b;} // without using function templates
  float add(float a, float b) { return a+b;} // without using function templates

If there were more data types to be handled, more functions would have to be added. Using C++ function templates for this task makes the entire process a lot easier, by reducing the code to a single C++ function template. Here is the function template code for the same add() functions.

 template <class T>  //The class keyword here means any 
                           //standard OR user-defined type
 T add(T a, T b)           //C++ function template example
 {
   return a+b;
 }

Now as before, logically this example is a bit simplistic as the "+" operator does the same thing anyway -- however, it is a good start. C++ function templates can be used wherever the same functionality has to be performed with a number of data types. Though very useful, experience tells us that lots of care should be taken to test the C++ template functions during development. A well written C++ template will go a long way in saving development time.

Templates are different than classes though -- when you instantiate a template the compiler has to see its definition before it can generate its source code. The usual approach is to define the entire template in a header file and then #include it in every source file that uses this template i.e., do not separate the template into a .h and .cpp file. This brings up an (arguably) interesting point, since a class template must be in a header file it means that the source code is always exposed, even if you are selling your product to an untrusted client.

Class Templates

Class templates are often used to build type-safe containers. Class templates allow us to create a class that works with/on any user-defined class (type), so the obvious application is for advanced storage. This functionality is provided by C++ Class templates, also called parameterized types, and the technique is called generic programming. Here is a short example of a made-up class called Storage that provides basic storage of values of a user-defined type:

  // First Template Example
  // by Derek Molloy - Template Example
  
  #include<iostream>
  using namespace std;
  
  template<class T>
  class Storage{
    T values[100]; // can store 100 values of type T (quite basic)
    
    public:
      T& operator [](int index){
        return values[index];
      }
    };
    
    int main(){
      Storage<int>   intArray;
      Storage<float> floatArray;
      
      for (int i=0; i<10; i++){
        intArray[i] = i * i;
        floatArray[i] = (float)i/2.1234 ; 
      }
      
      for (int i=0; i<10; i++){
        cout << " intArray value   = " <<   intArray[i] 
          << " floatArray value = " << floatArray[i] << endl; 
      }
    }

The full source code for this example is listed in ClassTemplates1.cpp

This first example is a little basic, as it is fixed to contain only 100 elements of the user-defined type. We can remove this hard coding, by rewriting the code to:

  // Second Template Example
  // by Derek Molloy - More advanced Template Example.
  
  #include<iostream.h>
  using namespace std;
  
  template<class T, int size>
  class Storage{
    T values[size]; // can store size values of type T
    
    public:
      T& operator [](int index){
        return values[index];
      } 
    };
    
    int main(){
      Storage<int,10> intArray;
      Storage<float,20> floatArray;
      
      for (int i=0; i<10; i++){
        intArray[i] = i * i;
        floatArray[i] = (float)i/2.1234 ; 
      }
      
      for (int i=0; i<10; i++){
        cout << " intArray value = " << intArray[i] 
          << " floatArray value = " << floatArray[i] << endl;
      }
    }

The full source code for this example is listed in ClassTemplates2.cpp

That is not quite everything to do with templates:

  • Inheritance: Class templates can inherit properties from other class templates or even non-templates.

  • Friends: We can use friend functions with templates

  • Static: A class template can have static members, but these static members are shared amongst each specialization of the class template. For example, if you had a class template as above and you used it for int and float, then there would be one static member for the int specialization and one for the float specialization.

STL Introduction

The Standard Template Library (STL) uses C++ templates to implement a standardized 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.

The components of STL can be described and categorised as follows:

  • Containers: Data structures with memory management capability.

  • Iterators: Logic that binds containers and algorithms together.

  • Algorithms: Provide a mechanism for manipulating data through the iterator interface.

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 management 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 re-sized 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

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 implements 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 modifying the state of Fish through compiler checks (".... in read-only structure" error).

Functors etc.

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() algorithm, just like an object! This is a very useful facility in C++. as we can use the same for_each() algorithm for an unlimited number of applications.

Finally, for completeness, we can implement 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>());
  }



These notes are copyright Dr. Derek Molloy, School of Electronic Engineering, Dublin City University, Ireland 2013-present. Please contact him directly before reproducing any of the content in any way.
ċ
ClassTemplates1.cpp
(1k)
Derek Molloy,
26 Oct 2013, 04:11
ċ
ClassTemplates2.cpp
(1k)
Derek Molloy,
26 Oct 2013, 04:11
ċ
for_each_fish.cpp
(1k)
Derek Molloy,
26 Oct 2013, 04:11
ċ
for_each_fish_with_sort.cpp
(1k)
Derek Molloy,
26 Oct 2013, 04:11
Comments