Issue 704: MoveAssignable requirement for container value type overly strict (original) (raw)

This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of C++11 status.

704. `MoveAssignable` requirement for container value type overly strict

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

Priority: Not Prioritized

View all other issues in [container.requirements].

View all issues with C++11 status.

Discussion:

The move-related changes inadvertently overwrote the intent of 276 (i). Issue 276 (i) removed the requirement of CopyAssignable from most of the member functions of node-based containers. But the move-related changes unnecessarily introduced the MoveAssignable requirement for those members which used to require CopyAssignable.

We also discussed (c++std-lib-18722) the possibility of dropping MoveAssignablefrom some of the sequence requirements. Additionally the in-place construction work may further reduce requirements. For purposes of an easy reference, here are the minimum sequence requirements as I currently understand them. Those items in requirements table in the working draft which do not appear below have been purposefully omitted for brevity as they do not have any requirements of this nature. Some items which do not have any requirements of this nature are included below just to confirm that they were not omitted by mistake.

Container Requirements

X u(a)	value_type must be CopyConstructible
X u(rv)	array requires value_type to be CopyConstructible
a = u	Sequences require value_type to be CopyConstructible and CopyAssignable. Associative containers require value_type to be CopyConstructible.
a = rv	array requires value_type to be CopyAssignable. Sequences containers with propagate_on_container_move_assignment == false allocators require value_type to be MoveConstructible and MoveAssignable. Associative containers with propagate_on_container_move_assignment == false allocators require value_type to be MoveConstructible.
swap(a,u)	array requires value_type to be Swappable.

Sequence Requirements

X(n)	value_type must be DefaultConstructible
X(n, t)	value_type must be CopyConstructible
X(i, j)	Sequences require value_type to be constructible from *i. Additionally if input_iterators are used, vector and deque require MoveContructible and MoveAssignable.
a.insert(p, t)	The value_type must be CopyConstructible. The sequences vector and deque also require the value_type to be CopyAssignable.
a.insert(p, rv)	The value_type must be MoveConstructible. The sequences vector and deque also require the value_type to be MoveAssignable.
a.insert(p, n, t)	The value_type must be CopyConstructible. The sequences vector and deque also require the value_type to be CopyAssignable.
a.insert(p, i, j)	If the iterators return an lvalue the value_type must be CopyConstructible. The sequences vector and deque also require the value_type to be CopyAssignable when the iterators return an lvalue. If the iterators return an rvalue the value_type must be MoveConstructible. The sequences vector and deque also require the value_type to be MoveAssignable when the iterators return an rvalue.
a.erase(p)	The sequences vector and deque require the value_type to be MoveAssignable.
a.erase(q1, q2)	The sequences vector and deque require the value_type to be MoveAssignable.
a.clear()
a.assign(i, j)	If the iterators return an lvalue the value_type must be CopyConstructible and CopyAssignable. If the iterators return an rvalue the value_type must be MoveConstructible and MoveAssignable.
a.assign(n, t)	The value_type must be CopyConstructible and CopyAssignable.
a.resize(n)	The value_type must be DefaultConstructible. The sequence vector also requires the value_type to be MoveConstructible.
a.resize(n, t)	The value_type must be CopyConstructible.

Optional Sequence Requirements

a.front()
a.back()
a.push_front(t)	The value_type must be CopyConstructible.
a.push_front(rv)	The value_type must be MoveConstructible.
a.push_back(t)	The value_type must be CopyConstructible.
a.push_back(rv)	The value_type must be MoveConstructible.
a.pop_front()
a.pop_back()
a[n]
a.at[n]

Associative Container Requirements

X(i, j)	If the iterators return an lvalue the value_type must be CopyConstructible. If the iterators return an rvalue the value_type must be MoveConstructible.
a_uniq.insert(t)	The value_type must be CopyConstructible.
a_uniq.insert(rv)	The key_type and the mapped_type (if it exists) must be MoveConstructible.
a_eq.insert(t)	The value_type must be CopyConstructible.
a_eq.insert(rv)	The key_type and the mapped_type (if it exists) must be MoveConstructible.
a.insert(p, t)	The value_type must be CopyConstructible.
a.insert(p, rv)	The key_type and the mapped_type (if it exists) must be MoveConstructible.
a.insert(i, j)	If the iterators return an lvalue the value_type must be CopyConstructible. If the iterators return an rvalue the key_type and the mapped_type (if it exists) must be MoveConstructible..

Unordered Associative Container Requirements

X(i, j, n, hf, eq)	If the iterators return an lvalue the value_type must be CopyConstructible. If the iterators return an rvalue the value_type must be MoveConstructible.
a_uniq.insert(t)	The value_type must be CopyConstructible.
a_uniq.insert(rv)	The key_type and the mapped_type (if it exists) must be MoveConstructible.
a_eq.insert(t)	The value_type must be CopyConstructible.
a_eq.insert(rv)	The key_type and the mapped_type (if it exists) must be MoveConstructible.
a.insert(p, t)	The value_type must be CopyConstructible.
a.insert(p, rv)	The key_type and the mapped_type (if it exists) must be MoveConstructible.
a.insert(i, j)	If the iterators return an lvalue the value_type must be CopyConstructible. If the iterators return an rvalue the key_type and the mapped_type (if it exists) must be MoveConstructible..

Miscellaneous Requirements

map[lvalue-key]	The key_type must be CopyConstructible. The mapped_type must be DefaultConstructible and MoveConstructible.
map[rvalue-key]	The key_type must be MoveConstructible. The mapped_type must be DefaultConstructible and MoveConstructible.

[ Kona (2007): Howard and Alan to update requirements table in issue with emplace signatures. ]

[ Bellevue: This should be handled as part of the concepts work. ]

[ 2009-07-20 Reopened by Howard: ]

This is one of the issues that was "solved by concepts" and is now no longer solved.

In a nutshell, concepts adopted the "minimum requirements" philosophy outlined in the discussion of this issue, and enforced it. My strong suggestion is that we translate the concepts specification into documentation for the containers.

What this means for vendors is that they will have to implement container members being careful to only use those characteristics of a type that the concepts specification formally allowed. Note that I am not talking about enable_if'ing everything. I am simply suggesting that (for example) we tell the vendor he can't call T'scopy constructor or move constructor within the emplace member function, etc.

What this means for customers is that they will be able to use types within C++03 containers which are sometimes not CopyConstructible, and sometimes not even MoveConstructible, etc.

[ 2009-10 Santa Cruz: ]

Leave open. Howard to provide wording.

[ 2010-02-06 Howard provides wording. ]

[ 2010-02-08 Moved to Tentatively Ready after 5 positive votes on c++std-lib. ]

[ 2010-02-10 Howard opened. I neglected to reduce the requirements on value_type for the insert function of the ordered and unordered associative containers when the argument is an rvalue. Fixed it. ]

[ 2010-02-11 Moved to Tentatively Ready after 5 positive votes on c++std-lib. ]

[ 2010-03-08 Nico opens: ]

I took the task to see whether 868 (i) is covered by 704 already. However, by doing that I have the impression that 704 is a big mistake.

Take e.g. the second change of 868 (i):

Change 23.3.5.2 [deque.cons] para 5:

Effects: Constructs a deque with n default constructed elements.

where "default constructed" should be replaced by "value-initialized". This is the constructor out of a number of elements:

ContType c(num)

704 says:

Remove the entire section 23.3.5.2 [deque.cons].

[ This section is already specified by the requirements tables. ]

BUT, there is no requirement table that lists this constructor at all, which means that we would lose the entire specification of this function !!!

In fact, I found with further investigation, if we follow 704 to remove 23.3.2.1 we

have no semantics forContType c(num)

have no complexity and no allocator specification forContType c(num,val)

have no semantics forContType c(num,val,alloc)

- have no complexity and no allocator specification forContType c(beg,end)

- have no semantics forContType c(beg,end,alloc)

- have different wording (which might or might not give the same guarantees) for the assign functions

because all these guarantees are given in the removed section but nowhere else (as far as I saw).

Looks to me that 704 need a significant review before we take that change, because chances are high that there are similar flaws in other proposed changes there (provided I am not missing anything).

[ 2010 Pittsburgh: ]

Removed the parts from the proposed wording that removed existing sections, and set to Ready for Pittsburgh.

Rationale:

[ post San Francisco: ]

Solved byN2776.

This rationale is obsolete.

Proposed resolution:

Change 23.2.2 [container.requirements.general]/4:

4 In Tables 91 and 92, X denotes a container class containing objects of type T, a and b denote values of type X,u denotes an identifier, r denotes ~~an lvalue or a const rvalue~~ a non-const value of type X, and rvdenotes a non-const rvalue of type X.

Change the following rows in Table 91 — Container requirements 23.2.2 [container.requirements.general]:

Table 91 — Container requirements

Expression Return type Assertion/notepre-/post-condition Complexity

X::value_type T Requires: T is Destructible. compile time

Expression	Return type	Assertion/notepre-/post-condition	Complexity
X::value_type	T	Requires: T is Destructible.	compile time

Change 23.2.2 [container.requirements.general]/10:

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

…

no erase(), clear(), pop_back() orpop_front() function throws an exception.

…

Insert a new paragraph prior to 23.2.2 [container.requirements.general]/14:

The descriptions of the requirements of the type T in this section use the terms CopyConstructible, MoveConstructible, constructible from *i, and constructible from args. These terms are equivalent to the following expression using the appropriate arguments:

allocator_traits::construct(x.get_allocator(), q, args...);

where x is a non-const lvalue of some container type X andq has type X::value_type*.

[Example: The container is going to move construct a T, so will call:

allocator_traits::construct(get_allocator(), q, std::move(t));

The default implementation of construct will call:

::new (q) T(std::forward(t)); // where forward is the same as move here, cast to rvalue

But the allocator author may override the above definition of constructand do the construction of T by some other means. — _end example_]

14 ...

Add to 23.2.2 [container.requirements.general]/14:

14 In Table 93, X denotes an allocator-aware container class with avalue_type of T using allocator of type A, udenotes a variable, a and b denote non-const lvalues of type X, t denotes an lvalue or a const rvalue of typeX, rv denotes a non-const rvalue of type X,m is a value of type A, and Q is an allocator type.

Change or add the following rows in Table 93 — Allocator-aware container requirements in 23.2.2 [container.requirements.general]:

Table 93 — Allocator-aware container requirements

Expression Return type Assertion/notepre-/post-condition Complexity

X(t, m)X u(t, m); Requires: T is CopyConstructible.post: u == t, get_allocator() == m linear

X(rv, m)X u(rv, m); Requires: T is MoveConstructible.post: u shall have the same elements, or copies of the elements, thatrv had before this construction, get_allocator() == m constant if m == rv.get_allocator(), otherwise linear

a = t X& Requires: T is CopyConstructible andCopyAssignablepost: a == t. linear

a = rv X& Requires: If allocator_traits< allocator_type > ::propagate_on_container_move_assignment ::value is false,T is MoveConstructible and MoveAssignable.All existing elements of a are either move assignedto or destroyed. a shall be equal to the value that rv had before this assignment linear

a.swap(b); void exchanges the contents of a and b constant

Expression	Return type	Assertion/notepre-/post-condition	Complexity
X(t, m)X u(t, m);	Requires: T is CopyConstructible.post: u == t, get_allocator() == m	linear
X(rv, m)X u(rv, m);	Requires: T is MoveConstructible.post: u shall have the same elements, or copies of the elements, thatrv had before this construction, get_allocator() == m	constant if m == rv.get_allocator(), otherwise linear
a = t	X&	Requires: T is CopyConstructible andCopyAssignablepost: a == t.	linear
a = rv	X&	Requires: If allocator_traits< allocator_type > ::propagate_on_container_move_assignment ::value is false,T is MoveConstructible and MoveAssignable.All existing elements of a are either move assignedto or destroyed. a shall be equal to the value that rv had before this assignment	linear
a.swap(b);	void	exchanges the contents of a and b	constant

Change the following rows in Table 94 — Sequence container requirements (in addition to container) in 23.2.4 [sequence.reqmts]:

Table 94 — Sequence container requirements (in addition to container)

Expression Return type Assertion/notepre-/post-condition

X(i, j)X a(i, j) Requires: ~~If the iterator's dereference operation returns an lvalue or a const rvalue, T shall be CopyConstructible.~~ T shall be constructible from *i. If the iterator does not meet the forward iterator requirements (24.3.5.5 [forward.iterators]), then vector also requires T to be MoveConstructible.Each iterator in the range [i,j) shall be dereferenced exactly once.post: size() == distance between i and jConstructs a sequence container equal to the range [i, j)

a = il; X& Requires: T is CopyConstructible andCopyAssignable. ~~a = X(il);~~ Assigns the range [il.begin(), il.end()) into a. All existing elements of a are either assigned or destroyed. rReturns *this;

a.emplace(p, args); iterator Requires: ~~ConstructibleAsElement<A, T, Args>.~~ T is constructible from args. vector and deque also require T to beMoveConstructible and MoveAssignable. Inserts an object of type T constructed withstd::forward(args)... before p.

a.insert(p, t); iterator Requires: ~~ConstructibleAsElement<A, T, Args> andT shall be CopyAssignable.~~ T shall beCopyConstructible. vector and deque also requireT to be CopyAssignable. Inserts a copy t beforep.

a.insert(p, rv); iterator Requires: ~~ConstructibleAsElement<A, T, T&&> and T shall be MoveAssignable.~~ T shall be MoveConstructible. vector anddeque also require T to be MoveAssignable.Inserts a copy rv before p.

a.insert(p, i, j) iterator Requires: ~~If the iterator's dereference operation returns an lvalue or a const rvalue, T shall be CopyConstructible.~~ T shall be constructible from *i. If the iterator does not meet the forward iterator requirements (24.3.5.5 [forward.iterators]), then vector also requires T to be MoveConstructible 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

a.erase(q); iterator Requires: ~~T and T shall beMoveAssignable.~~ vector and deque requireT to be MoveAssignable. Erases the element pointed to byq.

a.erase(q1, q2); iterator Requires: ~~T and T shall beMoveAssignable.~~ vector and deque requireT to be MoveAssignable. Erases the elements in the range[q1, q2).

a.clear(); void ~~erase(begin(), end())~~ Destroys all elements in a. Invalidates all references, pointers, and iterators referring to the elements of a and may invalidate the past-the-end iterator.post: ~~size() == 0~~ a.empty() == true

a.assign(i, j) void Requires: ~~If the iterator's dereference operation returns an lvalue or a const rvalue, T shall be CopyConstructible andCopyAssignable.~~ T shall be constructible and assignable from *i. If the iterator does not meet the forward iterator requirements (24.3.5.5 [forward.iterators]), then vector also requires T to be MoveConstructible.Each iterator in the range [i,j) shall be dereferenced exactly once.pre: i, j are not iterators into a.Replaces elements in a with a copy of [i, j).

Expression	Return type	Assertion/notepre-/post-condition
X(i, j)X a(i, j)	Requires: ~~If the iterator's dereference operation returns an lvalue or a const rvalue, T shall be CopyConstructible.~~ T shall be constructible from *i. If the iterator does not meet the forward iterator requirements (24.3.5.5 [forward.iterators]), then vector also requires T to be MoveConstructible.Each iterator in the range [i,j) shall be dereferenced exactly once.post: size() == distance between i and jConstructs a sequence container equal to the range [i, j)
a = il;	X&	Requires: T is CopyConstructible andCopyAssignable. ~~a = X(il);~~ Assigns the range [il.begin(), il.end()) into a. All existing elements of a are either assigned or destroyed. rReturns *this;
a.emplace(p, args);	iterator	Requires: ~~ConstructibleAsElement<A, T, Args>.~~ T is constructible from args. vector and deque also require T to beMoveConstructible and MoveAssignable. Inserts an object of type T constructed withstd::forward(args)... before p.
a.insert(p, t);	iterator	Requires: ~~ConstructibleAsElement<A, T, Args> andT shall be CopyAssignable.~~ T shall beCopyConstructible. vector and deque also requireT to be CopyAssignable. Inserts a copy t beforep.
a.insert(p, rv);	iterator	Requires: ~~ConstructibleAsElement<A, T, T&&> and T shall be MoveAssignable.~~ T shall be MoveConstructible. vector anddeque also require T to be MoveAssignable.Inserts a copy rv before p.
a.insert(p, i, j)	iterator	Requires: ~~If the iterator's dereference operation returns an lvalue or a const rvalue, T shall be CopyConstructible.~~ T shall be constructible from *i. If the iterator does not meet the forward iterator requirements (24.3.5.5 [forward.iterators]), then vector also requires T to be MoveConstructible 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
a.erase(q);	iterator	Requires: ~~T and T shall beMoveAssignable.~~ vector and deque requireT to be MoveAssignable. Erases the element pointed to byq.
a.erase(q1, q2);	iterator	Requires: ~~T and T shall beMoveAssignable.~~ vector and deque requireT to be MoveAssignable. Erases the elements in the range[q1, q2).
a.clear();	void	~~erase(begin(), end())~~ Destroys all elements in a. Invalidates all references, pointers, and iterators referring to the elements of a and may invalidate the past-the-end iterator.post: ~~size() == 0~~ a.empty() == true
a.assign(i, j)	void	Requires: ~~If the iterator's dereference operation returns an lvalue or a const rvalue, T shall be CopyConstructible andCopyAssignable.~~ T shall be constructible and assignable from *i. If the iterator does not meet the forward iterator requirements (24.3.5.5 [forward.iterators]), then vector also requires T to be MoveConstructible.Each iterator in the range [i,j) shall be dereferenced exactly once.pre: i, j are not iterators into a.Replaces elements in a with a copy of [i, j).

Change the following rows in Table 95 — Optional sequence container operations in 23.2.4 [sequence.reqmts]:

Table 95 — Optional sequence container operations

Expression Return type Operational semantics Container

a.emplace_front(args) void ~~a.emplace(a.begin(), std::forward(args)...)~~ Prepends an object of type T constructed withstd::forward(args).... Requires: ~~ConstructibleAsElement<A, T, Args>~~ T shall be constructible from args. list, deque, forward_list

a.emplace_back(args) void ~~a.emplace(a.end(), std::forward(args)...)~~ Appends an object of type T constructed withstd::forward(args).... Requires: ~~ConstructibleAsElement<A, T, Args>~~ T shall be constructible from args. vector also requires T to be MoveConstructible. list, deque, vector

a.push_front(t) void ~~a.insert(a.begin(), t)~~ Prepends a copy of t. Requires: ~~ConstructibleAsElement<A, T, T> andT shall be CopyAssignable.~~ T shall be CopyConstructible. list, deque, forward_list

a.push_front(rv) void ~~a.insert(a.begin(), t)~~ Prepends a copy of rv. Requires: ~~ConstructibleAsElement<A, T, T&&> andT shall be MoveAssignable.~~ T shall be MoveConstructible. list, deque, forward_list

a.push_back(t) void ~~a.insert(a.end(), t)~~ Appends a copy of t. Requires: ~~ConstructibleAsElement<A, T, T> andT shall be CopyAssignable.~~ T shall be CopyConstructible. vector, list, deque, basic_string

a.push_back(rv) void ~~a.insert(a.end(), t)~~ Appends a copy of rv. Requires: ~~ConstructibleAsElement<A, T, T&&> andT shall be MoveAssignable.~~ T shall be MoveConstructible. vector, list, deque, basic_string

a.pop_front() void ~~a.erase(a.begin())~~ Destroys the first element. Requires: a.empty() shall be false. list, deque, forward_list

a.pop_back() void ~~{ iterator tmp = a.end();--tmp;a.erase(tmp); }~~ Destroys the last element. Requires: a.empty() shall be false. vector, list, deque, basic_string

Expression	Return type	Operational semantics	Container
a.emplace_front(args)	void	~~a.emplace(a.begin(), std::forward(args)...)~~ Prepends an object of type T constructed withstd::forward(args).... Requires: ~~ConstructibleAsElement<A, T, Args>~~ T shall be constructible from args.	list, deque, forward_list
a.emplace_back(args)	void	~~a.emplace(a.end(), std::forward(args)...)~~ Appends an object of type T constructed withstd::forward(args).... Requires: ~~ConstructibleAsElement<A, T, Args>~~ T shall be constructible from args. vector also requires T to be MoveConstructible.	list, deque, vector
a.push_front(t)	void	~~a.insert(a.begin(), t)~~ Prepends a copy of t. Requires: ~~ConstructibleAsElement<A, T, T> andT shall be CopyAssignable.~~ T shall be CopyConstructible.	list, deque, forward_list
a.push_front(rv)	void	~~a.insert(a.begin(), t)~~ Prepends a copy of rv. Requires: ~~ConstructibleAsElement<A, T, T&&> andT shall be MoveAssignable.~~ T shall be MoveConstructible.	list, deque, forward_list
a.push_back(t)	void	~~a.insert(a.end(), t)~~ Appends a copy of t. Requires: ~~ConstructibleAsElement<A, T, T> andT shall be CopyAssignable.~~ T shall be CopyConstructible.	vector, list, deque, basic_string
a.push_back(rv)	void	~~a.insert(a.end(), t)~~ Appends a copy of rv. Requires: ~~ConstructibleAsElement<A, T, T&&> andT shall be MoveAssignable.~~ T shall be MoveConstructible.	vector, list, deque, basic_string
a.pop_front()	void	~~a.erase(a.begin())~~ Destroys the first element. Requires: a.empty() shall be false.	list, deque, forward_list
a.pop_back()	void	~~{ iterator tmp = a.end();--tmp;a.erase(tmp); }~~ Destroys the last element. Requires: a.empty() shall be false.	vector, list, deque, basic_string

Insert a new paragraph prior to 23.2.7 [associative.reqmts]/7, and edit paragraph 7:

The associative containers meet all of the requirements of Allocator-aware containers (23.2.2 [container.requirements.general]), except for the containers map and multimap, the requirements placed onvalue_type in Table 93 apply instead directly to key_type andmapped_type. [Note: For example key_type andmapped_type are sometimes required to be CopyAssignable even though the value_type (pair<const key_type, mapped_type>) is not CopyAssignable. — _end note_]

7 In Table 96, X denotes an associative container class, a denotes a value of X, a_uniq denotes a value of X whenX supports unique keys, a_eq denotes a value of Xwhen X supports multiple keys, u denotes an identifier,~~r denotes an lvalue or a const rvalue of type X,rv denotes a non-const rvalue of type X,~~ i andj satisfy input iterator requirements and refer to elements implicitly convertible to value_type, [i,j) denotes a valid range,p denotes a valid const iterator to a, q denotes a valid dereferenceable const iterator to a, [q1, q2) denotes a valid range of const iterators in a, il designates an object of type initializer_list<value_type>, t denotes a value of X::value_type, k denotes a value of X::key_typeand c denotes a value of type X::key_compare. Adenotes the storage allocator used by X, if any, orstd::allocator<X::value_type> otherwise, and m denotes an allocator of a type convertible to A.

Change or add the following rows in Table 96 — Associative container requirements (in addition to container) in 23.2.7 [associative.reqmts]:

Table 96 — Associative container requirements (in addition to container)

Expression Return type Assertion/notepre-/post-condition Complexity

X::key_type Key Requires: Key is ~~CopyConstructible andCopyAssignable~~ Destructible compile time

X::mapped_type (map and multimap only) T Requires: T is Destructible compile time

X(c)X a(c); Requires: ~~ConstructibleAsElement<A, key_compare, key_compare>~~. key_compare is CopyConstructible.Constructs an empty container.Uses a copy of c as a comparison object. constant

X()X a; Requires: ~~ConstructibleAsElement<A, key_compare, key_compare>~~. key_compare is DefaultConstructible.Constructs an empty container.Uses Compare() as a comparison object. constant

X(i, j, c)X a(i, j, c); Requires: ~~ConstructibleAsElement<A, key_compare, key_compare>~~. key_compare is CopyConstructible. value_typeshall be constructible from *i.Constructs an empty container ans inserts elements from the range [i, j) into it; uses c as a comparison object. N log N in general (N is the distance fromi to j); linear if [i, j) is sorted withvalue_comp()

X(i, j)X a(i, j); Requires: ~~ConstructibleAsElement<A, key_compare, key_compare>~~. value_type shall be constructible from *i. key_compare isDefaultConstructible. Same as above, but usesCompare() as a comparison object. same as above

a = il X& ~~a = X(il);return *this;~~ Requires: T is CopyConstructible andCopyAssignable. Assigns the range [il.begin(), il.end()) into a. All existing elements of a are either assigned or destroyed. ~~Same as a = X(il).~~ N log N in general (N is il.size() added to the existing size of a); linear if[il.begin(), il.end()) is sorted with value_comp()

a_uniq.emplace(args) pair<iterator, bool> Requires: T shall be constructible fromargsinserts a T object t constructed withstd::forward(args)... if and only if there is no element in the container with key equivalent to the key of t. The boolcomponent of the returned pair is true if and only if the insertion takes place, and the iterator component of the pair points to the element with key equivalent to the key of t. logarithmic

a_eq.emplace(args) iterator Requires: T shall be constructible fromargsinserts a T object t constructed withstd::forward(args)... and returns the iterator pointing to the newly inserted element. logarithmic

a_uniq.insert(t) pair<iterator, bool> Requires: T shall be MoveConstructible ift is a non-const rvalue expression, else T shall beCopyConstructible.inserts t if and only if there is no element in the container with key equivalent to the key of t. The bool component of the returned pair is true if and only if the insertion takes place, and the iterator component of the pair points to the element with key equivalent to the key oft. logarithmic

a_eq.insert(t) iterator Requires: T shall be MoveConstructible ift is a non-const rvalue expression, else T shall beCopyConstructible.inserts t and returns the iterator pointing to the newly inserted element. If a range containing elements equivalent to t exists ina_eq, t is inserted at the end of that range. logarithmic

a.insert(p, t) iterator Requires: T shall be MoveConstructible ift is a non-const rvalue expression, else T shall beCopyConstructible.inserts t if and only if there is no element with key equivalent to the key of t in containers with unique keys; always inserts t in containers with equivalent keys; always returns the iterator pointing to the element with key equivalent to the key of t. t is inserted as close as possible to the position just prior to p. logarithmic in general, but amortized constant if t is inserted right before p.

a.insert(i, j) void Requires: T shall be constructible from *i.pre: i, j are not iterators into a. inserts each element from the range [i,j) if and only if there is no element with key equivalent to the key of that element in containers with unique keys; always inserts that element in containers with equivalent keys. N log(size() + N ) (N is the distance from i to j)

Expression	Return type	Assertion/notepre-/post-condition	Complexity
X::key_type	Key	Requires: Key is ~~CopyConstructible andCopyAssignable~~ Destructible	compile time
X::mapped_type (map and multimap only)	T	Requires: T is Destructible	compile time
X(c)X a(c);	Requires: ~~ConstructibleAsElement<A, key_compare, key_compare>~~. key_compare is CopyConstructible.Constructs an empty container.Uses a copy of c as a comparison object.	constant
X()X a;	Requires: ~~ConstructibleAsElement<A, key_compare, key_compare>~~. key_compare is DefaultConstructible.Constructs an empty container.Uses Compare() as a comparison object.	constant
X(i, j, c)X a(i, j, c);	Requires: ~~ConstructibleAsElement<A, key_compare, key_compare>~~. key_compare is CopyConstructible. value_typeshall be constructible from *i.Constructs an empty container ans inserts elements from the range [i, j) into it; uses c as a comparison object.	N log N in general (N is the distance fromi to j); linear if [i, j) is sorted withvalue_comp()
X(i, j)X a(i, j);	Requires: ~~ConstructibleAsElement<A, key_compare, key_compare>~~. value_type shall be constructible from *i. key_compare isDefaultConstructible. Same as above, but usesCompare() as a comparison object.	same as above
a = il	X&	~~a = X(il);return this;~~ Requires:* T is CopyConstructible andCopyAssignable. Assigns the range [il.begin(), il.end()) into a. All existing elements of a are either assigned or destroyed.	~~Same as a = X(il).~~ N log N in general (N is il.size() added to the existing size of a); linear if[il.begin(), il.end()) is sorted with value_comp()
a_uniq.emplace(args)	pair<iterator, bool>	Requires: T shall be constructible fromargsinserts a T object t constructed withstd::forward(args)... if and only if there is no element in the container with key equivalent to the key of t. The boolcomponent of the returned pair is true if and only if the insertion takes place, and the iterator component of the pair points to the element with key equivalent to the key of t.	logarithmic
a_eq.emplace(args)	iterator	Requires: T shall be constructible fromargsinserts a T object t constructed withstd::forward(args)... and returns the iterator pointing to the newly inserted element.	logarithmic
a_uniq.insert(t)	pair<iterator, bool>	Requires: T shall be MoveConstructible ift is a non-const rvalue expression, else T shall beCopyConstructible.inserts t if and only if there is no element in the container with key equivalent to the key of t. The bool component of the returned pair is true if and only if the insertion takes place, and the iterator component of the pair points to the element with key equivalent to the key oft.	logarithmic
a_eq.insert(t)	iterator	Requires: T shall be MoveConstructible ift is a non-const rvalue expression, else T shall beCopyConstructible.inserts t and returns the iterator pointing to the newly inserted element. If a range containing elements equivalent to t exists ina_eq, t is inserted at the end of that range.	logarithmic
a.insert(p, t)	iterator	Requires: T shall be MoveConstructible ift is a non-const rvalue expression, else T shall beCopyConstructible.inserts t if and only if there is no element with key equivalent to the key of t in containers with unique keys; always inserts t in containers with equivalent keys; always returns the iterator pointing to the element with key equivalent to the key of t. t is inserted as close as possible to the position just prior to p.	logarithmic in general, but amortized constant if t is inserted right before p.
a.insert(i, j)	void	Requires: T shall be constructible from *i.pre: i, j are not iterators into a. inserts each element from the range [i,j) if and only if there is no element with key equivalent to the key of that element in containers with unique keys; always inserts that element in containers with equivalent keys.	N log(size() + N ) (N is the distance from i to j)

Insert a new paragraph prior to 23.2.8 [unord.req]/9:

The unordered associative containers meet all of the requirements of Allocator-aware containers (23.2.2 [container.requirements.general]), except for the containers unordered_map and unordered_multimap, the requirements placed on value_type in Table 93 apply instead directly to key_type and mapped_type. [Note: For example key_type and mapped_type are sometimes required to beCopyAssignable even though the value_type (pair<const key_type, mapped_type>) is not CopyAssignable. — _end note_]

9 ...

Change or add the following rows in Table 98 — Unordered associative container requirements (in addition to container) in 23.2.8 [unord.req]:

Table 98 — Unordered associative container requirements (in addition to container)

Expression Return type Assertion/notepre-/post-condition Complexity

X::key_type Key Requires: Key shall be ~~CopyAssignable andCopyConstructible~~ Destructible compile time

X::mapped_type (unordered_map andunordered_multimap only) T _Requires:_T is Destructible compile time

X(n, hf, eq)X a(n, hf, eq) X Requires: hasher and key_equal areCopyConstructible. Constructs an empty container with at leastn buckets, using hf as the hash function and eq as the key equality predicate. O(N)

X(n, hf)X a(n, hf) X Requires: hasher is CopyConstructible and key_equal is DefaultConstructible. Constructs an empty container with at least n buckets, using hf as the hash function and key_equal() as the key equality predicate. O(N)

X(n)X a(n) X Requires: hasher and key_equal areDefaultConstructible. Constructs an empty container with at leastn buckets, using hasher() as the hash function and key_equal() as the key equality predicate. O(N)

X()X a X Requires: hasher and key_equal areDefaultConstructible. Constructs an empty container an unspecified number of buckets, using hasher() as the hash function and key_equal() as the key equality predicate. constant

X(i, j, n, hf, eq)X a(i, j, n, hf, eq) X Requires: value_type is constructible from*i. hasher and key_equal areCopyConstructible.Constructs an empty container with at least n buckets, usinghf as the hash function and eq as the key equality predicate, and inserts elements from [i, j) into it. Average case O(N) (N is distance(i, j)), worst case O(N2)

X(i, j, n, hf)X a(i, j, n, hf) X Requires: value_type is constructible from *i.hasher is CopyConstructible and key_equal isDefaultConstructible. Constructs an empty container with at least n buckets, using hf as the hash function andkey_equal() as the key equality predicate, and inserts elements from[i, j) into it. Average case O(N) (N is distance(i, j)), worst case O(N2)

X(i, j, n)X a(i, j, n) X Requires: value_type is constructible from *i.hasher and key_equal areDefaultConstructible. Constructs an empty container with at least n buckets, using hasher() as the hash function andkey_equal() as the key equality predicate, and inserts elements from[i, j) into it. Average case O(N) (N is distance(i, j)), worst case O(N2)

X(i, j)X a(i, j) X Requires: value_type is constructible from *i.hasher and key_equal areDefaultConstructible. Constructs an empty container with an unspecified number of buckets, using hasher() as the hash function andkey_equal() as the key equality predicate, and inserts elements from[i, j) into it. Average case O(N) (N is distance(i, j)), worst case O(N2)

X(b)X a(b) X Copy constructor. In addition to the ~~contained elements~~ requirements of Table 93 (23.2.2 [container.requirements.general]), copies the hash function, predicate, and maximum load factor. Average case linear in b.size(), worst case quadratic.

a = b X& Copy assignment operator. In addition to the ~~contained elements~~ requirements of Table 93 (23.2.2 [container.requirements.general]), copies the hash function, predicate, and maximum load factor. Average case linear in b.size(), worst case quadratic.

a = il X& ~~a = X(il); return *this;~~ Requires: T is CopyConstructible andCopyAssignable. Assigns the range [il.begin(), il.end()) into a. All existing elements of a are either assigned or destroyed. Average case linear in il.size(), worst case quadratic.

a_uniq.emplace(args) pair<iterator, bool> Requires: T shall be constructible fromargsinserts a T object t constructed withstd::forward(args)... if and only if there is no element in the container with key equivalent to the key of t. The boolcomponent of the returned pair is true if and only if the insertion takes place, and the iterator component of the pair points to the element with key equivalent to the key of t. Average case O(1), worst case O(a_uniq.size()).

a_eq.emplace(args) iterator Requires: T shall be constructible fromargsinserts a T object t constructed withstd::forward(args)... and returns the iterator pointing to the newly inserted element. Average case O(1), worst case O(a_eq.size()).

a.emplace_hint(p, args) iterator Requires: T shall be constructible fromargsequivalent to a.emplace( std::forward(args)...). Return value is an iterator pointing to the element with the key equivalent to the newly inserted element. The const_iterator p is a hint pointing to where the search should start. Implementations are permitted to ignore the hint. Average case O(1), worst case O(a.size()).

a_uniq.insert(t) pair<iterator, bool> Requires: T shall be MoveConstructible ift is a non-const rvalue expression, else T shall beCopyConstructible.Inserts t if and only if there is no element in the container with key equivalent to the key of t. The bool component of the returned pair indicates whether the insertion takes place, and the iterator component points to the element with key equivalent to the key of t. Average case O(1), worst case O(a_uniq.size()).

a_eq.insert(t) iterator Requires: T shall be MoveConstructible ift is a non-const rvalue expression, else T shall beCopyConstructible.Inserts t, and returns an iterator pointing to the newly inserted element. Average case O(1), worst case O(a_uniq.size()).

a.insert(q, t) iterator Requires: T shall be MoveConstructible ift is a non-const rvalue expression, else T shall beCopyConstructible.Equivalent to a.insert(t). Return value is an iterator pointing to the element with the key equivalent to that of t. The iterator qis a hint pointing to where the search should start. Implementations are permitted to ignore the hint. Average case O(1), worst case O(a_uniq.size()).

a.insert(i, j) void Requires: T shall be constructible from *i.Pre: i and j are not iterators in a. Equivalent toa.insert(t) for each element in [i,j). Average case O(N), where N is distance(i, j). Worst case O(N * a.size()).

Expression	Return type	Assertion/notepre-/post-condition	Complexity
X::key_type	Key	Requires: Key shall be ~~CopyAssignable andCopyConstructible~~ Destructible	compile time
X::mapped_type (unordered_map andunordered_multimap only)	T	_Requires:_T is Destructible	compile time
X(n, hf, eq)X a(n, hf, eq)	X	Requires: hasher and key_equal areCopyConstructible. Constructs an empty container with at leastn buckets, using hf as the hash function and eq as the key equality predicate.	O(N)
X(n, hf)X a(n, hf)	X	Requires: hasher is CopyConstructible and key_equal is DefaultConstructible. Constructs an empty container with at least n buckets, using hf as the hash function and key_equal() as the key equality predicate.	O(N)
X(n)X a(n)	X	Requires: hasher and key_equal areDefaultConstructible. Constructs an empty container with at leastn buckets, using hasher() as the hash function and key_equal() as the key equality predicate.	O(N)
X()X a	X	Requires: hasher and key_equal areDefaultConstructible. Constructs an empty container an unspecified number of buckets, using hasher() as the hash function and key_equal() as the key equality predicate.	constant
X(i, j, n, hf, eq)X a(i, j, n, hf, eq)	X	Requires: value_type is constructible from*i. hasher and key_equal areCopyConstructible.Constructs an empty container with at least n buckets, usinghf as the hash function and eq as the key equality predicate, and inserts elements from [i, j) into it.	Average case O(N) (N is distance(i, j)), worst case O(N2)
X(i, j, n, hf)X a(i, j, n, hf)	X	Requires: value_type is constructible from *i.hasher is CopyConstructible and key_equal isDefaultConstructible. Constructs an empty container with at least n buckets, using hf as the hash function andkey_equal() as the key equality predicate, and inserts elements from[i, j) into it.	Average case O(N) (N is distance(i, j)), worst case O(N2)
X(i, j, n)X a(i, j, n)	X	Requires: value_type is constructible from *i.hasher and key_equal areDefaultConstructible. Constructs an empty container with at least n buckets, using hasher() as the hash function andkey_equal() as the key equality predicate, and inserts elements from[i, j) into it.	Average case O(N) (N is distance(i, j)), worst case O(N2)
X(i, j)X a(i, j)	X	Requires: value_type is constructible from *i.hasher and key_equal areDefaultConstructible. Constructs an empty container with an unspecified number of buckets, using hasher() as the hash function andkey_equal() as the key equality predicate, and inserts elements from[i, j) into it.	Average case O(N) (N is distance(i, j)), worst case O(N2)
X(b)X a(b)	X	Copy constructor. In addition to the ~~contained elements~~ requirements of Table 93 (23.2.2 [container.requirements.general]), copies the hash function, predicate, and maximum load factor.	Average case linear in b.size(), worst case quadratic.
a = b	X&	Copy assignment operator. In addition to the ~~contained elements~~ requirements of Table 93 (23.2.2 [container.requirements.general]), copies the hash function, predicate, and maximum load factor.	Average case linear in b.size(), worst case quadratic.
a = il	X&	~~a = X(il); return this;~~ Requires:* T is CopyConstructible andCopyAssignable. Assigns the range [il.begin(), il.end()) into a. All existing elements of a are either assigned or destroyed.	Average case linear in il.size(), worst case quadratic.
a_uniq.emplace(args)	pair<iterator, bool>	Requires: T shall be constructible fromargsinserts a T object t constructed withstd::forward(args)... if and only if there is no element in the container with key equivalent to the key of t. The boolcomponent of the returned pair is true if and only if the insertion takes place, and the iterator component of the pair points to the element with key equivalent to the key of t.	Average case O(1), worst case O(a_uniq.size()).
a_eq.emplace(args)	iterator	Requires: T shall be constructible fromargsinserts a T object t constructed withstd::forward(args)... and returns the iterator pointing to the newly inserted element.	Average case O(1), worst case O(a_eq.size()).
a.emplace_hint(p, args)	iterator	Requires: T shall be constructible fromargsequivalent to a.emplace( std::forward(args)...). Return value is an iterator pointing to the element with the key equivalent to the newly inserted element. The const_iterator p is a hint pointing to where the search should start. Implementations are permitted to ignore the hint.	Average case O(1), worst case O(a.size()).
a_uniq.insert(t)	pair<iterator, bool>	Requires: T shall be MoveConstructible ift is a non-const rvalue expression, else T shall beCopyConstructible.Inserts t if and only if there is no element in the container with key equivalent to the key of t. The bool component of the returned pair indicates whether the insertion takes place, and the iterator component points to the element with key equivalent to the key of t.	Average case O(1), worst case O(a_uniq.size()).
a_eq.insert(t)	iterator	Requires: T shall be MoveConstructible ift is a non-const rvalue expression, else T shall beCopyConstructible.Inserts t, and returns an iterator pointing to the newly inserted element.	Average case O(1), worst case O(a_uniq.size()).
a.insert(q, t)	iterator	Requires: T shall be MoveConstructible ift is a non-const rvalue expression, else T shall beCopyConstructible.Equivalent to a.insert(t). Return value is an iterator pointing to the element with the key equivalent to that of t. The iterator qis a hint pointing to where the search should start. Implementations are permitted to ignore the hint.	Average case O(1), worst case O(a_uniq.size()).
a.insert(i, j)	void	Requires: T shall be constructible from *i.Pre: i and j are not iterators in a. Equivalent toa.insert(t) for each element in [i,j).	Average case O(N), where N is distance(i, j). Worst case O(N * a.size()).

Change [forwardlist]/2:

2 A forward_list satisfies all of the requirements of a container (table 91), except that the size() member function is not provided.A forward_list also satisfies all of the requirements of an allocator-aware container (table 93). And forward_list provides theassign member functions as specified in Table 94, Sequence container requirements, and several of the optional sequence container requirements (Table 95).Descriptions are provided here only for operations on forward_list that are not described in that table or for operations where there is additional semantic information.

Add a new paragraph after [forwardlist.modifiers]/23:

void clear();

23 Effects: Erases all elements in the range [begin(),end()).

Remarks: Does not invalidate past-the-end iterators.

Change 23.3.13.3 [vector.capacity]/13:

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

13 Requires: T shall be CopyConstructible.If value_type has a move constructor, that constructor shall not throw any exceptions.

In 23.5.6 [unord.set] and 23.5.7 [unord.multiset] substitute "Key" for "Value".

[ The above substitution is normative as it ties into the requirements table. ]

Issue 704: MoveAssignable requirement for container value type overly strict (original) (raw)

704. MoveAssignable requirement for container value type overly strict

704. `MoveAssignable` requirement for container value type overly strict