【C++ Templates（18）】基于类型属性的重载

2018-06-16 本文已影响35人 downdemo

想基于模板实参属性重载函数模板是很自然想做的，如

template<typename Number> void f(Number); // only for numbers
template<typename Container> void f(Container);// only for containers

然而，C++现在还不提供任何直接表达基于类型属性重载的方法，两个f其实是相同的函数模板声明，因为比较两个函数模板时，模板参数会被忽略。幸运的是，有许多技术可以用于替代基于类型属性的函数模板重载

算法特化

函数模板重载的一个常见动机是提供更多特化版本的算法，比如交换两个值的swap()

template<typename T>
void swap(T& x, T& y)
{
    T tmp(x);
    x = y;
    y = tmp;
}

这个实现涉及三个拷贝操作，然而对一些类型可以提供更高效的操作，比如Array<T>，元素为指向数组内容和长度的指针

template<typename T>
void swap(Array<T>& x, Array<T>& y)
{
    swap(x.ptr, y.ptr);
    swap(x.len, y.len);
}

这个实现更高效，因为它利用了Array<T>可用的附加属性，是更特殊的特化
为一个通用算法引入更特化的变体的设计与优化方法称为算法特化
算法特化实现的关键是更特化变体自动选择的属性，甚至不需要调用者意识到变体的存在
不是所有概念上更特化的算法变体都可以直接翻译成提供正确的局部排序行为的函数模板，比如下例中提出的替代方案更广泛适用，advanceIter()函数把迭代器x移动n步，通用算法可用于任何输入的迭代器

template<typename InputIterator, typename Distance>
void advanceIter(InputIterator& x, Distance n)
{
    while (n > 0) { // linear time
        ++x;
        --n;
    }
}

对一个提供随机访问操作的迭代器类，可以提供更高效的实现

template<typename RandomAccessIterator, typename Distance>
void advanceIter(RandomAccessIterator& x, Distance n) {
    x += n; // constant time
}

不幸的是，定义这两个模板将导致编译错误，因为函数模板的重载会忽略模板参数

标签调度（Tag Dispatching）

算法特化的一个方法是，用能识别变体的独有的类型标签化不同的实现变体，比如用标准库的迭代器类别tag type来识别advanceIter()不同的实现变体

template<typename Iterator, typename Distance>
void advanceIterImpl(Iterator& x, Distance n, std::input_iterator_tag)
{
    while (n > 0) { // linear time
        ++x;
        --n;
    }
}
template<typename Iterator, typename Distance>
void advanceIterImpl(Iterator& x, Distance n,
    std::random_access_iterator_tag) {
    x += n; // constant time
}

之后，advanceIter()函数模板本身用适当的标签转发实参

template<typename Iterator, typename Distance>
void advanceIter(Iterator& x, Distance n)
{
    advanceIterImpl(x, n,
        typename
        std::iterator_traits<Iterator>::iterator_category());
}

trait类std::iterator_traits的成员类型iterator_category提供了迭代器类别，迭代器类别是_tag类型之一。标准库中可用的tag定义如下

namespace std {
    struct input_iterator_tag { };
    struct output_iterator_tag { };
    struct forward_iterator_tag : public input_iterator_tag { };
    struct bidirectional_iterator_tag : public forward_iterator_tag { };
    struct random_access_iterator_tag : public bidirectional_iterator_tag { };
}

高效使用tag dispatching的关键在于标签间的关系，两个advanceIterImpl()变体被标签为std::input_iterator_tag和std::random_access_iterator_tag，因为后者派生自前者，因此无论何时用随机访问迭代器调用advanceIterImpl()都将选择更特化的使用后者的算法变体
tag dispatching适合有自然的分层结构的被算法使用的属性，和已有的一系列提供标签值的trait。当算法特化依赖于特定类型属性，如T是否有一个平凡的拷贝赋值运算符，tag dispatching则是不方便的，这需要更强力的技术

启用/禁用函数模板

标准库提供了std::enable_if<>，这里引入一个对应的EnableIf别名模板实现。和std::enable_if<>一样，EnableIf别名模板可用于启用或禁用特定条件下的特定函数模板，比如随机访问版本的advanceIter()算法可以实现如下

