c++ - 为什么 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 不起作用并找不到 boost::end在表达式 end(range) 中?如果是故意的，其背后的理由是什么？

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

Answer 1

历史背景

此 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有(可能是默认的!)模板参数，或在其实现中隐藏的基类，模板参数及其基类的关联命名空间也被 ADL 考虑。每个关联的命名空间都可能导致 begin 的许多重载和 end在参数相关查找期间被拉入。

在重载决议期间无法区分不受约束的模板 .例如。在 namespace std , begin和 end函数模板不会为每个容器单独重载，或者以其他方式受限于所提供容器的签名。当另一个命名空间(例如 boost )也提供类似的不受约束的函数模板时，重载决议将考虑两者相等匹配，并发生错误。

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

一个小型容器库

第一个要素是有一个容器类模板，很好地包装在它自己的命名空间中，并带有一个派生自 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 找到 3 个重载和 end :来自 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类模板。

Live Example With ADL barriers

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

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

还要注意 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