C++20 中的 CPO（定制点对象）与 niebloid

三月 15, 2024 更新: 三月 18, 2024 [C/C++] #C++ #obsidian #合集

C++ 20 CPO 和 Ranges 新算法

在之前的 Ranges 文章中我称 Ranges 为重要改进，不仅仅是因为 Ranges 本身提供了容器无关的抽象，还因为 Ranges 带来了“新的”算法，解决了一些函数查找的历史问题。

这篇文章鸽了好久了，因为理解不到位外加犯懒于是一种都只是半成品草稿，当然，实际上现在发表的这篇也是半成品整理出来的，因为这个话题太复杂了。

从函数查找说起

C++ 的函数查找机制主要分为两类：基于作用域从内到外的查找和实参依赖查找（ADL）。从内到外的查找很好理解，包括有限定的查找和简单的无限定查找（当然，也有注入类名这种“特殊”规则），而 ADL 作为无限定查找的一种情况，跳出了单纯的从内到外的查找方式，在发展的过程中变得非常复杂。

由于本文重点不在 ADL，本人也没能力解释清楚 ADL 的所有规则，因此仅介绍基本内容。

ADL 人如其名，是参考了函数的实参类型的查找规则，简单来讲，ADL 会根据实参的类型，查找从该类型的类内开始，到包含该类声明的第一个外部的命名空间为止的所有函数声明/定义，这代表会查找类内定义和声明的函数，基类的函数，以及存在嵌套类的情况，会查找到其外部类（因为此时还未查找到命名空间）里的函数。

无限定查找的一个重点是无限定查找在内部作用域中找到名字后便不再继续查找外部作用域的名字。

无限定查找有 3 种情况优于 ADL，因此会阻止 ADL：

如果该调用在类内，则会查找到类内成员的声明
调用的块作用域内的函数声明（注意，using 声明不是函数声明）
通过向外层作用域查找找到非函数，例如对象（变量）和类型，和函数模板

第三条是重点，是接下来的内容的核心：如果能查找到变量名，则不使用 ADL。

CPO

C++ 20 全新设计了一类被叫做 CPO（customization point object，定制点对象）的 “函数”。

所谓的定制点，是指 C++ 静态多态的接口，即定制点是 C++ 中可以由用户或者标准库本身改写默认实现的地方，这些定制点是标准规定的或者约定俗成的。

例如 C++ 11 中的 std::begin<T>(T&)，会自动选择成员函数 begin()，还有就是有些库按照约定俗成的 swap 函数，会优先使用用户定义的 swap 而不是 std::swap，虽然 std::begin 不存在默认实现，但是第三方库仍然可以选择使用成员函数，或者非成员函数。这种选择函数的地方就叫定制点。

这些函数包括在 ranges 和 iterator 头文件中的：

ranges::begin
ranges::end
ranges::cbegin
ranges::cend
ranges::rbegin
ranges::rend
ranges::crbegin
ranges::crend
ranges::size
ranges::ssize
ranges::empty
ranges::data
ranges::cdata

以及在 concept 头文件中的

ranges::swap

以及为 C++ 20 的三路比较服务的 compare 头文件里的

strong_order
weak_order
partial_order
compare_strong_order_fallback
compare_weak_order_fallback
compare_partial_order_fallback

使用这些新算法就可以自动完成选择操作，这实际上是为了简化定制点的实现。

传统上定制点大概有 2 种方式：

手动添加特化（注意，不是重载，重载 STL 是未定义行为）
使用 ADL 两步法

显然给 STL 加特化是繁琐而且不安全的，扩展性也不够好，因为用户很可能误操作删除了特化，并且有泛型的“特化”是重载，所以这种方法几乎不被使用

另一种方式是使用 ADL 两步法：


class A {
    void swap(A& other);
}

A a, b;

using std::swap;
swap(a, b);
int i{}, j{};
swap(i, j);

