> Maybe the situation has gotten better since constexpr was introduced, though.
Since C++11? Yes.
> even something like 'this array must be sorted' encoded fully in types is going to add a lot to your program's length
template< class Cmp, class Array> class Sorted;// The type of your parameter.
I think this could be implemented even in C++03.