Template Specialization

The previous lesson showed that a template makes the compiler write a new body for every new type, and that this cost stays in the compile kind. The body a template produces is the same pattern for every type, but for some types the pattern may be wrong or wasteful. This lesson covers replacing the pattern by hand in that case, which is specialization. The question has not changed: where did this mechanism move the cost? Here the answer is not the number of bodies but how many slots the data is spread across in memory.

The Primary Template and Full Specialization

Consider a Pack<T> that holds eight values. The primary template reserves one slot for each value: T slot[8]. For bool this is wasteful, because a value carries one bit but occupies one byte. A full specialization (template <>) replaces the primary template entirely for a given type; here Pack<bool> keeps the eight values in a single unsigned char. The interface stays the same, the body changes.

// pack.hpp — primary template and full specialization for bool
#ifndef PACK_HPP
#define PACK_HPP

template <typename T>
struct Pack {
    T slot[8] = {};
    const void* where(int i) const { return &slot[i]; }
    void write(int i, T value) { slot[i] = value; }
    T read(int i, int&) const { return slot[i]; }
};

template <>
struct Pack<bool> {
    unsigned char bits = 0;
    const void* where(int) const { return &bits; }
    void write(int i, bool value) {
        if (value) bits = static_cast<unsigned char>(bits | (1u << i));
        else bits = static_cast<unsigned char>(bits & ~(1u << i));
    }
    bool read(int i, int& steps) const {
        steps += 2;   // one shift, one mask
        return ((bits >> i) & 1) != 0;
    }
};

#endif

where shows which slot a value sits in; we will count slots with pointer equality, without printing addresses. If two pointers are equal, the two values are in the same slot. The program below fills both packs with the same pattern, reads them and prints the distinct slot count.

// specialization.cpp — same interface, different slot count
#include <cstdio>

#include "pack.hpp"

template <typename T>
static int distinct_slots(const Pack<T>& p) {
    int distinct = 0;
    for (int i = 0; i < 8; ++i) {
        bool fresh = true;
        for (int j = 0; j < i; ++j)
            if (p.where(i) == p.where(j)) fresh = false;
        if (fresh) ++distinct;
    }
    return distinct;
}

template <typename T>
static void try_pack(const char* name, Pack<T>& p) {
    int steps = 0;
    p.write(1, true);
    p.write(6, true);
    std::printf("%s ", name);
    for (int i = 0; i < 8; ++i) std::printf("%d", static_cast<int>(p.read(i, steps)));
    std::printf(" slots=%d\n", distinct_slots(p));
}

int main() {
    Pack<int> general;
    Pack<bool> packed;
    try_pack("int ", general);
    try_pack("bool", packed);
    return 0;
}

int  01000010 slots=8
bool 01000010 slots=1

MT6. The two packs read the same values in the same order; the only difference is the slot count: Pack<int> uses eight distinct slots, Pack<bool> uses one. The int=8 bool=1 counts in the bool specialization row of the core are this measurement. The cost falls under the memory kind: the same work touches a different number of storage slots depending on the layout of the data.

Partial Specialization and Selecting the Most Specialized Match

A full specialization names types one by one. A partial specialization captures a pattern of parameters instead: “if the two parameters are the same type” or “if the type is a pointer”. For a two-parameter Pair<T, U>, the primary template captures distinct types, the Pair<T, T> partial specialization captures identical types, and the Pair<int, int> full specialization captures only the int pair. When more than one specialization fits a use, the compiler picks the most specialized one.

// pair.hpp — primary template, partial and full specialization
#ifndef PAIR_HPP
#define PAIR_HPP

template <typename T, typename U>
struct Pair {
    static const char* kind() { return "different"; }
};

template <typename T>
struct Pair<T, T> {
    static const char* kind() { return "same"; }
};

template <>
struct Pair<int, int> {
    static const char* kind() { return "integer"; }
};

#endif

// pair-select.cpp — which specialization was chosen
#include <cstdio>

#include "pair.hpp"

int main() {
    std::printf("int,double    %s\n", Pair<int, double>::kind());
    std::printf("double,double %s\n", Pair<double, double>::kind());
    std::printf("int,int       %s\n", Pair<int, int>::kind());
    return 0;
}

int,double    different
double,double same
int,int       integer

