std::vector erasing with first iterator after last

Question

What will happen when erasing a range whose first iterator is after the last iterator?

std::vector<int> v{1,2}; v.erase( v.begin() + 1, v.begin() );

What about other containers?

That overload requires a valid range. begin() + 1, begin() is not a valid range, so you may not call that overload with those iterators. — François Andrieux
– François Andrieux, Commented Aug 19, 2020 at 19:29
The great thing about undefined behavior is that ANYTHING might happen. Could crash. Could appear to work. Might even give the expected results. Might destroy the Earth. (If the Earth is destroyed, please file a bug report with the compiler vendor. That sort of thing can result in bad reviews.) — Eljay
– Eljay, Commented Aug 19, 2020 at 19:42

Bitwize · Accepted Answer · 2020-08-19 19:42:47Z

It's undefined behavior to call erase with an invalid range on any container. In practice, it will generally crash the program if you are lucky, or smash adjacent memory if you're unlucky.

This should be true for just about any API that accepts an iterator range. If a range is invalid, there is no way for the underlying code/algorithm to be aware of what the stopping condition actually is.

Iterator ranges delimit the start and end of a range for any input or algorithm. The end iterator is always used to indicate the completion of that range, and must always be reachable by repeatedly incrementing the first iterator (e.g. by calling operator++).

Most algorithms make use of operator!= to detect the completion of the range, from the LegacyInputIterator requirement. Some ranges may optionally make use of the distance between iterators if that that range is a LegacyRandomAccessIterator.

In either case, this detection requires that the first iterator be before the last, otherwise code like:

for (auto it = first; first != last; ++first) { ... }

will never reach the end of the range, and similarly:

auto distance = last - first;

will return an incorrect value for the distance between iterators.

Most iterative algorithms will compare iterators using operator!=, such algorithms will not be able to detect the case where the 1st iterator is after the 2nd iterator. It is expected that the 1st iterator will eventually compare equal to the 2nd iterator when the iteration is finished.
It is possible to detect out of order iterators, but only if they fulfill the random access requirements because those support operator< which determines order. So in practice this can be done in algorithm that require random access iterators. In the case of std::vector::erase which only ever uses random access iterators, the inversion could be detected, but I don't think any implementation does. Since the situation is UB anyway, an implementation could decide to swap the iterators for you and erase correctly. It would be a bad idea though, as it would hide simple mistakes.

Collectives™ on Stack Overflow

std::vector erasing with first iterator after last

1 Answer 1

2 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Related