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() << '\n';
    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.

Answer 2

This is argument dependent lookup. According to Stroustroup's The C++ Programming Language: 4th Edition, there are two rules that apply here:

1) If an argument is a member of a namespace, the associated namespaces are the enclosing namespaces.

2) If an argument is a built-in type, there are no associated namespaces.

In your first and second cases, begin() and end() return iterators. However, the C++ standard defines an iterator as any variable of any type, upon which an iteration operation can be performed. (In other words, an iterator is a design concept that is enforced via a template.)

According to the other answer, the iterators in the first case are variables of a data type that belongs to the same namespace as sort(). However, the iterators in the second case have a primitive data type. Per Rule #2, these iterators have no associated namespace.