由于 swap(a, b) 是一个无限定查找，同时 A 不是基础类型，并且 using 声明不是函数声明（不会阻止 ADL），因此 ADL 生效，找到了 A::swap 并使用，而后面的 swap(i, j) 中由于 int 是基础类型，因此不应用 ADL，并且当前作用域存在 std::swap，因此找到了 std::swap 并使用。

但问题是，开发者和用户必须要严格遵守这个模式，即先使用 using 声明载进行无限定的调用，否则该效果不会被应用：假设把无限定调用改成对 std::swap 的有限定调用，会导致没有使用用户的 swap；而将 using 指令去掉，会导致无法交换 int 类型的变量。

因此，ranges 新算法内部自己实现了 ADL 两步法，所以老的 std::swap 和 ADL 两步法的无限定调用都可以直接改成 range::swap，同时，range 新算法本身是函数对象而不是函数，使得用户可以使用 using 声明引入这个函数对象，同时使用无限定调用，最后一定找到的是这个函数对象。

隐藏友元

在类内的友元函数，如果不在类外部重写声明，是无法通过有限定查找找到的，但可以被无限定查找中的 ADL 找到。

根据以上知识，我们现在可以说，任何定制点优先使用成员函数，如果左操作数不是同类型的对象，例如一些二元运算符的重载，则应实现为隐藏友元。

Niebloids

Niebloids 是 C++ 20 添加的 Ranges 新算法的一种叫法，Niebloids 采用了多返回值以及 Concepts 约束，更安全也更易用。

同时，Niebloids 保证在无限定调用能同时找到老 STL 算法和 Niebloids 时，一定优先考虑 Niebloids，而不是老的 STL 算法。

例如：


using std::vector;
using namespace std::ranges;
// or using std::ranges::find;

vetcor<int> a;
find(a.begin(), a.end(), 2);
// should call std::ranges::find

但是现在存在两个问题：

vector 在 std 命名空间里，因此 ADL 可以找到 std:find
std::find 作为老 STL 算法，通常要求 begin 和 end 迭代器有相同类型，而新算法不要求，因此 std::find 比 std::ranges::find 更特化同时，std::ranges::find 存在 Concepts，更约束，但是特化优于约束

因此如果 std::ranges::find 是普通函数，则上述代码会使用 std::find。

因此解决方法很简单：将 std::ranges::find 实现为函数对象。

注意，由于 Ranges 新算法不需要定制，因此这些算法不叫作定制点对象。

如何实现 CPO 和 Niebloids

学习如何实现 CPO 和 Niebloids 还是有用的，因为作为库作者很可能需要我们自己提供定制点，但 CPO 和 Niebloids 实际上不能通过 Lambda 实现，原因在 A note on namespace __cpo。

当然，实现 CPO 和 Niebloids 并不需要多么复杂，如果你不想要知道原因（除了定制标准和发明 CPO 以外没人需要知道原因），照抄下面的模板即可：


namespace std::ranges {
  namespace __iter_swap {
    struct __fn {
      auto operator()(~~~) const { ~~~ }
    };
  }
  inline namespace __cpo {
    inline constexpr auto iter_swap = __iter_swap::__fn{};
  }
}

C++的定制点设计

定制点（customization point）在特定领域里也是老生常谈的话题了，本文快速总结相关的设计方案。

什么是定制点

作为库开发者的大佬们想必都会思考如何为库使用者提供一种定制能力，这就是广义上的定制点。

另外也可以通过C++语言标准了解定制点。它的定义是较为狭义的（标准库视角），但也只要求是写在std命名空间外部的某种重载方式就行了。

Other than in namespace std or in a namespace within namespace std, a program may provide an overload for any library function template designated as a customization point , provided that (a) the overload’s declaration depends on at least one user-defined type and (b) the overload meets the standard library requirements for the customization point.

本文不局限于标准库，探讨广义的C++定制点。

有哪些定制点

目前C++的主流方案有：

类继承。
类模板特化。
实参依赖查找（ADL）。
定制点对象（CPO）。
tag_invoke。

未来可能提供的方案有：

可定制函数（customizable functions）。
静态反射。

_{不受待见(?)的方案有：依赖注入（DI）。}

类继承

