Unqualified sort() -- why does it compile when used on std::vector and not on std::array, and which compiler is correct?

Question

When calling std::sort() on a std::array:

#include <vector>
#include <array>
#include <algorithm>

int main() {
    std::vector<int> foo{4, 1, 2, 3};
    sort(begin(foo), end(foo));

    std::array<int, 4> foo2{4, 1, 2, 3};
    sort(begin(foo2), end(foo2));
}

Both gcc and clang return an error on the sort on the std::array -- clang says

error: use of undeclared identifier 'sort'; did you mean 'std::sort'?

Changing to std::sort(begin(foo2), end(foo2)) fixes the problem.

MSVC compiles the code above as written.

Why the difference in treatment between std::vector and std::array; and which compiler is correct?

`sort(...` --> `std::sort(...`. I *guess* that ADL (argument dependant lookup) is what's tripping you up. That, or deduction guides. In any case; *always* qualify the functions you call. — Jesper Juhl, Jan 03 '20 at 18:10
Could be that the MSVC library have some specialization of `std::sort` that leads to [argument-dependent lookup](https://en.cppreference.com/w/cpp/language/adl) (like you already have for `std::begin` and `std::end`)? — Some programmer dude, Jan 03 '20 at 18:11
@Someprogrammerdude It's simply that all of the containers in VC++'s stdlib use class type iterators defined in `namespace std` even where a simple pointer type would have worked. I believe this is to insert debug-build checks to detect overruns and other common errors. — François Andrieux, Jan 03 '20 at 18:21

NathanOliver · Accepted Answer · 2020-01-03T18:40:12.010

16

This is comes down to the type that begin and end result to and how that works with Argument Dependent Lookup.

In

sort(begin(foo), end(foo));

you get

sort(std::vector<int>::iterator, std::vector<int>::iterator)

and since std::vector<int>::iterator is a member of std ADL finds sort in std and the call succeeds.

With

sort(begin(foo2), end(foo2));

You get

sort(int*, int*)

and because int* is not a member of std, ADL will not look into std and you can't find std::sort.

This works in MSVC because

sort(begin(foo2), end(foo2));

becomes

sort(std::_Array_iterator, std::_Array_iterator)

and since std::_Array_iterator is part of std ADL finds sort.

Both compilers are correct with this behavior. std::vector and std::array don't have any requirement on what type is used for the iterator except that it satisfies the LegacyRandomAccessIterator requirement and in C++ 17 for std::array that the type also be a LiteralType and in C++20 that it be a ConstexprIterator

edited Jan 03 '20 at 18:40

answered Jan 03 '20 at 18:15

NathanOliver

171,901
28
288
402

1

I guess the question is whether MSVC's behavior is conforming, i.e. does the `std::array` iterator *have* to be `int*` or can it be a class type? Similarly for `std::vector` it would be relevant to the question whether the iterator *has to be* a class type on which ADL will work, or whether it can be `int*` as well. – walnut Jan 03 '20 at 18:17
@walnut It can be whatever the implementation wants it to be. It could be a `std::iterator`, something else, or just a pointer. – NathanOliver Jan 03 '20 at 18:18
1

I also wonder why in this library implementation they chose to use `int*` for `std::array` but not for `std::vector`. – François Andrieux Jan 03 '20 at 18:19
1

The iterator types for both `std::array` and `std::vector` are unspecified, meaning the implementation is allowed to define them as raw pointers (code won't compile) or class-type wrappers (code will compile only if the class type has `std` as an ADL associated namespace). – aschepler Jan 03 '20 at 18:25
@FrançoisAndrieux No idea. Personally I like that `std::vector` use a "real" iterator and `std::array` use a pointer but that's just my preference. As long as it supports the random access requirements it doesn't really matter what it is. – NathanOliver Jan 03 '20 at 18:29
`std::vector::iterator` isn't necessarily a member of `std`. [Last I checked](https://stackoverflow.com/questions/41491995/using-stdsort-without-prefix-std-and-also-without-using-namespace-std-c), it was a member of `__gnu_cxx` on the GCC setup I tried it on, and the ADL looked in `std` for other reasons. – user2357112 Jan 04 '20 at 02:49
@user2357112supportsMonica `iteratror` is a member of `vector` and `vector` is a member of `std` so `std::vector::iterator` is a member of `std`. – NathanOliver Jan 04 '20 at 02:54
@NathanOliver: That only applies if `std::vector::iterator` is actually a nested class, rather than an alias for a class not actually nested in `std::vector`. – user2357112 Jan 04 '20 at 03:06
1

[Here's a demo](https://ideone.com/Qx9lyd) where the ADL fails with an alias, and [here's a demo](https://ideone.com/U5SIkr) where the ADL succeeds with a nested class. Both here and in my earlier tests, `std::vector::iterator` is an alias. – user2357112 Jan 04 '20 at 03:12

Unqualified sort() -- why does it compile when used on std::vector and not on std::array, and which compiler is correct?

1 Answers1