Using Templates in Practice

This excerpt from Vandevoorde's and Josuttis's "C++ Templates, The Complete Guide" offers a practical look at how to apply templates to everyday programming


February 01, 2003
URL:http://drdobbs.com/using-templates-in-practice/184403945

February 2003/Using Templates in Practice


Chapter 6 (pages 61-86) taken from the book C++ Templates by Vandevoorde & Josuttis. © 2002 Pearson Education Inc. Reproduced by permission of Pearson Education, Inc. All rights reserved.

Template code is a little different from ordinary code. In some ways templates lie somewhere between macros and ordinary (nontemplate) declarations. Although this may be an oversimplification, it has consequences not only for the way we write algorithms and data structures using templates, but also for the day-to-day logistics of expressing and analyzing programs involving templates.

In this chapter we address some of these practicalities without necessarily delving into the technical details that underlie them. Many of these details are explored in Chapter 10. To keep the discussion simple, we assume that our C++ compilation systems consist of fairly traditional compilers and linkers (C++ systems that don't fall in this category are quite rare).

6.1 The Inclusion Model

There are several ways to organize template source code. This section presents the most popular approach as of the time of this writing: the inclusion model.

6.1.1 Linker Errors

Most C and C++ programmers organize their nontemplate code largely as follows:

This works well: It makes the needed type definition easily available throughout the program and avoids duplicate definition errors on variables and functions from the linker.

With these conventions in mind, a common error about which beginning template programmers complain is illustrated by the following (erroneous) little program. As usual for "ordinary code," we declare the template in a header file:

// basics/myfirst.hpp

#ifndef MYFIRST_HPP
#define MYFIRST_HPP

//declaration of template
template <typename T>
void print_typeof (T const&);

#endif // MYFIRST_HPP

print_typeof() is the declaration of a simple auxiliary function that prints some type information. The implementation of the function is placed in a dot-C file:

// basics/myfirst.cpp    

#include <iostream>    
#include <typeinfo>    
#include "myfirst.hpp"    

// implementation/definition of template
template <typename T>
void print_typeof (T const& x)
{
    std::cout << typeid(x).name() << std::endl;
}

The example uses the typeid operator to print a string that describes the type of the expression passed to it (see Section 5.6 on page 58).

Finally, we use the template in another dot-C file, into which our template declaration is #included:

// basics/myfirstmain.cpp
#include "myfirst.hpp"

// use of the template
int main()
{
    double ice = 3.0;
    print_typeof(ice); //call function template for type double
}

A C++ compiler will most likely accept this program without any problems, but the linker will probably report an error, implying that there is no definition of the function print_typeof().

The reason for this error is that the definition of the function template print_typeof() has not been instantiated. In order for a template to be instantiated, the compiler must know which definition should be instantiated and for what template arguments it should be instantiated. Unfortunately, in the previous example, these two pieces of information are in files that are compiled separately. Therefore, when our compiler sees the call to print_typeof() but has no definition in sight to instantiate this function for double, it just assumes that such a definition is provided elsewhere and creates a reference (for the linker to resolve) to that definition. On the other hand, when the compiler processes the file myfirst.cpp, it has no indication at that point that it must instantiate the template definition it contains for specific arguments.

6.1.2 Templates in Header Files

The common solution to the previous problem is to use the same approach that we would take with macros or with inline functions: We include the definitions of a template in the header file that declares that template. For our example, we can do this by adding

#include "myfirst.cpp"

at the end of myfirst.hpp or by including myfirst.cpp in every dot-C file that uses the template. A third way, of course, is to do away entirely with myfirst.cpp and rewrite myfirst.hpp so that it contains all template declarations and template definitions:

// basics/myfirst2.hpp

#ifndef MYFIRST_HPP
#define MYFIRST_HPP

#include <iostream>
#include <typeinfo>

// declaration of template
template <typename T>
void print_typeof (T const&);

// implementation/definition of template
template <typename T>
void print_typeof (T const& x)
{
    std::cout << typeid(x).name() << std::endl;
}

#endif // MYFIRST_HPP

This way of organizing templates is called the inclusion model. With this in place, you should find that our program now correctly compiles, links, and executes.

There are a few observations we can make at this point. The most notable is that this approach has considerably increased the cost of including the header file myfirst.hpp. In this example, the cost is not the result of the size of the template definition itself, but the result of the fact that we must also include the headers used by the definition of our template — in this case <iostream> and <typeinfo>. You may find that this amounts to tens of thousands of lines of code because headers like <iostream> contain similar template definitions.

This is a real problem in practice because it considerably increases the time needed by the compiler to compile significant programs. We will therefore examine some possible ways to approach this problem in upcoming sections. However, real-world programs quickly end up taking hours to compile and link (we have been involved in situations in which it literally took days to build a program completely from its source code).

Despite this build-time issue, we do recommend following this inclusion model to organize your templates when possible. We examine two alternatives, but in our opinion their engineering deficiencies are more serious than the build-time issue discussed here. They may have other advantages not directly related to the engineering aspects of software development, however.

Another (more subtle) observation about the inclusion approach is that noninline function templates are distinct from inline functions and macros in an important way: They are not expanded at the call site. Instead, when they are instantiated, they create a new copy of a function. Because this is an automatic process, a compiler could end up creating two copies in two different files, and some linkers could issue errors when they find two distinct definitions for the same function. In theory, this should not be a concern of ours: It is a problem for the C++ compilation system to accommodate. In practice, things work well most of the time, and we don't need to deal with this issue at all. For large projects that create their own library of code, however, problems occasionally show up. A discussion of instantiation schemes in Chapter 10 and a close study of the documentation that came with the C++ translation system (compiler) should help address these problems.

Finally, we need to point out that what applies to the ordinary function template in our example also applies to member functions and static data members of class templates, as well as to member function templates.

6.2 Explicit Instantiation

The inclusion model ensures that all the needed templates are instantiated. This happens because the C++ compilation system automatically generates those instantiations as they are needed. The C++ standard also offers a construct to instantiate templates manually: the explicit instantiation directive.

6.2.1 Example of Explicit Instantiation

To illustrate manual instantiation, let's revisit our original example that leads to a linker error (see page 62). To avoid this error we add the following file to our program:

// basics/myfirstinst.cpp

#include "myfirst.cpp"
// explicitly instantiate print_typeof() for type double
template void print_typeof<double>(double const&);

The explicit instantiation directive consists of the keyword template followed by the fully substituted declaration of the entity we want to instantiate. In our example, we do this with an ordinary function, but it could be a member function or a static data member. For example:

// explicitly instantiate a constructor of MyClass<> for int
template MyClass<int>::MyClass();

// explicitly instantiate a function template max() for int
template int const& max (int const&, int const&);

You can also explicitly instantiate a class template, which is short for requesting the instantiation of all its instantiatable members. This excludes members that were previously specialized as well as those that were already instantiated:

// explicitly instantiate class Stack<> for int :
template class Stack<int>;

// explicitly instantiate some member functions of Stack<> for strings:
template Stack<std::string>::Stack();
template void Stack<std::string>::push(std::string const&);
template std::string Stack<std::string>::top();

// ERROR: can't explicitly instantiate a member function of a
// class that was itself explicitly instantiated: 

template Stack<int>::Stack();

There should be, at most, one explicit instantiation of each distinct entity in a program. In other words, you could explicitly instantiate both print_typeof<int> and print_typeof<double>, but each directive should appear only once in a program. Not following this rule usually results in linker errors that report duplicate definitions of the instantiated entities.

Manual instantiation has a clear disadvantage: We must carefully keep track of which entities to instantiate. For large projects this quickly becomes an excessive burden; hence we do not recommend it. We have worked on several projects that initially underestimated this burden, and we came to regret our decision as the code matured.

However, explicit instantiation also has a few advantages because the instantiation can be tuned to the needs of the program. Clearly, the overhead of large headers is avoided. The source code of template definition can be kept hidden, but then no additional instantiations can be created by a client program. Finally, for some applications it can be useful to control the exact location (that is, the object file) of a template instance. With automatic instantiation, this may not be possible (see Chapter 10 for details).

Figure 6.1. Separation of template declaration and definition

6.2.2 Combining the Inclusion Model and Explicit Instantiation

To keep the decision open whether to use the inclusion model or explicit instantiation, we can provide the declaration and the definition of templates in two different files. It is common practice to have both files named as header files (using an extension ordinarily used for files that are intended to be #included), and it is probably wise to stick to this convention. (Thus, myfirst.cpp of our motivating example becomes myfirstdef.hpp, with preprocessor guards around the code inserted.) Figure 6.1 demonstrates this for a Stack<> class template.

Now if we want to use the inclusion model, we can simply include the definition header file stackdef.hpp. Alternatively, if we want to instantiate the templates explicitly, we can include the declaration header stack.hpp and provide a dot-C file with the necessary explicit instantiation directives (see Figure 6.2).

Figure 6.2. Explicit instantiation with two template header files

6.3 The Separation Model

Both approaches advocated in the previous sections work well and conform entirely to the C++ standard. However, this same standard also provides the alternative mechanism of exporting templates. This approach is sometimes called the C++ template separation model.

6.3.1 The Keyword export

In principle, it is quite simple to make use of the export facility: Define the template in just one file, and mark that definition and all its nondefining declarations with the keyword export. For the example in the previous section, this results in the following function template declaration:

// basics/myfirst3.hpp
#ifndef MYFIRST_HPP
#define MYFIRST_HPP
// declaration of template
export
template <typename T>
void print_typeof (T const&);

#endif // MYFIRST_HPP

Exported templates can be used without their definition being visible. In other words, the point where a template is being used and the point where it is defined can be in two different translation units. In our example, the file myfirst.hpp now contains only the declaration of the member functions of the class template, and this is sufficient to use those members. Comparing this with the original code that was triggering linker errors, we had to add only one export keyword in our code and things now work just fine.

Within a preprocessed file (that is, within a translation unit), it is sufficient to mark the first declaration of a template with export. Later redeclarations, including definitions, implicitly keep that attribute. This is why myfirst.cpp does not need to be modified in our example. The definitions in this file are implicitly exported because they were so declared in the #included header file. On the other hand, it is perfectly acceptable to provide redundant export keywords on template definitions, and doing so may improve the readability of the code.

The keyword export really applies to function templates, member functions of class templates, member function templates, and static data members of class templates. export can also be applied to a class template declaration. It implies that every one of its exportable members is exported, but class templates themselves are not actually exported (hence, their definitions still appear in header files). You can still have implicitly or explicitly defined inline member functions. However, these inline functions are not exported:

export template <typenameT>
class MyClass {
  public:
    void memfun1();    // exported
    void memfun2(){    // not exported because implicitly inline
      ...
    }
    void memfun3();// not exported because explicitly inline
      ...
};

template <typename T>
inline void MyClass<T>::memfun3 ()
{
      ...
}

However, note that the keyword export cannot be combined with inline and must always precede the keyword template. The following is invalid:

template <typename T>
class Invalid {
  public:
    export void wrong(T);      // ERROR: export not followed by template
};

export template<typename T>    // ERROR: both export and inline
inline void Invalid<T>::wrong(T)
{
}

export inline T const& max (T const&a, T const& b)
{                              // ERROR: both export and inline
    return a < b ? b : a;
}

6.3.2 Limitations of the Separation Model

At this point it is reasonable to wonder why we're still advocating the inclusion approach when exported templates seem to offer just the right magic to make things work. There are a few different aspects to this choice.

First, even four years after the standard came out, only one company has actually implemented support for the export keyword. (As far as we know, Edison Design Group, Inc. [EDG] is still that company. Their technology is available through other vendors, however.) Therefore, experience with this feature is not as widespread as other C++ features. Clearly, this also means that at this point experience with exported templates is fairly limited, and all our observations will ultimately have to be taken with a grain of salt. It is possible that some of our misgivings will be addressed in the future (and we show how to prepare for that eventuality).

Second, although export may seem quasi-magical, it is not actually magical. Ultimately, the instantiation process has to deal with both the place where a template is instantiated and the place where its definition appears. Hence, although these two seem neatly decoupled in the source code, there is an invisible coupling that the system establishes behind the scenes. This may mean, for example, that if the file containing the definition changes, both that file and all the files that instantiate the templates in that file may need to be recompiled. This is not substantially different from the inclusion approach, but it is no longer obviously visible in the source code. As a consequence, dependency management tools (such as the popular make and nmake programs) that use traditional source-based techniques no longer work. It also means that quite a few bits of extra processing by the compiler are needed to keep all the bookkeeping straight; and in the end, the build times may not be better than those of the inclusion approach.

Finally, exported templates may lead to surprising semantic consequences, the details of which are explained in Chapter 10.

A common misconception is that the export mechanism offers the potential of being able to ship libraries of templates without revealing the source code for their definitions (just like libraries of nontemplate entities). (Not everybody considers this closed-source approach a plus.) This is a misconception in the sense that hiding code is not a language issue: It would be equally possible to provide a mechanism to hide included template definitions as to hide exported template definitions. Although this may be feasible (the current implementations do not support this model), it unfortunately creates new challenges in dealing with template compilation errors that need to refer to the hidden source code.

6.3.3 Preparing for the Separation Model

One workable idea is to prepare our sources in such a way that we can easily switch between the inclusion and export models using a harmless dose of preprocessor directives. Here is how it can be done for our simple example;

// basics/myfirst4.hpp
#ifndef MYFIRST_HPP
#define MYFIRST_HPP

// use export if USE-EXPORT is defined
#if defined (USE_EXPORT)
#define EXPORT export
#else
#define EXPORT
#endif

// declaration of template
EXPORT
template <typename T>
void print_typeof (T const&);


// include definition if USE_EXPORT is not defined
#if !defined(USE_EXPORT)
#include "myfirst.cpp"
#endif

#endif // MYFIRST_HPP

By defining or omitting the preprocessor symbol USE_EXPORT, we can now select between the two models. If a program defines USE_EXPORT before it includes myfirst.hpp, the separation model is used:

// use separation model:
#define USE_EXPORT
#include "myfirst.hpp"
...

If a program does not define USE_EXPORT, the inclusion model is used because in this case myfirst.hpp automatically includes the definitions in myfirst.cpp:

// use inclusion model:
#include "myfirst.hpp"
...

Despite this flexibility, we should reiterate that besides the obvious logistical differences, there can be subtle semantic differences between the two models.

Note that we can also explicitly instantiate exported templates. In this case the template definition can be in another file. To be able to choose between the inclusion model, the separation model, and explicit instantion, we can combine the organization controlled by USE_EXPORT with the conventions described in Section 6.2.2 on page 67.

6.4 Templates and inline

Declaring short functions to be inline is a common tool to improve the running time of programs. The inline specifier indicates to the implementation that inline substitution of the function body at the point of call is preferred over the usual function call mechanism. However, an implementation is not required to perform this inline substitution at the point of call.

Both function templates and inline functions can be defined in multiple translation units. This is usually achieved by placing the definition in a header file that is included by multiple dot-C files.

This may lead to the impression that function templates are inline by default. However, they're not. If you write function templates that should be handled as inline functions, you should use the inline specifier (unless the function is inline already because it is defined inside a class definition).

Therefore, many short template functions that are not part of a class definition should be declared with inline. (We may not always apply this rule of thumb because it may distract from the topic at hand.)

6.5 Precompiled Headers

Even without templates, C++ header files can become very large and therefore take a long time to compile. Templates add to this tendency, and the outcry of waiting programmers has in many cases driven vendors to implement a scheme usually known as precompiled headers. This scheme operates outside the scope of the standard and relies on vendor-specific options. Although we leave the details on how to create and use precompiled header files to the documentation of the various C++ compilation systems that have this feature, it is useful to gain some understanding of how it works.

When a compiler translates a file, it does so starting from the beginning of the file and works through to the end. As it processes each token from the file (which may come from #included files), it adapts its internal state, including such things as adding entries to a table of symbols so they may be looked up later. While doing so, the compiler may also generate code in object files.

The precompiled header scheme relies on the fact that code can be organized in such a manner that many files start with the same lines of code. Let's assume for the sake of argument that every file to be compiled starts with the same N lines of code. We could compile these N lines and save the complete state of the compiler at that point in a so-called precompiled header. Then, for every file in our program, we could reload the saved state and start compilation at line N+1. At this point it is worthwhile to note that reloading the saved state is an operation that can be orders of magnitude faster than actually compiling the first N lines. However, saving the state in the first place is typically more expensive than just compiling the N lines. The increase in cost varies roughly from 20 to 200 percent.

The key to making effective use of precompiled headers is to ensure that — as much as possible — files start with a maximum number of common lines of code. In practice this means the files must start with the same #include directives, which (as mentioned earlier) consume a substantial portion of our build time. Hence, it can be very advantageous to pay attention to the order in which headers are included. For example, the following two files

#include <iostream>
#include <vector>
#include <list>
...

and

#include <list>
#include <vector>
...

inhibit the use of precompiled headers because there is no common initial state in the sources.

Some programmers decide that it is better to #include some extra unnecessary headers than to pass on an opportunity to accelerate the translation of a file using a precompiled header. This decision can considerably ease the management of the inclusion policy. For example, it is usually relatively straightforward to create a header file named std.hpp that includes all the standard headers (In theory, the standard headers do not actually need to correspond to physical files. In practice, however, they do, and the files are very large.):

#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <list>
...

This file can then be precompiled, and every program file that makes use of the standard library can then simply be started as follows:

#include "std.hpp"
...

Normally this would take a while to compile, but given a system with sufficient memory, the precompiled header scheme allows it to be processed significantly faster than almost any single standard header would require without precompilation. The standard headers are particularly convenient in this way because they rarely change, and hence the precompiled header for our std.hpp file can be built once. (Some committee members find the concept of a comprehensive std.hpp header so convenient that they have suggested introducing it as a standard header. We would then be able to write #include <std>. Some even suggest that it should be implicitly included so that all the standard library facilities become available without #include.) Otherwise, precompiled headers are typically part of the dependency configuration of a project (for example, they are updated as needed by the popular make tool).

One attractive approach to manage precompiled headers is to create layers of precompiled headers that go from the most widely used and stable headers (for example, our std.hpp header) to headers that aren't expected to change all the time and therefore are still worth precompiling. However, if headers are under heavy development, creating precompiled headers for them can take more time than what is saved by reusing them. A key concept to this approach is that a precompiled header for a more stable layer can be reused to improve the precompilation time of a less stable header. For example, suppose that in addition to our std.hpp header (which we have precompiled), we also define a core.hpp header that includes additional facilities that are specific to our project but nonetheless achieve a certain level of stability:

#include "std.hpp"
#include "core_data.hpp"
#include "core_algos.hpp"
...

Because this file starts with #include "std.hpp", the compiler can load the associated precompiled header and continue with the next line without recompiling all the standard headers. When the file is completely processed, a new precompiled header can be produced. Applications can then use #include "core.hpp" to provide access quickly to large amounts of functionality because the compiler can load the latter precompiled header.

6.6 Debugging Templates

Templates raise two classes of challenges when it comes to debugging them. One set of challenges is definitely a problem for writers of templates: How can we ensure that the templates we write will function for any template arguments that satisfy the conditions we document? The other class of problems is almost exactly the opposite: How can a user of a template find out which of the template parameter requirements it violated when the template does not behave as documented?

Before we discuss these issues in depth, it is useful to contemplate the kinds of constraints that may be imposed on template parameters. In this section we deal mostly with the constraints that lead to compilation errors when violated, and we call these constraints syntactic constraints. Syntactic constraints can include the need for a certain kind of constructor to exist, for a particular function call to be unambiguous, and so forth. The other kind of constraint we call semantic constraints.

These constraints are much harder to verify mechanically. In the general case, it may not even be practical to do so. For example, we may require that there be a < operator defined on a template type parameter (which is a syntactic constraint), but usually we'll also require that the operator actually defines some sort of ordering on its domain (which is a semantic constraint).

The term concept is often used to denote a set of constraints that is repeatedly required in a template library. For example, the C++ standard library relies on such concepts as random access iterator and default constructible. Concepts can form hierarchies in the sense that one concept can be a refinement of another. The more refined concept includes all the constraints of the other concept but adds a few more. For example, the concept random access iterator refines the concept bidirectional iterator in the C++ standard library. With this terminology in place, we can say that debugging template code includes a significant amount of determining how concepts are violated in the template implementation and in their use.

6.6.1 Decoding the Error Novel

Ordinary compilation errors are normally quite succinct and to the point. For example, when a compiler says "class x has no member 'fun'," it usually isn't too hard to figure out what is wrong in our code (for example, we might have mistyped run as fun). Not so with templates. Consider the following relatively simple code excerpt using the C++ standard library. It contains a fairly small mistake: list<string> is used, but we are searching using a greater<int> function object, which should have been a greater<string> object:

 
std::list<std::string> coll;
...
// Find the first element greater than "A"
std::list<std::string>::iterator pos;
pos = std::find_if(coll.begin(),coll.end(),                // range 
                   std::bind2nd(std::greater<int>(),"A")); // criterion

This sort of mistake commonly happens when cutting and pasting some code and forgetting to adapt parts of it.

A version of the popular GNU C++ compiler reports the following error:

/local/include/stl/_algo.h: In function 'struct _STL::_List_iterator<_STL::basic _string
<char,_STL::char_traits<char>,_STL::allocator<char>>,_STL::_Nonconst_traits
<_STL::basic_string<char,_STL::char_traits<char>,_STL::allocator<char>>>>
_STL::find_if<_STL::_List_iterator<_STL::basic_string<char,_STL::char_traits<char>,
_STL::allocator<char>>,_STL::_Nonconst_traits<_STL::basic_string<char,_STL::char_traits<char>,
_STL::allocator<char>>>>,_STL::binder2nd<_STL::greater<int>>>(_STL::_List_iterator
<_STL::basic_string<char,_STL::char_traits<char>,_STL::allocator<char>>>>,
_STL::_Nonconst_traits<_STL::basic_string<char,_STL::char_traits<char>,_STL::allocator<char>>>>,
_STL::_List_iterator<_STL::basic_string<char,_STL::char_traits<char>,_STL::allocator<char>>,
_STL::_Nonconst_traits<_STL::basic_string<char,_STL::char_traits<char>,_STL::allocator<char>>>>,
_STL::binder2nd<_STL::greater<int>>,_STL::input_iterator_tag)':
/local/include/stl/_algo.h:115: instantiated from '_STL::find_if<_STL::_List_iterator
<_STL::basic_string<char,_STL::char_traits<char>,_STL::allocator<char>>, _STL::Nonconst_traits
<_STL::basic_string<char,_STL::char_traits<char>,__STL::allocator<char>>>>,
_STL::binder2nd<_STL::greater<int>>>(_STL::_List_iterator<_STL::basic_string<char,
_STL::char_traits<char>,_STL::allocator<char>>,_STL::_Nonconst_traits<_STL::basic_string<char,
_STL::char_traits<char>,_STL::allocator<char>>>>,_STL::_List_iterator<_STL::basic_string<char,
_STL::char_traits<char>,_STL::allocator<char>>,_STL::Nonconst_traits<_STL::basic_string<char,
_STL::char_traits<char>,_STL::allocator<char>>>>,_STL:: binder2nd<_STL::greater<int>>)'
testprog.cpp:18: instantiated from here
/local/include/stl/_algo.h:78: no match for call to '(_STL:binder2nd<_STL::greater<int>>) 
(_STL::basic_string<char,_STL::char_traits<char>,_STL::allocator<char>>&)'
/local/include/stl/_function.h:261: candidates are: bool _STL::binder2nd<
_STL::greater<int> >::operator ()(const int &) const

A message like this starts looking more like a novel than a diagnostic. It can also be overwhelming to the point of discouraging novice template users. However, with some practice, messages like this become manageable, and the errors are relatively easily located.

The first part of this error message says that an error occurred in a function template instance (with a horribly long name) deep inside the /local/include/stl/_algo.h header. Next, the compiler reports why it instantiated that particular instance. In this case it all started on line 18 of testprog.cpp (which is the file containing our example code), which caused the instantiation of a find_if template on line 115 of the _algo.h header. The compiler reports all this in case we simply were not expecting all these templates to be instantiated. It allows us to determine the chain of events that caused the instantiations.

However, in our example we're willing to believe that all kinds of templates needed to be instantiated, and we just wonder why it didn't work. This information comes in the last part of the message: The part that says "no match for call" implies that a function call could not be resolved because the types of the arguments and the parameter types didn't match. Furthermore, just after this, the line containing"candidates are" explains that there was a single candidate type expecting an integer type (parameter type const int&). Looking back at line 18 of the program, we see std::bind2nd(std::greater<int>(),"A"), which does indeed contain an integer type (<int>) that is not compatible with the string type objects for which we're looking in our example. Replacing <int> with <std::string> makes the problem go away.

There is no doubt that the error message could be better structured. The actual problem could be omitted before the history of the instantiation, and instead of using fully expanded template instantiation names like MyTemplate<YourTemplate<int> >, decomposing the instance as in MyTemplate<T> with T=YourTemplate<int> can reduce the overwhelming length of names. However, it is also true that all the information in this diagnostic could be useful in some situations. It is therefore not surprising that other compilers provide similar information (although some use the structuring techniques mentioned).

6.6.2 Shallow Instantiation

Diagnostics such as those discussed earlier arise when errors are found after a long chain of instantiations. To illustrate this, consider the following somewhat contrived code:

template <typename T>
void clear (T const& p)
{
  *p = 0; // assumes T is a pointer-like type
}

template <typename T>
void core (T const& p)
{
  clear(p);
}

template <typename T>
void middle (typename
T::Index p)
{
  core(p);
}

template <typename T>
void shell (T const& env)
{
  typename T::Index I;
  middle<T>(i);
}

class Client {
  public:
    typedef int Index;
};

Client main_client;

int main()
{
  shell(main_client);
}

This example illustrates the typical layering of software development: High-level function templates like shell() rely on components like middle(), which themselves make use of basic facilities like core(). When we instantiate shell(), all the layers below it also need to be instantiated. In this example, a problem is revealed in the deepest layer: core() is instantiated with type int (from the use of Client::Index in middle()) and attempts to dereference a value of that type, which is an error. A good generic diagnostic includes a trace of all the layers that led to the problems, but we observe that so much information can appear unwieldy.

An excellent discussion of the core ideas surrounding this problem can be found in [StroustrupDnE], in which Bjarne Stroustrup identifies two classes of approaches to determine earlier whether template arguments satisfy a set of constraints: through a language extension or through earlier parameter use. We cover the former option to some extent in Section 13.11 on page 218. The latter alternative consists of forcing any errors in shallow instantiations. This is achieved by inserting unused code with no other purpose than to trigger an error if that code is instantiated with template arguments that do not meet the requirements of deeper levels of templates.

In our previous example we could add code in shell() that attempts to dereference a value of type T::Index. For example:

template (typename T>
inline void ignore(T const&)
{
{

template <typename T>
void shell (T const& env)
{
  class ShallowChecks {
    void deref(T::Index ptr) {
      ignore(*ptr);
    }
  };
  typename T::Index I;
  middle(i);
}

If T is a type such that T::Index cannot be dereferenced, an error is now diagnosed on the local class ShallowChecks. Note that because the local class is not actually used, the added code does not impact the running time of the shell() function. Unfortunately, many compilers will warn about the fact that ShallowChecks is not used (and neither are its members). Tricks such as the use of the ignore() template can be used to inhibit such warnings, but they add to the complexity of the code.

Clearly, the development of the dummy code in our example can become as complex as the code that implements the actual functionality of the template. To control this complexity it is natural to attempt to collect various snippets of dummy code in some sort of library. For example, such a library could contain macros that expand to code that triggers the appropriate error when a template parameter substitution violates the concept underlying that particular parameter. The most popular such library is the Concept Check Library, which is part of the Boost distribution (see [BCCL]).

Unfortunately, the technique isn't particularly portable (the way errors are diagnosed differs considerably from one compiler to another) and sometimes masks issues that cannot be captured at a higher level.

6.6.3 Long Symbols

The error message analyzed in Section 6.6.1 on page 75 demonstrates another problem of templates: Instantiated template code can result in very long symbols. For example, in the implementation used earlier std::string is expanded to

_STL::basic_string<char,_STL::char_traits<char>,
                           _STL::allocator<char> >

Some programs that use the C++ standard library produce symbols that contain more than 10,000 characters. These very long symbols can also cause errors or warnings in compilers, linkers, and debuggers. Modern compilers use compression techniques to reduce this problem, but in error messages this is not apparent.

6.6.4 Tracers

So far we have discussed bugs that arise when compiling or linking programs that contain templates. However, the most challenging task of ensuring that a program behaves correctly at run time often follows a successful build. Templates can sometimes make this task a little more difficult because the behavior of generic code represented by a template depends uniquely on the client of that template (certainly much more so than ordinary classes and functions). A tracer is a software device that can alleviate that aspect of debugging by detecting problems in template definitions early in the development cycle.

A tracer is a user-defined class that can be used as an argument for a template to be tested. Often, it is written just to meet the requirements of the template and no more than those requirements. More important, however, a tracer should generate a trace of the operations that are invoked on it. This allows, for example, to verify experimentally the efficiency of algorithms as well as the sequence of operations.

Here is an example of a tracer that might be used to test a sorting algorithm:

//basics/tracer.hpp

#include <iostream>

class SortTracer {
  private:
    int value;    // integer value to be sorted
    int generation;    // generation of this tracer
    static long n_created;     // number of constructor calls
    static long n_destroyed;    // number of destructor calls
    static long n_assigned    // number of assignments
    static long n_compared;    // number of comparisons
    static long n_max_live;    //maximum of existing objects
    //recompute maximum of existing objects
    static void update_max_live() {
      if (n_created-n_destroyed > n_max_live) {
      n_max_live = n_created-n_destroyed;
      }
  }

public:
  static long creations() {
    return n_created;
  }
  static long destructions() {
    return n_destroyed;
  }
  static long assignments() {
    return n_assigned;
  }
  static long comparisons() {
    return n_compared;
  }
  static long_max_live() {
    return n_max_live;
  }

public:
  // constructor
  SortTracer (int v = 0) : value(v), generation(1) {
    ++n_created;
    update_max_live();
    std::cerr << "SortTracer #" << n_created
          << ", created generation " << generation
          << " (total: " << n_created - n_destroyed
          << ")\n";

} // copy constructor SortTracer (SortTracer const& b) : value(b.value), generation(b.generation+1) { ++n_created; update_max_live(); std::cerr << "SortTracer #" << n_created << ", copied as generation " << generation << "(total: " << n_created - n_destroyed << ")\n"; } // destructor ~SortTracer() { ++n_destroyed; update_max_live(); std::cerr << "SortTracer generation" << generation << " destroyed (total: " << n_created - n_destroyed << ")\n"; } // assignment SortTracer& operator= (SortTracer const& b) { ++n_assigned; std::cerr << "SortTracer assignment #" << n_assigned << " (generation " << generation << ")\n"; value = b.value; return *this; } // comparison friend bool operator < (SortTracer const& a, SortTracer const& b) { ++n_compared; std::cerr << "SortTracer comparison #" << n_compared << " (generation " << a.generation << " < " << b.generation << ")\n"; return a.value < b.value; } int val() const { return value; } };

In addition to the value to sort, value, the tracer provides several members to trace an actual sort: generation traces for each object how many copies it is from the original. The other static members trace the number of creations (constructor calls), destructions, assignment comparisons, and the maximum number of objects that ever existed.

The static members are defined in a separate dot-C file:

// basics/tracer.cpp
#include "tracer.hpp"

long SortTracer::n_created = 0;
long SortTracer::n_destroyed = 0;
long SortTracer::n_max_live = 0;
long SortTracer::n_assigned = 0;
long SortTracer::n_compared = 0;

This particular tracer allows us to track the pattern or entity creation and destruction as well as assignments and comparisons performed by a given template. The following test program illustrates this for the std::sort algorithm of the C++ standard library:

// basics/tracertest.cpp

#include <iostream>
#include <algorithm>
#include "tracer.hpp"

int main()
{
  // prepare sample input:
  SortTracer input[] = { 7, 3, 5, 6, 4, 2, 0, 1, 9, 8 };

  // print initial values:
  for (int i=0; i<10; ++i) {
    std::cerr << input [i].val() << ' ';
  }
  std::cerr <<  std::endl;

  // remember initial conditions:
  long created_at_start = SortTracer::creations();
  long max_live_at_start = SortTracer::max_live();
  long assigned_at_start = SortTracer::assignments();
  long compared_at_start = SortTracer::comparisons();
  
  // execute algorithm:
  std::cerr << "---[ Start std::sort() ]--------------------\n";
  std::sort<>(&input[0], &input[9]+1);
  std::cerr << "---[ End std::sort() ]----------------------\n";
  
  // verify result:
  for (int i=0; i<10; ++i) {
    std::cerr << input[i].val() << ' ';
  }
  std::cerr << "\n\n";
  
  // final report:
  std::cerr << "std::sort() of 10 SortTracer's"
            << " was performed by:\n "
            << SortTracer::creations() - created_at_start
            << " temporary tracers\n "
            << "up to "
            << SortTracer::max_live()
            << " tracers at the same time ("
            << max_live_at_start << " before)\n "
            << SortTracer::assignments() - assigned_at_start
            << " assignments\n "
            << SortTracer::comparisons() - compared_at_start
            << " comparisons\n\n";
}

Running this program creates a considerable amount of output, but much can be concluded from the "final report." For one implementation of the std::sort()function, we find the following:

std::sort() of 10 SortTracer's was performed by:
  15 temporary tracers
  up to 12 tracers at the same time (10 before)
  33 assignments
  27 comparisons

For example, we see that although 15 temporary tracers were created in our program while sorting, at most two additional tracers existed at any one time.

Our tracer thus fulfills two roles: It proves that the standard sort()algorithm requires no more functionality than our tracer (for example, operators == and > were not needed), and it gives us a sense of the cost of the algorithm. It does not, however, reveal much about the correctness of the sorting template.

6.6.5 Oracles

Tracers are relatively simple and effective, but they allow us to trace the execution of templates only for specific input data and for a specific behavior of its related functionality. We may wonder, for example, what conditions must be met by the comparison operator for the sorting algorithm to be meaningful (or correct), but in our example we have only tested a comparison operator that behaves exactly like less-than for integers.

An extension of tracers is known in some circles as oracles (or run-time analysis oracles). They are tracers that are connected to a so-called inference engine — a program that can remember assertions and reasons about them to infer certain conclusions. One such system that was applied to certain parts of a standard library implementation is called MELAS and is discussed in [MusserWangDynaVeri]. (One author, David Musser, was also a key figure in the development of the C++ standard library. Among other things, he designed and implemented the first associative containers.)

Oracles allow us, in some cases, to verify template algorithms dynamically without fully specifying the substituting template arguments (the oracles are the arguments) or the input data (the inference engine may request some sort of input assumption when it gets stuck). However, the complexity of the algorithms that can be analyzed in this way is still modest (because of the limitations of the inference engines), and the amount of work is considerable. For these reasons, we do not delve into the development of oracles, but the interested reader should examine the publication mentioned earlier (and the references contained therein).

6.6.6 Archetypes

We mentioned earlier that tracers often provide an interface that is the minimal requirement of the template they trace. When such a minimal tracer does not generate run-time output, it is sometimes called an archetype. An archetype allows us to verify that a template implementation does not require more syntactic constraints than intended. Typically, a template implementer will want to develop an archetype for every concept identified in the template library.

6.7 Afternotes

The organization of source code in header files and dot-C files is a practical consequence of various incarnations of the so-called one-definition rule or ODR. An extensive discussion of this rule is presented in Appendix A.

The inclusion versus separation model debate has been a controversial one. The inclusion model is a pragmatic answer dictated largely by existing practice in C++ compiler implementations. However, the first C++ implementation was different: The inclusion of template definitions was implicit, which created a certain illusion of separation (see Chapter 10 for details on this original model).

[StroustrupDnE] contains a good presentation of Stroustrup's vision for template code organization and the associated implementation challenges. It clearly wasn't the inclusion model. Yet, at some point in the standardization process, it seemed as if the inclusion model was the only viable approach after all. After some intense debates, however, those envisioning a more decoupled model garnered sufficient support for what eventually became the separation model. Unlike the inclusion model, this was a theoretical model not based on any existing implementation. It took more than five years to see its first implementation published (May 2002).

It is sometimes tempting to imagine ways of extending the concept of precompiled headers so that more than one header could be loaded for a single compilation. This would in principle allow for a finer grained approach to precompilation. The obstacle here is mainly the preprocessor: Macros in one header file can entirely change the meaning of subsequent header files. However, once a file has been precompiled, macro processing is completed, and it is hardly practical to attempt to patch a precompiled header for the preprocessor effects induced by other headers.

A fairly systematic attempt to improve C++ compiler diagnostics by adding dummy code in high level templates can be found in Jeremy Siek's Concept Check Library (see [BCCL]). It is part of the Boost library (see [Boost]).

6.8 Summary

Bibliography

[BCCL] Jeremy Siek. The Boost Concept Check Library, <www.boost.org/libs/concept_check/concept_check.htm>.

[Boost] The Boost Repository for Free, Peer-Reviewed C++ Libraries, <www.boost.org>.

[EDG] Edison Design Group. Compiler Front Ends for the OEM Market, <www.edg.com>.

[MusserWangDynaVeri] D.R. Musser and C. Wang. Dynamic Verification of C++ Generic Algorithms, IEEE Transactions on Software Engineering, Vol. 23, No. 5, May 1997.

[StroustrupDnE] Bjarne Stroustrup. Bjarne Stroustrup's C++ Glossary, <www.research.att.com/~bs/glossary.html>.

About the Authors

David Vandevoorde is an engineer at the Edison Design Group. He is an active member of the ANSI C++ Standards Committee, and a cofounder of the newsgroup comp.lang.c++.moderated. A graduate of the Brussels Free University and the Rensselaer Polytechnic University, his interests include algorithm development, programming languages, and teaching. He is the author of C++ Solutions: Companion to the C++ Programming Language, Third Edition (Addison-Wesley, 1998). See <www.vandevoorde.com>.

Nicolai M. Josuttis is an independent technical consultant who designs object-oriented software for the telecommunications, traffic, finance, and manufacturing industries. He is an active member of the C++ Standards Committee Library Working Group. Nicolai has written several books on object-oriented programming and C++, including The C++ Standard Library (Addison-Wesley, 1999). See <www.josuttis.com>.

Vandevoorde/Josuttis, C++ Templates, pp. 61-86. © 2003 Pearson Education Inc. Reproduced by permission of Pearson Education, Inc. All rights reserved.

Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.