为什么 ADL 不适用于 Boost.Range？

Question

正在考虑：

#include <cassert>
#include <boost/range/irange.hpp>
#include <boost/range/algorithm.hpp>

int main() {
    auto range = boost::irange(1, 4);
    assert(boost::find(range, 4) == end(range));
}

Live Clang demo Live GCC demo

这给出：

main.cpp:8:37: error: use of undeclared identifier 'end'

考虑到如果你写 using boost::end; 它 works just fine，这意味着 boost::end 是可见的：

为什么 ADL 不工作并在表达式 end(range) 中找到 boost::end？如果是故意的，背后的原理是什么？

需要明确的是，预期结果类似于 this example 中使用 std::find_if 和不合格的 end(vec).

中发生的结果

Answer 1

那是因为 boost::end 是 inside an ADL barrier, which is then pulled in boost at the end of the file。

但是，来自 cppreference's page on ADL（抱歉，我手边没有 C++ 草稿）：

1) using-directives in the associated namespaces are ignored

这会阻止它被包含在 ADL 中。

Answer 2

在 boost/range/end.hpp 中，他们通过将 end 放入 range_adl_barrier 命名空间，然后 using namespace range_adl_barrier; 将其放入 boost 命名空间来明确阻止 ADL。

因为 end 实际上不是来自 ::boost，而是来自 ::boost::range_adl_barrier，ADL 找不到它。

boost/range/begin.hpp描述了他们的推理：

// Use a ADL namespace barrier to avoid ambiguity with other unqualified
// calls. This is particularly important with C++0x encouraging
// unqualified calls to begin/end.

没有给出这会导致问题的示例，因此我只能对他们在谈论的内容进行理论化。

这是我发明的一个例子，说明 ADL 如何导致歧义：

namespace foo {
  template<class T>
  void begin(T const&) {}
}

namespace bar {
  template<class T>
  void begin(T const&) {}

  struct bar_type {};
}

int main() {
  using foo::begin;
  begin( bar::bar_type{} );
}

live example。 foo::begin 和 bar::begin 都是在该上下文中调用 begin( bar::bar_type{} ) 的同样有效的函数。

这可能就是他们在谈论的内容。他们的 boost::begin 和 std::begin 在 boost 的类型上有 using std::begin 的上下文中可能同样有效。通过将它放在 boost 的子命名空间中，std::begin 被调用（自然地在范围内工作）。

如果命名空间 boost 中的 begin 不太通用，那将是首选，但他们不是这样写的。

Answer 3

历史背景

根本原因在此 closed Boost ticket

中进行了讨论

With the following code, compiler will complain that no begin/end is found for "range_2" which is integer range. I guess that integer range is missing ADL compatibility ?

#include <vector>

#include <boost/range/iterator_range.hpp>
#include <boost/range/irange.hpp>

int main() {
    std::vector<int> v;

    auto range_1 = boost::make_iterator_range(v);
    auto range_2 = boost::irange(0, 1); 

    begin(range_1); // found by ADL
      end(range_1); // found by ADL
    begin(range_2); // not found by ADL
      end(range_2); // not found by ADL

    return 0;
}

boost::begin() and boost::end() are not meant to be found by ADL. In fact, Boost.Range specifically takes precautions to prevent boost::begin() and boost::end() from being found by ADL, by declaring them in the namespace boost::range_adl_barrier and then exporting them into the namespace boost from there. (This technique is called an "ADL barrier").

In the case of your range_1, the reason unqualified begin() and end() calls work is because ADL looks not only at the namespace a template was declared in, but the namespaces the template arguments were declared in as well. In this case, the type of range_1 is boost::iterator_range<std::vector<int>::iterator>. The template argument is in namespace std (on most implementations), so ADL finds std::begin() and std::end() (which, unlike boost::begin() and boost::end(), do not use an ADL barrier to prevent being found by ADL).

To get your code to compile, simply add "using boost::begin;" and "using boost::end;", or explicitly qualify your begin()/end() calls with "boost::".

说明 ADL 危险的扩展代码示例

ADL 对 begin 和 end 的不合格调用的危险是双重的：

