17-基于类型属性的重载

  • 基于模板实参属性重载函数模板是很自然的需求,比如
template<typename Number> void f(Number); // only for numbers
template<typename Container> void f(Container); // only for containers
  • 然而,C++现在还不提供任何直接表达基于类型属性重载的方法,两个f其实是相同的函数模板声明。幸运的是,有许多技术可以用于替代基于类型属性的重载

算法特化

  • 函数模板重载的一个常见动机是提供更多特化版本的算法
template<typename T>
void swap(T& x, T& y)
{
  T tmp(x);
  x = y;
  y = tmp;
}
  • 这个实现涉及三个拷贝操作。对一些类型可以提供更高效的操作,为一个通用算法引入更专用(specialized)的变体称为算法特化
template<typename T>
void swap(Array<T>& x, Array<T>& y)
{
  swap(x.ptr, y.ptr);
  swap(x.len, y.len);
}
  • 算法特化实现的关键是更专用的变体的属性被自动选择,甚至不需要调用者意识到变体的存在。但不是所有概念上更专用的变体都可以像上面这样重载,比如基于迭代器类型实现不同的算法
template<typename InputIterator, typename Distance>
void advanceIter(InputIterator& x, Distance n)
{
  while (n > 0)
  { // 线性时间
    ++x;
    --n;
  }
}

template<typename RandomAccessIterator, typename Distance>
void advanceIter(RandomAccessIterator& x, Distance n) // 错误:重定义
{
  x += n; // 常数时间
}
  • 这两个模板本质上是相同的,为此需要引入一个用于区分的标签

标签分派(Tag Dispatching)

template<typename Iterator, typename Distance>
void advanceIterImpl(Iterator& x, Distance n, std::input_iterator_tag)
{
  while (n > 0)
  { // 线性时间
    ++x;
    --n;
  }
}

template<typename Iterator, typename Distance>
void advanceIterImpl(Iterator& x, Distance n, std::random_access_iterator_tag)
{
  x += n; // 常数时间
}

template<typename Iterator, typename Distance>
void advanceIter(Iterator& x, Distance n)
{
  advanceIterImpl(x, n,
    typename std::iterator_traits<Iterator>::iterator_category());
}
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 {};
}
  • 两个advanceIterImpl变体分别标签为std::input_iterator_tag和std::random_access_iterator_tag,后者派生自前者,因此对随机访问迭代器调用advanceIterImpl时就会选择更专用的使用后者的算法变体
  • 标签分派适合有自然分层结构的属性,当算法特化依赖于特定类型属性(如T是否有一个平凡的拷贝赋值运算符)时,则需要更强力的技术

启用/禁用函数模板

  • 标准库提供了std::enable_if用于启用或禁用特定条件下的特定函数模板,这里自定义一个简单实现
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;
  • 现在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; // 常数时间
}

template<typename Iterator, typename Distance>
EnableIf<!IsRandomAccessIterator<Iterator>> // 必须指定此条件,否则两个模板一样特殊
advanceIter(Iterator& x, Distance n)
{
  while (n > 0)
  { // 线性时间
    ++x;
    --n;
  }
}
  • 现在想实现负距离往回移动,这需要稍微复杂一些的逻辑,每个函数模板需要指定一个与其他变体互斥的条件
// 随机访问迭代器
template<typename Iterator, typename Distance>
EnableIf<IsRandomAccessIterator<Iterator>>
advanceIter(Iterator& x, Distance n)
{
  x += n; // 常数时间
}

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

// 双向迭代器且非随机访问迭代器
template<typename Iterator, typename Distance>
EnableIf<IsBidirectionalIterator<Iterator> &&
  !IsRandomAccessIterator<Iterator>>
advanceIter(Iterator& x, Distance n)
{
  if (n > 0)
  {
    for (; n > 0; ++x, --n) {} // 线性时间
  }
  else
  {
    for (; n < 0; --x, ++n) {} // 线性时间
  }
}

