c++ - Using std::sort() without prefix "std" and also without "using namespace std;" compiles successfully

Question

As sort() is defined in namespace std it must always be used as std::sort.But the following code compiles correctly even without std.

#include <vector>
#include <algorithm>

int main()
{
    std::vector<int> nums = {4,3,1,7,2,0};
    sort(nums.begin(),nums.end());
}

ideone.com

But this code doesn't.

#include <array>
#include <algorithm>

int main()
{

    std::array<int,5> nums = {4,1,8,9,6};
    sort(nums.begin(),nums.end());
}

Using gcc 4.8.4 with -std=c++11 flag enabled.

From both these code snippets it is clear that std::vector has something to do with this.But I can't figure it out.

Answer 1

This is argument-dependent lookup. If you use typeid to examine the types of the iterators involved:

#include <iostream>
#include <typeinfo>
#include <vector>
#include <array>

int main() {
    std::cout << typeid(std::vector<int>::iterator).name() << '
';
    std::cout << typeid(std::array<int, 5>::iterator).name() << std::endl;
    return 0;
}

at least on Ideone, you get the following output:

N9__gnu_cxx17__normal_iteratorIPiSt6vectorIiSaIiEEEE
Pi

With Revolver_Ocelot's help in the comments, we see that these types are __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > > and int*.

For the vector, after the usual name lookup fails, the compiler searches the __gnu_cxx and std namespaces for a sort function, __gnu_cxx because it's the namespace of __gnu_cxx::normal_iterator and std because it's the namespace of one of the template arguments, std::vector<int, std::allocator<int> >. It finds std::sort.

For the std::array, the iterators are just int*s, so argument-dependent lookup searches no additional namespaces and finds no sort function.