Why does a global merge() function conflict with std::merge()?

Question

Consider the following code:

#include <vector>
#include <algorithm>

template <typename Input1, typename Input2, typename Output>
void merge(Input1 begin1, Input1 end1, Input2 begin2, Input2 end2, Output out)
{
}

int main()
{
    std::vector<int> a = {1, 2};
    int b[] = {3, 4};
    int c[4];

    merge(a.begin(), a.end(), b, b + 2, c);
}

Compiling yields:

$ clang++ -std=c++11 -stdlib=libc++ merge.cpp 
merge.cpp:15:5: error: call to 'merge' is ambiguous
    merge(a.begin(), a.end(), b, b + 2, c);
    ^~~~~
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../lib/c++/v1/algorithm:4056:1: note: 
      candidate function [with _InputIterator1 = std::__1::__wrap_iter<int *>,
      _InputIterator2 = int *, _OutputIterator = int *]
merge(_InputIterator1 __first1, _InputIterator1 __last1,
^
merge.cpp:5:6: note: candidate function [with Input1 = std::__1::__wrap_iter<int
      *>, Input2 = int *, Output = int *]
void merge(Input1 begin1, Input1 end1, Input2 begin2, Input2 end2, Output out)
     ^
1 error generated.

Compiler version:

$ clang++ --version
Apple LLVM version 5.0 (clang-500.2.78) (based on LLVM 3.3svn)
Target: x86_64-apple-darwin13.0.0
Thread model: posix

Why is the call to merge ambiguous? It's not sure if I meant ::merge() or std::merge(), though clearly(?) it should be ::merge() since I'm not specifying any using directives. My merge function is in the global namespace, which I thought wouldn't conflict with anything in the std namespace (since that's the main point of namespaces, right?). If I change a to be an int array like the others, it compiles without any ambiguity. Also, adding the colons and calling ::merge() works fine.

So my question is this: Is this a bug in Clang, or do I have a misunderstanding of namespaces? Why does my call to merge() result in ambiguity when the two functions aren't in the same namespace and I haven't made std::merge() visible with any using directives?

Answer 1

The problem is that std::vector<T>::iterator may be a class type (in your case, it is a class type): during overload resolution the compiler finds all visible declarations of a function. To this end, it goes looking in namespaces possibly associated with its arguments (this is called argument dependent look-up). The type std::vector<T>::iterator is defined in namespace std (or a namespace nested within) and, thus, function from namespace std are considered for overload resolutions. Since std::merge() and your merge() both match equally well, there is an ambiguity.

The easiest way to avoid the problem is to use a different name for the function template. Hiding the associated namespace is possible but not easy: associated namespaces are taken from the location where a class or a class template is defined as well as from its base classes and template arguments. Thus, creating a wrapper template for any iterator type wouldn't be sufficient as it still associates the original namespace with the types. You may try to make your function template a better match but given that it is meant to be as generic as the standard algorithm, this isn't quite viable, either.

Answer 2

It's due to argument dependent look-up (http://en.cppreference.com/w/cpp/language/adl) of an iterator from the std namespace.

you could write ::merge to get your function only, but I'd rather just use a different name.