类继承的介绍就无需多言了，示例如下：

class Loggable {
public:
    virtual void dump() = 0;
};

class Meme: public Loggable {
public:
    void dump() override { /*...*/ }
};

struct Logger {
    void log(Loggable &loggable) {
        loggable.dump();
    }
    // ...
};

virtual是语言特性直接给出的定制点支持，能得到的好处大家都懂，但缺陷还是值得一提。

有一种观点认为类继承是侵入式的设计：侵入指的是更改了类结构，比如引入了额外的子对象。而类继承显然引入了不必要的基类。其实引入不算问题，但是一个不能修改的类就无法完成定制确实是问题。

另一个问题是带来了可能不必要的额外运行时成本。虽说运行时多态是没有选择，但在编译期确认的情况下，成本再低也是成本。后续介绍的方案均为静态多态方案。

最后还有一点是类型系统的扩展问题。类继承只支持到类类型（class type，也就是口头的class或者struct），并没有覆盖到数组类型、指针类型和基本类型等更多类型的定制。

实际应用：随地都是。

类模板特化

如字面意思，定制点通过类模板的特化来实现。示例如下：

// 用户自定义类型
struct point {
    double x, y;
};

// 库提供的定制点
template <>
struct fmt::formatter<point> : nested_formatter<double> {
    auto format(point p, format_context& ctx) const {
        return write_padded(ctx, [=](auto out) {
            return format_to(out, "({}, {})", nested(p.x), nested(p.y));
        });
    }
};

int main() {
    fmt::print("[{:>20.2f}]", point{1, 2});
}

这种实现是完全非侵入式的，对类型系统有完善的支持且无额外运行时成本。

但也有问题，那就是特化出来的模板必须要全部实现，而不能只实现其中一个函数。也就是说这种定制点只适用于少量的定制。也可参考示例中通过静态的继承提供较为通用的非定制函数来缓解问题。

NOTE: 不建议使用特化的函数模板来完成定制，因为不支持偏特化。这也是为什么std::hash使用类模板的原因。

实际应用：{fmt} library。

实参依赖查找

实参依赖查找（argument-dependent lookup），又称ADL或Koenig查找。是C++语言标准中应用于无限定的函数名进行查找的规则。

ADL的细节很多，简单点可理解为实参所在的命名空间也被加入到当前的函数重载决议的候选集中。

最简单的示例如下：

#include <iostream>

int main() {
    endl(std::cout);
}

ADL检验std命名空间，因为endl的实参在std中，并找到了std::endl且唯一匹配。所以函数确认为std::endl。（你也可以在C++ Insights查看该示例的ADL结果。）

由此产生了隐藏友元惯用法（hidden friend idiom）搭配ADL作为定制点的方案，示例如下：

#include <iostream>

namespace Foo {
    class Bar {
        // A hidden (private) friend!
        friend void swap(Bar& a, Bar& b) {
            std::cout << "I am here" << std::endl;
        }
    };
} // Foo

int main() {
    Foo::Bar a, b;
    int x, y;
    using std::swap;
    swap(a, b);      // Foo::swap is called.
    swap(x, y);      // std::swap is called.
}

NOTE: 使用隐藏友元可以避免参与正常的名字查找过程，它只能应用于ADL过程，有更强的封装性。

This function is to be found via argument-dependent lookup only.

很显然它可以按需定制，没有类模板特化的先天缺陷。并且放弃使用友元的话（定制点函数写到类外即可），也可以做到非侵入式的定制。

但这种方案存在天坑：难以正确的使用（必须两阶段，先using再非限定名调用），难以检错（任何一步错了，也有可能编译成功，但是调用了哪个版本就难说了）；更离谱的是，调用正确但实现写错了是完全不知情（如果用户没有自行提供concept，写成swap-by-value编译器也不会吭声）。

连基本的保障都做不到，简直是犯了定制点的大忌。

实际应用：???

定制点对象

定制点对象（customization point object），又称CPO。CPO在核心语言中被定义为一种可与程序定义类型进行特定语义交互的字面类型函数对象。所谓特定语义，就认为是能当函数来调用就好了。

