C++尝鲜：在C++中实现​​​LINQ！

导语 | 在正式分析libunifex之前，我们需要了解一部分它依赖的基础机制，方便我们更容易的理解它的实现。本篇介绍的主要内容是关于c++ linq的，可能很多读者对c++的linq实现会比较陌生，但说到C#的linq，大家可能马上就能对应上了。没错，c++的linq就是在c++下实现类似C# linq的机制，本身其实就是在定义一个特殊的DSL，相关的机制已经被使用在c++20的ranges库，以及不知道何时会正式推出的execution库中，作为它们实现的基础之一。本篇我们主要围绕已进入标准的ranges实现来展开关于c++ linq的探讨，同时也将以ranges的一段代码为起点，逐步展开本篇的相关内容。

一、从ranges示例说起

ranges是c++20新增的特性，很好的弥补了c++容器和迭代器实现相对其他语言的不便性。它的使用并不复杂。我们先来看一个具体的例子:

auto const ints = { 0, 1, 2, 3, 4, 5 };
auto even_func = [](int i) { return i % 2 == 0; };
auto square_func = [](int i) { return i * i; };
auto tmpv = ints 
  | std::views::filter(even_func) 
  | std::views::transform(square_func);

for (int i : tmpv) {
  std::cout << i << ' ';
}

初次接触, 相信很多人都会疑惑:

• 这是如何实现的?

• c++里也能有linq?
  

• 为什么这种表达虽然其他语言常见, 在c++里存在却显得有点格格不入?

从逻辑上来讲, 上述代码起到的是类似语法糖的效果, linq表达: ints | std::views::filter(even_func) | std::views::transform(square_func)；

等价函数调用方式为: std::views::transform(std::views::filter(ints， event_func)， square_func)；

所以表面上来看，它似乎是通过特殊的|操作符重载来规避掉了多层函数嵌套表达，让代码有了更好的可读性，表达更简洁了。

但这里的深层次的设计其实并没有那么简单，这也是大家读ranges相关的文章，会发现这“语法糖”居然还会带来额外的好处，最终compiler生成的目标代码相当简洁。这是为什么呢？我们将在下一章中探讨这部分的实现机制。

二、特殊的DSL实现

其实本质上来说, 这种实现很巧妙的利用了部分compiler time的特性，最终在c++中实现了一个从“代码->Compiler->Runtime”的一个DSL，后续我们也介绍到，execution里也复用并发扬了这种机制。我们先来看一下ranges这部分的机制：

• DSL定义(BNF组成)-首先是范式的组成，ranges的linq用到的范式比较简单，我们可以认为，它是由Ranges Pipeline::=Data Source { '|' Range Adapter } '|' Range Adapter组成的。

• Compiler(Pipeline操作)-ranges实现里我们可以认为|运算的过程就是编译过程。

• Execute-具体的iterator过程，ranges里一般就是std::ranges::begin()，std::ranges::end()，以及iterator本身所支持的++操作等。

这种设计本身带来的好处，对比原始的容器和迭代器操作，Compiler部分和Execute过程被显示分离了，Compiler的时候，并不会对Data Source做任何的访问和操作，所有访问相关的操作其实是后续Execute过程再发生的(Lazy特性)。

另外，因为Compiler过程本身是结合comipler time特性来处理的，这样DSL本身在这个阶段是类型完备的，一方面compiler过程本身就能完成一些常规的类型匹配问题检查等操作，另外我们也能在该阶段在类型完备的情况下更好的处理相关逻辑。

大量使用compiler time特性带来的额外好处是原始的std容器和迭代器很多在运行时进行处理的操作，都可以在编译期完成，编译器会生成比原来运行效率高效很多的代码。

像这种设计精巧，系统性完备，优势又很明显的机制，必然会得到发扬光大。所以我们会看到，ranges库本身使用了相关机制，到几经迭代尚未正式推出的execution库，都已经拥抱了这种设计，将其作为自己基础的一部分，作为sender/receivers机制的基石，相关的实现也被越来越多的c++ coder所认可。

本篇我们还是回到ranges本身，先关注Compiler部分也就是Pipeline机制实现的细节，以微软官方的ranges实现为例，一起来详细了解一下它的实现机制。

三、pipeline机制浅析

（一）Pipe实现相关的concept

• _Pipe::_Can_pipe

namespace _Pipe {
  template <class _Left, class _Right>
  concept _Can_pipe = requires(_Left&& __l, _Right&& __r) {
    static_cast<_Right&&>(__r)(static_cast<_Left&&>(__l));
  };
}

这个concept比较简洁，能够组织成pipe的对象，以

auto pipe = l | r;

为例，能够以r(l)的形式调用的两个对象，即可满足pipe约束。

• _Can_compose

namespace _Pipe {
  template <class _Left, class _Right>
  concept _Can_compose = constructible_from<remove_cvref_t<_Left>, _Left>
    && constructible_from<remove_cvref_t<_Right>, _Right>;
}

这个主要是因为lazy evaluate的过程中，我们可能需要在中间对象中(如下文中的_Pipeline对象)，对_Left和_Right进行存储，所以需要它们是可构建的。

（二）Pipe实现相关的类

• struct _Base\<class _Derived\>类

相关源代码如下:

namespace _Pipe {

  template <class, class>
  struct _Pipeline;

