The foundation of the Matrix Template Library is generic programming, which means that the user of MTL should have some familiarity with the concepts associated with generic programming, and especially with the STL. Much of the terminology used in these documents originates from the STL. The following web resources provide a good place to start learning about generic programming and the STL. Below we also give a very short description of generic programming. Generic programming has recently entered the spotlight with the introduction of the Standard Template Library (STL) into the C++ standard[14]. The principal idea behind generic programming is that many algorithms can be abstracted away from the particular data structures on which they operate. Algorithms typically need the functionality of traversing through a data structure and accessing its elements. If data structures provide a standard interface for these operations, generic algorithms can be freely mixed and matched with data structures (called Containers in STL).

The main facilitator in the separation of algorithms and containers in STL is the Iterator (sometimes called a ``generalized pointer''). Iterators provide a mechanism for traversing containers and accessing their elements. The interface between an algorithm and a container is specified by the types of iterators exported by the container. Generic algorithms are written solely in terms of iterators and never rely upon specifics of a particular container. Iterators are classified into broad categories, some of which are: InputIterator, ForwardIterator, and RandomAccessIterator.

The STL defines a set of requirements for each class of iterators. The requirements are in the form of which operations (functions) are defined for each iterator, and what the meaning of the operation is. Take a moment to examine the requirements (Valid Expressions) for RandomAccessIterator or any of the other iterator concepts.

For a concrete example of generic programming we will look at the algorithm accumulate(), which successively applies a binary operator to each element of a container. A typical use of accumulate() would be to sum the elements of a container, using the addition operator. The code below shows how one could implement the accumulate() algorithm in C++. The first and last arguments are iterators that mark the beginning and the end of the container. All of the arguments to the function have template types, so that the algorithm can be used with any container that exports the InputIterator interface. 

  template 
  T accumulate(InputIterator first, InputIterator last,
               T init, BinaryOperator binary_op)
  {
    for (; first != last; ++first)
      init = binary_op(init, *first);
    return init;
  }
The syntax for iterator traversal is the same as for pointers, specifically operator++() increments to the next position. There are several other ways to move iterators (especially random access iterators). To access the container element pointed to by the iterator, one uses the dereference operator*(). One can also use the subscript operator[]() to access at an offset from the iterator. The code below is an example of how one could use the accumulate() template function with a vector and with a linked list (both from the STL). 
  // using accumulate with a vector
  std::vector x(10,1.0);
  double sum1 = accumulate(x.begin(),x.end(),0.0,plus());

  // using accumulate with a linked list
  std::list y;

  // copy vector's values into the list
  std::copy(x.begin(), x.end(), std::back_inserter(y));
  double sum2 = accumulate(y.begin(),y.end(),0.0,plus());
  assert(sum1 == sum2); // they should be equal
Each STL container provides its own iterators that fulfill the standard interface requirements, but that are implemented in terms of the concrete data structure. In C++ this is facilitated by the ability to nest type definitions within classes. Consider the example below of a vector and list class. The Vector class implements its iterator by just using a pointer. The List's iterator is implemented in terms of the node class. Note that in each class, the iterator type has the same name, i.e., iterator. The common naming scheme gives a uniform way to access the iterator types within a container. 
  template  class Vector {
    typedef T value_type;
    typedef T* iterator;      // Vector::iterator is a pointer
    ...
  };
  template  class List {
    typedef T value_type;
    struct node { T data; node* next; };
    class iterator {          // List::iterator is a nested class
      node* curr;
      iterator& operator++() { curr = curr->next; return *this; }
    };
    ...
  };

  template 
  void foo(ContainerX& x, ContainerY& y) {
    typename ContainerX::iterator xi;
    typename ContainerY::iterator yi;
    ...
  }
When dealing with some container class, we can access the correct type of iterator using the double-colon scope operator, as is demonstrated above in the function foo().