这种设计的存在就是为了弥补ADL定制点的缺陷。原理是基于C++类型系统中「函数非对象」的规则，将定制点函数替换为定制点函数对象，从而隐式关闭ADL（或者说是把ADL隐藏到库内部完成）。

NOTE: 很显然，函数对象不是函数。这也没啥好解释的，更多细节请自行翻阅。

一个迭代器CPO的示例如下，可以关注library::begin()的行为：

#include <type_traits>
#include <vector>
#include <iostream>

namespace library {

    // Best practice: provide a separate namespace for each CP class.
    namespace begin_cpo_detail {
        struct Begin_fn {
            template <typename /*👈concept is better*/ Container>
            decltype(auto) operator()(Container &&container) const {
                // Internal ADL here!
                return begin(std::forward<Container>(container));
            }
        };

        // Generic default begin function template(s).
        // TODO: array types...
        template <typename T>
        decltype(auto) begin(T &&obj) /*noexcept(noexcept(...))*/ {
            return std::forward<T>(obj).begin();
        }
    }

    // All CPOs should be wrapped into this inline namespace.
    inline namespace _cpo {
#if __cplusplus >= 201703L
        // A customization point OBJECT.
        inline constexpr begin_cpo_detail::Begin_fn begin {};
#else // __cplusplus >= 201703L
        // Workaround for C++14.
        template <typename Cpo>
        constexpr Cpo _static_const {};

        namespace {
            // A customization point "OBJECT".
            constexpr auto &begin = _static_const<begin_cpo_detail::Begin_fn>;
        }
#endif
    } // _cpo
} // library

namespace end_user {

template <typename T>
class Vector {
public:
    Vector(std::initializer_list<T> il): _real_vector(il) {}
    // User-defined default begin() function.
    // Called by std::begin().
    auto begin() { return _real_vector.begin(); }

private:
    std::vector<T> _real_vector;

    // User-defined customized begin() function.
    // A hooked begin-iterator (with hidden friend again).
    friend auto begin(Vector<T> &vec) {
        using Hook = std::vector<std::string>;
        static Hook strings {"hook", "jintianxiaomidaobilema"};
        return strings.begin();
    }
};

} // end_user

int main() {
    end_user::Vector<int> f { 1, 2, 3 };
    auto iter1 = f.begin();
    // [1]
    std::cout << *iter1 << std::endl;

    ::puts("===============");

    // STL-begin.
    auto iter2 = std::begin(f);
    // [1]
    std::cout << *iter2 << std::endl;

    ::puts("===============");

    // ADL enabled, STL-bypass-begin.
    auto iter3 = begin(f);
    // [hook]
    std::cout << *iter3 << std::endl;

    ::puts("===============");

    // **CPO is here.**
    // ADL disabled, since library::begin is an object.
    //
    // With library:: prefix, not end_user::,
    // `library` can detect user-defined hooks automatically.
    auto iter4 = library::begin(f);
    // [hook]
    std::cout << *iter4 << std::endl;
}

CPO实现使得通过显式的<库命名空间>::限定就能检测是否有用户定制实现。如果存在，则优先使用用户定制实现，否则再使用库内置实现。并不会存在任何歧义。显然也没有了最大的天坑问题，库现在可以主动内置concept避免错误。

但是这种方案在C++14版本是难以实现的，因为缺少inline constexpr变量的语法支持，所以还要通过引用多绕一层以满足ODR的要求。更具体地说就是模板本身可以ODR，然后通过匿名namespace的内部链接为每一个翻译单元准备一个引用，它们都指涉相同的CPO对象，由于引用具有相同的地址，因此符合ODR要求。不过这再怎么麻烦也都是过去的事情了。

NOTE0: 为什么示例中CPO（begin对象）需要被包裹在inline namespace？这是前人踩坑的经验……如果去掉这个inline namespace，在同一个library命名空间可能有另一个类使用了begin同名的隐藏友元函数，由于ADL候选了library命名空间的原因，隐藏友元仍可被查找，此时编译器认为存在歧义：begin既是对象，也是函数。但是语言标准保证了使用inline namespace后不会产生歧义。

