Why is this function call didn't reject the unsuitable overload?

Question

Consider the following code:

#include<vector>
#include<ranges>
#include<algorithm>
//using namespace std;
using namespace std::ranges;
int main()
{
    std::vector<int> a = {};
    sort(a);
    return 0;
}

It's running properly.

Obviously, it called this overload function(functor, strictly speaking):

template<random_access_range _Range,
     typename _Comp = ranges::less, typename _Proj = identity>
  requires sortable<iterator_t<_Range>, _Comp, _Proj>
  constexpr borrowed_iterator_t<_Range>
  operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
  {
return (*this)(ranges::begin(__r), ranges::end(__r),
           std::move(__comp), std::move(__proj));
  }

But after we introducing the namespace std, the function call became ambiguous(got compilation errors):

#include<vector>
#include<ranges>
#include<algorithm>
using namespace std;
using namespace std::ranges;
int main()
{
    std::vector<int> a = {};
    sort(a);
    return 0;
}

In addition to the previous reloads

 2045 |   inline constexpr __sort_fn sort{};

, there are many other overload functions found in namespace std like:

template<class _ExecutionPolicy, class _RandomAccessIterator> __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void> std::sort(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator)

and

template<class _RAIter, class _Compare> constexpr void std::sort(_RAIter, _RAIter, _Compare)

So my questions are:

The call of sort functor in std::ranges is the best match function, isn't it? Why do these functions later found in std cause ambiguity, rather than being abandoned due to the SFINAE principle?
If the functions in std are visible for sort(a) after we introduced the namespace std, shouldn't it be equally visible in the first code according to the ADL of a?

ADL only takes place if the initial unqualified lookup doesn't find anything. — Nathan Pierson, Jun 18 '22 at 18:36
SFINAE is a name of a specific design pattern. It has to be explicitly applied in code. `std::sort` uses it to disambiguate `ExecutionPolicy` overloads for example, but nothing else. This being said, I don't know why it's ambiguous, looks like an issue of having an object and function with the same name in the same namespace: https://godbolt.org/z/G1cMe1Yaz — Yksisarvinen, Jun 18 '22 at 18:42

score 5 · Answer 1 · answered Jun 18 '22 at 19:02

The problem is that std::ranges::sort is not actually a function template. It is some callable entity with special name lookup properties, sometimes called a niebloid. As a consequence it doesn't behave like a function (template) in name lookup.

You imported both std::ranges::sort and std::sort to be found by usual unqualified name lookup. std::sort is a function (template), but std::ranges::sort isn't.

If unqualified name lookup finds multiple entities and not all of them are functions or function templates, then the name lookup is ambiguous and the program usually ill-formed.

That is what is happening here.

score 3 · Accepted Answer · answered Jun 18 '22 at 19:05

The problem is that std::ranges::sort is implemented as function object and not a function. From name lookup rules:

For function and function template names, name lookup can associate multiple declarations with the same name, and may obtain additional declarations from argument-dependent lookup. [...]

For all other names (variables, namespaces, classes, etc), name lookup must produce a single declaration in order for the program to compile.

std::ranges::sort is a variable, and thus name lookup fails (because there is more than one declaration matching name sort). And std::ranges algorithms are explicitly allowed to be implemented as function objects (quote from std::ranges::sort cppreference):

The function-like entities described on this page are niebloids, that is: [...]

In practice, they may be implemented as function objects, or with special compiler extensions.

So, as long as standard library implements std::ranges::sort as function object (and both libstdc++ and libc++ seem to do that), there is no way to make sort name lookup work if you introduce both std::ranges and std in global namespace.

Why is this function call didn't reject the unsuitable overload?

2 Answers2