What is the difference between a trait and a policy?

Policies

Policies are classes (or class templates) to inject behavior into a parent class, typically through inheritance. Through decomposing a parent interface into orthogonal (independent) dimensions, policy classes form the building blocks of more complex interfaces. An often seen pattern is to supply policies as user-definable template (or template-template) parameters with a library-supplied default. An example from the Standard Library are the Allocators, which are policy template parameters of all STL containers

template<class T, class Allocator = std::allocator<T>> class vector;

Here, the Allocator template parameter (which itself is also a class template!) injects the memory allocation and deallocation policy into the parent class std::vector. If the user does not supply an allocator, the default std::allocator<T> is used.

As is typical in template-based polymporphism, the interface requirements on policy classes are implicit and semantic (based on valid expressions) rather than explicit and syntactic (based on the definition of virtual member functions).

Note that the more recent unordered associative containers, have more than one policy. In addition to the usual Allocator template parameter, they also take a Hash policy that defaults to std::hash<Key> function object. This allows users of unordered containers to configure them along multiple orthogonal dimensions (memory allocation and hashing).

Traits

Traits are class templates to extract properties from a generic type. There are two kind of traits: single-valued traits and multiple-valued traits. Examples of single-valued traits are the ones from the header <type_traits>

template< class T >
struct is_integral
{
    static const bool value /* = true if T is integral, false otherwise */;
    typedef std::integral_constant<bool, value> type;
};

Single-valued traits are often used in template-metaprogramming and SFINAE tricks to overload a function template based on a type condition.

Examples of multi-valued traits are the iterator_traits and allocator_traits from the headers <iterator> and <memory>, respectively. Since traits are class templates, they can be specialized. Below an example of the specialization of iterator_traits for T*

template<T>
struct iterator_traits<T*>
{
    using difference_type   = std::ptrdiff_t;
    using value_type        = T;
    using pointer           = T*;
    using reference         = T&;
    using iterator_category = std::random_access_iterator_tag;
};

The expression std::iterator_traits<T>::value_type makes it possible to make generic code for full-fledged iterator classes usable even for raw pointers (since raw pointers don't have a member value_type).

Interaction between policies and traits

When writing your own generic libraries, it is important to think about ways users can specialize your own class templates. One has to be careful, however, not to let users fall victim to the One Definition Rule by using specializations of traits to inject rather than to extract behavior. To paraphrase this old post by Andrei Alexandrescu

The fundamental problem is that code that doesn't see the specialized version of a trait will still compile, is likely to link, and sometimes might even run. This is because in the absence of the explicit specialization, the non-specialized template kicks in, likely implementing a generic behavior that works for your special case as well. Consequently, if not all the code in an application sees the same definition of a trait, the ODR is violated.

The C++11 std::allocator_traits avoids these pitfalls by enforcing that all STL containers can only extract properties from their Allocator policies through std::allocator_traits<Allocator>. If users choose not to or forget to supply some of the required policy members, the traits class can step in and supply default values for those missing members. Because allocator_traits itself cannot be specialized, users always have to pass a fully defined allocator policy in order to customize their containers memory allocation, and no silent ODR violations can occur.

Note that as a library-writer, one can still specialize traits class templates (as the STL does in iterator_traits<T*>), but it is good practice to pass all user-defined specializations through policy classes into multi-valued traits that can extract the specialized behavior (as the STL does in allocator_traits<A>).

UPDATE: The ODR problems of user-defined specializations of traits classes happen mainly when traits are used as global class templates and you cannot guarantee that all future users will see all other user-defined specializations. Policies are local template parameters and contain all the relevant definitions, allowing them to be user-defined without interference in other code. Local template parameters that only contain type and constants -but no behaviorally functions- might still be called "traits" but they would not be visible to other code like the std::iterator_traits and std::allocator_traits.

I think you will find the best possible answer to your question in this book by Andrei Alexandrescu. Here, I will try to give just a short overview. Hopefully it will help.

---

A traits class is class that is usually intended to be a meta-function associating types to other types or to constant values to provide a characterization of those types. In other words, it is a way to model properties of types. The mechanism normally exploits templates and template specialization to define the association:

template<typename T>
struct my_trait
{
    typedef T& reference_type;
    static const bool isReference = false;
    // ... (possibly more properties here)
};

template<>
struct my_trait<T&>
{
    typedef T& reference_type;
    static const bool isReference = true;
    // ... (possibly more properties here)
};

The trait metafunction my_trait<> above associates the reference type T& and the constant Boolean value false to all types T which are not themselves references; on the other hand, it associates the reference type T& and the constant Boolean value true to all types T that are references.

So for instance:

int  -> reference_type = int&
        isReference = false

int& -> reference_type = int&
        isReference = true

In code, we could assert the above as follows (all the four lines below will compile, meaning that the condition expressed in the first argument to static_assert() is satisfied):

static_assert(!(my_trait<int>::isReference), "Error!");
static_assert(  my_trait<int&>::isReference, "Error!");
static_assert(
    std::is_same<typename my_trait<int>::reference_type, int&>::value, 
    "Error!"
     );
static_assert(
    std::is_same<typename my_trait<int&>::reference_type, int&>::value, 
    "Err!"
    );

Here you could see I made use of the standard std::is_same<> template, which is itself a meta-function that accepts two, rather than one, type argument. Things can get arbitrarily complicated here.

Although std::is_same<> is part of the type_traits header, some consider a class template to be a type traits class only if it acts as a meta-predicate (thus, accepting one template parameter). To the best of my knowledge, however, the terminology is not clearly defined.

For an example of usage of a traits class in the C++ Standard Library, have a look at how the Input/Output Library and the String Library are designed.

---

A policy is something slightly different (actually, pretty different). It is normally meant to be a class that specifies what the behavior of another, generic class should be regarding certain operations that could be potentially realized in several different ways (and whose implementation is, therefore, left up to the policy class).

For instance, a generic smart pointer class could be designed as a template class that accepts a policy as a template parameter for deciding how to handle ref-counting - this is just a hypothetical, overly simplistic, and illustrative example, so please try to abstract from this concrete code and focus on the mechanism.

That would allow the designer of the smart pointer to make no hard-coded commitment as to whether or not modifications of the reference counter shall be done in a thread-safe manner:

template<typename T, typename P>
class smart_ptr : protected P
{
public:
    // ... 
    smart_ptr(smart_ptr const& sp)
        :
        p(sp.p),
        refcount(sp.refcount)
    {
        P::add_ref(refcount);
    }
    // ...
private:
    T* p;
    int* refcount;
};

In a multi-threaded context, a client could use an instantiation of the smart pointer template with a policy that realizes thread-safe increments and decrements of the reference counter (Windows platformed assumed here):

class mt_refcount_policy
{
protected:
    add_ref(int* refcount) { ::InterlockedIncrement(refcount); }
    release(int* refcount) { ::InterlockedDecrement(refcount); }
};

template<typename T>
using my_smart_ptr = smart_ptr<T, mt_refcount_policy>;

In a single-threaded environment, on the other hand, a client could instantiate the smart pointer template with a policy class that simply increases and decreases the counter's value:

class st_refcount_policy
{
protected:
    add_ref(int* refcount) { (*refcount)++; }
    release(int* refcount) { (*refcount)--; }
};

template<typename T>
using my_smart_ptr = smart_ptr<T, st_refcount_policy>;

This way, the library designer has provided a flexible solution that is capable of offering the best compromise between performance and safety ("You don't pay for what you don't use").