Policies - I got to know about them from Andrei's Modern C++ Design book. If there are different orthogonal (independent) ways to achieve a particular functionality, they are good candidates to be classified as policies and we can write types based on those policies. Policies, in general, are compile time variants of strategies as in Strategy pattern. For example, the allocator template parameter to STL classes could be said as an allocation policy - the default being std::allocator<T>.
Traits - I understand them as not achieve anything for the class or the type (policies do achieve some functionality for their host class). They basically tell something about the type.
For example, boost::type_traits (is_pod, is_fundamental, is_derived_of, is_polymorphic). All these help in knowing something about the type. They are not orthoganal (independent, de-coupled ) ways of doing something or exposing some functionality. They don't add something to the definition of the type rather they provide for a set of information.
If I may take another example : std::char_traits<charT>. They tell something about the type via a few typedefs but they also have functions that tell about how to compare, assign, find length, etc. These "add" to the definition of the type in the context (context meaning whatever char_traits is passed to make a string type out of basic_string). char_traits looks to include policies, looks like a collection of policies. It provides policies to compare, assign and find length. A basic_string of character type "char" can have a different definitions of (or ways to do) comparison. I can provide a specialization or a traits class of my own where I change the compare to be case insensitive. This seems like a policy because they are two different ways to achieve the same objective, to fulfil a requirement, to expose a functionality, to define the working in a specific context. I can define that policy as "A compare policy that must expose a Compare member function, callable with 2 char_type* types and a size_t argument signifying number of elements to compare and returns a boolean result".
As compared to char_traits if I take std::numeric_limits : this can be said to be a trait (or a collection of traits). They tell about what max() for a type is, what epsilon() for a type is. They are not policies. They don't achieve some behaviour but they may represent how types should/may behave or what properties they have. I cannot specialize traits. That would be wrong. Policies? Of course, specialize it, rename it.
Policies and traits are both compile time features. Type traits at runtime would be RTTI. Policies at runtime would be strategies. None of those need necessarily be templates though.
Based on the above understanding, I would be right in thinking that basic_string template would have been better defined as:
template <class> CharTPolicyCollection,
template <class> AllocationPolicy
class basic_string :
because otherwise, if you wrote something like this:
.. and you would not be wrong. The only problem being it will not work as expected for a sequence of char (i.e. like std::string). This problem exists because the basic_string doesn't use template template parameters. Had they used it, incompatible policies could not be clubbed with the host class to form a wierd type.
You should have protected CharTPolicyCollection and AllocationPolicy destructors if you are worried about the public inheriatnce and destruction via the base policy class pointers. Their virtual destructor would be also a solution but would be an unwanted overhead of the v-table. The typedefs there in std::char_traits though can be said to be traits, may be.
This is another reason why std::basic_string is not a very good design. The first being an overly loaded public interface.