*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.*

**Section:** 21.2 [container.requirements] **Status:** C++11
**Submitter:** Howard Hinnant **Opened:** 2007-05-20 **Last modified:** 2019-01-01

**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.
Issue 276 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 `MoveAssignable`
from 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.

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. |

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. |

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] |

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.. |

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.. |

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 nottalking aboutenable_if'ing everything. I am simply suggesting that (for example) we tell the vendor he can't callT'scopy constructor or move constructor within theemplacemember 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 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:

Change 21.3.8.2 [deque.cons] para 5:

Effects:Constructs adequewithndefault 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 21.3.8.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 for
ContType c(num)- have no complexity and no allocator specification for
ContType c(num,val)- have no semantics for
ContType c(num,val,alloc)- - have no complexity and no allocator specification for
ContType c(beg,end)- - have no semantics for
ContType c(beg,end,alloc)- - have different wording (which might or might not give the same guarantees) for the
assignfunctionsbecause 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 by N2776.

This rationale is obsolete.

**Proposed resolution:**

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

4 In Tables 91 and 92,

Xdenotes a container class containing objects of typeT,aandbdenote values of typeX,udenotes an identifier,rdenotes~~an lvalue or a const rvalue~~a non-const value of typeX, andrvdenotes a non-const rvalue of typeX.

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

Table 91 — Container requirements Expression Return type Assertion/note

pre-/post-conditionComplexity X::value_typeTRequires:TisDestructible.compile time

