Is there any way of implementing the insert method for a standards-compliant vector?

Question

Firstly, assume A is a type with:

• A potentially throwing copy constructor/assignment operator.
• No move constructor/assignment.

This is a common example of a C++03 RAII type. Now let me cite the C++14 standard (snipped irrelevant parts):

§23.2.1 General container requirements

¹¹ Unless otherwise specified (see ... and 23.3.6.5) all container types defined in this Clause meet the following additional requirements:

• if an exception is thrown by an insert() or emplace() function while inserting a single element, that function has no effects.

§23.3.6.5 vector modifiers

iterator insert(const_iterator position, const T& x);
...

¹Remarks: Causes reallocation if the new size is greater than the old capacity. If no reallocation happens, all the iterators and references before the insertion point remain valid. If an exception is thrown other than by the copy constructor, move constructor, assignment operator, or move assignment operator of T or by any InputIterator operation there are no effects. If an exception is thrown while inserting a single element at the end and T is CopyInsertable or is_nothrow_move_constructible<T>::value is true, there are no effects. Otherwise, if an exception is thrown by the move constructor of a non-CopyInsertable T, the effects are unspecified.

²Complexity: The complexity is linear in the number of elements inserted plus the distance to the end of the vector.

Now consider this:

std::vector<A> v(5);
v.reserve(10);
v.insert(begin() + 2, A());

Clearly we're inserting a single element, so §23.2.1 - 11 applies and either the operation succeeds or v is unchanged. §23.3.6.5 doesn't change anything about this. The exception is thrown by the copy constructor. We are not inserting at the end. The move constructor is not used.

But now consider this possible scenario during the implementation of insert assuming no reallocation happens:

01234_____ initial state
0123_4____ making space by copying
012_34____ continued
012?34____ continued, but copy operation threw

At this point all future copy operations could throw, making it impossible to restore the state as required. Oops.

I can't see any implementation without reallocation that enables strong exception safety. This means that any implementation must always reallocate when inserting a type without a move constructor and a throwing copy constructor in the middle. However:

1. insert(pos, value) becomes unbearably slow due to constant reallocations.
2. The complexity requirement isn't met (reallocation always requires n operations).

3. It could be argued that "Causes reallocation if the new size is greater than the old capacity." implies that no reallocation is allowed if the new size is not greater than the old capacity.

   To support this, consider that if an implementation may reallocate anytime, the user has no way of knowing. This makes the guarantee about preserving iterators ("If no reallocation happens, all the iterators and references before the insertion point remain valid.") useless information, and makes you wonder why both sentences were inserted into the standard in the first place.

1 & 2 are pretty damning observations, but if 3 is true then it's (as far as I can see) plain impossible to be compliant with the standard.

So, is there any way of implementing the insert method for a standards-compliant vector? Or is this a standard defect?

---

A demonstration of this issue can be seen here: http://coliru.stacked-crooked.com/a/afd2e838c34c8fcc

Answer 1

As far as my interpretation of the standard goes, here "Unless otherwise specified" means that once anything regarding exceptions is specified for insert in a corresponding clause for a particular container, the bullet point of the list in §23.2.1 is not applying anymore.

If an exception is thrown other than by the copy constructor [..] of T [..] there are no effects.

The opposite is indicated: When an exception is thrown by the copy constructor of T there is no guarantee that the call won't have any effects. The requirement that

if an exception is thrown by an insert() or emplace() function while inserting a single element, that function has no effects

is not applicable: §23.3.6.5 specifies "otherwise".