Skip to content

Latest commit

 

History

History
486 lines (386 loc) · 29.3 KB

concept.md

File metadata and controls

486 lines (386 loc) · 29.3 KB
Raw
title
概念

类型限制

使用 concept

未加类型限制的模板，类型错误到『实例化时 (instantiation time)』才会发现：

template<typename Seq, typename Val>
Val sum(Seq s, Val v) {
  for (const auto& x : s)
    v += x;
  return v;
}

假设已定义 Sequence 及 Value 两个 concepts，可定义类型受限的版本：

template<Sequence Seq, Value Val>
Val sum(Seq s, Val v) {
  for (const auto& x : s)
    v += x;
  return v;
}

requires 分句

template <Concept Type> 等价于 template<typename Type> requires Concept<Type>，其中 requires 开启「需求分句 (requires clause)」，其后的 Concept<Type> 为编译期谓词（Type 满足 Concept 则为 true）。

template<typename Seq, typename Val>
  requires Sequence<Seq> && Value<Val>
Val sum(Seq s, Val v) {
  for (const auto& x : s)
    v += x;
  return v;
}

进一步要求 Seq 的元素的类型可以与 Val 类型进行算术运算：

template<Sequence Seq, Value Val>
  requires Arithmetic<range_value_t<Seq>, Val>
Val sum(Seq s, Val n);
# 或更简洁的
template<Sequence Seq, Arithmetic<range_value_t<Seq>> Val>
Val sum(Seq s, Val n);

requires 表达式

template<forward_iterator Iter>
  requires requires(Iter p, int i) { p[i]; p+i; }  // 额外的需求
void advance(Iter p, int n) {
  p += n;  // ⚠️ 满足上述需求的 Iter，未必支持 +=
}

其中第二个 requires 开启「需求表达式 (requires expression)」。后者为编译期谓词（{} 中的代码合法则其值为 true），相当于泛型编程的汇编代码，只因出现在底层代码（如 concepts 的定义）中。

定义 concept

定义概念：

template<typename B>
concept Boolean = requires(B x, B y) {
  { x = true };
  { x = false };
  { x = (x == y) };
  { x = (x != y) };
  { x = !x };
  { x = (x = y) };
};

template<typename T>
concept EqualityComparable = requires (T a, T b) {
  { a == b } -> Boolean;  // -> 之后必须跟某个 concept
  { a != b } -> Boolean;
};

⚠️ { e } -> Concept 相当于 requires Concept<decltype((e))>，需考虑 decltype 引入的左值引用。

显式判断：

static_assert(EqualityComparable<int>);  // 通过编译

struct S { int a; };
static_assert(EqualityComparable<S>);  // 编译期报错

隐式判断：

template<EqualityComparable T>
bool cmp(T a, T b) {
  return a < b;  // ⚠️ 未在 EqualityComparable 中检查
}

bool b0 = cmp(cout, cerr);  // 未通过 EqualityComparable 检查
bool b1 = cmp(2, 3);        // OK
bool b2 = cmp(2+3i, 3+4i);  // 通过 EqualityComparable 检查，但在实例化时报错

补全开头的例子：

#include <ranges>
#include <iterator>
template<typename S>
concept Sequence = requires (S a) {
  typename range_value_t<S>;  // S 必须有 value type
  typename iterator_t<S>;     // S 必须有 iterator type

  requires input_iterator<iterator_t<S>>;  // S 的 iterator 必须可读
  requires same_as<range_value_t<S>, iter_value_t<S>>;  // 类型必须一致

  { a.begin() } -> same_as<iterator_t<S>>;  // S 必须有返回 iterator 的 begin()
  { a.end() } -> same_as<iterator_t<S>>;
};
template<typename T, typename U = T>
concept Numeric = requires(T x, U y) {
  x+y; x-y; x*y; x/y; x+=y; x-=y; x*=y; x/=y; x=x; x=0;
};
template<typename T, typename U = T>
concept Arithmetic = Numeric<T, U> && Numeric<U, T>;

💡 建议用形容词命名概念。

限制 auto

限制函数形参：

auto twice(Arithmetic auto x) { return x+x; } // 只支持算术类型
auto thrice(auto x) { return x+x+x; }         // 支持任意可 + 类型

auto x1 = twice(7);   // x1 == 14
auto s = string("Hello ");
auto x2 = twice(s);   // string 不满足 Arithmetic
auto x3 = thrice(s);  // x3 == "Hello Hello Hello "

限制变量类型：

Channel open_channel(string);

auto ch1 = open_channel("foo");              // ch1 为 Channel 变量
Arithmetic auto ch2 = open_channel("foo");   // Channel 不满足 Arithmetic
ChannelLike auto ch3 = open_channel("foo");  // Channel 满足 ChannelLike

