C++特殊定制：揭秘cpo与tag_invoke！

导语 | 本篇我们将重点介绍c++中特殊的定制, cpo与tag_invoke这部分的内容，希望对这部分感兴趣的开发者提供一些经验和思考。

前言

上一篇《C++尝鲜：在C++中实现LINQ！》中我们介绍了c++ linq，以及使用相关机制实现的c++20标准库ranges，主要对ranges中的Compiler阶段，也就是Pipeline机制进行较为详细的介绍，但其实ranges中还用到了一个比较特殊的，可能对大家来说都有点陌生的cpo机制，这种机制除了在ranges库中被使用外，execution也大量使用了它的进阶版tag_invoke机制，本篇我们将重点介绍这部分的内容。

一、C++定制概述

要理解cpo机制的产生和使用，并不是一件容易的事。说实话，笔者第一次看到这个机制，也是一头雾水，总有种剧本拿错，这不是我认识的C++的感觉，成功击中的自己的知识盲区。所以这里我们换个角度来讲述，不直接介绍cpo，而是尝试从定制本身说起，结合经典的定制方式，逐步理解cpo出现的原因和它开始被广泛使用的底层逻辑是怎么样的。我们先来看一下定制本身的定义：

（一）定制与定制点

对于framework来说，很容易有下图所示的分层运行情况，库作者负责Library部分逻辑的编写，用户则负责利用Library的功能组织外围业务逻辑。

这样的结构势必会引入Library需要提供一些定制点，供外围逻辑定义相关行为，来完成自定义的功能，良好设计的定制点一般要满足以下两个条件：

• Point A: Library需要User Logic层定制实现的代码点。

• Point B: Library调用User Logic层时使用的代码点(不能被外层用户定制的部分)

（二）标准的继承与多态

这个就不用细述了，老司机们都相当的熟练，熟知override的各种使用姿势，以及配套的N种设计模式，甚至还有万物皆可模式的流派。

• 标准多态的应用-std::pmr::memory_resource

标准库的std::pmr::memory_resource就是使用多态来封装的，的部分代码实现：

class memory_resource {
public:
    void *allocate(size_t bytes, size_t align = alignof(max_align_t)) {
        return do_allocate(bytes, align);
    }
private:
    virtual void *do_allocate(size_t bytes, size_t align) = 0;
};

class users_resource : public std::pmr::memory_resource {
    void *do_allocate(size_t bytes, size_t align) override {
        return ::operator new(bytes, std::align_val_t(align));
    }
};

user_resource::do_allocate()这里是我们提到的“Point A”，我们可以根据我们的需要来组织它的实现。

而memory_resource::allocate()此处则是“Point B”，库本身始终是使用这个接口来调用相关代码，注意此处“Point A”与“Point B”是不同名的。这是我们所鼓励的定制点实现方式，用户部分和库的调用点的名称不相同，我们也可以很简单的通过名称来区分哪个是内部使用的调用点，哪个是用户需要重载的调用点。

（三）IoC

全称是inversion of control-控制反转，在有反射的语言里是种很自然的事情，在C++里你得借助大量的离线或者Compiler Time的机制完成类型擦除，最终实现类似

auto obj = IoC_Create("ObjType");

的效果。所以这部分在C++社区中更多还是以C++反射支持的形式出现，直接提IoC的，反而不多。

（四）CRTP

curiously recurring template pattern，中文就不翻译了，感觉译名很奇怪，我们直接来看机制：

template <class T> 
struct Base
{
    void interface()
{
        // ...
        static_cast<T*>(this)->implementation();
        // ...
    }

    static void static_func()
{
        // ...
        T::static_sub_func();
        // ...
    }
};

struct Derived : Base<Derived>
{
    void implementation()；

    static void static_sub_func();
};

大家应该在一些比如Singleton<>的实现里看到过类似的表达。那么这种表达有什么好处呢？区别于标准继承和多态用法，最重要的一点，在基类中，我们可以很方便的通过static_cast<T*>直接获取到子类型，如：

void interface()
{
  // ...
  static_cast<T*>(this)->implementation();
  // ...
}

这样做的好处:

• 一方面，我们可以将原来需要依赖虚表来完成的多态特性，转变为纯粹的静态调用，明显性能更高。

• 另一方面，基类可以无成本的访问子类的功能和实现，这肯定比标准的多态自由多了。

（五）ADL机制

全称是: Argument-dependent lookup机制, 具体可参考ADL机制, 一个大部分人没怎么关注, 但确实是被比较多库用到的一个特性, 比如早期asio版本中自定义allocator的方式等, 都依赖于它.

• ADL用于定制-std::swap的例子