NOTE1: 从C++20开始，lambda也可以直接作为CPO使用。

NOTE2: 还有一个同样禁用ADL的玩家是niebloid。目前niebloid（的实现）就是等同于CPO，但是它的定义更加宽泛，未来如果有更新的标准支持显式禁用ADL，它还可能是一个函数。

The function-like entities described on this page are niebloids…In practice, they may be implemented as function objects, or with special compiler extensions.

实际应用：Range library。

tag_invoke

前面的CPO看起来已经是个不错的方案，但是探索远没有结束。

tag_invoke的动机是针对CPO定制点过多时改进的措施，以避免对命名空间造成大量污染。因为每增加一个CPO，那就意味着需要全局预留这个名字（用户使用这个名字将被库检测到并误判为定制点）。

tag_invoke的做法是全局只预留一个名字tag_invoke，它是唯一的全局预留CPO（未来的标准库会提供std::tag_invoke，但是tag_invoke的实现完全可以由库开发者自行完成），其它的定制点重载这个全局定制点再次派发。

tag_invoke的一个巧妙之处是利用了「CPO是对象」的性质：既然是对象，那么拿去当参数传递当然没问题。于是有了tag_invoke(cpo_type cpo, ARGS...)的定制点设计。

库的开发已经有明确方向了，但剩下用户的定制存在问题：用户怎么知道库使用了什么类型的CPO？为了避免无聊的萃取，可以在库（或者标准库）层面内置tag_t辅助工具。此时对于库用户来说，只需实现tag_invoke(tag_t<cpo>, ...)即可得到cpo同名定制点。

所以tag invoke就是CPO加上标签派发得到的产物，这里给出CPO章节修改后的tag_invoke示例：

#include <type_traits>
#include <vector>
#include <iostream>

// Part of std::tag_invoke.
// Copied and modified from Eric Niebler's gist:
// https://gist.github.com/ericniebler/056f5459cf259da526d9ea2279c386bb
namespace standard {
   namespace detail {
      void tag_invoke();
      struct tag_invoke_t {
         template<typename Tag, typename... Args>
         constexpr decltype(auto) operator() (Tag tag, Args &&... args) const /*noexcept(...)*/ {
            // Internal ADL!
            return tag_invoke(static_cast<Tag &&>(tag), static_cast<Args &&>(args)...);
         }
      };
   }

   inline constexpr detail::tag_invoke_t tag_invoke{};

   template<auto& Tag>
   using tag_t = std::decay_t<decltype(Tag)>;
}

namespace library {
    namespace begin_cpo_detail {
        struct Begin_fn {
            template <typename /*👈concept is better*/ Container>
            decltype(auto) operator()(Container &&container) const {
                // Goto the single reserved CPO (std::tag_invoke).
                return standard::tag_invoke(*this, std::forward<Container>(container));
            }
        };

        // Generic default begin function template(s).
        // TODO: array types...
        template <typename T>
        decltype(auto) tag_invoke(Begin_fn, T &&obj) /*noexcept(noexcept(...))*/ {
            return std::forward<T>(obj).begin();
        }
    }

    inline namespace _cpo {
        inline constexpr begin_cpo_detail::Begin_fn begin {};
    }
} // library

namespace end_user {

template <typename T>
class Vector {
public:
    Vector(std::initializer_list<T> il): _real_vector(il) {}
    // User-defined default begin() function.
    // Called by std::begin().
    auto begin() { return _real_vector.begin(); }

private:
    std::vector<T> _real_vector;

    // User-defined customized begin() function
    // A hooked begin-iterator (with hidden friend again).
    friend auto tag_invoke(standard::tag_t<library::begin>, Vector<T> &vec) {
        using Hook = std::vector<std::string>;
        static Hook strings {"hook", "xiaomijintiandaobila"};
        return strings.begin();
    }
};

} // end_user

