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

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.

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.

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.

In the simplest definition, generic programming is a style of computer programming in which algorithms are written in terms of to-be-specified-later types that are then instantiated when needed for specific types provided as parameters.

As a point of historical interest, the versions of C++ that came before templates were part of the language had a "generic.h" that contained preprocessor macros which could be expanded to class declarations. So you could have a generic schema ("template") for a class which you could vary by passing certain parameters into the macros when you expanded them to actual class declarations. However, preprocessor macros are not type safe and a bit clumsy to handle, and their use in C++ code significantly declined due to these reasons; C++ adopted the more versatile templates as elements of the language, but the term "generic" programming lived on. "Generics" are now used in other programming languages as glorified type casts. Other than that, the question has already been expertly answered.

generic programming: pretty much just involves templates.

container: A struct or class, which contains its own data and methods that act on that data.

Iterator: It is a pointer to some memory address that you can iterate through (like an array).

Correct me if wrong on any of the above.

the concept of type parameters, which make it possible to design classes and methods that defer the specification of one or more types until the class or method is declared and instantiated by client code.

Alex Stepanov, pioneer of generic programming and author of the STL, says in From Mathematics to Generic Programming (Stepanov + Rose):

> "Generic programming is an approach to programming that focuses on > designing algorithms and data structures so that they work in the most > general setting without loss of efficiency... > > "What about all that stuff about templates and iterator traits?” Those > are tools that...support generic programming...But generic programming > itself is more of an attitude toward programming than a particular set > of tools... > > "The components of a well-written generic program are easier to use > and modify than those of a program whose data structures, algorithms, > and interfaces hardcode unnecessary assumptions about a specific > application > > "Although the essence of generic programming is abstraction, > abstractions do not spring into existence fully formed. To see how to > make something more general, you need to start with something > concrete. In particular, you need to understand the specifics of a > particular domain to discover the right abstractions." > > "So where does this generic programming attitude come from, and how do > you learn it? It comes from mathematics, and especially from a branch > of mathematics called abstract algebra."

Let's start with a concrete algorithm and abstract away the non-essential details. Let's use linear search as an example. We're looking for an int in the range between the pointers begin (inclusive) and end (exclusive) aka [begin,end):

int* find_int(int* begin, int* end, int target){
  for(; begin != end; ++begin)
    if(*begin == target) break;
  return begin;
}

But the code to find a char or a float would be the same (s/int/float/)

float* find_float(float* begin, float* end, float target){
  for(; begin != end; ++begin)
    if(*begin == target) break;
  return begin;
}

Using templates, we can generalize this:

template<class T>
T* find_array(T* begin, T* end, T target){
  for(; begin != end; ++begin)
    if(*begin == target) break;
  return begin;
}

What if you want to search in a singly linked list? Let's ignore memory management for now and consider a linked list struct like

template<class T>
struct cell {
  T elt;
  cell* next;
};

Then find_list would look like

template<class T>
cell<T>* find_list(cell<T>* lst, T x){
  for(; lst != nullptr; lst = lst->next)
    if(lst->elt == x) break;
  return lst;
}

This looks superficially different, but the core process is the same: single step through the search space until we find x or reach the end. Here, cell<T>* fills the role T* did in find_array, nullptr fills the role end did, lst = lst->next fills the role of ++begin, and lst->elt fills the role of *begin.

Instead of rewriting find for each data structure, look at what guarantees you need for find to work (the abstract guarantees on your input types are called a concept in analogy to an algebraic structure). You need a way to refer to a place in a data structure, called an iterator. For find, our iterator only needs three things:

• we can read the data it points to (operator*)
• we can advance it by a single step (operator++)
• we can check if it reached the end (operator==).

An iterator with these capabilities is called a std::input_iterator.

What about T? We just need to know we can compare by ==. I wrote it to pass by copy, but if we pass by reference instead we can get rid of that:

#include <concepts> // for equality_comparable_with
#include <iterator> // for input_iterator

template<class I, class T>
requires std::input_iterator<I> 
  && std::equality_comparable_with<std::iter_value_t<I>, T>
  // ensures we can compare with == 
I find(I begin, I end, T const& target){
  for(; begin != end; ++begin)
    if(*begin == target) break;
  return begin;
}

This version of find will work on any data structure that exposes input iterators. All the standard library's containers do, usually through methods called begin and end.

If we wanted to do something more complicated, like sorting, we can use stronger guarantees on our iterators, like random access.