MT7. Pair<int, int> fits both the partial pattern (T, T) and the full specialization; the compiler chooses the full one. Pair<double, double> fits only the partial pattern. The selection ends at compile time and leaves no decision step at run time. There is one more rule: a specialization must be visible before the first instantiation of that type; a specialization that comes after the type has already been generated from the primary template makes the program ill-formed, and the compiler is not required to report it. Function templates, on the other hand, cannot be partially specialized; overloading is used for the same job, which the Overload Resolution and SFINAE lesson covers.

The Pointer Pattern and the Limit of Specialization

A partial specialization can also capture the shape of a type. Access<T*> captures every type that is a pointer, whatever T is; the primary template returns the value as it is. A limit shows up here: a specialization does not inherit the members of the primary template. A specialization is a new class definition on its own; every member that exists in the primary template and that we expect to be callable has to be written again in it. Keeping the interface common is not a compiler guarantee but a contract the author takes on. That Pack<bool> carries the members where, write and read under the same names as the primary template is this contract being honored.

// pointer.hpp — a partial specialization captures the pointer pattern
#ifndef POINTER_HPP
#define POINTER_HPP

template <typename T>
struct Access {
    static const char* name() { return "value"; }
    static T get(const T& x) { return x; }
};

template <typename T>
struct Access<T*> {
    static const char* name() { return "pointer"; }
    static T get(T* const& p) { return *p; }
};

#endif

// pointer-select.cpp — same call, two separate bodies
#include <cstdio>

#include "pointer.hpp"

int main() {
    int x = 7;
    int* p = &x;
    std::printf("%s %d\n", Access<int>::name(), Access<int>::get(x));
    std::printf("%s %d\n", Access<int*>::name(), Access<int*>::get(p));
    return 0;
}

value 7
pointer 7

MT8. Access<int*> comes not from the primary template but from the partial specialization that captures the pointer pattern, and it reads the value from where the pointer points. Both uses print seven, but the bodies behind them are different; which one is used is decided at compile time and no query is left at run time. The kind of this lesson still stays memory: the memory measurement is only the Pack<bool> row, and this section is a supporting example that shows the limit of specialization.

Full Specialization of a Function Template

Function templates cannot be partially specialized, but they can be fully specialized. There is a trap here concerning headers: a full specialization is no longer a template but an ordinary function, so if it is defined in a header it must be inline; otherwise every unit that includes the header defines the same function and the linker sees a duplicate definition. The primary template label below says other for every type, and the full specialization for int says integer.

// label.hpp — a function template and an inline full specialization
#ifndef LABEL_HPP
#define LABEL_HPP

template <typename T>
const char* label() { return "other"; }

template <>
inline const char* label<int>() { return "integer"; }

#endif

// label-select.cpp — which label was chosen
#include <cstdio>

#include "label.hpp"

int main() {
    std::printf("%s %s %s\n", label<double>(), label<int>(), label<long>());
    return 0;
}

other integer other

MT9. label<int> goes to the specialization, while label<double> and label<long> go to the primary template; the primary template yields two separate bodies, the specialization one. Here too the selection ends at compile time. For function templates, overloading is often preferred over specialization, because overload resolution picks candidates by different rules than specialization; the Overload Resolution and SFINAE lesson shows the difference.

std::vector<bool> and the Proxy Object

The standard library uses this idea itself: std::vector<bool> is a specialization, and the standard suggests for it a representation that packs the values into bits and saves space; common implementations do this the way Pack<bool> does. The result has a cost: it is not possible to take the address of an element, because the element is not a separate bool object. For this reason operator[] returns not the element itself but a proxy object that reads and writes that bit. Trying to take the address of an element is not run here; the defined alternative is to work with the proxy object.

// proxy.cpp — access to a vector<bool> element through a proxy object
#include <cstdio>
#include <vector>

int main() {
    std::vector<bool> v(8, false);
    v[3] = true;      // operator[] returns a proxy object, the assignment writes the bit
    bool three = v[3];   // the proxy object converts to bool

    int filled = 0;
    for (std::size_t i = 0; i < v.size(); ++i) filled += v[i];
    std::printf("filled %d, v[3] %d\n", filled, three ? 1 : 0);
    return 0;
}

filled 1, v[3] 1

Packing the bits pays back the cost gained in memory somewhere else. Where, the next section measures.

The Most Specialized Specialization Wins

More than one partial specialization can match the same type. The compiler picks the one whose pattern is more specific than the others: the T* pattern is more general than the const T* pattern, because const int* fits both and the second pattern is a subset of the first. If none is more specific than the other, the use is ambiguous and compilation stops; I leave that to prose, because code that does not compile is not written as a block. A full specialization always comes before a partial one.