限制返回类型：

Numeric auto some_function(int x) {
    // ...
    return fct(x);    // an error unless fct(x) returns a Numeric
}

标准库概念

<concepts>

标准库在 <concepts> 中定义了一些常用概念。

核心语言概念

比较概念

标准库在 <compare> 中定义了三种 ordering 类型，用于表示三路比较运算符 <=> 的结果。它们都支持六种比较运算，区别在于：

  • partial_ordering 表示相等的值不可替换（可以区分），且允许存在不可比较的值（即 a < b, a == b, a > b 可以都为 false，如质点（按 p.x < q.x && p.y < q.y 定义 p < q，相等时可按质量区分）。
  • weak_ordering 表示相等的值不可替换（可以区分），但不允许存在不可比较的值（即 a < b, a == b, a > b 有且仅有一个为 true），如学生（按姓名字典序比较，相等时可学号区分）。
  • strong_ordering 表示相等的值可以替换（无法区分），且不允许存在不可比较的值，如整数、字符串。

对象概念

可调用概念

<iterator>

迭代器概念

其中 sentinel 为 C++20 引入的概念，表示可直接与迭代器进行比较的类型，具体用法可参见示例：

#include <concepts>
#include <algorithm>
#include <iterator>
#include <iostream>

template<class Iter>
class Sentinel {
 public:
  Sentinel(int ee) : end(ee) { }
  Sentinel() : end(0) {}  // std::sentinel_for<S, I> 要求 S 有默认构造函数

  friend bool operator==(const Iter& p, Sentinel s) { return (*p == s.end); }
  friend bool operator!=(const Iter& p, Sentinel s) { return !(p == s); }

 private:
  std::iter_value_t<const char*> end;  // the sentinel value
};
static_assert(std::sentinel_for<Sentinel<const char*>, const char*>);

int main() {
  const char aa[] = "Hello, World!\nBye for now\n";
  // 打印 "Hello, World!"
  std::ranges::for_each(aa, Sentinel<const char*>('\n'),
      [](const char x) { std::cout << x; });
}

算法概念

为简化算法对类型的限制，标准库定义了一组概念：

其中

  • Proj 表示作用在 Iter 型迭代器所指类型（可由 std::iter_reference_t<Iter> 得到）上的可调用类型（返回值类型可由 std::indirect_result_t<Proj&, Iter> 得到），其名称来源于数学中的「投影 (projection)」，例如：

    // 按绝对值由大到小排序并打印
auto v = std::vector<int>{ -1, +2, -3 };
std::ranges::sort(v, /* Comp */std::ranges::greater{},
    /* a temporary Proj */[](int i){ return std::abs(i); });
std::ranges::for_each(v, /* another Proj */[](int i){ std::cout << i << ' '; });

  • 通常不需要实施上述投影，故标准库提供了默认投影类型 std::identity (defined in <functional>)，其 operator() 原样返回实参。

  • std::projected (defined in <iterator>) 用于提取 Proj 型可调用对象（作用于 In 型迭代器所指对象）的返回值类型：

    template< std::indirectly_readable In,
          std::indirectly_regular_unary_invocable<In> Proj >
struct projected {
  using value_type = std::remove_cvref_t<std::indirect_result_t<Proj&, In>>;
  std::indirect_result_t<Proj&, In> operator*() const; // 只声明不定义
};

<ranges>

Range

Range 是对容器概念的推广，可以由「起始迭代器 + END」来定义，其中 END 可以是：

  • 终止迭代器，如 { vec.begin(), vec.end() }
  • 个数，如 { vec.begin(), vec.size() }
  • 终止条件，如 { vec.begin(), [](int x){ return x % 2; } }

标准库在命名空间 std::ranges 中定义了一些常用的 range concepts：

Range concepts 说明
ranges::range 提供「起始迭代器 + END」
ranges::borrowed_range 迭代器可返回（不会空悬）
ranges::sized_range 支持 O(1) size()
ranges::view 支持 O(1) operator=()
ranges::input_range 支持 input_iterator
ranges::output_range 支持 output_iterator
ranges::forward_range 支持 forward_iterator
ranges::bidirectional_range 支持 bidirectional_iterator
ranges::random_access_range 支持 random_access_iterator
ranges::contiguous_range 支持 contiguous_iterator
ranges::common_range
ranges::viewable_range 可以安全地转化为 view
ranges::constant_range (C++23) 元素只读

标准库在命名空间 std::ranges 中还提供了一些对常用算法的封装，使得形如 std::sort(v.begin(), v.end()) 的调用可简化为 std::ranges::sort(v)，从而避免传错迭代器。

