Talk:cpp/container/vector/insert

The iterator invalidation section is incorrect for std::vector:

Causes reallocation if the new size() is greater than the old capacity(). If the new size() is greater than capacity(), all iterators and references are invalidated. Otherwise, only the iterators and references after the added element are invalidated. The past-the-end iterator is also invalidated.

The standard states that the iterator passed to the insert function is also invalidated. In particular:

Otherwise, only the iterators and references after the added element are invalidated. The past-the-end iterator is also invalidated.

should be changed to:

Otherwise, only the iterators and references *before* the insertion point remain valid.

The corner case is:

v.insert(it,value); // at this point 'it' is invalid

This is important in the sense that an iterator to the point where the new element was inserted, but obtained *before* the insertion is considered by some to refer to the 'added element', in which case the wording in the page claims that it would not be invalidated.

There is a related defect report: http://cplusplus.github.io/LWG/lwg-active.html#2256. While the DR refers to 'erase' and not insert the core issue is the same. According to the standard, the iterator is invalidated on insert/erase even if it *must* refer to a valid object.

Invalidation note updated, thank you for bringing attention to it. --Cubbi 09:21, 25 July 2013 (PDT)

first, last parameters description for insert function incorrectly excludes iterators for self

In the description of the parameters first, last, in the insert function, we can read:

the range of elements to insert, can't be iterators into the container for which insert is called

This is not the correct requirement for the insert operation on a vector.

The origin of this requirement probably comes from here: https://eel.is/c++draft/sequence.reqmts#37.sentence-3 but this is a requirement for sequence containers in general. They are overridden by descriptions of specific containers.

note: The general requirement for sequence containers most probably comes from the deque container, where insertion may invalidate both iterators and references: https://eel.is/c++draft/deque#modifiers-1

In the case of a specific container (vector here), we can read https://eel.is/c++draft/vector#modifiers-2 which is already reflected in the sentences just above the description of the parameters.

note: also sanitizers do not complain about the correct usage of iterators to self.

note: in short, the description makes the following code:

   int main(){
       std::vector<int> integers {1,2,3,4,5};
       integers.reserve(integers.size()+5);
       integers.insert(integers.end(), integers.begin() , integers.begin()+2);
       for(auto element : integers){
           std::cout << element << std::endl;
       }
   }

invalid, while it is valid.--DaPi (talk) 08:28, 24 January 2023 (PST)

What makes you think that sequence container requirements don't apply here? That vector::insert has a remark? --Ybab321 (talk) 13:10, 24 January 2023 (PST)

First of all, a sequence container is an interface description, for which the vector meets requirements https://eel.is/c++draft/sequences.general#1. As such interface can say, that something is disallowed like the first, last params being iterators to self (if you operate on the interface you cannot do that, because behavior depends on the specific implementation.), but it doesn't say if that is UB and what happens if anything - it cannot as it depends on the specific implementation of the interface and each implementation has specific notes on insert operations. Also, meeting the requirement of sequence container doesn't mean the vector cannot extend it with supporting first, last iterators to self (which it does in practice, regardless of what is written in the standard). Secondly, in https://eel.is/c++draft/vector#overview-2.sentence-3 we read, that descriptions for vector operations are provided when they are either missing from sequence container or when additional semantics apply. And that additional semantics (https://eel.is/c++draft/vector#modifiers-2 ) describes what exactly happens when we perform insertion from self to self.--DaPi (talk) 00:47, 25 January 2023 (PST)

A few points:

1) They are overridden by descriptions of specific containers.

Wrong. [vector.modifiers] p2 is a remark, as Ybab321 says. It specifies additional semantics on top of the requirements and effects stated in [vector.modifiers] p36-39, instead of overriding them.

2) but it doesn't say if that is UB and what happens if anything

Wrong. [structure.specifications] p3.3 clearly states that 'violation of any preconditions results in undefined behavior'.

3) Also, meeting the requirement of sequence container doesn't mean the vector cannot extend it with supporting first, last iterators to self (which it does in practice, regardless of what is written in the standard).

Yes, in practice no compiler is 100% following the standard. Therefore there is a 'Notes' section to talk about compiler conformance (such as #warning). Nevertheless, extension is extension, the description should clearly reflect what the standard says. 'Reference' and 'regardless' are naturally contradictory. --Xmcgcg

Thank you for discussion and clarification! Specifically, I missed the https://eel.is/c++draft/structure.specifications#3.3. In this case, I think it makes sense to discuss it further the reflectors if we want to keep that behavior. I think the discussion is closed then DaPi (talk) 02:21, 30 January 2023 (PST)