Working Draft, Standard for Programming Language C++ (N4713, 2017 year)

static locale::id id;

protected:

~money_put();

virtual iter_type do_put(iter_type, bool, ios_base&, char_type fill,

long double units) const;

virtual iter_type do_put(iter_type, bool, ios_base&, char_type fill,

const string_type& digits) const;

};

}

25.4.6.2.1

money_put members

[locale.money.put.members]

iter_type put(iter_type s, bool intl, ios_base& f, char_type fill, long double quant) const;

iter_type put(iter_type s, bool intl, ios_base& f, char_type fill, const string_type& quant) const;

Returns: do_put(s, intl, f, loc, quant).

25.4.6.2.2

money_put virtual functions

[locale.money.put.virtuals]

iter_type do_put(iter_type s, bool intl, ios_base& str,

char_type fill, long double units) const;

iter_type do_put(iter_type s, bool intl, ios_base& str,

char_type fill, const string_type& digits) const;

Effects: Writes characters to s according to the format specified by a moneypunct<charT, Intl> facet

reference mp and the character mapping specified by a ctype<charT> facet reference ct obtained from

the locale returned by str.getloc(), and str.flags(). The argument units is transformed into a

sequence of wide characters as if by

ct.widen(buf1, buf1 + sprintf(buf1, "%.0Lf", units), buf2)

for character buffers buf1 and buf2. If the first character in digits or buf2 is equal to ct.widen(’-’),

then the pattern used for formatting is the result of mp.neg_format(); otherwise the pattern is the result

of mp.pos_format(). Digit characters are written, interspersed with any thousands separators and

decimal point specified by the format, in the order they appear (after the optional leading minus sign) in

digits or buf2. In digits, only the optional leading minus sign and the immediately subsequent digit

characters (as classified according to ct) are used; any trailing characters (including digits appearing

after a non-digit character) are ignored. Calls str.width(0).

Remarks: The currency symbol is generated if and only if (str.flags() & str.showbase) is nonzero.

If the number of characters generated for the specified format is less than the value returned by

str.width() on entry to the function, then copies of fill are inserted as necessary to pad to the speci-

fied width. For the value af equal to (str.flags() & str.adjustfield), if (af == str.internal)

is true, the fill characters are placed where none or space appears in the formatting pattern; otherwise

(af == str.left) is true, they are placed after the other characters; otherwise, they are placed

before the other characters. [ Note: It is possible, with some combinations of format patterns and flag

values, to produce output that cannot be parsed using num_get<>::get.

— end note ]

Returns: An iterator pointing immediately after the last character produced.

25.4.6.3

Class template moneypunct

[locale.moneypunct]

namespace std {

class money_base {

public:

enum part { none, space, symbol, sign, value };

struct pattern { char field[4]; };

};

template<class charT, bool International = false>

class moneypunct : public locale::facet, public money_base {

public:

using char_type

= charT;

using string_type = basic_string<charT>;

explicit moneypunct(size_t refs = 0);

§ 25.4.6.3

742

charT

decimal_point() const;

charT

thousands_sep() const;

string

grouping()

const;

string_type

curr_symbol()

const;

string_type

positive_sign() const;

string_type

negative_sign() const;

int

frac_digits() const;

pattern

pos_format()

const;

pattern

neg_format()

const;

static locale::id id;

static const bool intl = International;

protected:

~moneypunct();

virtual charT

do_decimal_point() const;

virtual charT

do_thousands_sep() const;

virtual string

do_grouping()

const;

virtual string_type

do_curr_symbol()

const;

virtual string_type

do_positive_sign() const;

virtual string_type

do_negative_sign() const;

virtual int

do_frac_digits() const;

virtual pattern

do_pos_format()

const;

virtual pattern

do_neg_format()

const;

};

}

The moneypunct<> facet defines monetary formatting parameters used by money_get<> and money_put<>. A

monetary format is a sequence of four components, specified by a pattern value p, such that the part value

static_cast<part>(p.field[i]) determines the ith component of the format²⁵³ In the field member

of a pattern object, each value symbol, sign, value, and either space or none appears exactly once. The

value none, if present, is not first; the value space, if present, is neither first nor last.

Where none or space appears, white space is permitted in the format, except where none appears at the end,

in which case no white space is permitted. The value space indicates that at least one space is required at

that position. Where symbol appears, the sequence of characters returned by curr_symbol() is permitted,

and can be required. Where sign appears, the first (if any) of the sequence of characters returned by

positive_sign() or negative_sign() (respectively as the monetary value is non-negative or negative) is

required. Any remaining characters of the sign sequence are required after all other format components.

Where value appears, the absolute numeric monetary value is required.

The format of the numeric monetary value is a decimal number:

value ::= units [ decimal-point [ digits ]] |

decimal-point digits

if frac_digits() returns a positive value, or

value ::= units

otherwise. The symbol decimal-point indicates the character returned by decimal_point(). The other

symbols are defined as follows:

units ::= digits [ thousands-sep units ]

digits ::= adigit [ digits ]

In the syntax specification, the symbol adigit is any of the values ct.widen(c) for c in the range ’0’

through ’9’, inclusive, and ct is a reference of type const ctype<charT>& obtained as described in the

definitions of money_get<> and money_put<>. The symbol thousands-sep is the character returned by

thousands_sep(). The space character used is the value ct.widen(’ ’). White space characters are those

characters c for which ci.is(space, c) returns true. The number of digits required after the decimal point

(if any) is exactly the value returned by frac_digits().

The placement of thousands-separator characters (if any) is determined by the value returned by grouping(),

defined identically as the member numpunct<>::do_grouping().

253) An array of char, rather than an array of part, is specified for pattern::field purely for efficiency.

§ 25.4.6.3

743

25.4.6.3.1

moneypunct members

[locale.moneypunct.members]

charT

decimal_point() const;

charT

thousands_sep() const;

string

grouping()

const;

string_type

curr_symbol()

const;

string_type

positive_sign() const;

string_type

negative_sign() const;

int

frac_digits() const;

pattern

pos_format()

const;

pattern

neg_format()

const;

Each of these functions F returns the result of calling the corresponding virtual member function do_F ().

25.4.6.3.2

moneypunct virtual functions

[locale.moneypunct.virtuals]

charT do_decimal_point() const;

Returns: The radix separator to use in case do_frac_digits() is greater than zero.²⁵⁴

charT do_thousands_sep() const;

Returns: The digit group separator to use in case do_grouping() specifies a digit grouping pattern.²⁵⁵

string do_grouping() const;

Returns: A pattern defined identically as, but not necessarily equal to, the result of numpunct<charT>::

do_grouping().²⁵⁶

string_type do_curr_symbol() const;

Returns: A string to use as the currency identifier symbol. [ Note: For specializations where the second

template parameter is true, this is typically four characters long: a three-letter code as specified by

ISO 4217 followed by a space.

— end note ]

string_type do_positive_sign() const;

string_type do_negative_sign() const;

Returns: do_positive_sign() returns the string to use to indicate a positive monetary value;²⁵⁷

do_negative_sign() returns the string to use to indicate a negative value.

int do_frac_digits() const;

Returns: The number of digits after the decimal radix separator, if any.²⁵⁸

pattern do_pos_format() const;

pattern do_neg_format() const;

Returns: The specializations required in Table 70 (25.3.1.1.1), namely moneypunct<char>, moneypunct<

wchar_t>, moneypunct<char, true>, and moneypunct<wchar_t, true>, return an object of type

pattern initialized to { symbol, sign, none, value }.²⁵⁹

25.4.6.4

Class template moneypunct_byname

[locale.moneypunct.byname]

namespace std {

template<class charT, bool Intl = false>

class moneypunct_byname : public moneypunct<charT, Intl> {

public:

using pattern

= money_base::pattern;

using string_type = basic_string<charT>;

explicit moneypunct_byname(const char*, size_t refs = 0);

explicit moneypunct_byname(const string&, size_t refs = 0);

254) In common U.S. locales this is ’.’.

255) In common U.S. locales this is ’,’.

256) To specify grouping by 3s, the value is "\003" not "3".

257) This is usually the empty string.

258) In common U.S. locales, this is 2.

259) Note that the international symbol returned by do_curr_symbol() usually contains a space, itself; for example, "USD ".

