14

Considering:

#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

this gives:

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

Considering that if you write using boost::end; it works just fine, which implies that boost::end is visible:

Why is ADL not working and finding boost::end in the expression end(range)? And if it's intentional, what's the rationale behind it?


To be clear, the expected result would be similar to what happens in this example using std::find_if and unqualified end(vec).

4

3 回答 3

13

历史背景

根本原因在这个封闭的 Boost 票中讨论

使用以下代码,编译器将抱怨找不到range_2整数范围的“”的开始/结束。我猜整数范围缺少 ADL 兼容性?

#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()并且boost::end()不应该被 ADL 找到。事实上,Boost.Range 专门采取预防措施来防止 boost::begin()boost::end()被 ADL 发现,方法是在 中声明它们,namespace boost::range_adl_barrier然后namespace boost从那里将它们导出到。(这种技术称为“ADL 屏障”)。

在你的情况下range_1,不合格begin()end() 调用工作的原因是因为 ADL 不仅查看声明模板的命名空间,还查看声明模板参数的命名空间。在这种情况下,类型range_1boost::iterator_range<std::vector<int>::iterator>。模板参数在namespace std(在大多数实现中),因此 ADL 找到 std::begin()and std::end()(与boost::begin()and 不同boost::end(),它不使用 ADL 屏障来防止被 ADL 找到)。

要编译您的代码,只需添加“ using boost::begin;”和“ using boost::end;”,或使用“”明确限定您的begin()/end()调用boost::

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

beginADL 来自对和的不合格调用的危险end是双重的:

  1. 一组关联的命名空间可能比预期的要大得多。例如begin(x),如果x在其实现中有(可能是默认的!)模板参数或隐藏的基类,则 ADL 也会考虑模板参数及其基类的关联命名空间。这些关联的命名空间中的每一个都可能导致参数依赖查找期间的许多重载beginend被拉入。
  2. 在重载解析期间无法区分不受约束的模板。例如在 中namespace stdbeginend函数模板不会为每个容器单独重载,或者以其他方式受限于所提供容器的签名。当另一个命名空间(例如boost)也提供类似的无约束函数模板时,重载决策将同时考虑相等匹配,并发生错误。

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

一个小型容器库

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

#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

一个小范围库

第二个要素是拥有一个范围库,也包含在自己的命名空间中,还有另一组不受约束的函数模板beginend.

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 重载分辨率歧义

当尝试将迭代器范围放入容器时,麻烦就开始了,同时使用不合格的beginand进行迭代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;
}

现场示例

依赖于参数的名称查找rng将找到 3 个重载beginend from namespace R(因为rng存在于那里)、from namespace C(因为rng模板参数Container<int, 4>::Iterator存在于那里)和 from namespace std(因为迭代器派生自std::iterator)。然后,重载解决方案将所有 3 个重载视为相等匹配,这会导致硬错误。

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

带有 ADL 障碍的实时示例

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

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

另请注意,range-for 曾经具有上述语义(至少std作为关联命名空间执行 ADL)。这在N3257中进行了讨论,这导致了 range-for 的语义变化。当前的 range-for 首先查找成员函数beginand end,因此不会考虑std::beginand ,无论 ADL-barriers 和继承自.std::endstd::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;
}

现场示例

于 2015-11-06T21:36:30.277 回答
7

他们通过放入命名空间来boost/range/end.hpp显式阻止 ADL ,然后将其带入命名空间。endrange_adl_barrierusing namespace range_adl_barrier;boost

由于end实际上不是来自::boost,而是来自::boost::range_adl_barrier,因此 ADL 找不到它。

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

// 使用 ADL 命名空间屏障来避免与其他不合格的
// 调用产生歧义。这对于 C++0x 鼓励
// 不合格的开始/结束调用尤为重要。

没有给出这会导致问题的例子,所以我只能推测他们在说什么。

这是我发明的一个例子,说明 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{} );
}

活生生的例子。两者foo::begin和都是在该上下文中bar::begin调用的同样有效的函数。begin( bar::bar_type{} )

这可能就是他们正在谈论的内容。它们的boost::beginstd::begin可能在您拥有using std::begin来自 的类型的上下文中同样有效boost。通过将它放在 , 的子命名空间中booststd::begin被调用(并且自然地在范围上工作)。

如果begin命名空间boost中的 没有那么通用,那将是首选,但这不是他们编写它的方式。

于 2015-11-03T16:23:45.010 回答
6

那是因为boost::endADL 屏障内,然后在文件末尾拉入boost

但是,从ADL 上的 cppreference 页面(对不起,我手边没有 C++ 草稿):

1) 关联命名空间中的 using-directives 被忽略

这可以防止它被包含在 ADL 中。

于 2015-11-03T16:22:40.123 回答