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@lists.isocpp.org> 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? That would be quite an extraordinary behaviour, completely
user-unfriendly...
>
>> 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?
Copy and move constructors always create new objects, whereas the swap function doesn't. This allows swap to be noexcept in more cases. An example is libstdc++'s std::deque implementation (assuming standard allocator).
Anyway, I don't think that swapping is actually a valid implementation strategy. What if swap(T&, T&) has observable effects besides swapping the two objects? Is std::vector<T>::insert allowed to produce those effects?
My 2 c,
--
Giuseppe D'Angelo | giuseppe.dangelo@kdab.com | Senior Software Engineer
KDAB (France) S.A.S., a KDAB Group company
Tel. France +33 (0)4 90 84 08 53, http://www.kdab.com
KDAB - The Qt, C++ and OpenGL Experts
--
Std-Discussion mailing list
Std-Discussion@lists.isocpp.org
https://lists.isocpp.org/mailman/listinfo.cgi/std-discussion