2266. vector and deque have incorrect insert requirements

Section: 23.2.4 [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 23.2.4 [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
    …