§ 25.4.6.4

744

protected:

~moneypunct_byname();

};

}

25.4.7

The message retrieval category

[category.messages]

Class messages<charT> implements retrieval of strings from message catalogs.

25.4.7.1

Class template messages

[locale.messages]

namespace std {

class messages_base {

public:

using catalog = unspecified signed integer type ;

};

template<class charT>

class messages : public locale::facet, public messages_base {

public:

using char_type

= charT;

using string_type = basic_string<charT>;

explicit messages(size_t refs = 0);

catalog open(const basic_string<char>& fn, const locale&) const;

string_type get(catalog c, int set, int msgid,

const string_type& dfault) const;

void close(catalog c) const;

static locale::id id;

protected:

~messages();

virtual catalog do_open(const basic_string<char>&, const locale&)

const;

virtual string_type do_get(catalog, int set, int msgid,

const string_type& dfault) const;

virtual void do_close(catalog) const;

};

}

Values of type messages_base::catalog usable as arguments to members get and close can be obtained

only by calling member open.

25.4.7.1.1

messages members

[locale.messages.members]

catalog open(const basic_string<char>& name, const locale& loc) const;

Returns: do_open(name, loc).

string_type get(catalog cat, int set, int msgid, const string_type& dfault) const;

Returns: do_get(cat, set, msgid, dfault).

void close(catalog cat) const;

Effects: Calls do_close(cat).

25.4.7.1.2

messages virtual functions

[locale.messages.virtuals]

catalog do_open(const basic_string<char>& name, const locale& loc) const;

Returns: A value that may be passed to get() to retrieve a message from the message catalog identified

by the string name according to an implementation-defined mapping. The result can be used until it is

passed to close().

Returns a value less than 0 if no such catalog can be opened.

Remarks: The locale argument loc is used for character set code conversion when retrieving messages,

if needed.

§ 25.4.7.1.2

745

string_type do_get(catalog cat, int set, int msgid, const string_type& dfault) const;

Requires: cat shall be a catalog obtained from open() and not yet closed.

Returns: A message identified by arguments set, msgid, and dfault, according to an implementation-

defined mapping. If no such message can be found, returns dfault.

void do_close(catalog cat) const;

Requires: cat shall be a catalog obtained from open() and not yet closed.

Effects: Releases unspecified resources associated with cat.

Remarks: The limit on such resources, if any, is implementation-defined.

25.4.7.2

Class template messages_byname

[locale.messages.byname]

namespace std {

template<class charT>

class messages_byname : public messages<charT> {

public:

using catalog

= messages_base::catalog;

using string_type = basic_string<charT>;

explicit messages_byname(const char*, size_t refs = 0);

explicit messages_byname(const string&, size_t refs = 0);

protected:

~messages_byname();

};

}

25.4.8

Program-defined facets

[facets.examples]

A C++ program may define facets to be added to a locale and used identically as the built-in facets. To

create a new facet interface, C++ programs simply derive from locale::facet a class containing a static

member: static locale::id id.

[ Note: The locale member function templates verify its type and storage class.

— end note ]

[ Example: Traditional global localization is still easy:

#include <iostream>

#include <locale>

int main(int argc, char** argv) {

using namespace std;

locale::global(locale(""));

// set the global locale

// imbue it on all the std streams

cin.imbue(locale());

cout.imbue(locale());

cerr.imbue(locale());

wcin.imbue(locale());

wcout.imbue(locale());

wcerr.imbue(locale());

return MyObject(argc, argv).doit();

}

— end example ]

[ Example: Greater flexibility is possible:

#include <iostream>

#include <locale>

int main() {

using namespace std;

cin.imbue(locale(""));

// the user’s preferred locale

cout.imbue(locale::classic());

double f;

while (cin >> f) cout << f << endl;

§ 25.4.8

746

return (cin.fail() != 0);

}

In a European locale, with input 3.456,78, output is 3456.78.

— end example ]

This can be important even for simple programs, which may need to write a data file in a fixed format,

regardless of a user’s preference.

[ Example: Here is an example of the use of locales in a library interface.

// file: Date.h

#include <iosfwd>

#include <string>

#include <locale>

class Date {

public:

Date(unsigned day, unsigned month, unsigned year);

std::string asString(const std::locale& = std::locale());

};

std::istream& operator>>(std::istream& s, Date& d);

std::ostream& operator<<(std::ostream& s, Date d);

This example illustrates two architectural uses of class locale.

The first is as a default argument in Date::asString(), where the default is the global (presumably

user-preferred) locale.

The second is in the operators << and >>, where a locale “hitchhikes” on another object, in this case a stream,

to the point where it is needed.

// file: Date.C

#include "Date"

// includes <ctime>

#include <sstream>

std::string Date::asString(const std::locale& l) {

using namespace std;

ostringstream s; s.imbue(l);

s << *this; return s.str();

}

std::istream& operator>>(std::istream& s, Date& d) {

using namespace std;

istream::sentry cerberos(s);

if (cerberos) {

ios_base::iostate err = goodbit;

struct tm t;

use_facet<time_get<char>>(s.getloc()).get_date(s, 0, s, err, &t);

if (!err) d = Date(t.tm_day, t.tm_mon + 1, t.tm_year + 1900);

s.setstate(err);

}

return s;

}

— end example ]

A locale object may be extended with a new facet simply by constructing it with an instance of a class

derived from locale::facet. The only member a C++ program must define is the static member id, which

identifies your class interface as a new facet.

[ Example: Classifying Japanese characters:

// file: <jctype>

#include <locale>

namespace My {

using namespace std;

class JCtype : public locale::facet {

public:

static locale::id id;

// required for use as a new locale facet

bool is_kanji (wchar_t c) const;

§ 25.4.8

747

JCtype() { }

protected:

~JCtype() { }

};

}

// file: filt.C

#include <iostream>

#include <locale>

#include "jctype"

// above

std::locale::id My::JCtype::id; // the static JCtype member declared above.

int main() {

using namespace std;

using wctype = ctype<wchar_t>;

locale loc(locale(""),

// the user’s preferred locale ...

new My::JCtype);

// and a new feature ...

wchar_t c = use_facet<wctype>(loc).widen(’!’);

if (!use_facet<My::JCtype>(loc).is_kanji(c))

cout << "no it isn’t!" << endl;

}

The new facet is used exactly like the built-in facets.

— end example ]