Change 21.2.1 [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 21.2.1 [container.requirements.general]/14:

The descriptions of the requirements of the type

Tin this section use the termsCopyConstructible,MoveConstructible,constructible from, and*iconstructible from. These terms are equivalent to the following expression using the appropriate arguments:argsallocator_traits<allocator_type>::construct(x.get_allocator(), q, args...);where

xis a non-const lvalue of some container typeXandqhas typeX::value_type*.[

Example:The container is going to move construct aT, so will call:allocator_traits<allocator_type>::construct(get_allocator(), q, std::move(t));The default implementation of construct will call:

::new (q) T(std::forward<T>(t)); // where forward is the same as move here, cast to rvalueBut the allocator author may override the above definition of

constructand do the construction ofTby some other means. —end example]14 ...

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

14 In Table 93,

Xdenotes an allocator-aware container class with avalue_typeofTusing allocator of typeA,udenotes a variable,aandbdenote non-const lvalues of typeX,tdenotes an lvalue or a const rvalue of typeX,rvdenotes a non-const rvalue of typeX,mis a value of typeA, andQis an allocator type.

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

Table 93 — Allocator-aware container requirements Expression Return type Assertion/note

pre-/post-conditionComplexity X(t, m)

X u(t, m);Requires:TisCopyConstructible.

post:u == t,

get_allocator() == mlinear X(rv, m)

X u(rv, m);Requires:TisMoveConstructible.

post:ushall have the same elements, or copies of the elements, thatrvhad before this construction,

get_allocator() == mconstant if m == rv.get_allocator(), otherwise lineara = tX&Requires:TisCopyConstructibleandCopyAssignable

post:a == t.linear a = rvX&Requires:Ifallocator_traits< allocator_type > ::propagate_on_container_move_assignment ::valueisfalse,TisMoveConstructibleandMoveAssignable.

All existing elements ofaare either move assigned to or destroyed.

ashall be equal to the value thatrvhad before this assignmentlinear a.swap(b);voidexchanges the contents of aandbconstant

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

Table 94 — Sequence container requirements (in addition to container) Expression Return type Assertion/note

pre-/post-conditionX(i, j)

X a(i, j)Requires:~~If the iterator's dereference operation returns an lvalue or a const rvalue,~~Tshall beCopyConstructible.Tshall be constructible from*i.

If the iterator does not meet the forward iterator requirements (22.3.5.4 [forward.iterators]), thenvectoralso requiresTto beMoveConstructible.

Each iterator in the range[i,j)shall be dereferenced exactly once.

post:size() ==distance betweeniandj

Constructs a sequence container equal to the range[i, j)a = il;X&Requires:TisCopyConstructibleandCopyAssignable.

a = X(il);

Assigns the range[il.begin(), il.end())intoa. All existing elements ofaare either assigned or destroyed.

~~r~~Returns*this;a.emplace(p, args);iteratorRequires:ConstructibleAsElement<A, T, Args>.Tis constructible fromargs.vectoranddequealso requireTto beMoveConstructibleandMoveAssignable. Inserts an object of typeTconstructed withstd::forward<Args>(args)...beforep.a.insert(p, t);iteratorRequires:ConstructibleAsElement<A, T, Args>andTshall beCopyAssignable.Tshall beCopyConstructible.vectoranddequealso requireTto beCopyAssignable. Inserts a copytbeforep.a.insert(p, rv);iteratorRequires:ConstructibleAsElement<A, T, T&&>andTshall beMoveAssignable.Tshall beMoveConstructible.vectoranddequealso requireTto beMoveAssignable. Inserts a copyrvbeforep.a.insert(p, i, j)iteratorRequires:~~If the iterator's dereference operation returns an lvalue or a const rvalue,~~Tshall beCopyConstructible.Tshall be constructible from*i.

If the iterator does not meet the forward iterator requirements (22.3.5.4 [forward.iterators]), thenvectoralso requiresTto beMoveConstructibleandMoveAssignable.

Each iterator in the range[i,j)shall be dereferenced exactly once.

pre:iandjare not iterators intoa.

Inserts copies of elements in[i, j)beforepa.erase(q);iteratorRequires:TandTshall beMoveAssignable.vectoranddequerequireTto beMoveAssignable. Erases the element pointed to byq.a.erase(q1, q2);iteratorRequires:TandTshall beMoveAssignable.vectoranddequerequireTto beMoveAssignable. Erases the elements in the range[q1, q2).a.clear();voiderase(begin(), end())

Destroys all elements ina. Invalidates all references, pointers, and iterators referring to the elements ofaand may invalidate the past-the-end iterator.

post:~~size() == 0~~a.empty() == truea.assign(i, j)voidRequires:~~If the iterator's dereference operation returns an lvalue or a const rvalue,~~Tshall beCopyConstructibleandCopyAssignable.Tshall be constructible and assignable from*i. If the iterator does not meet the forward iterator requirements (22.3.5.4 [forward.iterators]), thenvectoralso requiresTto beMoveConstructible.

Each iterator in the range[i,j)shall be dereferenced exactly once.

pre:i,jare not iterators intoa.

Replaces elements inawith a copy of[i, j).

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

Table 95 — Optional sequence container operations Expression Return type Operational semantics Container a.emplace_front(args)voida.emplace(a.begin(), std::forward<Args>(args)...)

Prepends an object of typeTconstructed withstd::forward<Args>(args)....

Requires:ConstructibleAsElement<A, T, Args>Tshall be constructible fromargs.list,deque,forward_lista.emplace_back(args)voida.emplace(a.end(), std::forward<Args>(args)...)

Appends an object of typeTconstructed withstd::forward<Args>(args)....

Requires:ConstructibleAsElement<A, T, Args>Tshall be constructible fromargs.vectoralso requiresTto beMoveConstructible.list,deque,vectora.push_front(t)voida.insert(a.begin(), t)

Prepends a copy oft.

Requires:ConstructibleAsElement<A, T, T>andTshall beCopyAssignable.Tshall beCopyConstructible.list,deque,forward_lista.push_front(rv)voida.insert(a.begin(), t)

Prepends a copy ofrv.

Requires:ConstructibleAsElement<A, T, T&&>andTshall beMoveAssignable.Tshall beMoveConstructible.list,deque,forward_lista.push_back(t)voida.insert(a.end(), t)

Appends a copy oft.

Requires:ConstructibleAsElement<A, T, T>andTshall beCopyAssignable.Tshall beCopyConstructible.vector,list,deque,basic_stringa.push_back(rv)voida.insert(a.end(), t)

Appends a copy ofrv.

Requires:ConstructibleAsElement<A, T, T&&>andTshall beMoveAssignable.Tshall beMoveConstructible.vector,list,deque,basic_stringa.pop_front()voida.erase(a.begin())

Destroys the first element.

Requires:a.empty()shall befalse.list,deque,forward_lista.pop_back()void{ iterator tmp = a.end();

--tmp;

a.erase(tmp); }

Destroys the last element.

Requires:a.empty()shall befalse.vector,list,deque,basic_string

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

The associative containers meet all of the requirements of Allocator-aware containers (21.2.1 [container.requirements.general]), except for the containers

mapandmultimap, the requirements placed onvalue_typein Table 93 apply instead directly tokey_typeandmapped_type. [Note:For examplekey_typeandmapped_typeare sometimes required to beCopyAssignableeven though thevalue_type(pair<const key_type, mapped_type>) is notCopyAssignable. —end note]7 In Table 96,

Xdenotes an associative container class, a denotes a value ofX,a_uniqdenotes a value ofXwhenXsupports unique keys,a_eqdenotes a value ofXwhenXsupports multiple keys,udenotes an identifier,rdenotes an lvalue or a const rvalue of typeX,rvdenotes a non-const rvalue of typeX,iandjsatisfy input iterator requirements and refer to elements implicitly convertible tovalue_type,[i,j)denotes a valid range,pdenotes a valid const iterator toa,qdenotes a valid dereferenceable const iterator toa,[q1, q2)denotes a valid range of const iterators ina,ildesignates an object of typeinitializer_list<value_type>,tdenotes a value ofX::value_type,kdenotes a value ofX::key_typeandcdenotes a value of typeX::key_compare.Adenotes the storage allocator used byX, if any, orstd::allocator<X::value_type>otherwise, andmdenotes an allocator of a type convertible toA.

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

Table 96 — Associative container requirements (in addition to container) Expression Return type Assertion/note

pre-/post-conditionComplexity X::key_typeKeyRequires:KeyisCopyConstructibleandCopyAssignableDestructiblecompile time X::mapped_type(mapandmultimaponly)TRequires:TisDestructiblecompile time X(c)

X a(c);Requires:~~.~~ConstructibleAsElement<A, key_compare, key_compare>

key_compareisCopyConstructible.

Constructs an empty container.

Uses a copy ofcas a comparison object.constant X()

X a;Requires:~~.~~ConstructibleAsElement<A, key_compare, key_compare>

key_compareisDefaultConstructible.

Constructs an empty container.

UsesCompare()as a comparison object.constant X(i, j, c)

X a(i, j, c);Requires:~~.~~ConstructibleAsElement<A, key_compare, key_compare>

key_compareisCopyConstructible.value_typeshall be constructible from*i.

Constructs an empty container ans inserts elements from the range[i, j)into it; usescas a comparison object.NlogNin general (Nis the distance fromitoj); linear if[i, j)is sorted withvalue_comp()X(i, j)

X a(i, j);Requires:~~.~~ConstructibleAsElement<A, key_compare, key_compare>

value_typeshall be constructible from*i.key_compareisDefaultConstructible.

Same as above, but usesCompare()as a comparison object.same as above a = ilX&a = X(il);

return *this;

Requires:TisCopyConstructibleandCopyAssignable.

Assigns the range[il.begin(), il.end())intoa. All existing elements ofaare either assigned or destroyed.~~Same as~~.a = X(il)NlogNin general (Nisil.size()added to the existing size ofa); linear if[il.begin(), il.end())is sorted withvalue_comp()a_uniq.emplace(args)pair<iterator, bool>Requires:Tshall be constructible fromargs

inserts aTobjecttconstructed withstd::forward<Args>(args)...if and only if there is no element in the container with key equivalent to the key oft. Theboolcomponent 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.emplace(args)iteratorRequires:Tshall be constructible fromargs

inserts aTobjecttconstructed withstd::forward<Args>(args)...and returns the iterator pointing to the newly inserted element.logarithmic a_uniq.insert(t)pair<iterator, bool>Requires:Tshall beMoveConstructibleiftis a non-const rvalue expression, elseTshall beCopyConstructible.

insertstif and only if there is no element in the container with key equivalent to the key oft. Theboolcomponent 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)iteratorRequires:Tshall beMoveConstructibleiftis a non-const rvalue expression, elseTshall beCopyConstructible.

