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.

> 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.