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

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.