by Nathan C. Myers
<http://www.cantrip.org/>
Standard C++ is not the C++ we know. Its many new features enable you to write programs and libraries that cannot be written in any other language. This has been academic until now, because compilers that support the new features have not been available, but that has changed. In this talk I explore the more interesting of these new features and some examples of what can be done with them. [Ed. note: Gnarly is American slang; it suggests engaging and powerful.]
Cheapest EDG-based compiler is from Greg Comeau, www.comeaucomputing.com;
Others on Linux include Kuck & Associates and Portland Group. Egcs (a non-EDG compiler) now supports all the discussed features.
Most changes are useful but not fun:
e.g. "bool", "static_cast<>", "explicit" constructors
(Namespaces actually are fun, but need a paper of their own.)
Some let us do things we couldn't do before. This table lists the fun ones, and which of them are supported in the more advanced compilers.
| Gnarly New Feature: | EDG | Sun | HP | Egcs | |
| Member Templates | X | . | X | X | |
| Partial Specialization of Class Templates | X | . | X | X | |
| Overloading of Function Templates | X | X | X | X | |
| Template Default Arguments | X | . | X | X | |
| Explicit Template Function Qualification | X | X | X | X |
These can be used to do things that can't be done in any other compiled language.
(Note: Compilers based on EDG's front end aren't necessarily based on the latest version.)
The next few slides describe each language feature separately, before the gnarly examples.
Regular templates are global:
template <class T> void swap(T& a, T& b)
{ T tmp = a; a = b; b = tmp; }
Member templates are declared in a class definition:
template <class T, ...>
class list {
.
.
typedef . . . iterator; // the regular list<> iterator
.
.
template <class InputIter>
void insert(iterator position,
InputIter first, InputIter last);
};
This inserts the sequence of values from first to last for any iterator type InputIter.
Member operators & constructors can be templates.
Regular specialization binds all arguments:
template <class T, Class U>
class hashtable { . . . };
template <>
class hashtable<int,int> { . . . };
template <>
class hashtable<int,float> { . . . };
.
.
.
Partial specialization leaves one or more arguments unbound:
template <class U>
class hashtable<int, U> { . . . };
Regular function templates can be specialized by binding all parameters:
template <class Base, class Exponent>
Base pow(Base b, Exponent e);
template <>
int pow(int b, int e);
Function template overloading can leave an argument unbound:
template <class Base>
Base pow(Base b, int);
Notice that function template overloading isn't the same as partial specialization; the second template declaration above is a separate function template, and the compiler will choose which to use for each call. Besides, the overloaded template might have more parameters than what you might consider the "base" template:
template <class T>
void f(T);
template <class U, class V, class W>
void f(V (U::*)(const W&));
Regular template arguments must all be supplied, or deduced from function arguments:
template <class T, class Compare>
class set;
set<int,less<int> > ints;
Default arguments allow users to leave off parameter values in the common case:
template <class T, class Compare = less<T> >
class set;
set<int> ints; // same as "set<int,less<int> > ints;"
Notice that the default binding (in this case, less<T>) can depend on previous arguments (in this case, T). (!)
Regular template function parameters must be deduced from a function argument declaration:
template <class T, class U>
U implicit_cast(const T& t, const U*) { return t; }
// string str = "hello"; // invisible conversion
string str = implicit_cast("hello", (string*)0); // visible conversion
(implicit_cast<> performs the cast only if it would have been legal to leave it out; otherwise it's an error. It's safer than a "C"-style cast, but makes it clear to the reader what's going on. However, the syntax above is ugly; in traditional C++ you can't do better without a macro.)
Explicit Qualification permits direct specification, bypassing argument type deduction, and with a nice syntax:
template <class U, class T>
U implicit_cast(const T& t) { return t; }
string str = implicit_cast<string>("hello");
implicit_cast is not part of the core language, because it is easily implemented in library code. It does not appear in the Standard C++ Library mainly because it was proposed too late, after the committee had resolved not to add anything more.
The point of these features is that they let us write more powerful libraries that are easier for users, because they absorb work or complexity users would have to manage themselves otherwise. Of course we're all users . . .
The next few sections explore examples of how this power can be applied.
template <class T>
void swap(T& a, T& b)
{ T tmp = a; a = b; b = tmp; } // copy b once, a twice
This could be very expensive, for some T:
vector<string> a, b; ... swap(a,b); // copy whole vector three times. (!)
But we can declare a special case for vector<anything>:
template <class T>
void swap<vector<T> >(vector<T>& a, vector<T>& b)
{ a.swap(b); } // just change pointers
This swap is fast for all vectors. The Standard C++ Library includes partial specializations like this for all the containers.
With the following in a header file...
a forward declaration of the recursive template:
template <int Dim, class T>
struct dot_class;
a specialized base case for recursion:
template <class T>
struct dot_class<1,T> {
static inline T dot(const T* a, const T* b)
{ return *a * *b; }
};
the recursive template:
template <int Dim, class T>
struct dot_class {
static inline T dot(const T* a, const T* b)
{ return dot_class<Dim-1,T>::dot(a+1,b+1) + *a * *b; }
};
... and some syntactic sugar:
template <int Dim, class T>
inline T dot_product(const T* a, const T* b)
{ return dot_class<Dim,T>::dot(a, b); }
Then
int product = dot_product<3>(a, b);
results in the same (optimal) code as
int product = a[0]*b[0] + a[1]*b[1] + a[2]*b[2];
by way of the compile-time template expansions
int product = dot_class<3,int>::dot(a,b); int product = dot_class<2,int>::dot(a+1,b+1) + *a * *b; int product = dot_class<1,int>::dot(a+2,b+2) + *(a+1) * *(b+1) + *a * *b; int product = *(a+2) * *(b+2) + *(a+1) * *(b+1) + *a * *b;
This technique has been demonstrated for
and results in code as good as specially optimized FORTRAN, but from an ordinary C++ compiler.
For more (and even more impressive) examples, see http://oonumerics.org/blitz/, work by Todd Veldhuizen.
C++ has no template typedef. However, a member template can be used to fake it. In this example, it is called rebind<>:
template <class T>
class allocator {
. . .
template <class U>
struct rebind { typedef allocator<U> other; };
. . .
template <class U>
allocator(const allocator<U>&);
};
Here is an authentic use of it, taken from the Standard Library.
template <class T, class Allocator = allocator<T> >
class list {
private:
typedef . . . listnode;
typedef typename Allocator::rebind<listnode>::other
Node_allocator;
Node_allocator alloc_;
list_node* make_node()
{ return new(alloc_.allocate(1)) list_node; }
public:
list(const Allocator& a = Allocator())
: alloc_(a) { } // implicit conversion
. . .
};
A list<> doesn't need to allocate objects of type T; it needs to allocate listnodes. The member rebind<> lets list<> name the allocator type that it needs, given only the template argument Allocator.
Note the new keyword typename above. It's just a syntax hack so that the C++ lexer can tell that a type name follows.
Traits template arguments allow libraries to extend flexibility from compile time to run time without harming convenience.
Default template arguments add flexibility.
template <
class T,
class Allocator = allocator<T> > // default at compile time
class list {
explicit list(
const Allocator& = Allocator()); // default at run time
};
list<int> li;
// same as: list<int,allocator<int> > li(allocator<int>());
Or
template <class Char, class Traits = char_traits<char> >
class streambuf;
See http://www.cantrip.org/traits.html
Traits allow return types to be deduced for function templates. Without them, this is what the STL iterator-difference function must look like:
template <class Iterator, class Size>
void distance(Iterator first, Iterator second, Size& total);
distance(p, p+10, dist); // ick: stores difference into dist
because template parameters can't be deduced from return types.
The Standard Library now has iterator traits. Most Iterators are expected to have a member typedef distance_type:
template <class Iterator>
struct iterator_traits {
typedef typename Iterator::distance_type distance_type;
. . .
};
Pointers have no distance_type member;
but ptrdiff_t is right for any pointer, so specialize:
template <class T>
struct iterator_traits<T*> {
typedef ptrdiff_t distance_type;
. . .
};
Now a distance() can be declared that can be used like any other function:
template <class Iterator>
typename iterator_traits<Iterator>::distance_type
distance(Iterator first, Iterator last);
A use of it looks like this:
dist = distance(p, p+10); // better.
template <class A, class B>
struct pair {
typedef A first_type;
typedef B second_type;
A first;
B second;
pair() : first(A()), second(B()) { }
pair(const A& a, const B& b) : first(a), second(b) { }
template <class U, class V>
pair(const pair<U,V>& p)
: first(p.first), second(p.second) { }
};
With the template constructor, the type
pair<int,int>
converts to
pair<const int,int>
for use with map<>::insert(). (The lack of this conversion is probably the single most common complaint about the public domain STL.)
Note: default definitions of copy constructor and assignment operator are still generated -- the template copy constructor does not prevent it. For pair that's OK, but some classes need to declare both the template copy constructor and a regular copy constructor. Caveat Scriptor!
Explicit Qualification allows any named conversion.
From Standard Library, Chapter 22, the class locale encapsulates formatting and other cultural preferences.
class locale;A global function template extracts those preferences.
template <class Facet>
const Facet& use_facet(const locale&);
For example, you could design a time zone preference
class TimeZone : public std::locale::facet {
. . .
static std::locale::id id; // used by use_facet<>()
int minutes_off() const;
};
and stow it in a locale object; then extract it using
a notation similar to a cast:
locale here;
. . .
int offset = use_facet<TimeZone>(here).minutes_off();
The C++ template instantiator is a primitive-recursive function evaluator. This was discovered by Erwin Unruh, who walked into a standards meeting one day with a listing of an illegal program that made the compiler emit a list of prime numbers in its error messages.
The same tricks are usable in working programs. Given N, compute a compile-time table size ceil(sqrt(N)):
template <int Size, int Low = 1, int High = Size> struct Root;
template <int Size, int Mid>
struct Root<Size,Mid,Mid> { static const int root = Mid; };
template <int Size, int Low, int High>
struct Root {
static const int mean = (Low + High)/2;
static const bool down = (mean * mean >= Size);
static const int root = Root<
Size, (down ? Low : mean+1), (down ? mean : High)>::root;
};
// compute sqrt, use it for static table size
int table[Root<N>::root];
(This example also draws on work by Todd Veldhuizen.)
Here are some definitions: