Issue 675: Move assignment of containers

675. Move assignment of containers

Section: 23.2 [container.requirements] Status: CD1 Submitter: Howard Hinnant Opened: 2007-05-05 Last modified: 2016-01-28

Priority: Not Prioritized

View all other issues in [container.requirements].

View all issues with CD1 status.

Discussion:

James Hopkin pointed out to me that if vector<T> move assignment is O(1) (just a swap) then containers such as vector<shared_ptr<ostream>> might have the wrong semantics under move assignment when the source is not truly an rvalue, but a moved-from lvalue (destructors could run late).

vector<shared_ptr<ostream>> v1;
vector<shared_ptr<ostream>> v2;
...
v1 = v2;               // #1
v1 = std::move(v2);    // #2

Move semantics means not caring what happens to the source (v2 in this example). It doesn't mean not caring what happens to the target (v1). In the above example both assignments should have the same effect on v1. Any non-shared ostream's v1 owns before the assignment should be closed, whether v1 is undergoing copy assignment or move assignment.

This implies that the semantics of move assignment of a generic container should be clear, swap instead of just swap. An alternative which could achieve the same effect would be to move assign each element. In either case, the complexity of move assignment needs to be relaxed to O(v1.size()).

The performance hit of this change is not nearly as drastic as it sounds. In practice, the target of a move assignment has always just been move constructed or move assigned from. Therefore under clear, swap semantics (in this common use case) we are still achieving O(1) complexity.

Proposed resolution:

Change 23.2 [container.requirements]:

Table 89: Container requirements
expression return type operational semantics assertion/note pre/post-condition complexity

a = rv; X& All existing elements of a are either move assigned or destructed a shall be equal to the value that rv had before this construction ~~(Note C)~~ linear

Notes: the algorithms swap(), equal() and lexicographical_compare() are defined in clause 25. Those entries marked "(Note A)" should have constant complexity. Those entries marked "(Note B)" have constant complexity unless allocator_propagate_never<X::allocator_type>::value is true, in which case they have linear complexity. Those entries marked "(Note C)" have constant complexity if a.get_allocator() == rv.get_allocator() or if either allocator_propagate_on_move_assignment<X::allocator_type>::value is true or allocator_propagate_on_copy_assignment<X::allocator_type>::value is true and linear complexity otherwise.

Table 89: Container requirements
expression	return type	operational semantics	assertion/note pre/post-condition	complexity
`a = rv;`	`X&`	All existing elements of `a` are either move assigned or destructed	`a` shall be equal to the value that `rv` had before this construction	~~(Note C)~~ linear

[ post Bellevue Howard adds: ]

This issue was voted to WP in Bellevue, but accidently got stepped on by N2525 which was voted to WP simulataneously. Moving back to Open for the purpose of getting the wording right. The intent of this issue and N2525 are not in conflict.

[ post Sophia Antipolis Howard updated proposed wording: ]