insertstand returns the iterator pointing to the newly inserted element. If a range containing elements equivalent totexists ina_eq,tis inserted at the end of that range.logarithmic a.insert(p, t)iteratorRequires:Tshall beMoveConstructibleiftis a non-const rvalue expression, elseTshall beCopyConstructible.

insertstif and only if there is no element with key equivalent to the key oftin containers with unique keys; always insertstin containers with equivalent keys; always returns the iterator pointing to the element with key equivalent to the key oft.tis inserted as close as possible to the position just prior top.logarithmic in general, but amortized constant if tis inserted right beforep.a.insert(i, j)voidRequires:Tshall be constructible from*i.

pre:i,jare not iterators intoa. 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 21.2.7 [unord.req]/9:

The unordered associative containers meet all of the requirements of Allocator-aware containers (21.2.1 [container.requirements.general]), except for the containers

unordered_mapandunordered_multimap, the requirements placed onvalue_typein Table 93 apply instead directly tokey_typeandmapped_type. [Note:For examplekey_typeandmapped_typeare sometimes required to beCopyAssignableeven though thevalue_type(pair<const key_type, mapped_type>) is notCopyAssignable. —end note]9 ...

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

Table 98 — Unordered associative container requirements (in addition to container) Expression Return type Assertion/note

pre-/post-conditionComplexity X::key_typeKeyRequires:Keyshall beCopyAssignableandCopyConstructibleDestructiblecompile time X::mapped_type(unordered_mapandunordered_multimaponly)TRequires:TisDestructiblecompile time X(n, hf, eq)

