C++ Logo


Advanced search

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

From: Andrey Semashev <andrey.semashev_at_[hidden]>
Date: Tue, 27 Jul 2021 23:42:51 +0300
On 7/27/21 10:48 PM, Giuseppe D'Angelo via Std-Discussion wrote:
> Hello,
> On 27/07/2021 21:09, Andrey Semashev via Std-Discussion wrote:
>> On 7/27/21 6:29 PM, Jason McKesson via Std-Discussion wrote:
>>> On Sun, Jul 25, 2021 at 3:21 PM Andrey Semashev via Std-Discussion
>>> <std-discussion_at_[hidden]> wrote:
>>>> 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.
>> Exactly. The important part is "unless reallocation occurs".
>>> And reallocation is only *permitted* to occur if
>>> the number of new elements inserted exceeds the available capacity -
>>> size.
>> Is it? I don't see where the spec has such restriction for insert. There
>> is one for e.g. reserve, but not for insert.
> Are you saying that insert() may reallocate even if you have extra
> capacity?

I'm saying that I don't see the standard prohibiting this.

> That would be quite an extraordinary behaviour, completely
> user-unfriendly...

Well, that's a matter of perspective. Yes, reallocation may look
surprising. But so is undefined state of the vector if the insert fails
without a reallocation.

>>> 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.
>> The standard doesn't specify the exact algorithm of insertion. So the
>> implementation is permitted e.g. to push_back the new element and then
>> move it to its desired position via swaps, if that implementation has
>> benefits. This implementation would satisfy the complexity requirements.
>> Though, as I said, such case is unusual, so it is unlikely any real
>> implementation would bother doing this.
> If you have a type that is throwing copyable and movable, I think it's a
> safe bet to assume it's also throwing swappable. Such "append at end and
> swap into position" algorithm would therefore fail to work -- what if an
> exception is thrown while you're swapping?

You don't have to assume anything - there are traits to discover whether
swap is able to throw. If it does, then the whole push_back+swap
algorithm makes no sense and the implementation would use a different
implementation, like with full reallocation.

Received on 2021-07-27 15:42:56