Loading... <div class="tip inlineBlock info"> 这篇文章是一个使用、编写向的源码速读笔记，不进行深度分析。所分析代码基于C++20标准定义接口和`libstdc++`，`gcc`version为`11.2.0` </div> Range——作为C++20四大组件之一——给我们提供了一套全新的便捷而友好的手法去实现管道语义（pipeline）。现在我们可以像很多现代语言一样，去对一个范围进行连贯的复杂操作，而不需要函数调用的嵌套了！ 比如说，我们可以简单地用这样一段代码去实现输出100以内的倒数10个素数： ```cpp int main() { for (int x : views::iota(1, 100) | views::filter(isprime) | views::reverse | views::take(10) | views::reverse ) std::cout<<x<<' '; return 0; } ``` 输出是 ```plaintext 53 59 61 67 71 73 79 83 89 97 ``` 最重要的是，它不仅如此的方便，而且是**zero-overhead**的！ 那么这是怎么做到的呢，我们来对照源代码逐步分析： # 分析 # 1 ranges 我们都知道`range`可以很容易的代表一个范围（可迭代）对象，有了它我们可以非常方便的调用ranges算法。例如：既然`vector`存储了一个范围（我们假设它叫`arr`），那么我们就可以用`std::ranges::sort(arr)`去代替`std::sort(arr.begin(), arr.end())`。这是怎么实现的呢？ 1. 首先，`range`如何表示一个范围的呢？我们看一下它的定义： ```cpp template<typename _Tp> concept range = requires(_Tp& __t) { ranges::begin(__t); ranges::end(__t); }; ``` 喔！具有`begin`和`end`属性的对象就可以被看做是一个`range`——这也非常合理，我们只要能保证它能够通过`begin`和`end`去**迭代**，那么它就具有了作为“范围”被使用的资格。 2. 但`begin`和`end`的语义怎么保证的呢？它们也有可能表示某个事态的开始和结束，而非我们想要的迭代器。这点我们的`ranges::begin`和`ranges::end`当然做了检查，我们以`ranges::begin`为例： ```cpp template<__maybe_borrowed_range _Tp> requires is_array_v<remove_reference_t<_Tp>> || __member_begin<_Tp> || __adl_begin<_Tp> constexpr auto operator()(_Tp&& __t) const noexcept(_S_noexcept<_Tp&>()) { if constexpr (is_array_v<remove_reference_t<_Tp>>) { static_assert(is_lvalue_reference_v<_Tp>); return __t + 0; } else if constexpr (__member_begin<_Tp>) return __t.begin(); else return begin(__t); } }; ``` 可以看到检查是通过`requires`来实现的，看看调用者是否可以进行`begin`调用或者具有`begin`语义（例如数组类型），并且派发到正确的调用。对于通过成员函数和ADL查找提供的迭代器，这里就做了检查： ```cpp template<typename _Tp> concept __member_begin = requires(_Tp& __t) { { __decay_copy(__t.begin()) } -> input_or_output_iterator; }; template<typename _Tp> concept __adl_begin = __class_or_enum<remove_reference_t<_Tp>> && requires(_Tp& __t) { { __decay_copy(begin(__t)) } -> input_or_output_iterator; }; ``` 可以看到这里检测了它们是否真的能够提供用来遍历`range`的迭代器。 3. 考虑一个极端情况，如果我们的`range`提供了`begin`和`end`成员，也满足了提供`input_or_output_iterator`的`requires`检测，但实际上该迭代器并不是用来迭代范围的怎么办呢？答案是**没有办法**。**形式检查无法检测实质**，确实是`concept`体系所面临的一个普遍问题，只能通过程序员自己意识到才能保证不发生这种情况。幸运的是这不难避免。当你去使用某个`concept`的时候你至少有机会意识到它会对**哪些名字的特定使用**敏感。 4. 总之，有了`range`就意味着可以获取`begin`和`end`，那么两种调用很容易等价。只不过`range`算法会需要通过niebloid手法保证**非ADL**调用——为什么需要这样，我们会有专门的文章讲解。现在以`sort`为例看一下`range` algorithm的实现： ```cpp struct __sort_fn { //... template<random_access_range _Range, typename _Comp = ranges::less, typename _Proj = identity> requires sortable<iterator_t<_Range>, _Comp, _Proj> constexpr borrowed_iterator_t<_Range> operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const { return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__comp), std::move(__proj)); } }; inline constexpr __sort_fn sort{}; ``` 在里面正常使用`begin`和`end`即可，并且最终将其**转发到**`std`**当中的对应实现**。niebloid本身一般只对`range`参数做拆分和分类调用处理。 # 2 views `range`保证能够代表“范围”了，接下来是`views`。`view`本身是什么，和`range`有什么关系和区别？ 1. 首先我们来看看标准当中的规定：  就像早在C++17就引入的`string_view`一样，`view`（视图）这个概念本身代表的含义是：对对象的一种固定的观察视角，而并不建立任何原对象的数据拷贝。它的核心是**轻量**。 2. 再看一下语言上是如何实现这种规定的： ```cpp template<typename _Tp> concept view = range<_Tp> && movable<_Tp> && default_initializable<_Tp> && enable_view<_Tp>; template<typename _Derived> requires is_class_v<_Derived> && same_as<_Derived, remove_cv_t<_Derived>> class view_interface : public view_base { //... } struct view_base { }; template<typename _Tp> inline constexpr bool enable_view = derived_from<_Tp, view_base>; template<typename _Tp> concept viewable_range = range<_Tp> && (borrowed_range<_Tp> || view<remove_cvref_t<_Tp>>); template<typename _Tp> concept borrowed_range = range<_Tp> && __detail::__maybe_borrowed_range<_Tp>; ``` 由此可以看到，一个`view`本身： * 需要是一个`range` * 需要是可移动的（作为视图的性能要求） * 需要无歧义地从`view_base`派生（意味着我们希望它成为一个`view`） 也就是说，一个`view`**本质上就是一个**`range`，**但不复制原对象资源，而是通过一种固定的观察方式每次灵活地使用**。而附带地，一个`range`想要被作为`view`使用（例如，我们在一个pipeline中一开始传入一个`range`作为本体），则需要满足`borrowed_range`概念，它是指： * 我们能按值传递这个`range`（就像我们所做的一样） * 且函数能够返回从它上得到的无悬垂的迭代器（以供管道下游使用） 3. 有了`viewable_range`这个概念，我们就可以通过范围适配器非常容易的生成一个`view`了。事实上，对于一个`view`而言，**一般存在2个相关工具**，我们以`take_while`为例来看一下：  可以看到，这里主要出现了`take_while_view`类和`take_while`对象： 1. `take_while_view`类型被称作**范围适配器**： ```cpp template<view _Vp, typename _Pred> requires input_range<_Vp> && is_object_v<_Pred> && indirect_unary_predicate<const _Pred, iterator_t<_Vp>> class take_while_view : public view_interface<take_while_view<_Vp, _Pred>> ``` 同时这里还给出了一个**显式推导指引**来帮助推导： ```cpp template<typename _Range, typename _Pred> take_while_view(_Range&&, _Pred) -> take_while_view<views::all_t<_Range>, _Pred>; ``` ——它会自动通过`views::all`来帮助我们把合规的`range`推导成`view`，非常重要。由此我们就能够通过一个`range`去生成各种`view`啦，例如： ```cpp auto less_than_five_view = take_while_view(arr, [](int x){ return x < 5; }); ``` 2. `take_while`则是一个范围适配器**对象**，它的本质是一个niebloid（如有不解，请参看我的另一篇文章——这会儿还没写完）。调用`ranges::views::take_while(e, f)`就等价于`take_while_view(e, f)`。 4. 至此我们知道，`view`是一种特殊的`range`，通过范围适配器们，我们可以轻松地用`range`产生我们所需要的`view`。而这个`view`就需要我们使用技巧去完成**轻量的（必须是懒惰的）** 操作辣。比方说，我现在就可以实现一个简易版的“素数视图”： ```cpp template<view T> struct prime_view : view_interface<prime_view<T>> { template<typename InnerIter, typename Sentinel> struct Iter { InnerIter now_pointer; Sentinel sentinel; typedef std::iterator_traits<InnerIter> __traits_type; typedef InnerIter iterator_type; typedef typename __traits_type::iterator_category iterator_category; typedef typename __traits_type::value_type value_type; typedef typename __traits_type::difference_type difference_type; typedef typename __traits_type::reference reference; typedef typename __traits_type::pointer pointer; Iter() = default; Iter(const InnerIter &innerIter, const Sentinel &sentinel) : now_pointer(innerIter), sentinel(sentinel) {} constexpr static bool isprime(const int &arg) { if (arg < 2) return false; for (int i = 2; i <= sqrt(arg); i++) if (arg % i == 0) return false; return true; } constexpr Iter &operator++() { do { ++now_pointer; } while (!isprime(*now_pointer) && now_pointer != sentinel); return *this; } constexpr Iter operator++(int) { auto t = now_pointer; do { ++now_pointer; } while (!isprime(*now_pointer) && now_pointer != sentinel); return t; } constexpr bool operator!=(const Iter &arg) { return now_pointer != arg.now_pointer; } constexpr value_type operator*() { return *now_pointer; } }; constexpr prime_view() = default; constexpr prime_view(T &&m_base) : m_begin(m_base.begin()), m_end(m_base.end()) {} constexpr auto begin() const { return Iter(m_begin, m_end); } constexpr auto end() const { return Iter(m_end, m_end); } private: decltype(std::declval<T>().begin()) m_begin; decltype(std::declval<T>().end()) m_end; }; template<viewable_range range> prime_view(range &&) -> prime_view<views::all_t<range>>; int main() { std::vector<int> arr(100); std::iota(arr.begin(), arr.end(), 0); for (auto v: prime_view(arr)) std::cout << v << std::endl; return 0; } ``` 由此也可以看到：视图的实现没有一定之规，主要在于如何巧妙地满足`views`的概念要求：**它需要是轻量的**。 # 3 pipeline 接下来是我们所关心的最后一个问题：**pipeline究竟是如何实现的？**——也就是文章一开头的那个例子，那种特别pythonic的写法究竟是什么东西？那个`operator|`是怎么实现的？ 1. 首先我们要找到`operator|`的实现，它在这里： ```cpp struct _RangeAdaptorClosure { // range | adaptor is equivalent to adaptor(range). template<typename _Self, typename _Range> requires derived_from<remove_cvref_t<_Self>, _RangeAdaptorClosure> && __adaptor_invocable<_Self, _Range> friend constexpr auto operator|(_Range&& __r, _Self&& __self) { return std::forward<_Self>(__self)(std::forward<_Range>(__r)); } // Compose the adaptors __lhs and __rhs into a pipeline, returning // another range adaptor closure object. template<typename _Lhs, typename _Rhs> requires derived_from<_Lhs, _RangeAdaptorClosure> && derived_from<_Rhs, _RangeAdaptorClosure> friend constexpr auto operator|(_Lhs __lhs, _Rhs __rhs) { return _Pipe<_Lhs, _Rhs>{std::move(__lhs), std::move(__rhs)}; } }; ``` 可以看到，`operator|`定义在`_RangeAdaptorClosure`类型中。这里有两个重载，第一个从line6可以看出，是个方便调用，让我们可以直接在管道开始处使用`range_arg_for_adaptor | generate_view_adaptor | ...`来替代`generate_view_adaptor(range_arg_for_adaptor) | ...`或者是`views::all(range_arg_for_adaptor) | generate_view_adaptor | ...`。从第二个重载可以看到：所谓的管道（pipe）就是不断从一个**闭包**应用下一个范围适配器，接连产生新的闭包的过程。 而由于闭包需要是一元的，因此普通的范围适配器通过偏调用的辅助类型拆分为闭包对象： ```cpp //普通范围适配器 template<typename _Derived> struct _RangeAdaptor { // Partially apply the arguments __args to the range adaptor _Derived, // returning a range adaptor closure object. template<typename... _Args> requires __adaptor_partial_app_viable<_Derived, _Args...> constexpr auto operator()(_Args&&... __args) const { return _Partial<_Derived, decay_t<_Args>...>{std::forward<_Args>(__args)...}; } }; //其中一个偏调用模板 // A range adaptor closure that represents partial application of // the range adaptor _Adaptor with arguments _Args. template<typename _Adaptor, typename... _Args> struct _Partial : _RangeAdaptorClosure { //... // Invoke _Adaptor with arguments __r, _M_args... according to the // value category of this _Partial object. template<typename _Range> requires __adaptor_invocable<_Adaptor, _Range, const _Args&...> constexpr auto operator()(_Range&& __r) const & { auto __forwarder = [&__r] (const auto&... __args) { return _Adaptor{}(std::forward<_Range>(__r), __args...); }; return std::apply(__forwarder, _M_args); } template<typename _Range> requires __adaptor_invocable<_Adaptor, _Range, _Args...> constexpr auto operator()(_Range&& __r) && { //... } //... }; ``` 至此我们知道了，C++是如何使用范围适配器（闭包）这一设计来提升我们的编码体验的。它本质上是**在整个pipeline被使用前，就巧妙地将所有适配器连接在一起形成了一个全新的闭包**（而不是在调用时再让数据依次通过他们[^1]——虽然实质是相同的）。本质上类似于将一串嵌套的函数调用`f(g(h(x)))`组合成一个`nested_func(x)`。 2. 在pipeline中如何被添加到下一个`RangeAdaptor`对应参数位置？我们来追踪一个具体调用就一目了然了： ```cpp for (auto x: arr | views::take_while([](int x) { return x < 5; })) std::cout << x << std::endl; ``` 比如说这个合并，`take_while`会通过上述的`_Partial`**生成一个偏调用的对象**——就像`bind`函数所做的一样，给`arr`留下一个slot： ```cpp template<typename _Derived> struct _RangeAdaptor { // Partially apply the arguments __args to the range adaptor _Derived, // returning a range adaptor closure object. template<typename... _Args> requires __adaptor_partial_app_viable<_Derived, _Args...> constexpr auto operator()(_Args&&... __args) const { return _Partial<_Derived, decay_t<_Args>...>{std::forward<_Args>(__args)...}; } }; ``` 然后具体而言我们就拿到了一个`views::__adaptor::_Partial<std::ranges::views::_TakeWhile, <lambda> >`对象。这样再调用`_RangeAdaptorClosure`的对应重载就可以了。 [^1]: 这在语法上也是不可能的，读者可以自行思考原因。 © 允许规范转载 打赏 赞赏作者 赞 2 如果觉得我的文章对你有用，请随意赞赏