C++: Using fully qualified name with sort function - inconsistent behaviour

Question

I have the following C++ code that computes the median of a container taken from Accelerated C++ by Koenig.

median.h

#ifndef GUARD_median_h
#define GUARD_median_h

#include <stdexcept>
#include <algorithm>
#include <cstddef>

template<class T, class Iterator>
T median (Iterator begin, Iterator end)
{
    size_t size = end - begin;
    if (size == 0)
        throw std::domain_error("median of an empty vector");

    sort(begin, end);

    size_t mid = size/2;

    return size%2 == 0 ? (begin[mid] + begin[mid-1])/2 : begin[mid];
}
#endif

median_test.cpp

#include <vector>
#include <iostream>
#include "median.h"

using std::vector;  using std::cin;
using std::cout;    using std::endl;

int main()
{
    vector<double> myVec;

    cout << "Please enter integers: ";

    double val;
    while (cin >> val) {
        myVec.push_back(val);
    }

    cout << "The median is: " << median<double>(myVec.begin(), myVec.end()) << endl;

    return 0;
}

This code compiles and runs just fine. But if I make a slight modification to test the median function with an array rather than a vector like so...

median_test_array.cpp

#include <iostream>
#include "median.h"

using std::cin;
using std::cout;    using std::endl;

int main()
{
    double myVec[1000];

    cout << "Please enter integers: ";

    double val;
    size_t i = 0;
    while (cin >> val) {
        myVec[i++] = val;
    }

    cout << "The median is: " << median<double>(myVec, myVec+i) << endl;

    return 0;
}

I get the following compile error:

| => g++-6 -I. median_test_array.cpp
In file included from median_test_array.cpp:2:0:
median.h: In instantiation of 'T median(Iterator, Iterator) [with T = double; Iterator = double*]':
median_test_array.cpp:19:60:   required from here
median.h:15:9: error: 'sort' was not declared in this scope
     sort(begin, end);
     ~~~~^~~~~~~~~~~~
median.h:15:9: note: suggested alternative:
In file included from /usr/local/Cellar/gcc/6.2.0/include/c++/6.2.0/algorithm:62:0,
                 from median.h:5,
                 from median_test_array.cpp:2:
/usr/local/Cellar/gcc/6.2.0/include/c++/6.2.0/bits/stl_algo.h:4727:5: note:   'std::sort'
     sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
     ^~~~

This error goes away if I give the fully qualified name for sort (std::sort), but what I would like to know is why I need a fully qualified name in this instance, but not in the vector example.

http://stackoverflow.com/questions/8111677/what-is-argument-dependent-lookup-aka-adl-or-koenig-lookup — Brian Bi, Dec 03 '16 at 01:35

score 2 · Answer 1 · answered Dec 03 '16 at 01:37

The first code was compiled due to the so-called Argument Dependent Lookup. As the std::vector<double>::iterator belongs to the namespace std then the function sort was also looked up in this namespace.

When you use pointers then there is no ADL. Thus the compiler can not find the declaration of the name sort.

Use the qualified name std::sort.

songyuanyao · Accepted Answer · 2016-12-03T02:47:35.047

It's an ADL issue.

For your 1st code sample, it seems that the implementation declare std::vector::iterator as class inside the namespace std, then ADL takes effect, std::sort is found for the calling with arguments of type std::vector::iterator.

For your 2nd code sample, the argument passed to sort is just double*, ADL doesn't take effect anymore, then the name sort can't be found.

Note that such behavior is not guaranteed; the standard doesn't specify where std::vector::iterator should be implemented, it even doesn't have to be a class, so you'd better to specify qualifier std::, or use it with using std::sort;.

C++: Using fully qualified name with sort function - inconsistent behaviour

2 Answers2