一组关联的命名空间可能比预期的要大得多。例如。在 begin(x) 中，如果 x 有（可能是默认的！）模板参数，或者在它的实现中隐藏了基础 classes，模板参数及其基础的关联命名空间 classes 也被 ADL 考虑。这些关联的命名空间中的每一个都可能导致 begin 和 end 在参数相关查找期间被引入许多重载。
在重载解析期间无法区分不受约束的模板。例如。在 namespace std 中，begin 和 end 函数模板不会为每个容器单独重载，或者以其他方式限制所提供容器的签名。当另一个命名空间（例如boost）也提供类似的不受约束的函数模板时，重载解析将认为两者相等匹配，并发生错误。

以下代码示例说明了以上几点。

一个小型容器库

第一个要素是有一个容器 class 模板，很好地包装在它自己的命名空间中，带有一个派生自 std::iterator 的迭代器，以及通用和不受约束的函数模板 begin 和 end.

#include <iostream>
#include <iterator>

namespace C {

template<class T, int N>
struct Container
{
    T data[N];
    using value_type = T;

    struct Iterator : public std::iterator<std::forward_iterator_tag, T>
    {
        T* value;
        Iterator(T* v) : value{v} {}
        operator T*() { return value; }
        auto& operator++() { ++value; return *this; }
    };

    auto begin() { return Iterator{data}; }
    auto end() { return Iterator{data+N}; }
};

template<class Cont>
auto begin(Cont& c) -> decltype(c.begin()) { return c.begin(); }

template<class Cont>
auto end(Cont& c) -> decltype(c.end()) { return c.end(); }

}   // C

小范围库

第二个要素是拥有一个范围库，它也包含在自己的命名空间中，带有另一组不受约束的函数模板 begin 和 end。

namespace R {

template<class It>
struct IteratorRange
{
    It first, second;

    auto begin() { return first; }
    auto end() { return second; }
};

template<class It>
auto make_range(It first, It last)
    -> IteratorRange<It>
{
    return { first, last };    
}

template<class Rng>
auto begin(Rng& rng) -> decltype(rng.begin()) { return rng.begin(); }

template<class Rng>
auto end(Rng& rng) -> decltype(rng.end()) { return rng.end(); }

} // R

通过 ADL 重载解析歧义

当一个人试图将迭代器范围放入容器时，问题就开始了，同时使用不合格的 begin 和 end 进行迭代：

int main() 
{
    C::Container<int, 4> arr = {{ 1, 2, 3, 4 }};
    auto rng = R::make_range(arr.begin(), arr.end());
    for (auto it = begin(rng), e = end(rng); it != e; ++it)
        std::cout << *it;
}

Live Example

rng 上的参数相关名称查找将为 begin 和 end 找到 3 个重载：来自 namespace R （因为 rng 住在那里），来自 namespace C （因为 rng 模板参数 Container<int, 4>::Iterator 住在那里），以及来自 namespace std （因为迭代器是从std::iterator)。 重载解析将认为所有 3 个重载均等匹配，这会导致硬错误。

Boost 通过将 boost::begin 和 boost::end 放入内部命名空间并使用指令将它们拉入封闭的 boost 命名空间来解决这个问题。另一种方法，也是 IMO 更直接的方法，是 对类型 （不是函数）进行 ADL 保护，因此在这种情况下，Container 和 IteratorRange class 个模板。

Live Example With ADL barriers

保护您自己的代码可能还不够

有趣的是，ADL 保护 Container 和 IteratorRange 将 - 在这种特殊情况下 - 足以让上面的代码运行没有错误，因为 std::begin 和std::end 将被调用，因为 std::iterator 不受 ADL 保护。 这非常令人惊讶和脆弱。例如。如果 C::Container::Iterator 的实现不再派生自 std::iterator，代码将停止编译。因此，最好在 namespace R 的任何范围内使用合格的调用 R::begin 和 R::end，以防止这种不正当的名称劫持。

另请注意，range-for 曾经具有上述语义（使用至少 std 作为关联命名空间来执行 ADL）。这在 N3257 中进行了讨论，这导致了 range-for 的语义变化。当前的 range-for 首先查找成员函数 begin 和 end，因此 std::begin 和 std::end 将不被考虑，无论 ADL 障碍和继承自 std::iterator.

int main() 
{
    C::Container<int, 4> arr = {{ 1, 2, 3, 4 }};
    auto rng = R::make_range(arr.begin(), arr.end());
    for (auto e : rng)
        std::cout << e;
}

Live Example

为什么 ADL 不适用于 Boost.Range？

Why is ADL not working with Boost.Range?

c++

boost

namespaces

argument-dependent-lookup

boost-range

历史背景

说明 ADL 危险的扩展代码示例

保护您自己的代码可能还不够