template<typename Iterator>
constexpr bool IsRandomAccessIterator =
    IsConvertible<
        typename std::iterator_traits<Iterator>::iterator_category,
        std::random_access_iterator_tag>;

template<typename Iterator, typename Distance>
EnableIf<IsRandomAccessIterator<Iterator>>
advanceIter(Iterator& x, Distance n) {
    x += n; // constant time
}

EnableIf简单实现如下

// typeoverload/enableif.hpp

template<bool, typename T = void>
struct EnableIfT {
};

template< typename T>
struct EnableIfT<true, T> {
    using Type = T;
};

template<bool Cond, typename T = void>
using EnableIf = typename EnableIfT<Cond, T>::Type;

现在建立了激活对应用类型更特化模板的方法，然而这是不够的，还需要取消更不特化的模板，因为编译器不会排序两个模板，如果两个版本都能适用则报告二义性错误。实现这点只要对更不特化的模板使用同样的EnableIf模式，非随机访问迭代器版本的advanceIter()实现如下

template<typename Iterator, typename Distance>
EnableIf<!IsRandomAccessIterator<Iterator>>
advanceIter(Iterator& x, Distance n)
{
    while (n > 0) { // linear time
        ++x;
        --n;
    }
}

提供多重特化

一个新的advanceIter()算法变体：这次想允许指定一个负距离往回移动。对输入迭代器明显无效而对访问迭代器有效。然而标准库包含了双向迭代器的概念，它不需要随机访问就能往回移动。实现这个情况需要稍微复杂一些的逻辑：每个函数模板必须用EnableIf指定一个与其他变体互斥的条件，这导致下列条件
- 随机访问迭代器：随机访问情况（常数时间，向后或向前）
- 双向迭代器和非随机访问：双向情况（线性时间，向后或向前）
- 输入迭代器和非双向：通用情况（线性时间，向后）
下列函数模板实现这点

// typeoverload/advance2.hpp

#include <iterator>
// implementation for random access iterators:
template<typename Iterator, typename Distance>
EnableIf<IsRandomAccessIterator<Iterator>>
advanceIter(Iterator& x, Distance n) {
    x += n; // constant time
}

template<typename Iterator>
constexpr bool IsBidirectionalIterator =
    IsConvertible<
    typename std::iterator_traits<Iterator>::iterator_category,
    std::bidirectional_iterator_tag>;

// implementation for bidirectional iterators:
template<typename Iterator, typename Distance>
EnableIf<IsBidirectionalIterator<Iterator> &&
    !IsRandomAccessIterator<Iterator>>
advanceIter(Iterator& x, Distance n) {
    if (n > 0) {
        for ( ; n > 0; ++x, --n) { // linear time
        }
    } else {
        for ( ; n < 0; --x, ++n) { //linear time
        }
    }
}

// implementation for all other iterators:
template<typename Iterator, typename Distance>
EnableIf<!IsBidirectionalIterator<Iterator>>
advanceIter(Iterator& x, Distance n) {
    if (n < 0) {
        throw "advanceIter(): invalid iterator category for negative n";
    }
    while (n > 0) { // linear time
        ++x;
        --n;
    }
}

EnableIf在哪运行

EnableIf常用于函数模板的返回类型，但对构造函数模板或转换函数模板不可用，因为他们没有特定的返回类型。此外，EnableIf的使用会使返回类型难读，为此可以把EnableIf嵌入一个默认模板实参

// typeoverload/container1.hpp

#include <iterator>
#include "enableif.hpp"
#include "isconvertible.hpp"

template<typename Iterator>
constexpr bool IsInputIterator =
    IsConvertible<
        typename std::iterator_traits<Iterator>::iterator_category,
        std::input_iterator_tag>;

template<typename T>
class Container {
public:
    // construct from an input iterator sequence:
    template<typename Iterator,
        typename = EnableIf<IsInputIterator<Iterator>>>
    Container(Iterator first, Iterator last);