  template <class _Derived>
  struct _Base {
    template <class _Other>
    constexpr auto operator|(_Base<_Other>&& __r) &&  {
      return _Pipeline{static_cast<_Derived&&>(*this), static_cast<_Other&&>(__r)};
    }

    template <class _Other>
    constexpr auto operator|(const _Base<_Other>& __r) &&  {
      return _Pipeline{static_cast<_Derived&&>(*this), static_cast<const _Other&>(__r)};
    }

    template <class _Other>
    constexpr auto operator|(_Base<_Other>&& __r) const& {
      return _Pipeline{static_cast<const _Derived&>(*this), static_cast<_Other&&>(__r)};
    }

    template <class _Other>
    constexpr auto operator|(const _Base<_Other>& __r) const& {
      return _Pipeline{static_cast<const _Derived&>(*this), static_cast<const _Other&>(__r)};
    }

    template <_Can_pipe<const _Derived&> _Left>
    friend constexpr auto operator|(_Left&& __l, const _Base& __r)
    {
      return static_cast<const _Derived&>(__r)(_STD forward<_Left>(__l));
    }

    template <_Can_pipe<_Derived> _Left>
    friend constexpr auto operator|(_Left&& __l, _Base&& __r)
    {
      return static_cast<_Derived&&>(__r)(_STD forward<_Left>(__l));
    }
  };
}

以微软版range库的实现为例，各个range adapter-如std::views::filter，std::views::transform等都继承自_Base类，_Base类主要完成以下两个功能：

• 完成对其它_Base类的管道操作。

• 通过友元和模板来完成对其它类的管道操作(自己作为右操作数)
  

• 具体的重载不再具体展开了，主要是不同_Right类型的差异处理，可自行参阅相关代码。

struct _Pipeline<class _Left，class _Right>类

相关代码如下:

template <class _Left, class _Right>
struct _Pipeline : _Base<_Pipeline<_Left, _Right>> {
  _Left __l;
  _Right __r;

  template <class _Ty1, class _Ty2>
  constexpr explicit _Pipeline(_Ty1&& _Val1, _Ty2&& _Val2)
    : __l(std::forward<_Ty1>(_Val1))
    , __r(std::forward<_Ty2>(_Val2)) {
  }

  template <class _Ty>
  constexpr auto operator()(_Ty&& _Val) 
    requires requires {
    __r(__l(static_cast<_Ty&&>(_Val)));
    }
  { return __r(__l(_STD forward<_Ty>(_Val))); }

  template <class _Ty>
  constexpr auto operator()(_Ty&& _Val) const 
    requires requires {
    __r(__l(static_cast<_Ty&&>(_Val)));
    }
  { return __r(__l(std::forward<_Ty>(_Val))); }
};

template <class _Ty1, class _Ty2>
_Pipeline(_Ty1, _Ty2) -> _Pipeline<_Ty1, _Ty2>;

_Pipeline主要用于将两个range adapter进行复合的情况，比如下面的情况：

auto v = std::views::filter(even_func) | std::views::transform(square_func);

这个时候我们会构建_Pipeline对象, 区别于这种情况则是不依赖中间_Pipeline对象, 比如下面的情况:

auto ints = {1, 2, 3, 4, 5};
auto v = ints | std::views::filter(even_func);

这种情况 , 我们就不需要依赖_Pipeline对象, 直接触发的是_Pipe这个版本的operator|重载:

template <_Can_pipe<_Derived> _Left>
friend constexpr auto operator|(_Left&& __l, _Base&& __r)
{
  return static_cast<_Derived&&>(__r)(_STD forward<_Left>(__l));
}

std::views::filter本身是一个CPO closure对象，不理解CPO没关系，下篇中将进行具体介绍，我们可以先将它简单理解成一个带up value的函数对象，上例中的even_func被携带到了一个std::views::filter CPO对象中， 然后我们可以以 filter_cpo(ints) 的方式来产生一个预期的views，cpo的这个特性倒是跟其他语言的closure特性基本一致，除了C++的CPO对象比较Hack，使用形式不如其他语言简洁外。

另外需要关注的一点是：

template <class _Ty1, class _Ty2>
        _Pipeline(_Ty1, _Ty2) -> _Pipeline<_Ty1, _Ty2>;

这个是c++17添加的Custom template argument deduction rules(或者user-defined template argument deduction rules)，利用用户自行指定的推导规则，我们可以使用简单的_Pipeline(a，b)来替换_Pipeline<a，b>()，以得到更简单的表达，如_Base类中的使用一样:

_Pipeline{static_cast<const _Derived&>(*this), static_cast<_Other&&>(__r)};

四、总结

本篇中我们简单介绍了c++ linq，以及ranges中相关机制的使用，也侧重介绍了作为linq Compiler部分的Pipeline的具体实现。但可能有细心的读者已经发现了，ranges中的各种range adapter-如std::views::transform()和std::views::filter()的实现，好像跟自己之前见到的惯用的C++封装方式不太一样，这也是我们下一篇中将介绍的内容。

参考资料：

1.ranges-cppreference

 作者简介

沈芳

腾讯后台开发工程师

IEG研发效能部开发人员，毕业于华中科技大学。目前负责CrossEngine Server的开发工作，对GamePlay技术比较感兴趣。

 推荐阅读