I read that std::sort only accepts random access iterators. So, I expected to find code in the sort function that ensures only random access iterators are accepted, but I couldn't find any.

Why is it that std::sort can only take random access iterators? Did I miss something?

I'm using MSVC STL with C++17.

I read that std::sort only accepts random access iterators. So, I expected to find code in the sort function that ensures only random access iterators are accepted, but I couldn't find any.

Why is it that std::sort can only take random access iterators? Did I miss something?

I'm using MSVC STL with C++17.

• c++
• sorting
• iterator
• std

• I assume that it will simply use the operations (like adding a number to the iterator) that only a random access iterator has, and therefore has no explicit check. – gerum Commented Feb 17 at 7:10
• If you really want to know you can always look into the (microsoft) STL source code, the header files are available. The only thing I see is _Adl_verify_range, so I assume the rest is just "checked" when your code is compiled and results in a compilation error or not. (There isn't a C++20 requires clause or something) – Pepijn Kramer Commented Feb 17 at 7:18
• If std::sort() uses operations that are known to only be valid for a random access iterator, one of more of those operations will produce a diagnosable error if another (not random access iterator) is passed. The diagnostics might not be particularly clear, but that's all the standard requires. An implementation of std::sort() is permitted but not required (although that may change in more modern standards) to have code that does compile-time checks (e.g. via traits) of iterator properties (e.g. if that produces a less cryptic diagnostic). – Peter Commented Feb 17 at 7:19
• std::ranges::sort uses concept to check its parameters. std::sort existed before concept (even if SFINAE might be possible at that time). – Jarod42 Commented Feb 17 at 8:56
• C++ does not include training wheels. If the requirement is a random access iterator, then the implementation is allowed to assume that that is what you provide. If you fail to meet the contract, the implementation is allowed to fail to uphold it's end of the bargain and fail in arbitrary ways (including seeming to work) and doesn't have to tell you. It's on you to ensure you provide what is required. – Jesper Juhl Commented Feb 17 at 13:56

1 Answer 1

That the iterator is a random access iterator is a requirement of std::sort. If the iterator passed to std::sort does not meet the requirements of the named requirement LegacyRandomAccessIterator then std::sort might work correctly or not. In any case the program is ill-formed. std::sort assumes that the iterator is a random access iterator, it does not have to explicitly check that it is one. std::sort uses operations that a RandomAccessIterator supports. If the iterator is not a RandomAccessIterator those operations might fail.

std::sort can check the requirements listed, but it does not have to. It's up to you to make sure the iterator meets them.

It's like you apply for a job where they require you to be able to jump 15m high. In the interview they will do the usual chat, but they will not check that you can jump that high. They assume you can, because they clearly stated it as requirement for the job. On day one you have to jump and you fail. End of story ;).