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

Question

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

Принимая во внимание:

#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

это дает:

main.cpp: 8: 37: ошибка: использование необъявленного идентификатора "конец"

Учитывая, что если вы напишите using boost::end; это работает просто отлично, что подразумевает, что boost::end виден:

Почему ADL не работает и не находит boost::end в выражении end(range)? И если это сделано намеренно, в чем причина этого?

Чтобы было ясно, ожидаемый результат будет аналогичен тому, что происходит в этом примере, используя std::find_if и неквалифицированный end(vec),

15

c++ boost namespaces argument-dependent-lookup boost-range

Источник

user493122 03 ноя '15 в 16:08

3 ответа

Решение

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

Основная причина обсуждается в этом закрытом билете 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 является двойным:

набор связанных пространств имен может быть намного больше, чем можно ожидать. Например в 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;
}

Живой пример

Поиск имени в зависимости от аргумента rng найдет 3 перегрузки для обоих begin а также 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 шаблоны классов.

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

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

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

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

Живой пример

15

Источник

user819272 06 ноя '15 в 21:36

Это потому что boost::end находится внутри барьера ADL, который затем втягивается boost в конце файла.

Однако со страницы cppreference на ADL (извините, у меня нет под рукой черновика C++):

1) директивы using в связанных пространствах имен игнорируются

Это предотвращает его включение в ADL.

6

Источник

user1737909 03 ноя '15 в 16:22

Другие вопросы по тегам c++ boost namespaces argument-dependent-lookup boost-range

user1774667 03 ноя '15 в 16:23 2015-11-03 16:23 · Accepted Answer · 2015-11-03 16:23

В 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 было бы менее общим, было бы предпочтительнее, но они не так написали.