区别于上面多态的正面例子，这里算是一个反面例子了，虽然这部分同样也是标准库的实现。我们一起来看一下std::swap的实现：

namespace std {
    template<class T>
    void swap(T& a, T& b) {
        T temp(std::move(a));
        a = std::move(b);
        b = std::move(temp);
    }
}

namespace users {
    class Widget { ... };

    void swap(Widget& a, Widget& b) {
        a.swap(b);
    }
}

用户在自己的命名空间下通过定义同名的swap函数来实现用户空间结构体的swap，然后我们通过ADL机制(Argument-dependent lookup机制) :

using std::swap;  // pull `std::swap` into scope
swap(ta, tb);

可以匹配到正确版本的swap()实现。像这种用同名方式处理“Point A”和“Point B”的方式，明显容易带来混乱和理解成本的增加。

而且当我们使用std::swap()和不带命名空间的swap()时，得到的又是完全不一样的语义，前者调用的始终是模板实现的std::swap版本，而后者可以正确利用ADL匹配到用户自定义的swap，或者模板版本的实现，这显然不是我们想要看到的情况。不过std::swap的实现之所以有这种情况，主要还是因为相关的代码是差不多20多年前的实现了，为了兼容已有代码，没办法很简单的重构，所以就只能保持现状了，我们注意到这一点就好。

（六）ranges中的定制机制

我们回到ranges的示例代码：

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

如果此处的ints变为其他类型，也就是 std::views::filter(x，even_func)，很明显，现在的ranges库是能很好的兼容各种类型的容器的，那应该怎么来做到这一点呢？假定我们是实现者，我们会如何来实现这种任意类型的支持?

• 多态?-此处的ints等有可能是build in类型，针对所有build in类型再包装一个额外的类，明显不是特别优雅的方法。

• CRTP?-同上，也有需要侵入式修改原始实现，或者Wrapper原始实现的问题。

• IoC?-简单看，好像有那种意思在，接受任意类型的参数，然后生成预期类型的返回值。但此处的x可能如上例一样，只是标准的std::initializer_list<int>，在目前c++无反射支持的情况下，我们很难只依赖编译期特性实现出高性能的 std::views::filter()版本。

• ADL?-通过swap的实现，我们猜测它可能是比较接近真相的机制，但swap本身的实现就有它的问题，并不是一个特别优雅的解决方案。

事情到这里进入了僵局，即要泛型，又需要实现类似IoC的机制，该怎么做到呢?

众所周知，c++是轮子语言，从来不缺乏一些奇怪的轮子，这次发光发热的轮子就是前文我们简单提到的CPO机制了，利用CPO机制，我们可以很好的来完成对类似std::views::filter()这种使用场合的功能的封装，下面我们来具体了解CPO机制本身。

（七）cpo概述

CPO全称是: customization point object，是c++库最近几个大版本开始使用的一个用来对特定功能进行定制特性，它与泛型良好的兼容性，另外本身又弥补了ADL之前我们看到的问题，用于解决前面说到的std::views::filter()的实现，还是很适合的。下面我们直接看看一下ranges中cpo的使用情况。

三、Ranges的例子

Ranges中的CPO:

当然，除了这些之外，前面提到的各种range adapter如std::views::filter()这些也是CPO。

（一）cpo与concept

当然，有了对泛型良好支持的CPO机制，我们很多地方还需要对CPO所能接受的参数类型进行约束。

通过前面提到的ranges的源码，细心的同学可能已经发现了，代码中包含大量的concept的定义和使用。concept这里其实就是用来对CPO本身接受的参数类型进行约束的，传入参数类型不匹配，编译期就能很好的发现问题，第一时间发现相关的错误。

如下图所示，ranges中就定义了大量辅助性的concept：

（二）ranges cpo实现范例-微软版

我们以ranges::begin这个cpo为例来看一下ranges库大概是以哪种方式来完成cpo的定义的:

namespace ranges {
    template <class>
    inline constexpr bool _Has_complete_elements = false;

    template <class _Ty>
        requires requires(_Ty& __t) { sizeof(__t[0]); }
    inline constexpr bool _Has_complete_elements<_Ty> = true;

    template <class>
    inline constexpr bool enable_borrowed_range = false;

    template <class _Rng>
    concept _Should_range_access = is_lvalue_reference_v<_Rng> || enable_borrowed_range<remove_cvref_t<_Rng>>;

    namespace _Begin {
        template <class _Ty>
        void begin(_Ty&) = delete;
        template <class _Ty>
        void begin(const _Ty&) = delete;

        template <class _Ty>
        concept _Has_member = requires(_Ty __t) {
            { _Fake_decay_copy(__t.begin()) } -> input_or_output_iterator;
        };

