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.