14.5 Generic Programming

Ru-Brd

Static polymorphism leads to the concept of generic programming . However, there is no one universally agreed-on definition of generic programming (just as there is no one agreed-on definition of object-oriented programming ). According to [ CzarneckiEiseneckerGenProg ], definitions go from programming with generic parameters to finding the most abstract representation of efficient algorithms . The book summarizes:

Generic programming is a subdiscipline of computer science that deals with finding abstract representations of efficient algorithms, data structures, and other software concepts, and with their systematic organization . Generic programming focuses on representing families of domain concepts. (pages 169 and 170)

In the context of C++, generic programming is sometimes defined as programming with templates (whereas object-oriented programming is thought of as programming with virtual functions ). In this sense, just about any use of C++ templates could be thought of as an instance of generic programming. However, practitioners often think of generic programming as having an additional essential ingredient: Templates have to be designed in a framework for the purpose of enabling a multitude of useful combinations.

By far the most significant contribution in this area is the STL (the Standard Template Library , which later was adapted and incorporated into the C++ standard library). The STL is a framework that provides a number of useful operations, called algorithms , for a number of linear data structures for collections of objects, called containers . Both algorithms and containers are templates. However, the key is that the algorithms are not member functions of the containers. Instead, the algorithms are written in a generic way so that they can be used by any container (and linear collection of elements). To do this, the designers of STL identified an abstract concept of iterators that can be provided for any kind of linear collection. Essentially, the collection-specific aspects of container operations have been factored out into the iterators' functionality.

As a consequence, implementing an operation such as computing the maximum value in a sequence can be done without knowing the details of how values are stored in that sequence:

 template <class Iterator>  Iterator max_element (Iterator beg,  // refers to start of collection  Iterator end)  // refers to end of collection  {  // use only certain  Iterator  's operations to traverse all elements   // of the collection to find the element with the maximum value   // and return its position as  Iterator   } 

Instead of providing all useful operations such as max_element() by every linear container, the container has to provide only an iterator type to traverse the sequence of values it contains and member functions to create such iterators:

 namespace std {      template <class T,   >      class vector {        public:          typedef   const_iterator;  // implementation-specific iterator   // type for constant  vector  s  const_iterator begin() const;  // iterator for start of collection  const_iterator end() const;  // iterator for end of collection    };      template <class T,  ...  >      class list {        public:          typedef   const_iterator;  // implementation-specific iterator   // type for constant  list  s  const_iterator begin() const;  // iterator for start of collection  const_iterator end() const;  // iterator for end of collection    };  } 

Now, you can find the maximum of any collection by calling the generic max_element() operation with the beginning and end of the collection as arguments (special handling of empty collections is omitted):

  // poly/printmax.cpp  #include <vector>  #include <list>  #include <algorithm>  #include <iostream>  #include "MyClass.hpp"  template <typename T>  void print_max (T const& coll)  {  // declare local iterator of collection  typename T::const_iterator pos;  // compute position of maximum value  pos = std::max_element(coll.begin(),coll.end());  // print value of maximum element of  coll  (if any):  if (pos != coll.end()) {          std::cout << *pos << std::endl;      }      else {          std::cout << "empty" << std::endl;      }  }  int main()  {      std::vector<MyClass> c1;      std::list<MyClass> c2;   print_max (c1);      print_max (c2);  } 

By parameterizing its operations in terms of these iterators, the STL avoids an explosion in the number of operation definitions. Instead of implementing each operation for every container, you implement the algorithm once so that it can be used for every container. The generic glue is the iterators that are provided by the containers and that are used by the algorithms. This works because iterators have a certain interface that is provided by the containers and used by the algorithms. This interface is usually called a concept , which denotes a set of constraints that a template has to fulfill to fit into this framework.

In principle, functionally such as an STL-like approach could be implemented with dynamic polymorphism. In practice, however, it would be of limited use because the iterator concept is too lightweight compared with the virtual function call mechanism. Adding an interface layer based on virtual functions would most likely slow down our operations by an order of magnitude (or more).

Generic programming is practical exactly because it relies on static polymorphism, which resolves interfaces at compile time. On the other hand, the requirement that the interfaces be resolved at compile time also calls for new design principles that are different in many ways from object-oriented design principles. Many of the most important of these generic design principles are described in the remainder of this book.

Ru-Brd