    // convert to a container so long as the value types are convertible:
    template<typename U, typename = EnableIf<IsConvertible<T, U>>>
    operator Container<U>() const;
};

然而，这有一个问题，如果尝试添加另一个重载，比如一个用于随机访问迭代器的更高效的Container构造函数，将导致错误

// construct from an input iterator sequence:
template<typename Iterator,
    typename = EnableIf<IsInputIterator<Iterator> &&
    !IsRandomAccessIterator<Iterator>>>
Container(Iterator first, Iterator last);

template<typename Iterator,
    typename = EnableIf<IsRandomAccessIterator<Iterator>>>
Container(Iterator first, Iterator last); // ERROR: 重复声明构造函数模板

原因是两个构造函数模板都有默认模板实参，但确定两个模板是否等价时不会考虑默认模板实参。为了缓和这个问题，可以添加另一个默认模板参数，这样两个构造函数模板就有不同数量的模板参数

// construct from an input iterator sequence:
template<typename Iterator,
    typename = EnableIf<IsInputIterator<Iterator> &&
    !IsRandomAccessIterator<Iterator>>>
Container(Iterator first, Iterator last);

template<typename Iterator,
    typename = EnableIf<IsRandomAccessIterator<Iterator>>,
    typename = int> // extra dummy parameter to enable both constructors
Container(Iterator first, Iterator last); // OK now

编译期if

C++17的constexpr if特性在许多情况下避免了对EnableIf的需求，比如C++17中可以重写advanceIter()如下

// typeoverload/advance3.hpp

template<typename Iterator, typename Distance>
void advanceIter(Iterator& x, Distance n) {
    if constexpr(IsRandomAccessIterator<Iterator>) {
        // implementation for random access iterators:
        x += n; // constant time
    }

    else if constexpr(IsBidirectionalIterator<Iterator>) {
        // implementation for bidirectional iterators:
        if (n > 0) {
            for ( ; n > 0; ++x, --n) { // linear time for positive n
            }
        } else {
            for ( ; n < 0; --x, ++n) { // linear time for negative n
            }
        }
    }

    else {
        // implementation for all other iterators that are at least input iterators:
        if (n < 0) {
            throw "advanceIter(): invalid iterator category for negative n";
        }
        while (n > 0) { // linear time for positive n only
            ++x;
            --n;
        }
    }
}

这样更清晰，更特化的代码路径将只在能支持类型时实例化，在涉及不适用于所有迭代器的操作（如+=）时更安全
然而constexpr if的缺点是，要求通用的组件能在函数模板体内完整表达。对于一些情况仍需要EnableIf
- 调用了不同的接口
- 需要不同的类定义
- 有效的实例化不应该存在于某个模板实参列表
用下面的模式实现最后一种情况看起来很吸引人

template<typename T>
void f(T p) {
    if constexpr (condition<T>::value) {
        // do something here...
    }
    else {
        // not a T for which f() makes sense:
        static_assert(condition<T>::value, "can't call f() for such a T");
    }
}

但不建议这样做，因为它不支持SFINAE：f<T>()没有从候选列表中移除，可能抑制另一个重载解析输出。使用EnableIf f<T>()，当替换EnableIf<...>失败时则将被一起移除

Concepts

以上技术通常比较笨拙，且使用大量编译器资源，出错时将导致难懂的诊断信息。为此可能将添加一项称为concepts的特性，比如希望重载的container构造函数简单看起来如下

// typeoverload/container4.hpp

template<typename T>
class Container {
public:
    // construct from an input iterator sequence:
    template<typename Iterator>
    requires IsInputIterator<Iterator>
    Container(Iterator first, Iterator last);

    // construct from a random access iterator sequence:
    template<typename Iterator>
    requires IsRandomAccessIterator<Iterator>
    Container(Iterator first, Iterator last);

    // convert to a container so long as the value types are convertible:
    template<typename U>
    requires IsConvertible<T, U>
    operator Container<U>() const;
};