// 其他迭代器(输入迭代器且非双向迭代器)
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)
  { // 线性时间
    ++x;
    --n;
  }
}
  • EnableIf常用于函数模板的返回类型,这会降低代码可读性,并且不能用于没有返回类型的构造函数模板或转换函数模板,为此可以把EnableIf写为一个默认模板实参
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;
};
  • 但使用EnableIf作为默认实参时,添加重载将导致错误,因为确定两个模板是否等价时不会考虑默认模板实参
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); // 错误:重复声明
  • 为此可以添加一个额外的模板参数,以使两个模板有不同数量的模板参数
// 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 constexpr

  • C++17的if constexpr在许多情况下避免了对EnableIf的需求
template<typename Iterator, typename Distance>
void advanceIter(Iterator& x, Distance n) {
  if constexpr (IsRandomAccessIterator<Iterator>)
  {
    x += n;
  }
  else if constexpr (IsBidirectionalIterator<Iterator>)
  {
    if (n > 0)
    {
      for (; n > 0; ++x, --n) {}
    }
    else
    {
      for (; n < 0; --x, ++n) {}
    }
  }
  else
  {
    if (n < 0)
    {
      throw "advanceIter(): invalid iterator category for negative n";
    }
    while (n > 0)
    {
      ++x;
      --n;
    }
  }
}
  • 但if constexpr要求通用的组件能在函数模板体内完整表达。对于一些情况仍需要EnableIf
    • 调用了不同的接口
    • 需要不同的类定义
    • 有效的实例化不应该存在于某个模板实参列表
  • 如下实现最后一种情况看起来没问题,但它不支持SFINAE,替换失败时模板不被丢弃可能导致抑制另一个重载版本,而使用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");
  }
}

Concepts

  • 以上技术比较笨拙,使用了大量编译器资源,出错时将造成复杂的诊断信息。C++20可能引入Concepts来简化这个问题
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的更直接表达,且带有顺序而不再需要标签分派,此外还能用于非模板
template<typename T>
class Container {
 public:
  requires HasLess<T>
  void sort()
  {
    ...
  }
};

类特化

  • 类模板偏特化就像为函数模板使用重载一样。对于如下的基于std::vector实现的类模板,如果K支持operator<就可以提供一个基于std::map的更高效的实现,类似地,如果K支持哈希操作就可以提供基于std::unordered_map的更高效的实现
template<typename K, typename V>
class Dictionary {
 public:
  //subscripted access to the data:
  value& operator[](const K& k)
  {
    // search for the element with this k:
    for (auto& element : data)
    {
      if (element.first == k)
      {
        return element.second;
      }
    }
    // there is no element with this k; add one
    data.push_back(std::pair<const K, V>(k, V{}));
    return data.back().second;
  }
  ...
 private:
  std::vector<std::pair<const K, V>> data;
};

启用/禁用类模板

  • 启用/禁用类模板的不同实现的方法就是启用/禁用类模板的偏特化。为了对类模板偏特化使用EnableIf,先引入一个未命名的默认模板参数
template<typename K, typename V, typename = void>
class Dictionary {
  ... // std::vector implementation as above
};
  • 这个新模板参数相当于EnableIf的锚
template<typename K, typename V>
class Dictionary<K, V, EnableIf<HasLess<K>>> {
 public:
  value& operator[](const K& k)
  {
    return data[k];
  }
  ...
 private:
  std::map<K, V> data;
};
  • 类模板偏特化优先于原始模板,所以不需要像函数模板那样为原始模板禁用条件,但偏特化之间的条件必须互斥
template<typename K, typename V, typename = void>
class Dictionary {
  ... // std::vector implementation as above
};

template<typename K, typename V>
class Dictionary<K, V, EnableIf<HasLess<K> && !HasHash<K>>> {
  ... // std::map implementation as above
};