X a(n, hf, eq)XRequires:hasherandkey_equalareCopyConstructible. Constructs an empty container with at leastnbuckets, usinghfas the hash function andeqas the key equality predicate.O(N)X(n, hf)

X a(n, hf)XRequires:hasherisCopyConstructibleandkey_equalisDefaultConstructible. Constructs an empty container with at leastnbuckets, usinghfas the hash function andkey_equal()as the key equality predicate.O(N)X(n)

X a(n)XRequires:hasherandkey_equalareDefaultConstructible. Constructs an empty container with at leastnbuckets, usinghasher()as the hash function andkey_equal()as the key equality predicate.O(N)X()

X aXRequires:hasherandkey_equalareDefaultConstructible. Constructs an empty container an unspecified number of buckets, usinghasher()as the hash function andkey_equal()as the key equality predicate.constant X(i, j, n, hf, eq)

X a(i, j, n, hf, eq)XRequires:value_typeis constructible from*i.hasherandkey_equalareCopyConstructible.

Constructs an empty container with at leastnbuckets, usinghfas the hash function andeqas the key equality predicate, and inserts elements from[i, j)into it.Average case O(N)(Nisdistance(i, j)), worst caseO(N^{2})X(i, j, n, hf)

X a(i, j, n, hf)XRequires:value_typeis constructible from*i.hasherisCopyConstructibleandkey_equalisDefaultConstructible.

Constructs an empty container with at leastnbuckets, usinghfas the hash function andkey_equal()as the key equality predicate, and inserts elements from[i, j)into it.Average case O(N)(Nisdistance(i, j)), worst caseO(N^{2})X(i, j, n)

