This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of C++17 status.

### 2266. `vector` and `deque` have incorrect `insert` requirements

Section: 22.2.3 [sequence.reqmts] Status: C++17 Submitter: Ahmed Charles Opened: 2013-05-17 Last modified: 2017-07-30

Priority: 2

View other active issues in [sequence.reqmts].

View all other issues in [sequence.reqmts].

View all issues with C++17 status.

Discussion:

According to Table 100 in n3485 22.2.3 [sequence.reqmts]/4 the notes for the expression `a.insert(p,i,j)` say:

> Requires: `T` shall be `EmplaceConstructible` into `X` from `*i`. For `vector`, if the iterator does not meet the forward iterator requirements (24.2.5), `T` shall also be `MoveInsertable` into `X` and `MoveAssignable`.

> Each iterator in the range `[i,j)` shall be dereferenced exactly once.

> pre: `i` and `j` are not iterators into `a`.

> Inserts copies of elements in `[i, j)` before `p`

There are two problems with that wording: First, the special constraints for `vector`, that are expressed to be valid for forward iterators only, are necessary for all iterator categories. Second, the same special constraints are needed for `deque`, too.

[2013-10-05, Stephan T. Lavavej comments and provides alternative wording]

In Chicago, we determined that the original proposed resolution was correct, except that it needed additional requirements. When `vector` `insert(p, i, j)` is called with input-only iterators, it can't know how many elements will be inserted, which is obviously problematic for insertion anywhere other than at the end. Therefore, implementations typically append elements (geometrically reallocating), followed by `rotate()`. Given forward+ iterators, some implementations append and `rotate()` when they determine that there is sufficient capacity. Additionally, `deque` `insert(p, i, j)` is typically implemented with prepending/appending, with a possible call to `reverse()`, followed by a call to `rotate()`. Note that `rotate()`'s requirements are strictly stronger than `reverse()`'s.

Therefore, when patching Table 100, we need to add `rotate()`'s requirements. Note that this does not physically affect code (implementations were already calling `rotate()` here), and even in Standardese terms it is barely noticeable — if an element is `MoveInsertable` and `MoveAssignable` then it is almost certainly `MoveConstructible` and swappable. However, this patch is necessary to be strictly correct.

Previous resolution from Ahmed Charles:

> 1. Change Table 100 as indicated:

>    > Table 100 — Sequence container requirements (in addition to container) (continued)
>    > Expression | Return type | Assertion/note pre-/post-condition
>    > --- | --- | ---
>    > `…`
>    > `a.insert(p,i,j)` | `iterator` | Requires: `T` shall be `EmplaceConstructible` into `X` from `*i`. For `vector` and `deque`, if the iterator does not meet the forward iterator requirements (24.2.5), `T` shall also be `MoveInsertable` into `X` and `MoveAssignable`. Each iterator in the range `[i,j)` shall be dereferenced exactly once. pre: `i` and `j` are not iterators into `a`. Inserts copies of elements in `[i, j)` before `p`
>    > `…`

[2014-02-15 post-Issaquah session : move to Tentatively Ready]

Pablo: We might have gone too far with the fine-grained requirements. Typically these things come in groups.

Alisdair: I think the concepts folks assumed we would take their guidance.

Move to Tentatively Ready.

Proposed resolution:

1. Change Table 100 as indicated:

   > Table 100 — Sequence container requirements (in addition to container) (continued)
   > Expression | Return type | Assertion/note pre-/post-condition
   > --- | --- | ---
   > `…`
   > `a.insert(p,i,j)` | `iterator` | Requires: `T` shall be `EmplaceConstructible` into `X` from `*i`. For `vector` and `deque`, if the iterator does not meet the forward iterator requirements (24.2.5), `T` shall also be `MoveInsertable` into `X`, `MoveConstructible`, and `MoveAssignable`, and swappable (16.4.4.3 [swappable.requirements]). Each iterator in the range `[i,j)` shall be dereferenced exactly once. pre: `i` and `j` are not iterators into `a`. Inserts copies of elements in `[i, j)` before `p`
   > `…`