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.
Web Resources
A Very Short Introduction
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 < class InputIterator, class T, class BinaryOperator >
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.
// 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 T > class Vector {
typedef T value_type;
typedef T* iterator; // Vector::iterator is a pointer
...
};
template < class T > 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 < class ContainerX, class ContainerY >
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().
|