int main() {
    end_user::Vector<int> f { 1, 2, 3 };
    auto iter1 = f.begin();
    // [1]
    std::cout << *iter1 << std::endl;

    ::puts("===============");

    // STL-begin.
    auto iter2 = std::begin(f);
    // [1]
    std::cout << *iter2 << std::endl;

    ::puts("===============");

    // No ADL enabled.
    // auto iter3 = begin(f);
    //
    // ::puts("===============");

    // **tag_invoke is here.**
    // ADL disabled, since library::begin is an object.
    //
    // With library:: prefix, not end_user::,
    // `library` can detect user-defined hooks automatically.
    auto iter4 = library::begin(f);
    // [hook]
    std::cout << *iter4 << std::endl;
}

无需锐评，tag_invoke就是目前ADL科技的终极版本。

实际应用：NVIDIA stdexec。

看提案，战未来？

先别急着ADL YES。各种基于ADL的定制点都难免让实现藏得更深，也许该从语法上提供直接改进。

提案P2279R0提到2种新的定制点思路：可定制函数和静态反射。我粗略看了一下，可定制函数指的是通过新的语法去完成virtual转换到静态多态的过程（恰好virtual不能应用于类外，现在填上这个坑作为新的用途），而不用再考虑复杂的ADL问题；静态反射则是另一个思路，通过支持静态反射来完成可定制函数，而不必专门为定制点开发新的语法（其实文本太长没怎么看，很可能是我瞎说的……反正都是思路）。

这些美好设想现在还看不到弊端，但是有更多的可行手段必然是利好开发者。

结束语

本文快速总结了各种定制点的优缺点及实际应用，有写库需求的时候也可以作为技术选型的参考。

另外，C++20之后的标准库也渗透着越来越多的定制点（实际应用里面的三巨头将全被收入标准库），其实还藏有很多坑留给大家去踩……这是个漫长的过程，总之先这样吧。

References

Customization Methods: Connecting User and C++ Library Code (CppCon 2023) – YouTube API Reference – fmt 10.2.0 documentation Argument-dependent lookup – cppreference [customization.point.object] – Working Draft Recommendations for Specifying “Hidden Friends” – ISOCPP We need a language mechanism for customization points – ISOCPP A note on namespace __cpo – Arthur O’Dwyer Suggested Design for Customization Points – ISOCPP tag_invoke: A general pattern for supporting customisable functions – ISOCPP

Niebloids and Customization Point Objects

C++20 Ranges bring with them several new ideas by way of solving a lot of different problems.

Two of the new terms in Ranges, niebloids and customization point objects (or CPOs), are very frequently confused and used interchangeably. This confusion is pretty understandable (the two are pretty similar, and we don’t even have a language mechanism to implement them differently so the fact that they are different at all is more specification handwaviness than actual implementation difference), but the two exist to solve different problems and apply to different parts of the library.

I wanted to take the time here to elaborate on the differences and hopefully alleviate some confusion.

Customization Point Objects Solve Customization Dispatch

There are a few problems in the ADL-based customization point space.

First, we have this problem where if you want to swap two objects, there is a very specific incantation you have to use:

// wrong, might not even find a candidate
swap(a, b);

// wrong, might not find customization point
std::swap(a, b);

// correct, but painful
using std::swap; swap(a, b);

What customization point objects do is wrap the customization dispatch in a single object. So that you don’t have to do any of this:

// correct
std::ranges::swap(a, b);

// same thing, just as correct
using namespace std::ranges;
swap(a, b);

A second problem with the two step isn’t just that it’s Yet Another C++ Incantation. If ADL lookup finds a user-provided function, that function gets called and that’s that. We don’t have the ability to actually check that the user-provided function is correct. What if the user provided begin(e) but that’s actually a void function that starts some execution context and has nothing to do with ranges at all? We don’t want to pick that up! Customization point objects also allow you to impose constraints checking in all cases.

In the standard library, customization point object is a specific term of art that is a semiregular, function object that is const-invocable. And the standard library has a whole bunch of them in the std::ranges namespace (begin, end, swap, etc.) but even a few in plain old std (e.g. strong_order).

