On Sun, Jul 25, 2021 at 3:21 PM Andrey Semashev via Std-Discussion
<std-discussion_at_[hidden]> wrote:
>
> On 7/25/21 9:45 PM, Jason McKesson via Std-Discussion wrote:
> > When inserting a `T` into the middle of a `vector<T>`, the `vector`
> > must slide all of the elements over to make room for the new `T`. The
> > standard makes it clear that if `T` is not CopyInsertable, and `T`'s
> > move constructor throws, then the state of the `vector` is
> > unspecified. But otherwise, the `vector<T>`'s state in the event of an
> > exception is unchanged.
> >
> > So there are 3 possibilities:
> >
> > 1. `T` is no-throw moveable.
> > 2. `T` is copyable, but has a throwing move.
> > 3. `T` is not copyable and has a throwing move.
> >
> > Case 3 is pretty easy to implement: if an exception happens, you just
> > let it bubble up. Case 1 is easy to implement: don't do copying. Case
> > 2 is the tricky one, and at present, I'm not sure how to go about
> > implementing it.
> >
> > If the `vector` needs to reallocate to insert the elements, then
> > things are easy. You allocate the new buffer; copy the elements before
> > the insertion point, insert the new elements, and copy those after the
> > insertion point. If an exception happens at any point, you destroy all
> > of the copies and deallocate the buffer before allowing the exception
> > to proceed.
> >
> > The problem is if `vector` *doesn't* need to reallocate. To handle
> > this, you need to slide some elements over to make room.
> >
> > Let's say you have the following vector's contents. The letters
> > represent valid elements, and the `*` are extra storage.
> >
> > | A | B | C | D | E | F | * | * | * |
> >
> > So you want to insert one element after C. So, step one is to
> > copy-insert elements to the unused space:
> >
> > | A | B | C | D | E | F | F | * | * |
> >
> > Next, you copy-assign elements over existing ones:
> >
> > | A | B | C | D | D | E | F | * | * |
> >
> > Now, we copy-assign the new element `N` over the first `D`:
> >
> > | A | B | C | N | D | E | F | * | * |
> >
> > However, let's say that this throws an exception. So our list looks like:
> >
> > | A | B | C | ? | D | E | F | * | * |
> >
> > Where `?` means a damaged instance of the object. Its value is unknown.
> >
> > So, to recover, we should destroy the `?` element, then copy all of
> > the elements back to where they started.
> >
> > But... what happens if copying `F` (or any of these elements) *itself* throws?
> >
> > | A | B | C | D | E | ? | F | * | * |
> >
> > How do you fix that? The standard requires that we are somehow able to
> > fix this, but I don't know how. We could try to copy it again, but who
> > is to say that it won't throw again?
>
> There is always the solution to always reallocate the storage and do the
> full copy with the inserted element.

That isn't allowed. `insert` is required to maintain the validity of
pointers/references to elements before the insertion point *unless*
reallocation occurs. And reallocation is only *permitted* to occur if
the number of new elements inserted exceeds the available capacity -
size.

So you can't implement it that way.

> Also, there is a possibility of a non-throwing swap, although if move is
> throwing then swap will likely be throwing as well.

I don't see anything in the standard requiring such a thing or
permitting a `vector` implementation to use it. So `vector` still has
to provide this behavior for types with throwing copies that don't
have non-throwing swaps.