Strange overloading rules in C++

Question

I'm trying to compile this code with GCC 4.5.0:

#include <algorithm>
#include <vector>

template <typename T> void sort(T, T) {}

int main()
{
    std::vector<int> v;
    sort(v.begin(), v.end());
}

But it doesn't seem to work:

$ g++ -c nm.cpp
nm.cpp: In function ‘int main()’:
nm.cpp:9:28: error: call of overloaded ‘sort(std::vector<int>::iterator, std::vector<int>::iterator)’ is ambiguous
nm.cpp:4:28: note: candidates are: void sort(T, T) [with T = __gnu_cxx::__normal_iterator<int*, std::vector<int> >]
/usr/lib/gcc/i686-pc-linux-gnu/4.5.0/../../../../include/c++/4.5.0/bits/stl_algo.h:5199:69: note:                 void std::sort(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<int*, std::vector<int> >]

Comeau compiles this code without errors. (4.3.10.1 Beta2, strict C++03, no C++0x)

Is this valid C++?

Why is GCC even considering std::sort as a valid overload?

---

I did some experiments, and I think I know why Comeau might compile this (but I don't know this for a fact):

namespace foo {
typedef int* iterator_a;
class        iterator_b {};
template <typename T> void bar(T) {}
}

template <typename T> void bar(T) {}

int main()
{
    bar(foo::iterator_a()); // this compiles
    bar(foo::iterator_b()); // this doesn't
}

My guess is that the first call resolves to bar(int*) so there's no ADL and no ambiguity, while the second call resolves to bar(foo::iterator_b) and pulls in foo::bar (but I'm not really sure).

So GCC probably uses something like iterator_b while Comeau uses iterator_a.

Answer 1

You can explicitly specify your sort function by fully qualifying the name as ::sort.

The ambiguous overload is due to argument dependent lookup. The C++ standard doesn't specify how std::vector<*>::iterator should be implemented. The gcc library writers have chosen to use a template (__gnu_cxx::__normal_iterator) with a template type argument of std::vector, which brings namespace std into the list of associated namespaces.

---

Is this valid C++?

Yes, but the behaviour of both compilers is also compliant with the C++ standard. ADL presents a huge headache from this perspective and the full consequences weren't understood until after standardization.