Title
Strong guarantee on vector::push_back() still broken with C++11?
Status
c++14
Section
[vector.modifiers]
Submitter
Nicolai Josuttis

Created on 2013-04-21.00:00:00 last changed 123 months ago

Messages

Date: 2013-09-26.20:20:45

Proposed resolution:

This wording is relative to N3691.

  1. Edit [container.requirements.general] p10 b2 as indicated:

    • if an exception is thrown by an insert() or emplace() function while inserting a single element, that function has no effects.

    • if an exception is thrown by a push_back() or, push_front(), emplace_back(), or emplace_front() function, that function has no effects.

  2. Edit [deque.modifiers] as indicated:

    iterator insert(const_iterator position, const T& x);
    iterator insert(const_iterator position, T&& x);
    iterator insert(const_iterator position, size_type n, const T& x);
    template <class InputIterator>
      iterator insert(const_iterator position,
                      InputIterator first, InputIterator last);
    iterator insert(const_iterator position, initializer_list<T>);
    template <class... Args> void emplace_front(Args&&... args);
    template <class... Args> void emplace_back(Args&&... args);
    template <class... Args> iterator emplace(const_iterator position, Args&&... args);
    void push_front(const T& x);
    void push_front(T&& x);
    void push_back(const T& x);
    void push_back(T&& x);
    

    -1- Effects: An insertion in the middle of the deque invalidates all the iterators and references to elements of the deque. An insertion at either end of the deque invalidates all the iterators to the deque, but has no effect on the validity of references to elements of the deque.

    -2- Remarks: If an exception is thrown other than by the copy constructor, move constructor, assignment operator, or move assignment operator of T there are no effects. If an exception is thrown while inserting a single element at either end, there are no effects. IfOtherwise, if an exception is thrown by the move constructor of a non-CopyInsertable T, the effects are unspecified.

    -3- Complexity: The complexity is linear in the number of elements inserted plus the lesser of the distances to the beginning and end of the deque. Inserting a single element either at the beginning or end of a deque always takes constant time and causes a single call to a constructor of T.

  3. Edit [vector.modifiers] as indicated:

    iterator insert(const_iterator position, const T& x);
    iterator insert(const_iterator position, T&& x);
    iterator insert(const_iterator position, size_type n, const T& x);
    template <class InputIterator>
      iterator insert(const_iterator position, InputIterator first, InputIterator last);
    iterator insert(const_iterator position, initializer_list<T>);
    template <class... Args> void emplace_back(Args&&... args);
    template <class... Args> iterator emplace(const_iterator position, Args&&... args);
    void push_back(const T& x);
    void push_back(T&& x);
    

    -1- Remarks: Causes reallocation if the new size is greater than the old capacity. If no reallocation happens, all the iterators and references before the insertion point remain valid. If an exception is thrown other than by the copy constructor, move constructor, assignment operator, or move assignment operator of T or by any InputIterator operation there are no effects. If an exception is thrown while inserting a single element at the end and T is CopyInsertable or is_nothrow_move_constructible<T>::value is true, there are no effects. IfOtherwise, if an exception is thrown by the move constructor of a non-CopyInsertable T, the effects are unspecified.

    -2- Complexity: The complexity is linear in the number of elements inserted plus the distance to the end of the vector.

Date: 2013-09-15.00:00:00

[ 2013-09-26, Nico improves wording ]

The new proposed resolution is driven as follows:

  • In the container requirements section, there shall be general statements that single element insertions and push_back(), pop_back, emplace_front(), and emplace_back() have no effect on any exception.

    That is: we extend the first two statements by adding emplace_front() and emplace_back(), which are missing.

  • Formulate only the exceptions from that (or where other general statements might lead to the impression, that the blanket statement no longer applies):

    • remove the statement in list::push_back() saying again that exceptions have to effect.

    • Clarify that all single-element insertions at either end of a deque have the strong guarantee.

    • Clarify that all single-element insertions at the end of a vector have the strong guarantee.

Date: 2013-09-15.00:00:00

[ 2013-09-16, Nico provides concrete wording ]

Date: 2013-04-21.00:00:00

According to my understanding, the strong guarantee of push_back() led to the introduction of noexcept and to the typical implementation that vectors usually copy their elements on reallocation unless the move operations of their element type guarantees not to throw.

However, if I read the standard correctly, we still don't give the strong guarantee any more: Yes, [container.requirements.general]/10 specifies:

Unless otherwise specified (see 23.2.4.1, 23.2.5.1, 23.3.3.4, and 23.3.6.5) all container types defined in this Clause meet the following additional requirements:

  • […]
  • if an exception is thrown by a push_back() or push_front() function, that function has no effects.

However, [vector.modifiers] specifies for vector modifiers, including push_back():

If an exception is thrown other than by the copy constructor, move constructor, assignment operator, or move assignment operator of T or by any InputIterator operation there are no effects. If an exception is thrown by the move constructor of a non-CopyInsertable T, the effects are unspecified.

I would interpret this as an "otherwise specified" behavior for push_back(), saying that the strong guarantee is only given if constructors and assignments do not throw.

That means, the strong guarantee of C++03 is broken with C++11.

In addition to all that [container.requirements.general] p10 b2 doesn't mention the corresponding functions emplace_back() and emplace_front(). These are similar single-element additions and should provide the same strong guarantee.

Daniel adds:

It seems the error came in when N2350 and N2345 became accepted and where integrated into the working draft N2369. The merge resulted in a form that changed the previous meaning and as far as I understand it, this effect was not intended.

History
Date User Action Args
2014-02-27 17:03:20adminsetstatus: wp -> c++14
2014-02-20 13:52:38adminsetstatus: voting -> wp
2014-02-12 14:19:44adminsetstatus: ready -> voting
2013-09-26 20:20:45adminsetstatus: new -> ready
2013-09-26 17:36:37adminsetmessages: + msg6634
2013-09-18 12:48:59adminsetmessages: + msg6587
2013-09-18 12:48:59adminsetmessages: + msg6586
2013-04-21 00:00:00admincreate