Can't write range based for with non-member begin and end functions
Question
I'm writing a code that uses bitboards. since iterating on all bits of a bitboard is pretty common action, I decided to write some iterator class, and to use c++0x's range based loops.
However, g++ (version 4.6.3) tell me that there is not matching function for begin
or end
.
My code:
#include <iostream>
#include <cinttypes>
class bitscan {
uint64_t mask;
public:
bitscan(uint64_t m) : mask(m) {}
bool operator!=(bitscan it) const {return mask!=it.mask;}
bitscan &operator++() {mask&=(mask-1);return *this;}
int operator*() {return __builtin_ctzl(mask);}
};
bitscan begin(uint64_t m) {return m;}
bitscan end(uint64_t m) {return 0;}
int main() {
uint64_t num=49;
for (int i : num) std::cout<<i<<std::endl;
}
The error:
err.cpp: In function ‘int main()’:
err.cpp:18:15: error: no matching function for call to ‘begin(long unsigned int&)’
err.cpp:18:15: note: candidates are:
/usr/include/c++/4.6/initializer_list:86:5: note: template<class _Tp> constexpr const _Tp* std::begin(std::initializer_list<_Tp>)
/usr/include/c++/4.6/bits/range_access.h:87:5: note: template<class _Tp, long unsigned int _Nm> _Tp* std::begin(_Tp (&)[_Nm])
/usr/include/c++/4.6/bits/range_access.h:58:5: note: template<class _Container> decltype (__cont.begin()) std::begin(const _Container&)
/usr/include/c++/4.6/bits/range_access.h:48:5: note: template<class _Container> decltype (__cont.begin()) std::begin(_Container&)
err.cpp:18:15: error: no matching function for call to ‘end(long unsigned int&)’
err.cpp:18:15: note: candidates are:
/usr/include/c++/4.6/initializer_list:96:5: note: template<class _Tp> constexpr const _Tp* std::end(std::initializer_list<_Tp>)
/usr/include/c++/4.6/bits/range_access.h:97:5: note: template<class _Tp, long unsigned int _Nm> _Tp* std::end(_Tp (&)[_Nm])
/usr/include/c++/4.6/bits/range_access.h:78:5: note: template<class _Container> decltype (__cont.end()) std::end(const _Container&)
/usr/include/c++/4.6/bits/range_access.h:68:5: note: template<class _Container> decltype (__cont.end()) std::end(_Container&)
If I replace the loop by the line: for (auto it=begin(num);it!=end(num);++it) std::cout<<*it<<std::endl;
It works fine.
What is my mistake?
Solution
In the range-based for statement, the begin
and end
nonmember functions are only looked up via argument-dependent lookup(*) (C++11 §6.5.4/1). This means that they will only be found in a namespace associated with the argument type (C++11 §3.4.2/2).
A fundamental type, like uint64_t
, has no associated namespaces, so no begin
or end
will ever be found for it. You'll need to create a class type to wrap the uint64_t
so that nonmember begin
and end
functions may be found via argument-dependent lookup.
(*) Note: There are actually three ways that begin
and end
may be found, but this is the only way that applies to your scenario. There are also special cases for arrays and for classes with member functions named begin
and end
.