requires子句描述模板的要求，如果不满足任何要求，模板将不被考虑为候选，这相当于EnableIf的更直接表达。但requires子句比起EnableIf有一个额外的好处是，constraint subsumption提供一个基于requires子句的顺序，而不再需要tag dispatching。此外，requires子句可用于非模板，如提供一个仅当T可用<比较的sort()成员函数

template<typename T>
class Container {
public:
    ...
    requires HasLess<T>
    void sort() {
        ...
    }
};

类特化

类模板局部特化可提供可选对特定模板实参的特化实现，就像为函数模板使用重载一样。此外，它可以基于模板实参属性理解不同的局部特化。一个通用的以key和value类型作为模板参数的Dictionary类模板的简单实现如下

template<typename Key, typename Value>
class Dictionary {
private:
    vector<pair<Key const, Value>> data;
public:
    //subscripted access to the data:
    value& operator[](Key const& key)
    {
        // search for the element with this key:
        for (auto& element : data) {
            if (element.first == key){
                return element.second;
            }
        }
        // there is no element with this key; add one
        data.push_back(pair<Key const, Value>(key, Value()));
        return data.back().second;
    }
    ...
};

启用/禁用类模板

启用/禁用类模板的不同实现的方法就是启用/禁用类模板的局部特化。为了对类模板局部特化使用EnableIf，先引入一个未命名的默认模板参数

template<typename Key, typename Value, typename = void>
class Dictionary
{
    ... // vector implementation as above
};

这个新模板参数充当EnableIf的锚，它可以嵌入map版本的Dictionary局部特化的模板实参列表

template<typename Key, typename Value>
class Dictionary<Key, Value,
    EnableIf<HasLess<Key>>>
{
private:
    map<Key, Value> data;
public:
    value& operator[](Key const& key) {
        return data[key];
    }
    ...
};

不同于重载的函数模板，不需要为基本模板禁用任何条件，因为任何局部特化都优先于基本模板。然而，当为哈希操作的key添加另一个实现，则需要确保局部特化的条件互斥

template<typename Key, typename Value, typename = void>
class Dictionary
{
    ... // vector implementation as above
};

