Guarantees of reordering of a vector

Question

Say I have this code:

#include <iostream>
#include <vector>

int main() 
{
    std::vector<int> vec {10, 15, 20};
    auto itr = vec.begin();
    vec.erase(itr);
    for(const auto& element : vec)
    {
        std::cout << element << " ";
    }
    return 0;
}

This gives me 15 20 as expected. Now, cppreference says this about erase():

Invalidates iterators and references at or after the point of the erase, including the end() iterator

Fair enough, but is that the only guarantee the standard gives about vector::erase()?

Is a vector allowed to reorder it's element after the erased iterator?

For example, are these conditions guaranteed to hold after the erase which would mean all elements after the erase() iterator shifted 1 to the left:

vec[0] == 15
vec[1] == 20

Or are implementations allowed to move values around as they see fit, and thus, create scenarios where vec[0] == 20 etc?

I would like a quote of the relevant part of the standard.

Answer 1

Let's start at the beginning:

23.2.3 Sequence containers

A sequence container organizes a finite set of objects, all of the same type, into a strictly linear arrangement. The library provides four basic kinds of sequence containers: vector, forward_list, list, and deque.

Emphasis on "a strictly linear arrangement". This is unambiguous.

This definition is followed by a table called "sequence container requirements", which describes erase() thusly:

a.erase(q) [ ... ]
Effects:  Erases the element pointed to by q

Combined, this leaves no wiggle room for interpretation. The elements in a vector are always in "a strict linear arrangement", so when one of them is erase()d, there's only one possible outcome.

Answer 2

Technically, no, the standard doesn't write out a promise that it won't re-order elements when you least expect.

Practically, obviously it's not going to do that. That would be ridiculous.

Legally, you can probably take the "Effects" clause:

Erases the element pointed to by q

as having no other effects unless stated elsewhere (e.g. iterator invalidation, which follows from the erasure effect).

Answer 3

The two statements I found that I think guarantee it would be:

C++11 Standard

23.2.1 11 Unless otherwise specified (either explicitly or by defining a function in terms of other functions), invoking a container member function or passing a container as an argument to a library function shall not invalidate iterators to, or change the values of, objects within that container.

If you can't "change the values of" then you can't arbitrarily re-order elements (like swapping the end value with the erased one).

23.2.3 12 The iterator returned from a.erase(q) points to the element immediately following q prior to the element being erased. If no such element exists, a.end() is returned.

This implies that the conceptual erasure of an element is implemented by closing the physical gap from the right. Given the previous rule, conceptually closing the gap, can not be seen as conceptually changing their values. This means the only implementation would be to shift the values in order.

By means of explanation.

The Standard is dealing with the abstract concept not the actual implementation, although its statements do impact the implementation.

Conceptually erasing an element simply removes it and nothing more. So given the sequence:

3  5  7  4  2  9 (6 values)

If we erase the 3rd element what does that conceptually give us?

3  5  4  2  9 (5 values)

This must be true because of the first statement above:

23.2.1 11 Unless otherwise specified (either explicitly or by defining a function in terms of other functions), invoking a container member function or passing a container as an argument to a library function shall not invalidate iterators to, or change the values of, objects within that container.

If the implementation reordered the elements, say by swapping the erased element with the end element that rule would be broken because we would end up with this:

3  5  9  4  2  

Conceptually the resulting value to the right of the erased element has changed from a 4 to a 9, thus breaking the rule.