Почему ADL не работает с Boost.Range?

В boost/range/end.hpp они явно блокируют ADL, помещая end в range_adl_barrier, затем using 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::begin и std::begin могут быть одинаково действительными в контексте, где у вас есть using std::begin для типа из boost. Если поместить его в подпространство имен boost, будет вызвано std::begin (и, естественно, работает с диапазонами).

Если бы begin в пространстве имен boost было менее общим, оно было бы предпочтительнее, но они написали его иначе.

Историческое прошлое

Основная причина обсуждается в этом закрытом тикете 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_1 — boost::iterator_range<std::vector<int>::iterator>. Аргумент шаблона находится в namespace std (в большинстве реализаций), поэтому ADL находит std::begin() и std::end() (которые, в отличие от boost::begin() и boost::end(), не используют барьер ADL для предотвращения их обнаружения ADL).

Чтобы ваш код скомпилировался, просто добавьте "using boost::begin;" и "using boost::end;" или явным образом уточните вызовы begin()/end() с помощью "boost::".

Расширенный пример кода, иллюстрирующий опасности ADL

Опасность ADL от неквалифицированных вызовов begin и end двояка:

1. набор связанных пространств имен может быть намного больше, чем можно ожидать. Например. в begin(x), если x имеет (возможно, по умолчанию!) параметры шаблона или скрытые базовые классы в своей реализации, связанные пространства имен параметров шаблона и его базовых классов также рассматриваются ADL. Каждое из этих связанных пространств имен может привести ко многим перегрузкам begin и end во время поиска, зависящего от аргумента.
2. неограниченные шаблоны нельзя различить при разрешении перегрузки. Например. в 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;
}

Живой пример

Поиск имени в зависимости от аргумента для rng найдет 3 перегрузки для begin и end: from namespace R (потому что rng живет там), from namespace C (потому что там живет параметр шаблона rng Container<int, 4>::Iterator) и from namespace std ( потому что итератор получен из std::iterator). При разрешении перегрузки все 3 перегрузки будут считаться равными, что приведет к серьезной ошибке.

Boost решает эту проблему, помещая boost::begin и boost::end во внутреннее пространство имен и перетаскивая их во внешнее пространство имен boost с помощью директив. Альтернативой и, по-моему, более прямым способом будет защита ADL типов (а не функций), поэтому в данном случае шаблоны классов Container и IteratorRange.

Живой пример с барьерами ADL

Защиты собственного кода может быть недостаточно

Забавно, но защиты Container и IteratorRange с помощью ADL в данном конкретном случае будет достаточно, чтобы приведенный выше код выполнялся без ошибок, потому что std::begin и std::end будут вызываться, потому что std::iterator не защищен с помощью ADL. Это очень удивительно и хрупко. Например. если реализация C::Container::Iterator больше не является производной от std::iterator, код перестанет компилироваться. Поэтому предпочтительнее использовать квалифицированные вызовы R::begin и R::end в любом диапазоне от namespace R, чтобы защититься от такого закулисного перехвата имен.

Также обратите внимание, что range-for раньше имел вышеуказанную семантику (выполнение ADL по крайней мере с std в качестве связанного пространства имен). Это обсуждалось в N3257, что привело к семантическим изменениям в range-for. Текущий диапазон 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;
}