[Example: Replacing an existing facet is even easier. The code does not define a member id because it is

reusing the numpunct<charT> facet interface:

// file: my_bool.C

#include <iostream>

#include <locale>

#include <string>

namespace My {

using namespace std;

using cnumpunct = numpunct_byname<char>;

class BoolNames : public cnumpunct {

protected:

string do_truename() const { return "Oui Oui!"; }

string do_falsename() const { return "Mais Non!"; }

~BoolNames() { }

public:

BoolNames(const char* name) : cnumpunct(name) { }

};

}

int main(int argc, char** argv) {

using namespace std;

// make the user’s preferred locale, except for...

locale loc(locale(""), new My::BoolNames(""));

cout.imbue(loc);

cout << boolalpha << "Any arguments today? " << (argc

endl;

}

— end example ]

25.5

C library locales

[c.locales]

25.5.1

Header <clocale> synopsis

[clocale.syn]

namespace std {

struct lconv;

char* setlocale(int category, const char* locale);

lconv* localeconv();

}

§ 25.5.1

748

#define NULL see 21.2.3

#define LC_ALL see below

#define LC_COLLATE see below

#define LC_CTYPE see below

#define LC_MONETARY see below

#define LC_NUMERIC see below

#define LC_TIME see below

The contents and meaning of the header <clocale> are the same as the C standard library header <locale.h>.

Calls to the function setlocale may introduce a data race (20.5.5.9) with other calls to setlocale or with

calls to the functions listed in Table 81.

See also: ISO C 7.11

Table 81 — Potential setlocale data races

fprintf isprint iswdigit localeconv tolower

fscanf ispunct iswgraph mblen

toupper

isalnum isspace iswlower mbstowcs

towlower

isalpha isupper iswprint mbtowc

towupper

isblank iswalnum iswpunct setlocale

wcscoll

iscntrl iswalpha iswspace strcoll

wcstod

isdigit iswblank iswupper strerror

wcstombs

isgraph iswcntrl iswxdigit strtod

wcsxfrm

islower iswctype isxdigit strxfrm

wctomb

§ 25.5.1

749

Containers library

[containers]

26.1

General

[containers.general]

This Clause describes components that C++ programs may use to organize collections of information.

The following subclauses describe container requirements, and components for sequence containers and

associative containers, as summarized in Table 82.

Table 82 — Containers library summary

Subclause

Header(s)

26.2

Requirements

26.3

Sequence containers

<array>

<deque>

<forward_list>

<list>

26.4

Associative containers

<map>

<set>

26.5

Unordered associative containers

<unordered_map>

<unordered_set>

26.6

Container adaptors

<queue>

<stack>

26.2

Container requirements

[container.requirements]

26.2.1

General container requirements

[container.requirements.general]

Containers are objects that store other objects. They control allocation and deallocation of these objects

through constructors, destructors, insert and erase operations.

All of the complexity requirements in this Clause are stated solely in terms of the number of operations on

the contained objects. [ Example: The copy constructor of type vector<vector<int>> has linear complexity,

even though the complexity of copying each contained vector<int> is itself linear.

— end example ]

For the components affected by this subclause that declare an allocator_type, objects stored in these compo-

nents shall be constructed using the function allocator_traits<allocator_type>::rebind_traits<U>::

construct and destroyed using the function allocator_traits<allocator_type>::rebind_traits<U>::

destroy (23.10.9.2), where U is either allocator_type::value_type or an internal type used by the

container. These functions are called only for the container’s element type, not for internal types used by

the container. [ Note: This means, for example, that a node-based container might need to construct nodes

containing aligned buffers and call construct to place the element into the buffer.

— end note ]

In Tables 83, 84, and 85 X denotes a container class containing objects of type T, a and b denote values of

type X, u denotes an identifier, r denotes a non-const value of type X, and rv denotes a non-const rvalue of

type X.

Table 83 — Container requirements

Expression

Return type

Operational

Assertion/note

Complexity

semantics

pre-/post-condition

X::value_-

Requires: T is

compile time

type

Erasable from X

(see 26.2.1, below)

X::reference T&

compile time

X::const_-

const T&

compile time

reference

§ 26.2.1

750

Table 83

— Container requirements (continued)

Expression

Return type

Operational

Assertion/note

Complexity

semantics

pre-/post-condition

X::iterator

iterator type

any iterator category

compile time

whose value

that meets the

type is T

forward iterator

requirements.

convertible to

X::const_iterator.

X::const_-

constant

any iterator category

compile time

iterator

iterator type

that meets the

whose value

forward iterator

type is T

requirements.

X::dif-

signed integer

is identical to the

compile time

ference_type

type

difference type of

X::iterator and

X::const_iterator

X::size_type

unsigned

size_type can

compile time

integer type

represent any

non-negative value of

difference_type

X u;

Postconditions:

constant

u.empty()

X()

Postconditions:

constant

X().empty()

X(a)

Requires: T is

linear

CopyInsertable into

X (see below).

Postconditions: a ==

X(a).

X u(a);

Requires: T is

linear

X u = a;

CopyInsertable into

X (see below).

Postconditions: u ==

X u(rv);

Postconditions: u

(Note B)

X u = rv;

shall be equal to the

value that rv had

before this

construction

a = rv

All existing elements

a shall be equal to

linear

of a are either move

the value that rv had

assigned to or

before this

destroyed

assignment

(&a)->~X()

void

the destructor is

linear

applied to every

element of a; any

memory obtained is

deallocated.

a.begin()

iterator;

constant

const_-

iterator for

constant a

a.end()

iterator;

constant

const_-

iterator for

constant a

26.2.1

751

Table 83

— Container requirements (continued)

Expression

Return type

Operational

Assertion/note

Complexity

semantics

pre-/post-condition

a.cbegin()

const_-

const_cast<X

constant

iterator

const&>(a)

.begin();

a.cend()

const_-

const_cast<X

constant

iterator

const&>(a).end();

a == b

convertible to

== is an equivalence

Requires: T is

Constant if

bool

relation.

EqualityCompara-

a.size() !=

equal(a.begin(),

ble

b.size(),

a.end(),

linear

b.begin(),

otherwise

b.end())

a != b

convertible to

Equivalent to !(a ==

linear

bool

a.swap(b)

void

exchanges the

(Note A)

contents of a and b

swap(a, b)

void

a.swap(b)

(Note A)

r = a

Postconditions: r ==

linear

a.size()

size_type

distance(

constant

a.begin(),

a.end())

a.max_size()

size_type

distance(begin(),

constant

end()) for the largest

possible container

a.empty()

convertible to

a.begin() ==

constant

bool

a.end()

Those entries marked “(Note A)” or “(Note B)” have linear complexity for array and have constant complexity

for all other standard containers. [ Note: The algorithm equal() is defined in Clause 28.

— end note ]

The member function size() returns the number of elements in the container. The number of elements is

defined by the rules of constructors, inserts, and erases.

begin() returns an iterator referring to the first element in the container. end() returns an iterator which is

the past-the-end value for the container. If the container is empty, then begin() == end().

In the expressions

i == j

i != j

i < j

i <= j

i >= j

i > j

i - j

where i and j denote objects of a container’s iterator type, either or both may be replaced by an object of

the container’s const_iterator type referring to the same element with no change in semantics.

Unless otherwise specified, all containers defined in this clause obtain memory using an allocator (see 20.5.3.5).

[Note: In particular, containers and iterators do not store references to allocated elements other than

through the allocator’s pointer type, i.e., as objects of type P or pointer_traits<P>::template re-

bind<unspecified >, where P is allocator_traits<allocator_type>::pointer.

— end note ] Copy

constructors for these container types obtain an allocator by calling allocator_traits<allocator_-

type>::select_on_container_copy_construction on the allocator belonging to the container being copied.

Move constructors obtain an allocator by move construction from the allocator belonging to the container

being moved. Such move construction of the allocator shall not exit via an exception. All other constructors

§ 26.2.1

752

for these container types take a const allocator_type& argument.

[Note: If an invocation of a con-

structor uses the default value of an optional allocator argument, then the Allocator type must support

value-initialization.

— end note ] A copy of this allocator is used for any memory allocation and element

construction performed, by these constructors and by all member functions, during the lifetime of each

container object or until the allocator is replaced. The allocator may be replaced only via assignment or

swap(). Allocator replacement is performed by copy assignment, move assignment, or swapping of the alloca-

tor only if allocator_traits<allocator_type>::propagate_on_container_copy_assignment::value,

allocator_traits<allocator_type>::propagate_on_container_move_assignment::value, or alloca-

tor_traits<allocator_type>::propagate_on_container_swap::value is true within the implementa-

tion of the corresponding container operation. In all container types defined in this Clause, the member

get_allocator() returns a copy of the allocator used to construct the container or, if that allocator has

been replaced, a copy of the most recent replacement.

The expression a.swap(b), for containers a and b of a standard container type other than array, shall

exchange the values of a and b without invoking any move, copy, or swap operations on the individual container

elements. Lvalues of any Compare, Pred, or Hash types belonging to a and b shall be swappable and shall be

exchanged by calling swap as described in 20.5.3.2. If allocator_traits<allocator_type>::propagate_-

on_container_swap::value is true, then lvalues of type allocator_type shall be swappable and the

allocators of a and b shall also be exchanged by calling swap as described in 20.5.3.2. Otherwise, the

allocators shall not be swapped, and the behavior is undefined unless a.get_allocator() == b.get_-

allocator(). Every iterator referring to an element in one container before the swap shall refer to the same

element in the other container after the swap. It is unspecified whether an iterator with value a.end() before

the swap will have value b.end() after the swap.

If the iterator type of a container belongs to the bidirectional or random access iterator categories (27.2), the

container is called reversible and satisfies the additional requirements in Table 84.

Table 84 — Reversible container requirements

Expression

Return type

Assertion/note

Complexity

pre-/post-condition

X::reverse_- iterator type whose value type is reverse_iterator<iterator> compile time

iterator

X::const_-

constant iterator type whose

reverse_iterator<const_-

compile time

reverse_-

value type is T

iterator>

iterator

a.rbegin()

reverse_iterator;

reverse_iterator(end())

constant

const_reverse_iterator for

constant a

a.rend()

reverse_iterator;

reverse_iterator(begin())

constant

const_reverse_iterator for

constant a

a.crbegin()

const_reverse_iterator

const_cast<X

constant

const&>(a).rbegin()

a.crend()

const_reverse_iterator

const_cast<X

constant

const&>(a).rend()

Unless otherwise specified (see 26.2.6.1, 26.2.7.1, 26.3.8.4, and 26.3.11.5) all container types defined in this

Clause meet the following additional requirements:

(11.1)

—

if an exception is thrown by an insert() or emplace() function while inserting a single element, that

function has no effects.

(11.2)

—

if an exception is thrown by a push_back(), push_front(), emplace_back(), or emplace_front()

function, that function has no effects.

(11.3)

—

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

(11.4)

—

no copy constructor or assignment operator of a returned iterator throws an exception.

(11.5)

—

no swap() function throws an exception.

§ 26.2.1

753

(11.6)

—

no swap() function invalidates any references, pointers, or iterators referring to the elements of the

containers being swapped.

[Note: The end() iterator does not refer to any element, so it may be

invalidated.

— end note ]

Unless otherwise specified (either explicitly or by defining a function in terms of other functions), invoking a

container member function or passing a container as an argument to a library function shall not invalidate

iterators to, or change the values of, objects within that container.

A contiguous container is a container that supports random access iterators (27.2.7) and whose member

types iterator and const_iterator are contiguous iterators (27.2.1).

Table 85 lists operations that are provided for some types of containers but not others. Those containers for

which the listed operations are provided shall implement the semantics described in Table 85 unless otherwise

stated.

Table 85 — Optional container operations

Expression

Return type

Operational

Assertion/note

Complexity

semantics

pre-/post-condition

a < b

convertible to

lexicographical_-

Requires: < is defined

linear

bool

compare(

for values of T. < is a

a.begin(),

total ordering

a.end(),

relationship.

b.begin(),

b.end())

a > b

convertible to

b < a

linear

bool

a <= b

convertible to

!(a > b)

linear

bool

a >= b

convertible to

!(a < b)

linear

bool

[ Note: The algorithm lexicographical_compare() is defined in Clause 28.

— end note ]

All of the containers defined in this Clause and in 24.3.2 except array meet the additional requirements of

an allocator-aware container, as described in Table 86.

Given an allocator type A and given a container type X having a value_type identical to T and an allocator_-

type identical to allocator_traits<A>::rebind_alloc<T> and given an lvalue m of type A, a pointer p of

type T*, an expression v of type (possibly const) T, and an rvalue rv of type T, the following terms are

defined. If X is not allocator-aware, the terms below are defined as if A were allocator<T> — no allocator

object needs to be created and user specializations of allocator<T> are not instantiated:

—

(15.1)

T is DefaultInsertable into X means that the following expression is well-formed:

allocator_traits<A>::construct(m, p)

(15.2)

—

An element of X is default-inserted if it is initialized by evaluation of the expression

allocator_traits<A>::construct(m, p)

where p is the address of the uninitialized storage for the element allocated within X.

(15.3)

—

T is MoveInsertable into X means that the following expression is well-formed:

allocator_traits<A>::construct(m, p, rv)

and its evaluation causes the following postcondition to hold: The value of *p is equivalent to the value

of rv before the evaluation. [ Note: rv remains a valid object. Its state is unspecified — end note ]

(15.4)

—

T is CopyInsertable into X means that, in addition to T being MoveInsertable into X, the following

expression is well-formed:

allocator_traits<A>::construct(m, p, v)

and its evaluation causes the following postcondition to hold: The value of v is unchanged and is

equivalent to *p.

§ 26.2.1

754

(15.5)

—

T is EmplaceConstructible into X from args, for zero or more arguments args, means that the

following expression is well-formed:

allocator_traits<A>::construct(m, p, args)

(15.6)

—

T is Erasable from X means that the following expression is well-formed:

allocator_traits<A>::destroy(m, p)

[Note: A container calls allocator_traits<A>::construct(m, p, args) to construct an element at p

using args, with m == get_allocator(). The default construct in allocator will call ::new((void*)p)

T(args), but specialized allocators may choose a different definition.

— end note ]

In Table 86, X denotes an allocator-aware container class with a value_type of T using allocator of type A, u

denotes a variable, a and b denote non-const lvalues of type X, t denotes an lvalue or a const rvalue of type

X, rv denotes a non-const rvalue of type X, and m is a value of type A.

Table 86 — Allocator-aware container requirements

Expression

Return type

Assertion/note

Complexity

pre-/post-condition

allocator_-

Requires:

compile time

type

allocator_type::value_type

is the same as X::value_type.

get_-

constant

allocator()

X()

Requires: A is

constant

X u;

DefaultConstructible.

Postconditions: u.empty()

returns true,

u.get_allocator() == A()

X(m)

Postconditions: u.empty()

constant

returns true,

X u(m);

u.get_allocator() == m

X(t, m)

Requires: T is CopyInsertable

linear

X u(t, m);

into X.

Postconditions: u == t,

u.get_allocator() == m

X(rv)

Postconditions: u shall have the

constant

X u(rv);

same elements as rv had before

this construction; the value of

u.get_allocator() shall be

the same as the value of

rv.get_allocator() before

this construction.

X(rv, m)

Requires: T is MoveInsertable

constant if m

X u(rv, m);

into X.

== rv.get_-

Postconditions: u shall have the

allocator(),

same elements, or copies of the

otherwise

elements, that rv had before

linear

this construction,

u.get_allocator() == m

a = t

Requires: T is CopyInsertable

linear

into X and CopyAssignable.

Postconditions: a == t

§ 26.2.1

755

Table 86 — Allocator-aware container requirements (continued)

Expression

Return type

Assertion/note

Complexity

pre-/post-condition

a = rv

Requires: If allocator_-

linear

traits<allocator_type>

::propagate_on_container_-

move_assignment::value is

false, T is MoveInsertable

into X and MoveAssignable. All

existing elements of a are either

move assigned to or destroyed.

Postconditions: a shall be equal

to the value that rv had before

this assignment.

a.swap(b)

void

exchanges the contents of a and constant

The behavior of certain container member functions and deduction guides depends on whether types qualify

as input iterators or allocators. The extent to which an implementation determines that a type cannot be an

input iterator is unspecified, except that as a minimum integral types shall not qualify as input iterators.

Likewise, the extent to which an implementation determines that a type cannot be an allocator is unspecified,

except that as a minimum a type A shall not qualify as an allocator unless it satisfies both of the following

conditions:

(17.1)

—

The qualified-id A::value_type is valid and denotes a type (17.9.2).

(17.2)

—

The expression declval<A&>().allocate(size_t{}) is well-formed when treated as an unevaluated

operand.

26.2.2

Container data races

[container.requirements.dataraces]

For purposes of avoiding data races (20.5.5.9), implementations shall consider the following functions to be

const: begin, end, rbegin, rend, front, back, data, find, lower_bound, upper_bound, equal_range, at

and, except in associative or unordered associative containers, operator[].

Notwithstanding 20.5.5.9, implementations are required to avoid data races when the contents of the contained

object in different elements in the same container, excepting vector<bool>, are modified concurrently.

[ Note: For a vector<int> x with a size greater than one, x[1] = 5 and *x.begin() = 10 can be executed

concurrently without a data race, but x[0] = 5 and *x.begin() = 10 executed concurrently may result in

a data race. As an exception to the general rule, for a vector<bool> y, y[0] = true may race with y[1]

= true.

— end note ]

26.2.3

Sequence containers

[sequence.reqmts]

A sequence container organizes a finite set of objects, all of the same type, into a strictly linear arrangement.

The library provides four basic kinds of sequence containers: vector, forward_list, list, and deque. In

addition, array is provided as a sequence container which provides limited sequence operations because it

has a fixed number of elements. The library also provides container adaptors that make it easy to construct

abstract data types, such as stacks or queues, out of the basic sequence container kinds (or out of other

kinds of sequence containers that the user might define).

The sequence containers offer the programmer different complexity trade-offs and should be used accordingly.

vector or array is the type of sequence container that should be used by default. list or forward_list

should be used when there are frequent insertions and deletions from the middle of the sequence. deque is

the data structure of choice when most insertions and deletions take place at the beginning or at the end of

the sequence.

In Tables 87 and 88, X denotes a sequence container class, a denotes a value of type X containing elements of

type T, u denotes the name of a variable being declared, A denotes X::allocator_type if the qualified-id

X::allocator_type is valid and denotes a type (17.9.2) and allocator<T> if it doesn’t, i and j denote

iterators satisfying input iterator requirements and refer to elements implicitly convertible to value_type,

§ 26.2.3

756

[i, j) denotes a valid range, il designates an object of type initializer_list<value_type>, n denotes

a value of type X::size_type, p denotes a valid constant iterator to a, q denotes a valid dereferenceable

constant iterator to a, [q1, q2) denotes a valid range of constant iterators in a, t denotes an lvalue or

a const rvalue of X::value_type, and rv denotes a non-const rvalue of X::value_type. Args denotes a

template parameter pack; args denotes a function parameter pack with the pattern Args&&.

The complexities of the expressions are sequence dependent.

Table 87

— Sequence container requirements (in addition to con-

tainer)

Expression

Return type

Assertion/note

pre-/post-condition

X(n, t)

Requires: T shall be CopyInsertable into X.

X u(n, t);

Postconditions: distance(begin(), end())

== n

Constructs a sequence container with n copies

of t

X(i, j)

Requires: T shall be EmplaceConstructible

X u(i, j);

into X from *i. For vector, if the iterator

does not meet the forward iterator

requirements (27.2.5), T shall also be

MoveInsertable into X. Each iterator in the

range [i, j) shall be dereferenced exactly

once.

Postconditions: distance(begin(), end())

== distance(i, j)

Constructs a sequence container equal to the

range [i, j)

X(il)

Equivalent to X(il.begin(), il.end())

a = il

Requires: T is CopyInsertable into X and

CopyAssignable. Assigns the range

[il.begin(), il.end()) into a. All existing

elements of a are either assigned to or

destroyed.

Returns:

*this.

a.emplace(p,

args)

iterator

Requires: T is EmplaceConstructible into X

from args. For vector and deque, T is also

MoveInsertable into X and MoveAssignable.

Effects: Inserts an object of type T

constructed with

std::forward<Args>(args)... before p.

a.insert(p,t)

iterator

Requires: T shall be CopyInsertable into X.

For vector and deque, T shall also be

CopyAssignable.

Effects: Inserts a copy of t before p.

a.insert(p,rv)

iterator

Requires: T shall be MoveInsertable into X.

For vector and deque, T shall also be

MoveAssignable.

Effects: Inserts a copy of rv before p.

a.insert(p,n,t)

iterator

Requires: T shall be CopyInsertable into X

and CopyAssignable.

Inserts n copies of t before p.

§ 26.2.3

757

Table 87 — Sequence container requirements (in addition to con-

tainer) (continued)

Expression

Return type

Assertion/note

pre-/post-condition

a.insert(p,i,j)

iterator

Requires: T shall be EmplaceConstructible

into X from *i. For vector and deque, T shall

also be MoveInsertable into X,

MoveConstructible, MoveAssignable, and

swappable (20.5.3.2). Each iterator in the

range [i, j) shall be dereferenced exactly

once.

Requires: i and j are not iterators into a.

Inserts copies of elements in [i, j) before p

a.insert(p, il)

iterator

a.insert(p, il.begin(), il.end()).

a.erase(q)

iterator

Requires: For vector and deque, T shall be

MoveAssignable.

Effects: Erases the element pointed to by q.

a.erase(q1,q2)

iterator

Requires: For vector and deque, T shall be

MoveAssignable.

Effects: Erases the elements in the range [q1,

q2).

a.clear()

void

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.

Postconditions: a.empty() returns true.

Complexity: Linear.

a.assign(i,j)

void

Requires: T shall be EmplaceConstructible

into X from *i and assignable from *i. For

vector, if the iterator does not meet the

forward iterator requirements (27.2.5), T shall

also be MoveInsertable into X.

Each iterator in the range [i, j) shall be

dereferenced exactly once.

Requires: i, j are not iterators into a.

Replaces elements in a with a copy of [i, j).

Invalidates all references, pointers and

iterators referring to the elements of a. For

vector and deque, also invalidates the

past-the-end iterator.

a.assign(il)

void

a.assign(il.begin(), il.end()).

a.assign(n,t)

void

Requires: T shall be CopyInsertable into X

and CopyAssignable.

Requires: t is not a reference into a.

Replaces elements in a with n copies of t.

Invalidates all references, pointers and

iterators referring to the elements of a. For

vector and deque, also invalidates the

past-the-end iterator.

The iterator returned from a.insert(p,

t) points to the copy of t inserted into a.

The iterator returned from a.insert(p,

rv) points to the copy of rv inserted into a.

The iterator returned from a.insert(p,

n, t) points to the copy of the first element inserted into a, or p

if n

== 0.

The iterator returned from a.insert(p,

i, j) points to the copy of the first element inserted into a, or p

if i

== j.

§ 26.2.3

758

The iterator returned from a.insert(p, il) points to the copy of the first element inserted into a, or p if

il is empty.

The iterator returned from a.emplace(p, args) points to the new element constructed from args into a.

The iterator returned from a.erase(q) points to the element immediately following q prior to the element

being erased. If no such element exists, a.end() is returned.

The iterator returned by a.erase(q1, q2) points to the element pointed to by q2 prior to any elements

being erased. If no such element exists, a.end() is returned.

For every sequence container defined in this Clause and in Clause 24:

(13.1)

—

If the constructor

template<class InputIterator>

X(InputIterator first, InputIterator last,

const allocator_type& alloc = allocator_type());

is called with a type InputIterator that does not qualify as an input iterator, then the constructor

shall not participate in overload resolution.

(13.2)

—

If the member functions of the forms:

template<class InputIterator>

return-type F(const_iterator p,

InputIterator first, InputIterator last);

// such as insert

template<class InputIterator>

return-type F(InputIterator first, InputIterator last);

// such as append, assign

template<class InputIterator>

return-type F(const_iterator i1, const_iterator i2,

InputIterator first, InputIterator last);

// such as replace

are called with a type InputIterator that does not qualify as an input iterator, then these functions

shall not participate in overload resolution.

—

(13.3)

A deduction guide for a sequence container shall not participate in overload resolution if it has an

InputIterator template parameter and a type that does not qualify as an input iterator is deduced

for that parameter, or if it has an Allocator template parameter and a type that does not qualify as

an allocator is deduced for that parameter.

Table 88 lists operations that are provided for some types of sequence containers but not others. An

implementation shall provide these operations for all container types shown in the “container” column, and

shall implement them so as to take amortized constant time.

Table 88 — Optional sequence container operations

Expression

Return type

Operational semantics

Container

a.front()

reference; const_reference

*a.begin()

basic_string,

for constant a

array, deque,

forward_list,

list, vector

a.back()

reference; const_reference

{ auto tmp = a.end();

basic_string,

for constant a

--tmp;

array, deque,

return *tmp; }

list, vector

a.emplace_-

reference

Prepends an object of type T

deque,

front(args)

constructed with

forward_list,

std::forward<Args>(

list

args)

Requires: T shall be

EmplaceConstructible into X

from args.

Returns: a.front().

§ 26.2.3

759

Table 88 — Optional sequence container operations (continued)

Expression

Return type

Operational semantics

Container

a.emplace_-

reference

Appends an object of type T

deque, list,

back(args)

constructed with

vector

std::forward<Args>(

args)

Requires: T shall be

EmplaceConstructible into X

from args. For vector, T shall

also be MoveInsertable into X.

Returns: a.back().

a.push_-

void

Prepends a copy of t.

deque,

front(t)

Requires: T shall be

forward_list,

CopyInsertable into X.

list

a.push_-

void

Prepends a copy of rv.

deque,

front(rv)

Requires: T shall be

forward_list,

MoveInsertable into X.

list

a.push_-

void

Appends a copy of t.

basic_string,

back(t)

Requires: T shall be

deque, list,

CopyInsertable into X.

vector

a.push_-

void

Appends a copy of rv.

basic_string,

back(rv)

Requires: T shall be

deque, list,

MoveInsertable into X.

vector

a.pop_-

void

Destroys the first element.

deque,

front()

Requires: a.empty() shall be

forward_list,

false.

list

a.pop_back()

void

Destroys the last element.

basic_string,

Requires: a.empty() shall be

deque, list,

false.

vector

a[n]

reference;

const_reference

*(a.begin() + n)

basic_string,

for constant a

array, deque,

vector

a.at(n)

reference;

const_reference

*(a.begin() + n)

basic_string,

for constant a

array, deque,

vector

The member function at() provides bounds-checked access to container elements. at() throws out_of_range

if n

>= a.size().

26.2.4

Node handles

[container.node]

26.2.4.1

node_handle overview

[container.node.overview]

A node handle is an object that accepts ownership of a single element from an associative container (26.2.6)

or an unordered associative container (26.2.7). It may be used to transfer that ownership to another container

with compatible nodes. Containers with compatible nodes have the same node handle type. Elements may

be transferred in either direction between container types in the same row of Table 89.

If a node handle is not empty, then it contains an allocator that is equal to the allocator of the container

when the element was extracted. If a node handle is empty, it contains no allocator.

Class node_handle is for exposition only. An implementation is permitted to provide equivalent functionality

without providing a class with this name.

If a user-defined specialization of pair exists for pair<const Key, T> or pair<Key, T>, where Key is the

container’s key_type and T is the container’s mapped_type, the behavior of operations involving node handles

is undefined.

§ 26.2.4.1

760

Table 89 — Container types with compatible nodes

map<K, T, C1, A>

map<K, T, C2, A>

map<K, T, C1, A>

multimap<K, T, C2, A>

set<K, C1, A>

set<K, C2, A>

set<K, C1, A>

multiset<K, C2, A>

unordered_map<K, T, H1, E1, A>

unordered_map<K, T, H2, E2, A>

unordered_map<K, T, H1, E1, A>

unordered_multimap<K, T, H2, E2, A>

unordered_set<K, H1, E1, A>

unordered_set<K, H2, E2, A>

unordered_set<K, H1, E1, A>

unordered_multiset<K, H2, E2, A>

template<unspecified>

class node_handle

{

public:

// These type declarations are described in Tables 90 and 91.

using value_type

= see below;

// not present for map containers

using key_type

= see below;

// not present for set containers

using mapped_type

= see below;

// not present for set containers

using allocator_type = see below;

private:

using container_node_type = unspecified;

using ator_traits = allocator_traits<allocator_type>;

typename ator_traits::rebind_traits<container_node_type>::pointer

ptr_;

optional<allocator_type> alloc_;

public:

constexpr node_handle() noexcept : ptr_(), alloc_() {}

~node_handle();

node_handle(node_handle&&) noexcept;

node_handle& operator=(node_handle&&);

value_type& value() const;

// not present for map containers

key_type& key() const;

// not present for set containers

mapped_type& mapped() const;

// not present for set containers

allocator_type get_allocator() const;

explicit operator bool() const noexcept;

[[nodiscard]] bool empty() const noexcept;

void swap(node_handle&)

noexcept(ator_traits::propagate_on_container_swap::value ||

ator_traits::is_always_equal::value);

friend void swap(node_handle& x, node_handle& y) noexcept(noexcept(x.swap(y)))

{

x.swap(y);

}

};

26.2.4.2

node_handle constructors, copy, and assignment

[container.node.cons]

node_handle(node_handle&& nh) noexcept;

Effects: Constructs a node_handle object initializing ptr_ with nh.ptr_. Move constructs alloc_ with

nh.alloc_. Assigns nullptr to nh.ptr_ and assigns nullopt to nh.alloc_.

node_handle& operator=(node_handle&& nh);

Requires: Either !alloc_, or ator_traits::propagate_on_container_move_assignment is true, or

alloc_ == nh.alloc_.

Effects:

§ 26.2.4.2

761

(3.1)

—

If ptr_ != nullptr, destroys the value_type subobject in the container_node_type object

pointed to by ptr_ by calling ator_traits::destroy, then deallocates ptr_ by calling ator_-

traits::rebind_traits<container_node_type>::deallocate.

(3.2)

—

Assigns nh.ptr_ to ptr_.

(3.3)

—

If !alloc_ or ator_traits::propagate_on_container_move_assignment is true, move assigns

nh.alloc_ to alloc_.

(3.4)

—

Assigns nullptr to nh.ptr_ and assigns nullopt to nh.alloc_.

Returns: *this.

Throws: Nothing.

26.2.4.3

node_handle destructor

[container.node.dtor]

~node_handle();

Effects: If ptr_ != nullptr, destroys the value_type subobject in the container_node_type ob-

ject pointed to by ptr_ by calling ator_traits::destroy, then deallocates ptr_ by calling ator_-

traits::rebind_traits<container_node_type>::deallocate.

26.2.4.4

node_handle observers

[container.node.observers]

value_type& value() const;

Requires: empty() == false.

Returns: A reference to the value_type subobject in the container_node_type object pointed to by

ptr_.

Throws: Nothing.

key_type& key() const;

Requires: empty() == false.

Returns: A non-const reference to the key_type member of the value_type subobject in the contain-

er_node_type object pointed to by ptr_.

Throws: Nothing.

Remarks: Modifying the key through the returned reference is permitted.

mapped_type& mapped() const;

Requires: empty() == false.

Returns: A reference to the mapped_type member of the value_type subobject in the container_-

node_type object pointed to by ptr_.

Throws: Nothing.

allocator_type get_allocator() const;

Requires: empty() == false.

Returns: *alloc_.

Throws: Nothing.

explicit operator bool() const noexcept;

Returns: ptr_ != nullptr.

[[nodiscard]] bool empty() const noexcept;

Returns: ptr_ == nullptr.

26.2.4.5

node_handle modifiers

[container.node.modifiers]

void swap(node_handle& nh)

noexcept(ator_traits::propagate_on_container_swap::value ||

§ 26.2.4.5

762

ator_traits::is_always_equal::value);

Requires:

!alloc_, or !nh.alloc_, or ator_traits::propagate_on_container_swap is true, or

alloc_ == nh.alloc_.

Effects: Calls swap(ptr_, nh.ptr_). If !alloc_, or !nh.alloc_, or ator_traits::propagate_on_-

container_swap is true calls swap(alloc_, nh.alloc_).

26.2.5

Insert return type

[container.insert.return]

The associative containers with unique keys and the unordered containers with unique keys have a member

function insert that returns a nested type insert_return_type. That return type is a specialization of

the type specified in this subclause.

template<class Iterator, class NodeType>

struct INSERT_RETURN_TYPE

{

Iterator position;

bool

inserted;

NodeType node;

};

The name INSERT_RETURN_TYPE is exposition only. INSERT_RETURN_TYPE has the template parameters,

data members, and special members specified above. It has no base classes or members other than those

specified.

26.2.6

Associative containers

[associative.reqmts]

Associative containers provide fast retrieval of data based on keys. The library provides four basic kinds of

associative containers: set, multiset, map and multimap.

Each associative container is parameterized on Key and an ordering relation Compare that induces a strict

weak ordering (28.7) on elements of Key. In addition, map and multimap associate an arbitrary mapped type

T with the Key. The object of type Compare is called the comparison object of a container.

The phrase “equivalence of keys” means the equivalence relation imposed by the comparison and not the

operator== on keys. That is, two keys k1 and k2 are considered to be equivalent if for the comparison

object comp, comp(k1, k2) == false && comp(k2, k1) == false. For any two keys k1 and k2 in the

same container, calling comp(k1, k2) shall always return the same value.

An associative container supports unique keys if it may contain at most one element for each key. Otherwise,

it supports equivalent keys. The set and map classes support unique keys; the multiset and multimap

classes support equivalent keys. For multiset and multimap, insert, emplace, and erase preserve the

relative ordering of equivalent elements.

For set and multiset the value type is the same as the key type. For map and multimap it is equal to

pair<const Key, T>.

iterator of an associative container is of the bidirectional iterator category. For associative containers

where the value type is the same as the key type, both iterator and const_iterator are constant iterators.

It is unspecified whether or not iterator and const_iterator are the same type. [Note: iterator and

const_iterator have identical semantics in this case, and iterator is convertible to const_iterator.

Users can avoid violating the one-definition rule by always using const_iterator in their function parameter

lists.

— end note ]

The associative containers meet all the requirements of Allocator-aware containers (26.2.1), except that

for map and multimap, the requirements placed on value_type in Table 83 apply instead to key_type

and mapped_type.

[Note: For example, in some cases key_type and mapped_type are required to be

CopyAssignable even though the associated value_type, pair<const key_type, mapped_type>, is not

CopyAssignable. — end note ]

In Table 90, X denotes an associative container class, a denotes a value of type X, a2 denotes a value of a

type with nodes compatible with type X (Table 89), b denotes a possibly const value of type X, u denotes

the name of a variable being declared, a_uniq denotes a value of type X when X supports unique keys, a_eq

denotes a value of type X when X supports multiple keys, a_tran denotes a possibly const value of type X

when the qualified-id X::key_compare::is_transparent is valid and denotes a type (17.9.2), i and j satisfy

input iterator requirements and refer to elements implicitly convertible to value_type, [i, j) denotes a

valid range, p denotes a valid constant iterator to a, q denotes a valid dereferenceable constant iterator to a,

§ 26.2.6

763

r denotes a valid dereferenceable iterator to a, [q1, q2) denotes a valid range of constant iterators in a, il

designates an object of type initializer_list<value_type>, t denotes a value of type X::value_type, k

denotes a value of type X::key_type and c denotes a possibly const value of type X::key_compare; kl is a

value such that a is partitioned (28.7) with respect to c(r, kl), with r the key value of e and e in a; ku is

a value such that a is partitioned with respect to !c(ku, r); ke is a value such that a is partitioned with

respect to c(r, ke) and !c(ke, r), with c(r, ke) implying !c(ke, r). A denotes the storage allocator

used by X, if any, or allocator<X::value_type> otherwise, m denotes an allocator of a type convertible to

A, and nh denotes a non-const rvalue of type X::node_type.

Table 90 — Associative container requirements (in addition to

container)

Expression

Return type

Assertion/note

Complexity

pre-/post-condition

X::key_type

Key

compile time

X::mapped_-

compile time

type (map

and multimap

only)

X::value_-

Key

Requires: value_type is

compile time

type (set

Erasable from X

and multiset

only)

X::value_-

pair<const

Requires: value_type is

compile time

type (map

Key, T>

Erasable from X

and multimap

only)

X::key_-

Compare

Requires: key_compare is

compile time

compare

CopyConstructible.

X::value_-

a binary

is the same as key_compare for

compile time

compare

predicate type

set and multiset; is an

ordering relation on pairs

induced by the first component

(i.e., Key) for map and

multimap.

X::node_-

a specialization

see 26.2.4

compile time

type

of a

node_handle

class template,

such that the

public nested

types are the

same types as

the

corresponding

types in X.

X(c)

Effects: Constructs an empty

constant

X u(c);

container. Uses a copy of c as

a comparison object.

X()

Requires: key_compare is

constant

X u;

DefaultConstructible.

Effects: Constructs an empty

container. Uses Compare() as

a comparison object

§ 26.2.6

764

Table 90 — Associative container requirements (in addition to

container) (continued)

Expression

Return type

Assertion/note

Complexity

pre-/post-condition

X(i,j,c)

Requires: value_type is

N log N in general, where N

X u(i,j,c);

EmplaceConstructible into X

has the value distance(i,

from *i.

j); linear if [i, j) is sorted

Effects: Constructs an empty

with value_comp()

container and inserts elements

from the range [i, j) into it;

uses c as a comparison object.

X(i,j)

Requires: key_compare is

same as above

X u(i,j);

DefaultConstructible.

value_type is

EmplaceConstructible into X

from *i.

Effects: Same as above, but

uses Compare() as a

comparison object.

X(il)

same as X(il.begin(),

il.end())

X(il,c)

same as X(il.begin(),

il.end(), c)

a = il

Requires: value_type is

N log N in general, where N

CopyInsertable into X and

has the value il.size() +

CopyAssignable.

a.size(); linear if

Effects: Assigns the range

[il.begin(), il.end()) is

[il.begin(), il.end()) into

sorted with value_comp()

a. All existing elements of a

are either assigned to or

destroyed.

b.key_-

X::key_-

returns the comparison object

constant

comp()

compare

out of which b was constructed.

b.value_-

X::value_-

returns an object of

constant

comp()

compare

value_compare constructed

out of the comparison object

a_uniq.

pair<

Requires: value_type shall be

logarithmic

emplace(

iterator,

EmplaceConstructible into X

args)

bool>

from args.

Effects: Inserts a value_type

object t constructed with

std::forward<Args>(

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

of t.

§ 26.2.6

765

Table 90 — Associative container requirements (in addition to

container) (continued)

Expression

Return type

Assertion/note

Complexity

pre-/post-condition

a_eq.

iterator

Requires: value_type shall be

logarithmic

emplace(

EmplaceConstructible into X

args)

from args.

Effects: Inserts a value_type

object t constructed with

std::forward<Args>(

args)... and returns the

iterator pointing to the newly

inserted element. If a range

containing elements equivalent

to t exists in a_eq, t is

inserted at the end of that

range.

a.emplace_-

iterator

equivalent to a.emplace(

logarithmic in general, but

hint(p,

std::forward<Args>(

amortized constant if the

args)

args)...). Return value is an

element is inserted right

iterator pointing to the element

before p

with the key equivalent to the

newly inserted element. The

element is inserted as close as

possible to the position just

prior to p.

a_uniq.

pair<

Requires: If t is a non-const

logarithmic

insert(t)

iterator,

rvalue expression, value_type

bool>

shall be MoveInsertable into

X; otherwise, value_type shall

be CopyInsertable into X.

Effects: 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 of t.

a_eq.

iterator

Requires: If t is a non-const

logarithmic

insert(t)

rvalue expression, value_type

shall be MoveInsertable into

X; otherwise, value_type shall

be CopyInsertable into X.

Effects: Inserts t and returns

the iterator pointing to the

newly inserted element. If a

range containing elements

equivalent to t exists in a_eq,

t is inserted at the end of that

range.

§ 26.2.6

766

Table 90 — Associative container requirements (in addition to

container) (continued)

Expression

Return type

Assertion/note

Complexity

pre-/post-condition

a.insert(p,

iterator

Requires: If t is a non-const

logarithmic in general, but

rvalue expression, value_type

amortized constant if t is

shall be MoveInsertable into

inserted right before p.

X; otherwise, value_type shall

be CopyInsertable into X.

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

a.insert(i,

void

Requires: value_type shall be

N log(a.size() + N ), where

EmplaceConstructible into X

N has the value

from *i.

distance(i,

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

a.insert(

void

equivalent to

il)

a.insert(il.begin(),

il.end())

a_uniq.

insert_-

Requires: nh is empty or

logarithmic

insert(nh)

return_type

a_uniq.get_allocator() ==

nh.get_allocator().

Effects: If nh is empty, has no

effect. Otherwise, inserts the

element owned by nh if and

only if there is no element in

the container with a key

equivalent to nh.key().

Postconditions: If nh is empty,

inserted is false, position

is end(), and node is empty.

Otherwise if the insertion took

place, inserted is true,

position points to the

inserted element, and node is

empty; if the insertion failed,

inserted is false, node has

the previous value of nh, and

position points to an element

with a key equivalent to

nh.key().

26.2.6

767

Table 90 — Associative container requirements (in addition to

container) (continued)

Expression

Return type

Assertion/note

Complexity

pre-/post-condition

a_eq.

iterator

Requires: nh is empty or

logarithmic

insert(nh)

a_eq.get_allocator() ==

nh.get_allocator().

Effects: If nh is empty, has no

effect and returns a_eq.end().

Otherwise, inserts the element

owned by nh and returns an

iterator pointing to the newly

inserted element. If a range

containing elements with keys

equivalent to nh.key() exists

in a_eq, the element is inserted

at the end of that range.

Postconditions: nh is empty.

a.insert(p,

iterator

Requires: nh is empty or

logarithmic in general, but

nh)

a.get_allocator() ==

amortized constant if the

nh.get_allocator().

element is inserted right

Effects: If nh is empty, has no

before p.

effect and returns a.end().

Otherwise, inserts the element

owned by nh if and only if

there is no element with key

equivalent to nh.key() in

containers with unique keys;

always inserts the element

owned by nh in containers with

equivalent keys. Always

returns the iterator pointing to

the element with key equivalent

to nh.key(). The element is

inserted as close as possible to

the position just prior to p.

Postconditions: nh is empty if

insertion succeeds, unchanged

if insertion fails.

a.extract(

node_type

removes the first element in the

log(a.size())

container with key equivalent

to k. Returns a node_type

owning the element if found,

otherwise an empty

node_type.

a.extract(

node_type

removes the element pointed to

amortized constant

by q. Returns a node_type

owning that element.

§ 26.2.6

768

Table 90 — Associative container requirements (in addition to

container) (continued)

Expression

Return type

Assertion/note

Complexity

pre-/post-condition

a.merge(a2)

void

Requires: a.get_allocator()

N log(a.size()+N ), where

== a2.get_allocator().

N has the value a2.size().

Attempts to extract each

element in a2 and insert it into

a using the comparison object

of a. In containers with unique

keys, if there is an element in a

with key equivalent to the key

of an element from a2, then

that element is not extracted

from a2.

Postconditions: Pointers and

references to the transferred

elements of a2 refer to those

same elements but as members

of a. Iterators referring to the

transferred elements will

continue to refer to their

elements, but they now behave

as iterators into a, not into a2.

Throws: Nothing unless the

comparison object throws.

a.erase(k)

size_type

erases all elements in the

log(a.size()) + a.count(k)

container with key equivalent

to k. returns the number of

erased elements.

a.erase(q)

iterator

erases the element pointed to

amortized constant

by q. Returns an iterator

pointing to the element

immediately following q prior

to the element being erased. If

no such element exists, returns

a.end().

a.erase(r)

iterator

erases the element pointed to

amortized constant

by r. Returns an iterator

pointing to the element

immediately following r prior

to the element being erased. If

no such element exists, returns

a.end().

a.erase(

iterator

erases all the elements in the

log(a.size()) + N , where N

q1, q2)

range [q1, q2). Returns an

has the value distance(q1,

iterator pointing to the element

q2).

pointed to by q2 prior to any

elements being erased. If no

such element exists, a.end() is

returned.

a.clear()

void

a.erase(a.begin(),a.end())

linear in a.size().

Postconditions: a.empty()

returns true.

§ 26.2.6

769

Table 90 — Associative container requirements (in addition to

container) (continued)

Expression

Return type

Assertion/note

Complexity

pre-/post-condition

b.find(k)

iterator;

returns an iterator pointing to

logarithmic

const_-

an element with the key

iterator for

equivalent to k, or b.end() if

constant b.

such an element is not found

a_tran.

iterator;

returns an iterator pointing to

logarithmic

find(ke)

const_-

an element with key r such

iterator for

that !c(r, ke) && !c(ke,

constant

r), or a_tran.end() if such an

a_tran.

element is not found

b.count(k)

size_type

returns the number of elements

log(b.size()) + b.count(k)

with key equivalent to k

a_tran.

size_type

returns the number of elements

log(a_tran.size()) +

count(ke)

with key r such that !c(r,

a_tran.count(ke)

ke) && !c(ke, r)

b.lower_-

iterator;

returns an iterator pointing to

logarithmic

bound(k)

const_-

the first element with key not

iterator for

less than k, or b.end() if such

constant b.

an element is not found.

a_tran.

iterator;

returns an iterator pointing to

logarithmic

lower_-

const_-

the first element with key r

bound(kl)

iterator for

such that !c(r, kl), or

constant

a_tran.end() if such an

a_tran.

element is not found.

b.upper_-

iterator;

returns an iterator pointing to

logarithmic

bound(k)

const_-

the first element with key

iterator for

greater than k, or b.end() if

constant b.

such an element is not found.

a_tran.

iterator;

returns an iterator pointing to

logarithmic

upper_-

const_-

the first element with key r

bound(ku)

iterator for

such that c(ku, r), or

constant

a_tran.end() if such an

a_tran.

element is not found.

b.equal_-

pair<

equivalent to make_-

logarithmic

range(k)

iterator,

pair(b.lower_bound(k),

iterator>;

b.upper_bound(k)).

pair<const_-

iterator,

const_-

iterator> for

constant b.

a_tran.

pair<

equivalent to make_pair(

logarithmic

equal_-

iterator,

a_tran.lower_bound(ke),

range(ke)

iterator>;

a_tran.upper_bound(ke)).

pair<const_-

iterator,

const_-

iterator> for

constant

a_tran.

The insert and emplace members shall not affect the validity of iterators and references to the container,

and the erase members shall invalidate only iterators and references to the erased elements.

§ 26.2.6

770

The extract members invalidate only iterators to the removed element; pointers and references to the

removed element remain valid. However, accessing the element through such pointers and references while

the element is owned by a node_type is undefined behavior. References and pointers to an element obtained

while it is owned by a node_type are invalidated if the element is successfully inserted.

The fundamental property of iterators of associative containers is that they iterate through the containers

in the non-descending order of keys where non-descending is defined by the comparison that was used to

construct them. For any two dereferenceable iterators i and j such that distance from i to j is positive, the

following condition holds:

value_comp(*j, *i) == false

For associative containers with unique keys the stronger condition holds:

value_comp(*i, *j) != false

When an associative container is constructed by passing a comparison object the container shall not store a

pointer or reference to the passed object, even if that object is passed by reference. When an associative

container is copied, either through a copy constructor or an assignment operator, the target container shall

then use the comparison object from the container being copied, as if that comparison object had been passed

to the target container in its constructor.

The member function templates find, count, lower_bound, upper_bound, and equal_range shall not

participate in overload resolution unless the qualified-id Compare::is_transparent is valid and denotes a

type (17.9.2).

A deduction guide for an associative container shall not participate in overload resolution if any of the

following are true:

(15.1)

—

It has an InputIterator template parameter and a type that does not qualify as an input iterator is

deduced for that parameter.

(15.2)

—

It has an Allocator template parameter and a type that does not qualify as an allocator is deduced

for that parameter.

(15.3)

—

It has a Compare template parameter and a type that qualifies as an allocator is deduced for that

parameter.

26.2.6.1

Exception safety guarantees

[associative.reqmts.except]

For associative containers, no clear() function throws an exception. erase(k) does not throw an exception

unless that exception is thrown by the container’s Compare object (if any).

For associative containers, if an exception is thrown by any operation from within an insert or emplace

function inserting a single element, the insertion has no effect.

For associative containers, no swap function throws an exception unless that exception is thrown by the swap

of the container’s Compare object (if any).

26.2.7

Unordered associative containers

[unord.req]

Unordered associative containers provide an ability for fast retrieval of data based on keys. The worst-case

complexity for most operations is linear, but the average case is much faster. The library provides four

unordered associative containers: unordered_set, unordered_map, unordered_multiset, and unordered_-

multimap.

Unordered associative containers conform to the requirements for Containers (26.2), except that the expressions

a == b and a != b have different semantics than for the other container types.

Each unordered associative container is parameterized by Key, by a function object type Hash that meets the

Hash requirements (20.5.3.4) and acts as a hash function for argument values of type Key, and by a binary

predicate Pred that induces an equivalence relation on values of type Key. Additionally, unordered_map and

unordered_multimap associate an arbitrary mapped type T with the Key.

The container’s object of type Hash — denoted by hash — is called the hash function of the container. The

container’s object of type Pred — denoted by pred — is called the key equality predicate of the container.

Two values k1 and k2 of type Key are considered equivalent if the container’s key equality predicate returns

true when passed those values. If k1 and k2 are equivalent, the container’s hash function shall return the

same value for both. [ Note: Thus, when an unordered associative container is instantiated with a non-default

Pred parameter it usually needs a non-default Hash parameter as well.

— end note ] For any two keys k1

§ 26.2.7

771

Working Draft, Standard for Programming Language C++ (N4713, 2017 year) - page 26