C++ Logo

std-discussion

Advanced search

Re: Vector implementation of behavior when inserting objects whose copy constructor can throw

From: Andrey Semashev <andrey.semashev_at_[hidden]>
Date: Sun, 25 Jul 2021 22:21:41 +0300
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.

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

Received on 2021-07-25 14:21:46