Generic Programming in C++ : A conceptual overview

A computer deals with 3 things:

a) Data

b) Algorithm

c) Container

Let us consider a simple function to search an element in an array.

Observation

The search function above works only for an integer array. However the functionality search, is logically separate from array and applicable to all data types, i.e. searching a char in a char array or searching some integer in a linked list.

Hence, data, algorithms and containers are logically separate but very tightly coupled to each other.

Generic Programming enables us, the programmer, to achieve this logical separation by writing general algorithms that work on all containers with all data types.

Seperating data

A function can be made general to all data types with the help of templates.

Templates are a blueprint based on which compiler generates a function as per the requirements.

To create a template of search function, we replace int with a type T and tells compiler that T is a type using the statement template <class T>

Now the search function runs for all types of arrays for which statement 4 is defined.

1 int arrInt[100];
2 char arrChar[100];
3 float arrFloat[100];
4 Book arrBook[100], X;           //X is a book
5 search(arrInt, 100, 5);         //T is replaced by int
6 search(arrChar, 100, ‘A’);      //T is replaced by char
7 search(arrFloat, 100, 1.24);    //T is replaced by float
8 search(arrBook, 100, X);        //T is replaced by Book. 
// But does line 8 actually work??? Keep reading!

So, one function can be run on different data types. This makes our function general for all types of data.

Note:

In the actual code that is produced after compilation, 4 different functions will be produced based on the template with T replaced accordingly.

You could use <typename T> or <class T> in the template statement 1. The keywords typename and class serve the same purpose.

Separating Algorithm

The search function will not work for Book objects if computer doesn’t know how to compare 2 books. So our function is limited in some sense. To work it for all data types, we use a concept of compartors (also see predicate).

Let’s rewrite the templated search function again

To use the search function for integers, you shall now write:

Line 4 works since obj(xInt, yInt) is defined by the class compareInt.

To use search function for a book class, we should write a compareBook class.

The same search function now operates for Book just by writing a small compare class.

However, search function works only for arrays. That’s still a problem. Nevertheless, the functionality of searching extends to list equally. To make it general for all containers(here array) we introduce a concept of iterators in our discussion.

Separating Containers

Iterators

Visualise iterators as an entity using which you can access the data within a container with certain restrictions.

These are classified into 5 categories.

Input Iterator : An entity through which you can read from container and move ahead.

What sort of container will posses an input iterator???

A keyboard.

Output Iterator : An entity through which you can write into the container and move ahead.

A container like printer or monitor will posses such an iterator.

Forward Iterator : Iterator with functionalities of both Input and Output iterator.

A singly linked list will posses a forward entity since we can read/write only in the forward direction.

Bidirectional Iterator : Forward iterator that can move in both the directions.

A doubly linked list will posses a bidirectional iterator.

Random Access Iterator: Iterator that can read/write in both directions plus can also take jumps.

An array will have random access iterator. Since, you can jump by writing arr[5], which means jump to the 6th element.

Entity that does this, behaves like a pointer in some sense.

To write search function that is truly independent of data and the underlying container, we use iterator.

Here, beginOfContainer is a ForwardIterator, i.e., beginOfContainermust know how to read/write and move in forward direction.

So, if a container has atleast ForwardIterator, the algorithm works. Hence, it works for list, doubly linked list and array as well thus achieving generality over container.

//search for book in an array
search(arr, arr + n, X, compareBook);
//search for book in a list
list<Book> lb;  // see list
search(lb.begin(), lb.end(), X, compareBook);
//begin and end are member function of the class list.

Summary:

a) Using templates, we achieve freedom from data types

b) Using comparators, we achieve freedom from operation(s) acting on data

c) Using iterators, we achieve freedom from underlying data structure (container)

In case of any discussion, just leave a comment.