Historical background
The underlying reason is discussed in this 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::".
Extended code example illustrating the dangers of ADL
The danger of ADL from unqualified calls to begin and end is two-fold:
- the set of associated namespaces can be much larger than one expects. E.g. in
begin(x), if x has (possibly defaulted!) template parameters, or hidden base classes in its implementation, the associated namespaces of the template parameters and of its base classes are also considered by ADL. Each of those associated namespace can lead to many overloads of begin and end being pulled in during argument dependent lookup.
- unconstrained templates cannot be distinguished during overload resolution. E.g. in
namespace std, the begin and end function templates are not separately overloaded for each container, or otherwise constrained on the signature of the container being supplied. When another namespace (such as boost) also supplies similarly unconstrained function templates, overload resolution will consider both an equal match, and an error occurs.
The following code samples illustrate the above points.
A small container library
The first ingredient is to have a container class template, nicely wrapped in its own namespace, with an iterator that derives from std::iterator, and with generic and unconstrained function templates begin and 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
A small range library
The second ingredient is to have a range library, also wrapped in its own namespace, with another set of unconstrained function templates begin and 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
Overload resolution ambiguity through ADL
Trouble begins when one tries to make an iterator range into a container, while iterating with unqualified begin and 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
Argument-dependent name lookup on rng will find 3 overloads for both begin and end: from namespace R (because rng lives there), from namespace C (because the rng template parameter Container<int, 4>::Iterator lives there), and from namespace std (because the iterator is derived from std::iterator). Overload resolution will then consider all 3 overloads an equal match and this results in a hard error.
Boost solves this by putting boost::begin and boost::end in an inner namespace and pulling them into the enclosing boost namespace by using directives. An alternative, and IMO more direct way, would be to ADL-protect the types (not the functions), so in this case, the Container and IteratorRange class templates.
Live Example With ADL barriers
Protecting your own code may not be enough
Funny enough, ADL-protecting Container and IteratorRange would -in this particular case- be enough to let the above code run without error because std::begin and std::end would be called because std::iterator is not ADL-protected. This is very surprising and fragile. E.g. if the implementation of C::Container::Iterator no longer derives from std::iterator, the code would stop compiling. It is therefore preferable to use qualified calls R::begin and R::end on any range from namespace R in order to be protected from such underhanded name-hijacking.
Note also that the range-for used to have the above semantics (doing ADL with at least std as an associated namespace). This was discussed in N3257 which led to semantic changes in range-for. The current range-for first looks for member functions begin and end, so that std::begin and std::end will not be considered, regardless of ADL-barriers and inheritance from 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
find(range, 4)andfind(begin(v), end(v), 4)respectively. This is not recommended though, unless you intend to have a customizedfindalgorithm depending on the type passed to it. – Johannajohannahany_of_equalisany_ofwith predicate testing for equality to the value) – Johannajohannahmax(2, n/2), the proper bound for the division loop isfloor(sqrt(n)) + 1. (the bug is thatany_ofon an empty range returnstrue) Also:!any_of == none_of: see this example – Johannajohannahany_of, not primality testing :) Thanks for the thoughtful fixed version though! – Warthog