C++ Logo


Advanced search

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

From: Jason McKesson <jmckesson_at_[hidden]>
Date: Sun, 25 Jul 2021 14:45:39 -0400
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?

Received on 2021-07-25 13:45:54