        template <class _Ty>
        concept _Has_ADL = _Has_class_or_enum_type<_Ty> && requires(_Ty __t) {
            { _Fake_decay_copy(begin(__t)) } -> input_or_output_iterator;
        };

        class _Cpo {
        private:
            enum class _St { _None, _Array, _Member, _Non_member };

            template <class _Ty>
            static _CONSTEVAL _Choice_t<_St> _Choose() noexcept {
                if constexpr (is_array_v<remove_reference_t<_Ty>>) {
                    return {_St::_Array, true};
                } else if constexpr (_Has_member<_Ty>) {
                    return {_St::_Member, noexcept(_Fake_decay_copy(_STD declval<_Ty>().begin()))};
                } else if constexpr (_Has_ADL<_Ty>) {
                    return {_St::_Non_member, noexcept(_Fake_decay_copy(begin(_STD declval<_Ty>())))};
                } else {
                    return {_St::_None};
                }
            }

            template <class _Ty>
            static constexpr _Choice_t<_St> _Choice = _Choose<_Ty>();

        public:
            template <_Should_range_access _Ty>
                requires (_Choice<_Ty&>._Strategy != _St::_None)
            _NODISCARD constexpr auto operator()(_Ty&& _Val) const {
                constexpr _St _Strat = _Choice<_Ty&>._Strategy;

                if constexpr (_Strat == _St::_Array) {
                    return _Val;
                } else if constexpr (_Strat == _St::_Member) {
                    return _Val.begin();
                } else if constexpr (_Strat == _St::_Non_member) {
                    return begin(_Val);
                } else {
                    static_assert(_Always_false<_Ty>, "Should be unreachable");
                }
            }
        };
    } // namespace _Begin
    
    inline namespace _Cpos {
        inline constexpr _Begin::_Cpo begin;
    }

    template <class _Ty>
    using iterator_t = decltype(_RANGES begin(_STD declval<_Ty&>()));
} // namespace ranges

忽略一些细节，begin()这个CPO的定义与实现还是比较简单的。我们可以看到，ranges::_Begin::_Cpo 这个ranges::begin定制点，内部通过if constexpr处理了大部分平常我们会使用的序列容器：

• build in array；

• 带begin()成员的对象；

• 最后就是通过ADL的方式尝试去匹配被overload的begin()。

稍微注意通过inline namespace定义的ranges::_Begin::_Cpo类型的begin对象，这样我们简单的通过ranges::begin()就能访问内部定义的_Cpo了。

另外此处也很好的利用了if constexpr的compiler time特性来完成了对几类不同对象begin()的调用方式，对比c++17前的繁复tag dispatch表达，这种方式更简洁，也易于理解和维护。

为了加深理解，我们结合一个简单的例子看一下相应的执行栈。

测试代码:

auto const ints = { 0, 1, 2, 3, 4, 5 };
auto vi = std::ranges::begin(ints);

对应的执行栈-从顶到底:

>  range_test.exe!std::initializer_list<int>::begin() Line 38  C++
   range_test.exe!std::ranges::_Begin::_Cpo::operator()<std::initializer_list<int> const &>(const std::initializer_list<int> & _Val) Line 2035  C++
   range_test.exe!main() Line 93  C++

可以直观的看到当我们调用std::ranges::begin()的时候，访问的是上面给出源码的_Begin_Cpo对象的operator()操作符，最终符合我们预期的的访问到了std::intializer_list<>::begin()，正确的获取到了序列的首指针。抛开一点点编译期可优化的wrapper代码来看，cpo机制本身的运行还是比较简洁可控的。

（三）ranges cpo小结

泛型的cpo+表达各种约束的concept，一扬一抑，使得这种表达能够很好的用于库代码的组织和实现。从ranges中的cpo实现可以看到，相关的代码使用和组织因为层层的namespace定义，和关联对象的声明实现，整体的复杂度还是会比较高，如果库本身涉及的cpo很多，那么理解相关的实现肯定就会比较麻烦。虽然对比隔壁家的go interface和rust traits，简洁易理解的程度有待提升，但cpo机制总算是泛型定制的一种有效解法，而且随着更多库采用相关的实现机制，机制本身也会有更简洁的表达和更低的实用成本，这个我们也会从下一章节的内容中体会到，另外一种使用cpo的方式，整体会比ranges使用的更简洁易懂一些。

四、tag invoke-更好的cpo使用方式

考虑一个问题，如果库的规模扩大化，相关的cpo实现比ranges多比较多，或者就拿ranges来说，cpo多了之后，层层的Wrapper明显会给开发者带来不小的负担。libunifex在面临这个问题的时候，给我们带来了一种新的方式，cpo的tag_invoke模式。这种使用方式来自一个叫做tag_invoke的标准提案，该提案的具体细节我们不再展开了，感兴趣的可以自行去看看P18950R0。

