Why can I pass iterators of two different containers into sort?

user_14339850 0
Viewed 217

I was taking part in an online programming contest earlier today. There was a problem where I had to deal with three input vectors and one of them required sorting. My code, in a simple example, looked as follows:

vector <int> a;
vector <int> b;
.
.
.
sort(begin(a), end(b));

Notice how I mistakenly(/stupidly) made a typo sort(begin(a), end(b). It took me quite a while to figure this error out because the runtime error message doesn't say anything about it.

c:\programming\mingw\mingw 9.2.0\include\c++\9.2.0\bits\stl_algo.h:4825:
In function:
    void std::sort(_RAIter, _RAIter) [with _RAIter =
    __gnu_debug::_Safe_iterator<__gnu_cxx::__normal_iterator<int*,
    std::__cxx1998::vector<int, std::allocator<int> > >,
    std::__debug::vector<int>, std::random_access_iterator_tag>]

Error: function requires a valid iterator range [__first, __last).

Objects involved in the operation:
    iterator "__first" @ 0x000000000023FDB0 {
      type = __gnu_cxx::__normal_iterator<int*, std::__cxx1998::vector<int, std::allocator<int> > >
(mutable iterator);
      state = dereferenceable (start-of-sequence);
      references sequence with type 'std::__debug::vector<int, std::allocator<int> >' @ 0x0000000000
23FD10
    }
    iterator "__last" @ 0x000000000023FD80 {
      type = __gnu_cxx::__normal_iterator<int*, std::__cxx1998::vector<int, std::allocator<int> > >
(mutable iterator);
      state = past-the-end;
      references sequence with type 'std::__debug::vector<int, std::allocator<int> >' @ 0x0000000000
23FCD0
    }

This application has requested the Runtime to terminate it in an unusual way.
Please contact the application's support team for more information.

The only part I cared to look at was Error: function requires a valid iterator range [__first, __last). . I spent about 10 mins aimlessly thinking about what I'm doing wrong and though I glanced at the sort part a few times I failed to notice my stupid mistake. I didn't know that this was even possible (even though I've looked at the function definitions many times)!

So, my question: Why do C++ algorithms allow this and why hasn't the C++ committee done something about it? Why doesn't the compiler shout? Is it deliberately implemented this way to punish people making silly mistakes using C++ like all other things in C++?

c++
2 Answers

Why do C++ algorithms allow this and why hasn't the C++ committee done something about it?

Because it's not something that can be fixed. Lets say you have an array like int arr[500]; and you wan to sort it. You would pass arr and arr + 500 as the arguments to sort but those are just int*'s. They hold no other information then the address they point to. There is no way sort can check if those two pointers point to the same block of memory.

This is the same for iterators to standard containers. iterators don't provide a way to access the container they come from, so sort can't check if the iterators point to the same object or not.

user_43424980

Why? Because otherwise you'd pay a runtime cost of checking what should be checked at compile time: the iterators would need to be annotated with the container they came from, and sort would need to check that.

In other words: Your valid complaint should be targeted not towards the C++ library, but towards the compiler that doesn't include a static check for this. A static code analyzer such as PVS-Studio would typically catch this. A static code analyzer will catch many more rookie mistakes that can cause lots of wasted time, so I'd suggest you equip yourself with one. Since I'm most familiar with PVS-Studio, I can tell you right away that it's free for student use.

user_13296520
Related