341. Vector reallocation and swap

Section: 23.3.11.3 [vector.capacity] Status: CD1 Submitter: Anthony Williams Opened: 2001-09-27 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 CD1 status.

Discussion:

It is a common idiom to reduce the capacity of a vector by swapping it with an empty one:

  std::vector<SomeType> vec;
  // fill vec with data
  std::vector<SomeType>().swap(vec);
  // vec is now empty, with minimal capacity

However, the wording of 23.3.11.3 [vector.capacity]paragraph 5 prevents the capacity of a vector being reduced, following a call to reserve(). This invalidates the idiom, as swap() is thus prevented from reducing the capacity. The proposed wording for issue 329 does not affect this. Consequently, the example above requires the temporary to be expanded to cater for the contents of vec, and the contents be copied across. This is a linear-time operation.

However, the container requirements state that swap must have constant complexity (23.2 [container.requirements] note to table 65).

This is an important issue, as reallocation affects the validity of references and iterators.

If the wording of 23.2.4.2p5 is taken to be the desired intent, then references and iterators remain valid after a call to swap, if they refer to an element before the new end() of the vector into which they originally pointed, in which case they refer to the element at the same index position. Iterators and references that referred to an element whose index position was beyond the new end of the vector are invalidated.

If the note to table 65 is taken as the desired intent, then there are two possibilities with regard to iterators and references:

1. All Iterators and references into both vectors are invalidated.
2. Iterators and references into either vector remain valid, and remain pointing to the same element. Consequently iterators and references that referred to one vector now refer to the other, and vice-versa.

Proposed resolution:

Add a new paragraph after 23.3.11.3 [vector.capacity] paragraph 5:

  void swap(vector<T,Allocator>& x);

Effects: Exchanges the contents and capacity() of *this with that of x.

Complexity: Constant time.

[This solves the problem reported for this issue. We may also have a problem with a circular definition of swap() for other containers.]

Rationale:

swap should be constant time. The clear intent is that it should just do pointer twiddling, and that it should exchange all properties of the two vectors, including their reallocation guarantees.