// most-specific.cpp — the most specific pattern is chosen
#include <cstdio>

template <typename T>
struct TypeName { static const char* name() { return "generic"; } };

template <typename T>
struct TypeName<T*> { static const char* name() { return "pointer"; } };

template <typename T>
struct TypeName<const T*> { static const char* name() { return "const pointer"; } };

template <>
struct TypeName<int*> { static const char* name() { return "int pointer"; } };

int main() {
    std::printf("int          %s\n", TypeName<int>::name());
    std::printf("double*      %s\n", TypeName<double*>::name());
    std::printf("const char*  %s\n", TypeName<const char*>::name());
    std::printf("int*         %s\n", TypeName<int*>::name());
    return 0;
}

int          generic
double*      pointer
const char*  const pointer
int*         int pointer

MT10. int fits no pattern, so the primary template stays. double* fits only the T* pattern. const char* fits both the T* and the const T* pattern, and the second is more specific. For int* there is a full specialization, and it beats the partial one. This selection ends at compile time: one class definition is chosen for every type used, and no query is left at run time.

Function Templates Cannot Be Partially Specialized

Partial specialization exists only for class templates; for a function template only a full specialization can be written. The partial equivalent on the function side is overloading: two separate function templates are written for T and T*, and overload resolution decides which one is more specific. That decision is the subject of the next lessons; here seeing the result is enough. Full specializations of function templates, for their part, are mostly replaced with overloading, because specializations do not take part in overload resolution: the compiler first chooses among the primary templates, and then uses the specialization of the template it chose.

// function-overload.cpp — overloading instead of partial specialization for functions
#include <cstdio>

template <typename T>
const char* describe(T) { return "value"; }

template <typename T>
const char* describe(T*) { return "pointer"; }

int main() {
    int n = 5;
    std::printf("describe(n)  %s\n", describe(n));
    std::printf("describe(&n) %s\n", describe(&n));
    return 0;
}

describe(n)  value
describe(&n) pointer

MT11. For describe(n) only the T template is viable. For describe(&n) both are viable and the T* template is more specific, so it is chosen. What partial specialization does on the class side comes down to what overload resolution does on the function side; in both, the selection ends at compile time and the cost is in the compile kind.

The Bounding Measurement

Pack<bool> lowered the memory cost by fitting eight values into one slot. But to read a bit, the slot first has to be shifted and then masked; Pack<int> reads the value directly. The counter counts two steps (the shift and the mask) inside Pack<bool>::read and zero steps inside Pack<int>::read. The program below makes eight reads on each pack.

// read-steps.cpp — steps per read
#include <cstdio>

#include "pack.hpp"

template <typename T>
static void count_steps(const char* name, const Pack<T>& p) {
    int steps = 0;
    int reads = 0;
    for (int i = 0; i < 8; ++i) {
        p.read(i, steps);
        ++reads;
    }
    std::printf("%s reads=%d steps=%d per_read=%d\n", name, reads, steps, steps / reads);
}

int main() {
    Pack<int> general;
    Pack<bool> packed;
    count_steps("int ", general);
    count_steps("bool", packed);
    return 0;
}

int  reads=8 steps=0 per_read=0
bool reads=8 steps=16 per_read=2

MT12. Pack<bool> pays two steps on every read, Pack<int> pays zero. The cost gained in memory returned to run time: the slot count dropped from eight to one, but every read asks for a shift and a mask. The central measurement of this lesson stays in the memory kind, because the number in the core is the slot count; the steps per read are the bound that shows the cost is not gained in one direction only. The step count here is a model: the shift and the mask are counted by the counter lines, and it is not a measured time.

Summary

• The mechanism measured in this lesson moves the cost to the memory kind: Pack<bool> keeps eight values in one slot (int=8 bool=1).
• A full specialization (template <>) replaces the body of a single type; a partial specialization captures a pattern of parameters; when several match, the most specialized one is chosen.
• A specialization must be visible before the first instantiation of the type; function templates cannot be partially specialized, and their full specialization must be inline in a header.
• A specialization does not inherit the members of the primary template; a pattern like Access<T*> is captured with a partial specialization, and the author keeps the interface contract.
• The address of a std::vector<bool> element cannot be taken; operator[] returns a proxy object.
• Reading from a bit asks for two steps on every access: the cost gained in memory returns to run time.

Next Step

In this lesson the specialization put the cost into the slot, and the step per read carried it back to run time. The next lesson turns the number of template parameters from a constant into a variable: as a parameter pack is expanded, it measures how many bodies the compiler produces.