What is the meaning of "generic programming" in c++?

Question

What is the meaning of generic programming in c++?

Also, I am trying to figure out what container, iterator, and different types of them mean.

Answer 1

Generic programming means that you are not writing source code that is compiled as-is but that you write "templates" of source codes that the compiler in the process of compilation transforms into source codes. The simplest example for generic programming are container classes like arrays, lists or maps that contain a collection of other objects. But there's much more to generic programming. In the context of C++ (and called meta programming) it means to write programs that are evaluated at compile time.

A basic example of generic programming are templates of containers: In a statically typed language like C++ you would have to declare separate containers that hold integers, floats, and other types or deal with pointers to void and therefore losing all type information. Templates which are the C++ way of generic programming leverage this constraint by letting you define classes where one or more parameters are unspecified at the time you define the class. When you instance the template later you tell the compiler which type it should use to create the class out of the template. Example:

template<typename T> class MyContainer {     // Container that deals with an arbitrary type T };  void main()  {     // Make MyContainer take just ints.     MyContainer<int> intContainer; } 

Templates are generic because the compiler translates the template into actual code. Note that in the case you don't instantiate your template no code will be generated for it at all. On the other hand, if you declare a MyContainer<int>, a MyContainer<float>, and a MyContainer<String> the compiler will create three versions of your code each of them having a different type. There will be some optimizations involved but basically your template code will be instantianted to three new types.

Iterators are a design pattern that were popularized in the seminal book "Design Patterns" by Gamma et al. It's a pattern to iterate over the content of a container class. Unlike using a for-loop an iterator is an instance of a class that points to a member of the container and gives you an unified interface to traverse the container as well as accessing the members. Take look at this example:

// Instanciate template QList with type int QList<int> myList;  // put some ints into myList  // Copyconstruct iterator that points to the // first member of the list. QList<int>::iterator i = myList.begin();  // Iterate through the list  while (i != myList.end()) {   std::cout << *i << std::endl;   i++; } 

In this C++ example I'm instantating a template QList with type int. QList a container class that stores a list of objects. In this example we will use it to store integers.

Then I create an iterator i to traverse through the list. myList.begin() returns an iterator that points to the first element of the list. We can compare the iterator with another iterator myList.end() that points after the last element of the list. If both iterators are the same we know that we have passed the last elment. In the loop we're printing the element by accessing it with *i and go to the next element with i++.

Note that in this example * and ++ are overloaded operators and reimplemented by the iterator class. In a programming language without operator overloading there could be methods like i.element() or i.next() that do the same task. It's important to see that i is not a pointer but a whole class that just mimics the behaviour of a pointer.

What's the benefit of iterators? They provide a unified way to access the members of a container class, completely indepented on how the container class is implemented internally. No matter if your want to traverse a list, map or tree, the iterator classes (should) always work the same way.

Answer 2

Container

In C++, a container is a class that allows you to store objects. For example the standard library std::vector<T> is a resizable array which stores objects of some type T. In order to be formally considered a container class, it must expose certain functionality in order to facilitate generic programming. I could quote the exact requirements from the C++ standard, but for most purposes, the container classes that matter are the ones from the standard library: vector, deque, list, map, set and multimap/multiset.

One of the important requirements is that they must allow iterator access.

Iterator

"Iterator" can mean two things here: It is the name of a design pattern, but in C++ it is also the name of a specific expression of that design pattern. A C++ iterator is a type that allows traversal over a sequence of elements using a pointer-like syntax.

For example, if you have an array int a[10], you can use a plain pointer as an iterator:

int* first = a; // create an iterator that points to the beginning of the array ++first; // make the iterator point to the second element int i = *first; // get the value of the element pointed to by the iterator int* last = a+10; //create an "end" iterator, one which points one past the end of the array 

If I had a linked list, such as std::list<int> l, I could do much the same, although now my iterators are no longer just pointers, but instead a class type implemented to work specifically with std::list:

std::list<int>::iterator first = l.begin(); // create an iterator that points to the beginning of the list ++first; // make the iterator point to the second element int i = *first; // get the value of the element pointed to by the iterator std::list<int>::iterator last = l.end(); //create an "end" iterator, one which points one past the end of the list 

or with a vector std::vector<int> v:

std::vector<int>::iterator first = v.begin(); // create an iterator that points to the beginning of the vector ++first; // make the iterator point to the second element int i = *first; // get the value of the element pointed to by the iterator std::list<int>::iterator last = v.end(); //create an "end" iterator, one which points one past the end of the vector 

The important thing about iterators is that they give us a uniform syntax for traversing sequences of elements, regardless of how the sequence is stored in memory (or even if it is stored in memory. An iterator could be written to iterate over the contents of a database on disk. Or we can use iterator wrappers to make a stream such as std::cin look like a sequence of objects too:

std::istream_iterator<int>(std::cin) first;     ++first; // make the iterator point to the second element     int i = *first; // get the value of the element pointed to by the iterator     std::list<int>::iterator last; //create an "end" iterator, which marks the end of the stream 

although because this wraps a regular stream, it is a more limited type of iterator (you can't move backwards, for example, which means not all of the following algorithms work with stream iterators.

Now, given any of these iterator types, we can use all the standard library algorithms which are designed to work with iterators. For example, to find the first element in the sequence with value 4:

std::find(first, last, 4); // return the first iterator which equals 4 and which is located in the interval [first, last) 

Or we can sort the sequence (doesn't work with stream iterators):

std::sort(first, last); 

or if we write a function which squares an int, such as this:

int square(int i) { return i * i; } 

then we can apply it to the entire sequence:

// for every element in the range [first, last), apply the square function, and output the result into the sequence starting with first std::transform(first, last, first, square); 

That's the advantage of iterators: they abstract away the details of the container, so that we can apply generic operations on any sequence. Thanks to iterators, the same find or sort implementation works with linked lists as well as arrays, or even with your own home-made container classes.

Generic Programming

Generic programming is basically the idea that your code should be as generic as possible. As shown in the iterator examples above, we come up with a common set of functionality that a type must support in order to be called an iterator, and then we write algorithms that work with any iterator type.

Compare this with traditional object-oriented programming, where iterators would have to "prove" that they're iterators by inheriting from some kind of IIterator interface. That would prevent us from using raw pointers as iterators, so we'd lose genericity.

In C++, with generic programming, we don't need the official interface. We just write the algorithms using templates, so they accept any type which just so happens to look like an iterator, regardless of where, when and how they're defined, and whether or not they derive from a common base class or interface.