One bonus point of confusion here: customization point objects aren’t always customizeable! For instance, std::ranges::cbegin has no customization point cbegin that it tries to invoke; it only ever calls begin.

For more, see N4381.

Niebloids solve undesired ADL

While the term “customization point object” appears in the standard, the term “niebloid” does not. Instead, we have this text:

The entities defined in the std::ranges namespace in this Clause are not found by argument-dependent name lookup ([basic.lookup.argdep]). When found by unqualified ([basic.lookup.unqual]) name lookup for the postfix-expression in a function call ([expr.call]), they inhibit argument-dependent name lookup.

The problem here is completely unrelated to the problem that we need customization point objects for. Let’s take one of the simpler algorithms, std::copy. For C++98 through C++17, we had this overload (I’m ignoring the parallel one):

template<class InputIterator, class OutputIterator>
constexpr OutputIterator copy(InputIterator first, InputIterator last,
                              OutputIterator result);

Easy, familiar. But consider the return type. copy by definition has to go through the entire input range, yet it doesn’t return the end input iterator, only the new output iterator. This is okay in C++17 where we have iterator pairs, since you already by definition have the end input iterator. But once C++20 comes around, we might not actually have the end input iterator, we might only have a sentinel. For example:

struct zstring_sentinel {
    bool operator==(char const* p) const {
        return *p == '\0';
    }
};

void copy_string(char const* src, char* dst) {
    std::ranges::copy(some_ptr, zstring_sentinel{}, dst);
}

This works fine. In the process of copying this null-terminated string, we also do find the null terminator. But then we throw it away, even though that would be useful information that took work to compute! This is why the C++20 ranges overloads look different:

  namespace ranges {
    // basically a pair
    template<class I, class O>
      using copy_result = in_out_result<I, O>;

    template<input_iterator I, sentinel_for<I> S, weakly_incrementable O>
      requires indirectly_copyable<I, O>
      constexpr copy_result<I, O>
        copy(I first, S last, O result);

    template<input_range R, weakly_incrementable O>
      requires indirectly_copyable<iterator_t<R>, O>
      constexpr copy_result<borrowed_iterator_t<R>, O>
        copy(R&& r, O result);
  }
}

This is a pretty nice improvement, allowing us to both copy and find the end input iterator in one go. But we have this problem, what happens when we do:

using namespace std::ranges;

copy(first, last, result);

Which overload gets called? If none of first, last, or result have std as an associated namespace, then this is easy: we only have one possible candidate anyway (well, I guess two if you include the std::ranges::copy overload that takes a range, but it only takes two parameters, so it’s no kind of viable).

However, what happens if we do have std as an associated namespace? Now things get a little trickier. If first and last have different types, then std::copy couldn’t be a viable candidate, so we’d still call std::ranges::copy. But if first and last have the same type (i.e. this is “common” range), then we would call std::copy! Because it’s more specialized!

This is easier to see if strip some information and put them closer together:

template <typename T>
void f(T, T); // approximately std::copy

template <typename T, typename U>
    requires something<T, U>
void f(T, U); // approximately std::ranges::copy

“More specialized” as a tiebreaker precedes “more constrained”.

The consequence of this is that seemingly innocuous code like:

template <typename R>
void f(R&& r) {
    using namespace std::ranges;

    // intent is to use std::ranges::copy
    auto [i, o] = copy(r.begin(), r.end(), somewhere);
}

May or may not compile. Moreover, if r is a type as exotic as std::vector<int>, then whether or not the above works is entirely implementation-defined. If std::vector<int>::iterator is int* (entirely allowed), then the above is fine (ADL wouldn’t find std::copy). But if std::vector<int>::iterator is, say, __gnu_cxx::__normal_iterator<int*, std::vector<int> > (as it is in libstdc++), then the above is broken.

This is quite bad.

We definitely want to ensure that whenever this works:

std::ranges::some_algo(first, last, args...);

That this also works and does the same thing:

using namespace std::ranges;
some_algo(first, last, args...);