（http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p1895r0.pdf）

（一）tag invoke相关的示例代码

此处我们直接以例子的方式展示tag_invoke的大致使用方式:

#include <iostream>
#include <ranges>
#include <type_traits>

namespace tag_invoke_test {

  template <auto& CPO>
  using tag_t = std::remove_cvref_t<decltype(CPO)>;

    void tag_invoke();

  template <typename CPO, typename... Args>
  using tag_invoke_result_t = decltype(tag_invoke(std::declval<CPO&&>(), std::declval<Args&&>()...));

  template<typename CPO, typename... Args>
  concept nothrow_tag_invocable = noexcept(tag_invoke(std::declval<CPO&&>(), std::declval<Args&&>()...));
  
    struct example_cpo {
        // An optional default implementation
        template<typename T>
        friend bool tag_invoke(example_cpo, const T& x) noexcept {
            return false;
        }

        template<typename T>
        auto operator()(const T& x) const
          noexcept(nothrow_tag_invocable<example_cpo, const T&>) 
            -> tag_invoke_result_t<example_cpo, const T&>
        {
            return tag_invoke(example_cpo{}, x);
        }
          
    };
    inline constexpr example_cpo example{};

    struct my_type {
        friend bool tag_invoke(tag_t<example> , const my_type& t) noexcept {
            return t.is_example_;
        }

        bool is_example_;
    };
} //namespace tag_invoke_test

int main()
{
    auto val = tag_invoke_test::example(3);
    val = tag_invoke_test::example(tag_invoke_test::my_type{ true });

  return 0;
}

（二）代码讲解

如上代码所示，区别于直接在cpo对象的“operator()”操作符重载内完成相关的功能，我们选择在一个统一的tag_invoke()，首参数是cpo类型对象的函数里实现具体的cpo功能：

template<typename T>
friend bool tag_invoke(example_cpo, const T& x) noexcept {
  return false;
}

这样，如果库里面有多个cpo定义的需要，如libunifex中，我们仅需要定义好多个cpo，在需要定制的时候，overload相关的tag_t的tag_invoke()实现，如：

struct my_type {
  friend void tag_invoke(tag_t<set_done> , const my_type& t) noexcept {
    // something do here~~
  }
  friend void tag_invoke(tag_t<set_value> , const my_type& t) noexcept {
    // something do here~~
  }
};

在一个自定义类型中也可以通过不同的tag_t<cpo_object>来完成不同cpo的定制，tag对象的选择会决定我们需要定制的定制点，没有额外的namespace包裹，在用户对象定义中也是统一的采用tag_invoke()来进行重载和定制，tag_t<>本身的对象的名称也能很好的表达它代表的定制点，这对于代码的组织和实现，肯定是更有序更可控的方式了。看到此处，可能有细心的读者会问，不同的定制点需要携带额外的参数，这个其实通过泛型本身就能够很好的支持：

template<typename T, typename... Args>
friend bool tag_invoke(example_cpo, const T& x, Args&&... args) noexcept {
  return false;
}

我们再回头来看看测试代码：

auto val = tag_invoke_test::example(3);
val = tag_invoke_test::example(tag_invoke_test::my_type{ true });

第一次调用example()，我们匹配的是example_cpo中的默认实现，返回的val==false。第二次调用example()，因为我们定制过my_type对应tag的tag_invoke()，返回值则变为了我们定制过的true。

（三）tag invoke小结

&emsp此处我们没有过多的解释tag invoke的相关细节，更多还是通过示例代码来展示机制本身，通过明确的编译期类型，以简单的机制包装，我们能够很好的在泛型存在的情况下，很好的完成对对象的定制，并且这个定制能够很好的支持不同的返回值，不同的参数类型，并且相关的实现本身也并不复杂，这就足以让它成为一些泛型库的选择，如libunifex所做的那样。

五、总结

本章我们从C++定制本身说起，然后说到std::views::filter()的实现猜测，由此引出CPO机制，并更进一步的讲述了CPO的进阶版本，tag_invoke机制。

回到cpo本身，我们可以认为，它很好的补齐了override与泛型之间不那么匹配的问题，一些不那么依赖泛型的定制，如std::pmr::memrory_resource一样，直接使用override，可能是更好的选择。

当涉及到泛型，我们希望更多利用compiler time来组织代码实现的时候，tag invoke本身的优势就体现出来了。这个我们在后续的execution具体代码讲解的过程中也能实际感受到。

参考资料：

1.tag_invoke P18950R0提案

2.libunifex源码库

3.ranges-cppreference

4.Customization point design for library functions

 作者简介

沈芳

腾讯后台开发工程师

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

 推荐阅读