X a(i, j, n)XRequires:value_typeis constructible from*i.hasherandkey_equalareDefaultConstructible.

Constructs an empty container with at leastnbuckets, usinghasher()as the hash function andkey_equal()as the key equality predicate, and inserts elements from[i, j)into it.Average case O(N)(Nisdistance(i, j)), worst caseO(N^{2})X(i, j)

X a(i, j)XRequires:value_typeis constructible from*i.hasherandkey_equalareDefaultConstructible.

Constructs an empty container with an unspecified number of buckets, usinghasher()as the hash function andkey_equal()as the key equality predicate, and inserts elements from[i, j)into it.Average case O(N)(Nisdistance(i, j)), worst caseO(N^{2})X(b)

X a(b)XCopy constructor. In addition to the ~~contained elements~~requirements of Table 93 (21.2.1 [container.requirements.general]), copies the hash function, predicate, and maximum load factor.Average case linear in b.size(), worst case quadratic.a = bX&Copy assignment operator. In addition to the ~~contained elements~~requirements of Table 93 (21.2.1 [container.requirements.general]), copies the hash function, predicate, and maximum load factor.Average case linear in b.size(), worst case quadratic.a = ilX&a = X(il); return *this;

Requires:TisCopyConstructibleandCopyAssignable.

Assigns the range[il.begin(), il.end())intoa. All existing elements ofaare either assigned or destroyed.Average case linear in il.size(), worst case quadratic.a_uniq.emplace(args)pair<iterator, bool>Requires:Tshall be constructible fromargs

inserts aTobjecttconstructed withstd::forward<Args>(args)...if and only if there is no element in the container with key equivalent to the key oft. Theboolcomponent 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.Average case O(1), worst case O( a_uniq.size()).a_eq.emplace(args)iteratorRequires:Tshall be constructible fromargs

inserts aTobjecttconstructed withstd::forward<Args>(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)iteratorRequires:Tshall be constructible fromargs

equivalent toa.emplace( std::forward<Args>(args)...). Return value is an iterator pointing to the element with the key equivalent to the newly inserted element. Theconst_iterator pis 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:Tshall beMoveConstructibleiftis a non-const rvalue expression, elseTshall beCopyConstructible.

Insertstif and only if there is no element in the container with key equivalent to the key oft. Theboolcomponent of the returned pair indicates whether the insertion takes place, and the iterator component points to the element with key equivalent to the key oft.Average case O(1), worst case O( a_uniq.size()).a_eq.insert(t)iteratorRequires:Tshall beMoveConstructibleiftis a non-const rvalue expression, elseTshall beCopyConstructible.

Insertst, and returns an iterator pointing to the newly inserted element.Average case O(1), worst case O( a_uniq.size()).a.insert(q, t)iteratorRequires:Tshall beMoveConstructibleiftis a non-const rvalue expression, elseTshall beCopyConstructible.

Equivalent toa.insert(t). Return value is an iterator pointing to the element with the key equivalent to that oft. The iteratorqis 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)voidRequires:Tshall be constructible from*i.

Pre:iandjare not iterators ina. Equivalent toa.insert(t)for each element in[i,j).Average case O( N), whereNisdistance(i, j). Worst case O(N * a.size()).

Change 21.3.9 [forwardlist]/2:

2 A

forward_listsatisfies all of the requirements of a container (table 91), except that thesize()member function is not provided. Aforward_listalso satisfies all of the requirements of an allocator-aware container (table 93). Andforward_listprovides theassignmember 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 onforward_listthat are not described in that table or for operations where there is additional semantic information.

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

void clear();23

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

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

Change 21.3.11.3 [vector.capacity]/13:

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

Requires:Tshall beCopyConstructible. Ifvalue_typehas a move constructor, that constructor shall not throw any exceptions.

In 21.5.6 [unord.set] and 21.5.7 [unord.multiset] substitute
"`Key`" for "`Value`".

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