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.

> 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