template typename K, typename V>
class Dictionary K, V, EnableIf<HasHash<K>>> {
 public:
  value& operator[](const K& k)
  {
    return data[k];
  }
  ...
 private:
  unordered_std::map K, V> data;
};

用于类模板的标签分派

  • 标签分派也能用于选择类模板偏特化
// 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)
    {
      for (; n > 0; ++x, --n) {}
    }
    else
    {
      for (; 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;
  }
};
  • BestMatchInSet的行为相当于对一个迭代器类型标签,在如下重载中进行选择,再给出参数类型
void f(std::input_iterator_tag);
void f(std::bidirectional_iterator_tag);
void f(std::random_access_iterator_tag);
  • 因此BestMatchInSet的实现方法就是借助重载解析
// construct a set of f() overloads for the types in Types...:
template<typename... Types>
struct A;

// basis case: nothing matched:
template<>
struct A<> {
  static void f(...); // 如果下面对所有参数尝试匹配失败,则匹配此版本
};

// recursive case: introduce a new f() overload:
template<typename T1, typename... Rest>
struct A<T1, Rest...> : public A<Rest...> { // 递归继承
  static T1 f(T1); // 尝试匹配第一个参数,如果匹配则返回类型T1就是所需Type
  using A<Rest...>::f; // 否则递归调用自身基类,尝试匹配下一个参数
};

// find the best f for T in Types...:
template<typename T, typename... Types>
struct BestMatchInSetT { // f的返回类型就是所需要的Type
  using Type = decltype(A<Types...>::f(std::declval<T>()));
};

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

实例化安全的(instantiation-safe)模板

  • EnableIf的本质是仅当模板实参满足某些条件时才启用模板,把模板在模板实参上执行的每个操作写进EnableIf,模板实例化将永远不会失败,这样的模板称为实例化安全的模板
  • 如下模板要求类型T有一个operator<操作符来比较两个T值,然后把比较结果转为布尔值
template<typename T>
const T& min(const T& x, const T& y)
{
  if (y < x)
  {
    return y;
  }
  return x;
}
  • 为了使上面的模板实例化安全,先实现一个检查operator<的traits
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;
template<typename T>
std::enable_if_t<std::is_convertible_v<LessResult<const T&, const T&>, bool>, const T&>
min(const T& x, const T& y)
{
  if (y < x)
  {
    return y;
  }
  return x;
}

struct X1 {};
bool operator< (const X1&, const X1&) { 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<(const X5&, const X5&)
{
  return BoolConvertible();
}

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

struct BoolLike { // BoolLike不能隐式转换为bool
  explicit operator bool() const { return true; } // explicit conversion to bool
};
struct X7 {};
BoolLike operator<(const X7&, const X7&) { return BoolLike(); }

int main()
{ // 下面的ERROR源于实例化被拒绝,没有可匹配的重载
  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()
}
  • X7传给实例化安全的min失败,因为BoolLike不能隐式转换为bool。如果想根据上下文决定T能否转换为bool,则需要定义一个traits
template<typename T>
class IsContextualBoolT {
 private:
  template<typename T> struct Identity;
  template<typename U>
  static std::true_type
    test(Identity<decltype(std::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;

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

min(X7(), X7()); // OK

文章作者: 张小飞
版权声明: 本博客所有文章除特別声明外,均采用 CC BY-NC-ND 4.0 许可协议。转载请注明来源 张小飞 !
 上一篇
18-模板与继承 18-模板与继承
空基类优化(EBCO)布局原则 C++不允许类大小为0,比如数组元素为类时,若类大小为0则数组大小也是0,这会导致指针运算失效。虽然不能存在大小为0的类,但标准规定,空类为基类时,只要不与同一类型的另一个对象或子对象分配在同一地址,就不用分
下一篇 
16-Traits的实现 16-Traits的实现
01 一个实例:累加一个序列1.1 Fixed Traits#include <iostream> template <typename T> T accum(const T* beg, const T* end) { T
  目录