View

View 是对 range 的轻量化封装（适配器）。

标准库在命名空间 std::ranges 中提供了一些常用的 views：

VIEW for (auto x : VIEW) { use(x); } 的传统写法
all_view{r} for (auto x : r) use(x);
filter_view{r, p} for (auto x : r) if (p(x)) use(x);
transform_view{r, f} for (auto x : r) use(f(x));
take_view{r, n} int i{0}; for (auto x : r) if (i++ == n) break; else use(x);
drop_view{r, n} int i{0}; for (auto x : r) if (i++ < n) continue; else use(x);
take_while_view{r, p} for (auto x : r) if (!p(x)) break; else use(x);
drop_while_view{r, p} for (auto x : r) if (p(x)) continue; else use(x);
join_view{r} for (auto &y : r) for (auto x : y) use(x);
keys_view{r} for (auto [x, y] : r) use(x);
values_view{r} for (auto [y, x] : r) use(x);
ref_view{r} for (auto &x : r) use(x);
以下为生成器
iota_view{y} for (int i = 0: true; ++i) use(y + i);
iota_view{y, z} for (auto x = y: x < z; ++x) use(x);
istream_view<double>{cin} double x; while (cin >> x) use(x);

表中 ranges::X_view{ARGS} 等价于 views::X(ARGS)，即每个 views::X 函数生成一个 ranges::X_view 对象。

例如按条件过滤：

auto filter_odd(ranges::forward_range auto& r) {
  ranges::filter_view v {r, [](int x) { return x % 2; } };  // v 的用户只访问 r 中的奇数
  return v;  // 轻量化封装，直接按值返回
}
int main() {
  auto v = vector<int>{ 3, 5, 1, 2 };
  cout << "odd numbers: ";
  auto fv = filter_odd(v);
  static_assert(ranges::forward_range<decltype(fv)>);  // view 依然是 range
  ranges::for_each(fv, [](int x) { cout << x << ' '; });  // 可以像 range 一样使用 view
  cout << "\n";
}

可以创建 view of view，例如：

ranges::forward_range/* 类型限制 */ auto
take_2(ranges::view auto/* view 无需传引用 */ fv) {
  ranges::take_view tv {fv, 100};  // 只访问前 2 个奇数
  // 等价于 auto tv = views::take(fv, 100);
  return tv;
}
int main() {
  auto v = vector<int>{ 3, 5, 1, 2 };
  cout << "odd numbers: ";
  auto fv = filter_odd(v);
  auto tv = take_2(fv);  // view of view
  ranges::for_each(tv, [](int x) { cout << x << ' '; });
  cout << "\n";
}

Pipeline

标准库 range 及 view 支持 | 运算符，可以像在 Unix shell 中串联多个命令一样，串联多个 filters：

void user(ranges::forward_range auto& r) {
  auto odd = [](int x) { return x % 2; };
  for (int x : r | views::filter(odd) | views::take(3)) {
    cout << x << ' ';
  }
}
// 等价于
void user_pre20(ranges::forward_range auto& r) {
  auto odd = [](int x) { return x % 2; };
  int cnt = 0;
  for (int x : r) {
    if (odd(x)) {
      cout << x << ' ';
      if (++cnt == 3) {
        break;
      }
    }
  }
}

遍历嵌套数据结构：

#include <iostream>
#include <map>
#include <ranges>
 
int main() {
  auto name_to_game_to_score = std::map<std::string, std::map<std::string, int>>();
  name_to_game_to_score["Bob"] = {
      {"football", 10}, {"basketball", 20},
  };
  name_to_game_to_score["Alice"] = {
      {"football", 30}, {"basketball", 40}, {"volleyball", 50},
  };
  auto range_of_score = name_to_game_to_score
      | std::views::values  // range of std::map<std::string, int>
      | std::views::join    // range of std::pair<std::string, int>
      | std::views::values; // range of int
  for (int score : range_of_score) {
    std::cout << score << ' ';
  }
  std::cout << '\n';  // print 40 30 50 20 10
  auto range_of_score_ptr = range_of_score
      | std::views::transform([](int &i){ return &i; });
  for (int *score_ptr : range_of_score_ptr) {
    *score_ptr *= 10;
  }
  for (int score : range_of_score) {
    std::cout << score << ' ';
  }
  std::cout << '\n';  // print 400 300 500 200 100
  auto range_of_score_ref = range_of_score_ptr
      | std::views::transform([](int *i) -> int & { return *i; });
  for (int &score_ref : range_of_score_ref) {
    score_ref /= 10;
  }
  for (int score : range_of_score) {
    std::cout << score << ' ';
  }
  std::cout << '\n';  // print 40 30 50 20 10
}