2033. Preconditions of reserve, shrink_to_fit, and resize functions

Section: 23.3.11.3 [vector.capacity], 23.3.5.3 [deque.capacity] Status: C++14 Submitter: Nikolay Ivchenkov Opened: 2011-02-20 Last modified: 2016-01-28

Priority: Not Prioritized

View other active issues in [vector.capacity].

View all other issues in [vector.capacity].

View all issues with C++14 status.

Discussion:

I have several questions with regard to the working paper N3225 (C++0x working draft):

  1. Where the working draft specifies preconditions for shrink_to_fit member function of std::vector and std::deque?

  2. Where the working draft specifies preconditions for 'void reserve(size_type n)' member function of std::vector?

  3. Does a call to 'void resize(size_type sz)' of std::vector require the element type to be DefaultConstructible? If yes, why such requirement is not listed in the Requires paragraph?

  4. Does a call to 'void resize(size_type sz)' of std::vector require the element type to be MoveAssignable because the call erase(begin() + sz, end()) mentioned in the Effects paragraph would require the element type to be MoveAssignable?

  5. Why CopyInsertable requirement is used for 'void resize(size_type sz)' of std::vector instead of MoveInsertable requirement?

[2011-06-12: Daniel comments and provides wording]

According to my understanding of the mental model of vector (and to some parts for deque) the some requirements are missing in the standard as response to above questions:

  1. The preconditions of shrink_to_fit for both std::vector and std::deque should impose the MoveInsertable requirements. The reason for this is, that these containers can host move-only types. For a container type X the C++03 idiom X(*this).swap(*this) imposes the CopyInsertable requirements which would make the function call ill-formed, which looks like an unacceptable restriction to me. Assuming the committee decides to support the move-only case, further wording has to be added for the situation where such a move-only type could throw an exception, because this can leave the object in an unspecified state. This seems consistent with the requirements of reserve, which seems like a very similar function to me (for vector). And this brings us smoothly to the following bullet:

  2. I agree that we are currently missing to specify the preconditions of the reserve function. My interpretation of the mental model of this function is that it should work for move-only types, which seems to be supported by the wording used in 23.3.11.3 [vector.capacity] p2:

    […] If an exception is thrown other than by the move constructor of a non-CopyInsertable type, there are no effects.

    Given this statement, the appropriate requirement is MoveInsertable into the vector.

  3. I agree that vector::resize(size_type) misses to list the DefaultConstructible requirements.
  4. Unfortunately the current specification in terms of erase implies the MoveAssignable requirements. I don't think that this implication is intended. This function requires "append" and "pop-back" effects, respectively, where the former can be realized in terms of MoveInsertable requirements. The same fix in regard to using pop_back instead of erase is necessary for the two argument overload of resize as well (no MoveAssignable is required).
  5. The CopyInsertable requirement is incorrect and should be MoveInsertable instead.

In addition to above mentioned items, the proposed resolution adds a linear complexity bound for shrink_to_fit and attempts to resolve the related issue 2066.

[ 2011 Bloomington ]

Move to Ready.

Note for editor: we do not normally refer to 'linear time' for complexity requirements, but there is agreement that any clean-up of such wording is editorial.

Proposed resolution:

This wording is relative to the FDIS.

  1. Edit 23.3.5.3 [deque.capacity] as indicated [Remark: The suggested change of p4 is not redundant, because CopyInsertable is not necessarily a refinement of MoveInsertable in contrast to the fact that CopyConstructible is a refinement of MoveConstructible]:

    void resize(size_type sz);

    -1- Effects: If sz <= size(), equivalent to erase(begin() + sz, end());calling pop_back() size() - sz times. If size() < sz, appends sz - size() value-initialized elements to the sequence.

    -2- Requires: T shall be MoveInsertable into *this and DefaultConstructible. 

    void resize(size_type sz, const T& c);

    -3- Effects: If sz <= size(), equivalent to calling pop_back() size() - sz times. If size() < sz, appends sz - size() copies of c to the sequence. 

    if (sz > size())
  insert(end(), sz-size(), c);
else if (sz < size())
  erase(begin()+sz, end());
else
  ; // do nothing

    -4- Requires: T shall be MoveInsertable into *this and CopyInsertable into *this. 

    void shrink_to_fit();

    -?- Requires: T shall be MoveInsertable into *this.

    -?- Complexity: Takes at most linear time in the size of the sequence.

    -5- Remarks: shrink_to_fit is a non-binding request to reduce memory use but does not change the size of the sequence. [ Note: The request is non-binding to allow latitude for implementation-specific optimizations. — end note ]

  2. Edit 23.3.11.3 [vector.capacity] as indicated including edits that also resolve 2066 [Remark: The combined listing of MoveInsertable and CopyInsertable before p12 is not redundant, because CopyInsertable is not necessarily a refinement of MoveInsertable in contrast to the fact that CopyConstructible is a refinement of MoveConstructible]:

    […]

    void reserve(size_type n);

    -?- Requires: T shall be MoveInsertable into *this.

    -2- Effects: A directive that informs a vector of a planned change in size, so that it can manage the storage allocation accordingly. After reserve(), capacity() is greater or equal to the argument of reserve if reallocation happens; and equal to the previous value of capacity() otherwise. Reallocation happens at this point if and only if the current capacity is less than the argument of reserve(). If an exception is thrown other than by the move constructor of a non-CopyInsertable type, there are no effects.

    -3- Complexity: It does not change the size of the sequence and takes at most linear time in the size of the sequence.

    -4- Throws: length_error if n > max_size().[footnote 266]

    -5- Remarks: Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence. It is guaranteed that no reallocation takes place during insertions that happen after a call to reserve() until the time when an insertion would make the size of the vector greater than the value of capacity(). 

    void shrink_to_fit();

    -?- Requires: T shall be MoveInsertable into *this.

    -?- Complexity: Takes at most linear time in the size of the sequence.

    -6- Remarks: shrink_to_fit is a non-binding request to reduce capacity() to size(). [ Note: The request is non-binding to allow latitude for implementation-specific optimizations. — end note ] If an exception is thrown other than by the move constructor of a non-CopyInsertable T there are no effects.

    […]

    void resize(size_type sz);

    -9- Effects: If sz <= size(), equivalent to erase(begin() + sz, end());calling pop_back() size() - sz times. If size() < sz, appends sz - size() value-initialized elements to the sequence.

    -10- Requires: T shall be CopyMoveInsertable into *this and DefaultConstructible.

    -??- Remarks: If an exception is thrown other than by the move constructor of a non-CopyInsertable T there are no effects. 

    void resize(size_type sz, const T& c);

    -11- Effects: If sz <= size(), equivalent to calling pop_back() size() - sz times. If size() < sz, appends sz - size() copies of c to the sequence. 

    if (sz > size())
  insert(end(), sz-size(), c);
else if (sz < size())
  erase(begin()+sz, end());
else
  ; // do nothing

    -??- Requires: T shall be MoveInsertable into *this and CopyInsertable into *this.

    -12- RequiresRemarks: If an exception is thrown other than by the move constructor of a non-CopyInsertable T there are no effects.