Unfortunately, if we implemented std::ranges::copy as two overloaded function templates, we could not stop this from happening. We’re, basically, doomed. While this is especially bad for copy where the return type changes, it’s also not ideal for algorithms like find or any_of where even though the return type is the same, it’s still surprising that the two formulations can call different functions entirely.

However, ADL only kicks in if the initial unqualified lookup either found nothing or found functions or function templates. If unqualified look finds an object, no ADL happens. So if instead of declaring:

namespace ranges {
    template<input_iterator I, sentinel_for<I> S, weakly_incrementable O>
      requires indirectly_copyable<I, O>
      constexpr copy_result<I, O>
        copy(I first, S last, O result);

    template<input_range R, weakly_incrementable O>
      requires indirectly_copyable<iterator_t<R>, O>
      constexpr copy_result<borrowed_iterator_t<R>, O>
        copy(R&& r, O result);
}

we declared:

namespace ranges {
    struct copy_fn {
        template<input_iterator I, sentinel_for<I> S, weakly_incrementable O>
            requires indirectly_copyable<I, O>
        constexpr copy_result<I, O>
            operator()(I first, S last, O result) const;

        template<input_range R, weakly_incrementable O>
            requires indirectly_copyable<iterator_t<R>, O>
        constexpr copy_result<borrowed_iterator_t<R>, O>
            operator()(R&& r, O result) const;
    };

    inline constexpr copy_fn copy{};
}

Then we have no problem. std::ranges::copy and using namespace std::ranges; copy both find that object and lookup stops. Problem solved.

But… we don’t want to specify algorithms as overload function call operators. We want to specify algorithms as, well, algorithms. As functions. So we insert this wording about how magically all of these functions inhibit ADL, so that we can have sane specification. Even though our only current language mechanism for living up to this specification is to make them objects.

And indeed, the ranges::copy I wrote there meets the criteria for a customization point object. It’s just… not actually a customization point object, because we just don’t want to call it an object. We want to call it a function.

So it became a niebloid.

It’s possible that a future language feature might come around that would allow us to explicitly opt functions and functions templates out of ADL. This would allow an implementation strategy like:

namespace ranges {
    template<input_iterator I, sentinel_for<I> S, weakly_incrementable O>
        requires indirectly_copyable<I, O>
      no_adl constexpr copy_result<I, O>
        copy(I first, S last, O result);

    template<input_range R, weakly_incrementable O>
        requires indirectly_copyable<iterator_t<R>, O>
      no_adl constexpr copy_result<borrowed_iterator_t<R>, O>
        copy(R&& r, O result);
  }
}

For instance, Matt Calabrese’s Customization Point Functions proposal would allow you to declare a function final to get this desired ADL-inhibiting behavior.

And the specification is written in a way to allow such future language evolution without having to change anything. Indeed, it is within the implementation purview today for GCC to do something like add a __gcc_no_adl specifier that itself magically inhibits ADL and ends up with std::ranges::copy not being an object (although they do not do that today). Which means that while:

auto f = std::ranges::begin;

is specified to be valid code, the same is not true for:

auto g = std::ranges::copy;

Because std::ranges::copy need not actually be an object (though, again, that’s the only standard implementation strategy) and even if it were an object, it need not actually be copyable.

See also STL2 Issue #371. I thought I had read about this in a paper or blog at some point, but I can’t seem to find one at the moment.

Niebloids vs Customization Point Objects

In short:

a customization point object is a semiregular, function object (by definition) that exists to handle constrained ADL dispatch for you. ranges::begin, ranges::swap, etc, are customization point objects.
a niebloid is a colloquial name for the algorithms declared in std::ranges that inhibit ADL. The only implementation strategy in standard C++20 for them is to make them function objects, but they are not required to be objects at all (nor are they required to be copyable, etc.) and a possible future language extension would allow them to be implemented as proper function templates.

These terms are completely disjoint - they refer to different parts of the library and exist as solutions to different problems. A niebloid is not a customization point object (nor even required to be an object), a customization point object is not a niebloid (although, since it is an object, it does also inhibit ADL).

The More You Know.