Title
vector and deque have incorrect insert requirements
Status
c++17
Section
[sequence.reqmts]
Submitter
Ahmed Charles

Created on 2013-05-17.00:00:00 last changed 81 months ago

Messages

Date: 2014-03-03.13:52:20

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 ([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
Date: 2014-02-15.00:00:00

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

Date: 2013-10-15.00:00:00

[ 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
Date: 2013-05-17.00:00:00

According to Table 100 in n3485 [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.

History
Date User Action Args
2017-07-30 20:15:43adminsetstatus: wp -> c++17
2014-11-08 19:44:42adminsetstatus: voting -> wp
2014-11-04 10:26:50adminsetstatus: ready -> voting
2014-03-03 13:52:20adminsetmessages: + msg6895
2014-03-03 13:52:20adminsetstatus: new -> ready
2013-10-13 16:01:32adminsetmessages: + msg6741
2013-06-30 18:51:00adminsetmessages: + msg6541
2013-05-17 00:00:00admincreate