template<typename Key, typename Value>
class Dictionary<Key, Value,
    EnableIf HasLess Key> && !HasHash Key>>> {
{
    ... // map implementation as above
};

template typename Key, typename Value>
class Dictionary Key, Value,
    EnableIf HasHash Key>>>
{
private:
    unordered_map Key, Value> data;
public:
    value& operator[](Key const& key) {
        return data[key];
    }
    ...
};

用于类模板的Tag Dispatching

tag dispatching也能用于选择类模板局部特化。定义一个函数对象类型Advance<Iterator>，功能类似于advanceIter()算法。提供通用实现（用于输入迭代器）和用于双向和随机访问迭代器的特化实现，基于一个辅助的trait BestMatchInSet为迭代器类别标签选择最佳匹配

// primary template (intentionally undefined):
template<typename Iterator,
    typename Tag =
        BestMatchInSet<
            typename std::iterator_traits<Iterator>::iterator_category,
            std::input_iterator_tag,
            std::bidirectional_iterator_tag,
            std::random_access_iterator_tag>>
class Advance;

// general, linear-time implementation for input iterators:
template<typename Iterator>
class Advance<Iterator, std::input_iterator_tag>
{
public:
    using DifferenceType =
        typename std::iterator_traits<Iterator>::difference_type;
    void operator() (Iterator& x, DifferenceType n) const
    {
        while (n > 0) {
            ++x;
            --n;
        }
    }
};

// bidirectional, linear-time algorithm for bidirectional iterators:
template<typename Iterator>
class Advance<Iterator, std::bidirectional_iterator_tag>
{
public:
    using DifferenceType =
        typename std::iterator_traits<Iterator>::difference_type;
    void operator() (Iterator& x, DifferenceType n) const
    {
        if (n > 0) {
            while (n > 0) {
                ++x;
                --n;
            }
        } else {
            while (n < 0) {
                --x;
                ++n;
            }
        }
    }
};

// bidirectional, constant-time algorithm for random access iterators:
template<typename Iterator>
class Advance<Iterator, std::random_access_iterator_tag>
{
public:
    using DifferenceType =
        typename std::iterator_traits<Iterator>::difference_type;
    void operator() (Iterator& x, DifferenceType n) const
    {
        x += n;
    }
};

这个构建和函数模板的tag dispatching构建很相似，然而挑战是写trait BestMatchInSet，本质上它将说明给定一个迭代器类型标签后选用下列哪个重载，并报告它的参数类型

void f(std::input_iterator_tag);
void f(std::bidirectional_iterator_tag);
void f(std::random_access_iterator_tag);

最初替代重载解析的方法实际上就是使用重载解析

// construct a set of match() overloads for the types in Types...:
template<typename... Types>
struct MatchOverloads;

// basis case: nothing matched:
template<>
struct MatchOverloads<> {
    static void match(...);
};

// recursive case: introduce a new match() overload:
template<typename T1, typename... Rest>
struct MatchOverloads<T1, Rest...> : public MatchOverloads<Rest...>
{
    static T1 match(T1); // introduce overload for T1
    using MatchOverloads<Rest...>::match; // collect overloads from bases
};

// find the best match for T in Types...:
template<typename T, typename... Types>
struct BestMatchInSetT {
    using Type = decltype(MatchOverloads<Types...>::match(declval<T>()));
};

template<typename T, typename... Types>
using BestMatchInSet = typename BestMatchInSetT<T, Types...>::Type;

MatchOverloads模板使用递归继承来对每个输入Types的类型声明一个match()函数，每个递归的MatchOverloads局部特化的实例化引入一个新的用于列表中下个类型的match()函数，随后它使用一个using声明引入定义在基类中的match()函数以处理列表中剩余的类型。递归地应用后，结果是一系列对应于给定类型的match()重载，每个返回它自己的参数类型，BestMatchInSetT随后传递一个T对象给这些match()并产生最佳匹配的返回类型，如果没有函数匹配，void将标示错误

实例化安全的（instantiation-safe）模板

EnableIf的本质是仅当模板实参满足某些准则才启用一个特定的模板或局部特化，比如advanceIter()的最有效形式检查迭代器实参的类别可转换为std::random_access_iterator_tag，表明该算法对各种随机访问迭代器可行。极端地，把模板执行在模板实参上的每个操作编码为EnableIf条件的一部分，这样的模板实例化将永远不会失败，因为不提供要求操作的模板实参将造成一个推断错误（通过EnableIf）而不是允许实例化执行，这样的模板称为实例化安全的模板
先从最基本的min()模板出发

template<typename T>
T const& min(T const& x, T const& y)
{
    if (y < x) {
        return y;
    }
    return x;
}

这个模板要求类型T有一个<操作符来比较两个T值，然后把比较结果转为布尔值，下面的LessResultT trait可检查<操作符

// typeoverload/lessresult.hpp

#include <utility> // for declval()
#include <type_traits> // for true_type and false_type

template<typename T1, typename T2>
class HasLess {
    template<typename T> struct Identity;
    template<typename U1, typename U2> static std::true_type
        test(Identity<decltype(std::declval<U1>() < std::declval<U2>())>*);
    template<typename U1, typename U2> static std::false_type
        test(...);
public:
    static constexpr bool value = decltype(test<T1, T2>(nullptr))::value;
};

template<typename T1, typename T2, bool HasLess>
class LessResultImpl {
public:
    using Type = decltype(std::declval<T1>() < std::declval<T2>());
};

template<typename T1, typename T2>
class LessResultImpl<T1, T2, false> {
};

template<typename T1, typename T2>
class LessResultT
: public LessResultImpl<T1, T2, HasLess<T1, T2>::value> {
};

template<typename T1, typename T2>
using LessResult = typename LessResultT<T1, T2>::Type;

这个trait可以组合IsConvertible trait使得min()实例化安全

// typeoverload/min2.hpp

#include "isconvertible.hpp"
#include "lessresult.hpp"

template<typename T>
EnableIf<IsConvertible<LessResult<T const&, T const&>, bool>,
    T const&>
min(T const& x, T const& y)
{
    if (y < x) {
        return y;
    }
    return x;
}

对各种有不同的<操作符的类型调用min()是有益的

// typeoverload/min.cpp

#include"min.hpp"

struct X1 { };
bool operator< (X1 const&, X1 const&) { return true; }

struct X2 { };
bool operator<(X2, X2) { return true; }

struct X3 { };
bool operator<(X3&, X3&) { return true; }

struct X4 { };

struct BoolConvertible {
    operator bool() const { return true; } // implicit conversion to bool
};
struct X5 { };
BoolConvertible operator< (X5 const&, X5 const&)
{
    return BoolConvertible();
}

struct NotBoolConvertible { // no conversion to bool
};
struct X6 { };
NotBoolConvertible operator< (X6 const&, X6 const&)
{
    return NotBoolConvertible();
}

struct BoolLike {
    explicit operator bool() const { return true; } // explicit conversion to bool
};
struct X7 { };
BoolLike operator< (X7 const&, X7 const&) { return BoolLike(); }

int main()
{
    min(X1(), X1()); // X1 can be passed to min()
    min(X2(), X2()); // X2 can be passed to min()
    min(X3(), X3()); // ERROR: X3 cannot be passed to min()
    min(X4(), X4()); // ERROR: X4 can be passed to min()
    min(X5(), X5()); // X5 can be passed to min()
    min(X6(), X6()); // ERROR: X6 cannot be passed to min()
    min(X7(), X7()); // UNEXPECTED ERROR: X7 cannot be passed to min()
}

其中ERROR不来自min()的函数体，因为他们有非实例化安全的变体，他们将抱怨没有合适的min()，因为唯一的选项被SFINAE终止了。EnableIf只允许对满足要求的模板实参实例化，所以永远不会得到一个来自min()体内的错误。此外，如果有一些可能适用于这些类型的min()重载，重载解析将选用其中一个而非失败
X7阐述了实例化安全模板实现上的一些细微差别，特殊地，如果X7传给非实例化安全的min()，实例化将成功。然而实例化安全的min()将拒绝它，因为BoolLike不能隐式转换为bool
然而，坚持要有通用的到bool的隐式转换，对实例化安全的模板会造成过多约束，即EnableIf中的要求比实际模板实例化所需要的更强。另一方面，如果完全没有转换到bool的要求，min()模板将变得约束过少，这将允许一些模板实参造成实例化错误
为了修正实例化安全的min()，需要一个trait来确定T能否根据语境转换为bool。在这个trait的定义中，控制流语句是无用的，因为语句不能发生于SFINAE语境，逻辑操作也不能发生，因为它可以为任何类型重载。幸运的是，三元运算符?:是一个不能重载的表达式，因此它可以用于测试一个类型能否在语境中转换为bool

// typeoverload/iscontextualbool.hpp

#include <utility> // for declval()
#include <type_traits> // for true_type and false_type

template<typename T>
class IsContextualBoolT {
private:
    template<typename T> struct Identity;
    template<typename U> static std::true_type
        test(Identity<decltype(declval<U>()? 0 : 1)>*);
    template<typename U> static std::false_type
        test(...);
public:
    static constexpr bool value = decltype(test<T>(nullptr))::value;
};

template<typename T>
constexpr bool IsContextualBool = IsContextualBoolT<T>::value;

使用这个新trait可以提供一个EnableIf中含有正确需求的实例化安全的min()

// typeoverload/min3.hpp

#include "iscontextualbool.hpp"
#include "lessresult.hpp"

template<typename T>
EnableIf<IsContextualBool<LessResult<T const&, T const&>>, T const&>
min(T const& x, T const& y)
{
    if (y < x) {
        return y;
    }
    return x;
}

在标准库中

【C++ Templates（18）】基于类型属性的重载

算法特化

标签调度（Tag Dispatching）

启用/禁用函数模板

提供多重特化

EnableIf在哪运行

编译期if

Concepts

类特化

启用/禁用类模板

用于类模板的Tag Dispatching

实例化安全的（instantiation-safe）模板

在标准库中

猜你喜欢

热点阅读