In the generic programming/TMP world what exactly is a model / a policy and a "concept" ?

Question

I'd like to know the precise yet succinct definitions of these three concepts in one place. The quality of the answer should depend on the following two points.

1. Show a simple code snippet to show how and what the concept/technique is used for.
2. Be simple enough to understand so that a programmer without any exposure to this area can grasp it.

Note:

There are probably many correct answers since each concept has many different facets. If there are a lot of good answers I will eventually turn the question into CW and aggregate the answers.

-- Post Accept Edit --

Boost has a nice article on generic programming concepts

Answer 1

A concept is a set of requirements that a type must satisfy in order to model the concept.

For example, a type T is LessThanComparable if for a pair of objects a and b of type T the expression a < b is well-formed, convertible to bool and induces a strict weak ordering relation. The type int is an example of a model of LessThanComparable.

Concepts can form refinement hierarchies. Concept A is a refinement of concept B if the requirements of A are a superset of the requirements of B. For example, BidirectionalIterator is a refinement of ForwardIterator.

Concepts are used to restrict the set of types a template can be specialized with. For example, the std::sort algorithm can accept a pair of objects as long as they model RandomAccessIterator.

std::vector<int> vec;
std::list<int> list;

// OK, std::vector<int>::iterator is a model of `RandomAccessIterator`.
std::sort(vec.begin(), vec.end());

// error, std::list<int>::iterator is only a model of `BidirectionalIterator`.
std::sort(list.begin(), list.end());

Note that concepts are informal objects used in the C++ standard and various other documents. The language does not support concepts directly (yet).

Answer 2

A.o. the SGI documentation refers to 'model' as to what was introduced as 'concepts' in a C++0x proposal: it's the compile-time equivalent to what an 'interface' is in OO modelling. It summarizes the requirements generic code poses on a template parameter.

As an example you can say that the OutputIterator parameters of the std::transform function should implement operator++() and operator=( T ) in order for the function to work.

The policy is another thing: it makes an algorithm changeable from the outside. A nice example is the less used Allocator parameter of the stl containers: it tells the algorithm how to allocate memory. If one wants to, one can make a std::vector<int, AllocateOnCloud>, where the whole of the vector functions would allocate memory in the cloud instead of on the heap. (I'm not apt to implement this allocator, mind).

Answer 3

A concept is a set of requirements on a type. For example, you could have a concept called "RandomAccessible", which places the requirement on a type that it implements operator[](int) in O(1) time.

As concepts were dropped from the upcoming C++ standard, they only exist intangibly in C++ as documentation. As an example, you could read SGI's description of the Container concept.

When a type meets all the requirements of a concept, you call it a model of that concept. For example, std::vector is a model of the Container concept (or, equivalently, std::vector "models" Container).

Finally, a policy is a unit of behaviour, which can be combined with other units of behaviour to build complex classes. For example, say you wanted to build two classes: a fixed-size array, and a dynamically-resizable array. Both these classes have a lot of shared functionality, but just differ in their storage mechanisms, and some of their functionality (e.g. you can't call push_back on a fixed-size array).

template <class T, class StoragePolicy>
class array : public StoragePolicy
{
public:
  T& operator[](int i) { return data[i]; }
};

template <class T, int N>
class fixed_storage
{
  T data[N];
};

template <class T>
class dynamic_storage
{
  T* data;

public:
  void push_back(const T& value) 
  {
    // Code for dynamic array insertion
  }
};

Usage would be as follows:

int main()
{
  array<int, fixed_storage<int, 10> > fixed_array;
  array<int, dynamic_storage<int> > dynamic_array;

  dynamic_array.push_back(1);
  fixed_array[9] = dynamic_array[0];
}

Obviously this is a very crude and incomplete example, but I hope it illuminates the concept behind a policy.

Note that in the example, we could say that fixed_storage and dynamic_storage are "models" of the StoragePolicy concept. Of course, we would need to formally define exactly what the StoragePolicy concepts requires of its models. In this case, it would simply be to define an indexable data member variable.