Standard Template Library Programmers Guide - читать онлайн бесплатно полную версию книги . Страница 3

Containers

Concepts

General concepts

Container

Category: containers

Component type: concept

Description

A Container is an object that stores other objects (its elements), and that has methods for accessing its elements. In particular, every type that is a model of Container has an associated iterator type that can be used to iterate through the Container's elements.

There is no guarantee that the elements of a Container are stored in any definite order; the order might, in fact, be different upon each iteration through the Container. Nor is there a guarantee that more than one iterator into a Container may be active at any one time. (Specific types of Containers, such as Forward Container, do provide such guarantees.)

A Container "owns" its elements: the lifetime of an element stored in a container cannot exceed that of the Container itself. [1]

Refinement of

Assignable

Associated types

Value type	`X::value_type`	The type of the object stored in a container. The value type must be Assignable, but need not be DefaultConstructible. [2]
Iterator type	`X::iterator`	The type of iterator used to iterate through a container's elements. The iterator's value type is expected to be the container's value type. A conversion from the iterator type to the const iterator type must exist. The iterator type must be an input iterator. [3]
Const iterator type	`X::const_iterator`	A type of iterator that may be used to examine, but not to modify, a container's elements. [3] [4]
Reference type	`X::reference`	A type that behaves as a reference to the container's value type. [5]
Const reference type	`X::const_reference`	A type that behaves as a const reference to the container's value type. [5]
Pointer type	`X::pointer`	A type that behaves as a pointer to the container's value type. [6]
Distance type	`X::difference_type`	A signed integral type used to represent the distance between two of the container's iterators. This type must be the same as the iterator's distance type. [2]
Size type	`X::size_type`	An unsigned integral type that can represent any nonnegative value of the container's distance type. [2]

Notation

X A type that is a model of Container

a, b Object of type X

T The value type of X

Definitions

The size of a container is the number of elements it contains. The size is a nonnegative number.

The area of a container is the total number of bytes that it occupies. More specifically, it is the sum of the elements' areas plus whatever overhead is associated with the container itself. If a container's value type T is a simple type (as opposed to a container type), then the container's area is bounded above by a constant times the container's size times sizeof(T). That is, if a is a container with a simple value type, then a 's area is O(a.size()).

A variable sized container is one that provides methods for inserting and/or removing elements; its size may vary during a container's lifetime. A fixed size container is one where the size is constant throughout the container's lifetime. In some fixed-size container types, the size is determined at compile time.

Valid expressions

In addition to the expressions defined in Assignable, EqualityComparable, and LessThanComparable, the following expressions must be valid.

Name	Expression	Return type
Beginning of range	`a.begin()`	iterator if a is mutable, const_iterator otherwise [4] [7]
End of range	`a.end()`	iterator if a is mutable, const_iterator otherwise [4]
Size	`a.size()`	`size_type`
Maximum size	`a.max_size()`	`size_type`
Empty container	`a.empty()`	Convertible to bool
Swap	`a.swap(b)`	`void`

Expression semantics

Semantics of an expression is defined only where it differs from, or is not defined in, Assignable, Equality Comparable, or LessThan Comparable

Name	Expression	Semantics	Postcondition
Copy constructor	`X(a)`		`X().size() == a.size().`X() contains a copy of each of a 's elements.
Copy constructor	`X b(a);`		`b.size() == a.size().`b contains a copy of each of a 's elements.
Assignment operator	`b = a`		`b.size() == a.size().` b contains a copy of each of a 's elements.
Destructor	`a.~X()`	Each of a 's elements is destroyed, and memory allocated for them (if any) is deallocated.
Beginning of range	`a.begin()`	Returns an iterator pointing to the first element in the container. [7]	a.begin() is either dereferenceable or past-the-end. It is past-the-end if and only if a.size() == 0.
End of range	a.end()	Returns an iterator pointing one past the last element in the container.	a.end() is past-the-end.
Size	`a.size()`	Returns the size of the container, that is, its number of elements. [8]	`a.size() >= 0 && a.size() <= max_size()`
Maximum size	`a.max_size()`	Returns the largest size that this container can ever have. [8]	`a.max_size() >= 0 && a.max_size() >= a.size()`
Empty container	`a.empty()`	Equivalent to a.size() == 0. (But possibly faster.)
Swap	`a.swap(b)`	Equivalent to swap(a,b) [9]

Complexity guarantees

The copy constructor, the assignment operator, and the destructor are linear in the container's size.

begin() and end() are amortized constant time.

size() is linear in the container's size. [10]max_size() and empty() are amortized constant time. If you are testing whether a container is empty, you should always write c.empty() instead of c.size() == 0. The two expressions are equivalent, but the former may be much faster.

swap() is amortized constant time. [9]

Invariants

Valid range	For any container a, [a.begin(), a.end()) is a valid range. [11]
Range size	a.size() is equal to the distance from a.begin() to a.end().
Completeness	An algorithm that iterates through the range [a.begin(), a.end()) will pass through every element of a. [11]

Models

• vector

Notes

[1] The fact that the lifetime of elements cannot exceed that of of their container may seem like a severe restriction. In fact, though, it is not. Note that pointers and iterators are objects; like any other objects, they may be stored in a container. The container, in that case, "owns" the pointers themselves, but not the objects that they point to.

[2] This expression must be a typedef , that is, a synonym for a type that already has some other name.

[3] This may either be a typedef for some other type, or else a unique type that is defined as a nested class within the class X.

[4] A container's iterator type and const iterator type may be the same: there is no guarantee that every container must have an associated mutable iterator type. For example, set and hash_set define iterator and const_iterator to be the same type.

[5] It is required that the reference type has the same semantics as an ordinary C++ reference, but it need not actually be an ordinary C++ reference. Some implementations, for example, might provide additional reference types to support non-standard memory models. Note, however, that "smart references" (user-defined reference types that provide additional functionality) are not a viable option. It is impossible for a user-defined type to have the same semantics as C++ references, because the C++ language does not support redefining the member access operator (operator.).

[6] As in the case of references [5], the pointer type must have the same semantics as C++ pointers but need not actually be a C++ pointer. "Smart pointers," however, unlike "smart references", are possible. This is because it is possible for user-defined types to define the dereference operator and the pointer member access operator, operator* and operator->.

[7] The iterator type need only be an input iterator , which provides a very weak set of guarantees; in particular, all algorithms on input iterators must be "single pass". It follows that only a single iterator into a container may be active at any one time. This restriction is removed in Forward Container.

[8] In the case of a fixed-size container, size() == max_size().

[9] For any Assignable type, swap can be defined in terms of assignment. This requires three assignments, each of which, for a container type, is linear in the container's size. In a sense, then, a.swap(b) is redundant. It exists solely for the sake of efficiency: for many containers, such as vector and list, it is possible to implement swap such that its run-time complexity is constant rather than linear. If this is possible for some container type X , then the template specialization swap(X&, X&) can simply be written in terms of X::swap(X&). The implication of this is that X::swap(X&) should only be defined if there exists such a constant-time implementation. Not every container class X need have such a member function, but if the member function exists at all then it is guaranteed to be amortized constant time.

[10] For many containers, such as vector and deque, size is O(1). This satisfies the requirement that it be O(N).

[11] Although [a.begin(), a.end()) must be a valid range, and must include every element in the container, the order in which the elements appear in that range is unspecified. If you iterate through a container twice, it is not guaranteed that the order will be the same both times. This restriction is removed in Forward Container.

Forward Container

Category: containers

Component type: concept

Description

A Forward Container is a Container whose elements are arranged in a definite order: the ordering will not change spontaneously from iteration to iteration. The requirement of a definite ordering allows the definition of element-by-element equality (if the container's element type is Equality Comparable) and of lexicographical ordering (if the container's element type is LessThan Comparable).

Iterators into a Forward Container satisfy the forward iterator requirements; consequently, Forward Containers support multipass algorithms and allow multiple iterators into the same container to be active at the same time. Refinement of Container, EqualityComparable, LessThanComparable

Associated types

No additional types beyond those defined in Container. However, the requirements for the iterator type are strengthened: the iterator type must be a model of Forward Iterator.

Notation

X A type that is a model of Forward Container

a, b Object of type X

T The value type of X

Valid expressions

In addition to the expressions defined in Container, EqualityComparable, and LessThanComparable, the following expressions must be valid.

Name	Expression	Type requirements	Return type
Equality	`a == b`	T is EqualityComparable	Convertible to bool
Inequality	`a != b`	T is EqualityComparable	Convertible to bool
Less	`a < b`	T is LessThanComparable	Convertible to bool
Greater	`a > b`	T is LessThanComparable	Convertible to bool
Less or equal	`a <= b`	T is LessThanComparable	Convertible to bool
Greater or equal	`a >= b`	T is LessThanComparable	Convertible to bool

Expression semantics

Semantics of an expression is defined only where it is not defined in Container, EqualityComparable, or LessThanComparable, or where there is additional information.

Name	Expression	Semantics
Equality	`a == b`	Returns true if a.size() == b.size() and if each element of a compares equal to the corresponding element of b. Otherwise returns false.
Less	`a < b`	Equivalent to lexicographical_compare(a,b)

Complexity guarantees

The equality and inequality operations are linear in the container's size.

Invariants

Ordering

Two different iterations through a forward container will access its elements in the same order, providing that there have been no intervening mutative operations.

Models

• vector

• list

• slist

• deque

• set

• hash_set

• map

• hash_map

• multiset

• hash_multiset

• multimap

• hash_multimap

Reversible Container

Category: containers

Component type: concept

Description

A Reversible Container is a Forward Container whose iterators are Bidirectional Iterators. It allows backwards iteration through the container.

Refinement of

Forward Container

Associated types

Two new types are introduced. In addition, the iterator type and the const iterator type must satisfy a more stringent requirement than for a Forward Container. The iterator and reverse iterator types must be Bidirectional Iterators, not merely Forward Iterators.

Reverse iterator type	`X::reverse_iterator`	A Reverse Iterator adaptor whose base iterator type is the container's iterator type. Incrementing an object of type reverse_iterator moves backwards through the container: the Reverse Iterator adaptor maps operator++ to operator--.
Const reverse iterator type	`X::const_reverse_iterator`	A Reverse Iterator adaptor whose base iterator type is the container's const iterator type. [1]

Notation

X A type that is a model of Reversible Container

a, b Object of type X

Valid expressions

In addition to the expressions defined in Forward Container, the following expressions must be valid.

Name	Expression	Return type
Beginning of range	`a.rbegin()`	reverse_iterator if a is mutable, const_reverse_iterator otherwise [1]
End of range	`a.rend()`	reverse_iterator if a is mutable, const_reverse_iterator otherwise [1]

Expression semantics

Semantics of an expression is defined only where it is not defined in Forward Container, or where there is additional information.

Name	Expression	Semantics	Postcondition
Beginning of reverse range	`a.rbegin()`	Equivalent to `X::reverse_iterator(a.end()).`	a.rbegin() is dereferenceable or past-the-end. It is past-the-end if and only if a.size() == 0.
End of reverse range	`a.rend()`	Equivalent to `X::reverse_iterator(a.begin()).`	a.end() is past-the-end.

Complexity guarantees

The run-time complexity of rbegin() and rend() is amortized constant time.

Invariants

Valid range	[a.rbegin(), a.rend()) is a valid range.
Equivalence of ranges	The distance from a.begin() to a.end() is the same as the distance from a.rbegin() to a.rend().

Models

• vector

• list

• deque

Notes

[1] A Container's iterator type and const iterator type may be the same type: a container need not provide mutable iterators. It follows from this that the reverse iterator type and the const reverse iterator type may also be the same.

Random Access Container

Category: containers

Component type: concept

Description

A Random Access Container is a Reversible Container whose iterator type is a Random Access Iterator. It provides amortized constant time access to arbitrary elements.

Refinement of

Reversible Container

Associated types

No additional types beyond those defined in Reversible Container. However, the requirements for the iterator type are strengthened: it must be a Random Access Iterator.

Notation

X A type that is a model of Random Access Container

a, b Object of type X

T The value type of X

Valid expressions

In addition to the expressions defined in Reversible Container, the following expressions must be valid.

Name	Expression	Type requirements	Return type
Element access	`a[n]`	n is convertible to size_type	reference if a is mutable, const_reference otherwise

Expression semantics

Semantics of an expression is defined only where it is not defined in Reversible Container, or where there is additional information.

Name	Expression	Precondition	Semantics
Element access	`a[n]`	`0 <= n < a.size()`	Returns the n th element from the beginning of the container.

Complexity guarantees

The run-time complexity of element access is amortized constant time.

Invariants

Element access

The element returned by a[n] is the same as the one obtained by incrementing a.begin()n times and then dereferencing the resulting iterator.

Models

• vector

• deque

Sequences

Sequence

Category: containers

Component type: concept

Description

A Sequence is a variable-sized Container whose elements are arranged in a strict linear order. It supports insertion and removal of elements.

Refinement of

Forward Container, Default Constructible

Associated types

None, except for those of Forward Container.

Notation

X A type that is a model of Sequence

a, b Object of type X

T The value type of X

t Object of type T

p, q Object of type X::iterator

n Object of a type convertible to X::size_type

Definitions

If a is a Sequence, then p is a valid iterator in a if it is a valid (nonsingular) iterator that is reachable from a.begin().

If a is a Sequence, then [p, q) is a valid range in a if p and q are valid iterators in a and if q is reachable from p.

Valid expressions

In addition to the expressions defined in Forward Container, the following expressions must be valid.

Name	Expression	Type requirements	Return type
Fill constructor	`X(n, t)`		`X`
Fill constructor	`X a(n, t);`
Default fill constructor	`X(n)`	T is DefaultConstructible.	`X`
Default fill constructor	`X a(n);`	T is DefaultConstructible.
Range constructor	`X(i, j)`	i and j are Input Iterators whose value type is convertible to T [1]	`X`
Range constructor	`X a(i, j);`	i and j are Input Iterators whose value type is convertible to T [1]
Front	`a.front()`		reference if a is mutable, const_reference otherwise.
Insert	`a.insert(p, t)`		`X::iterator`
Fill insert	`a.insert(p, n, t)`	a is mutable	`void`
Range insert	`a.insert(p, i, j)`	i and j are Input Iterators whose value type is convertible to T [1]. a is mutable	`void`
Erase	`a.erase(p)`	a is mutable	`iterator`
Range erase	`a.erase(p,q)`	a is mutable	`iterator`
Clear	`a.clear()`	a is mutable	`void`
Resize	`a.resize(n, t)`	a is mutable	`void`
Resize	`a.resize(n)`	a is mutable	`void`

Expression semantics

Semantics of an expression is defined only where it is not defined in Forward Container, or where it differs.

Name	Expression	Precondition	Semantics	Postcondition
Fill constructor	`X(n, t)`	`n >= 0`	Creates a sequence with n copies of t	size() == n. Every element is a copy of t.
Fill constructor	`X a(n, t);`	`n >= 0`	Creates a sequence with n copies of t	a.size() == n . Every element of a is a copy of t.
Default fill constructor	`X(n)`	`n >= 0`	Creates a sequence of n elements initialized to a default value.	size() == n. Every element is a copy of T().
Default fill constructor	`X a(n, t);`	`n >= 0`	Creates a sequence with n elements initialized to a default value.	a.size() == n. Every element of a is a copy of T().
Default constructor	`X a;` or `X()`		Equivalent to X(0).	`size() == 0.`
Range constructor	`X(i, j)`	[i,j) is a valid range.	Creates a sequence that is a copy of the range [i,j)	size() is equal to the distance from i to j. Each element is a copy of the corresponding element in the range [i,j).
Range constructor	`X a(i, j);`	[i,j) is a valid range.	Creates a sequence that is a copy of the range [i,j)	a.size() is equal to the distance from i to j. Each element in a is a copy of the corresponding element in the range [i,j).
Front	`a.front()`	`!a.empty()`	Equivalent to *(a.first())
Insert	`a.insert(p, t)`	p is a valid iterator in a. a.size() < a.max_size()	A copy of t is inserted before p. [2] [3]	a.size() is incremented by 1. *(a.insert(p,t)) is a copy of t . The relative order of elements already in the sequence is unchanged.
Fill insert	`a.insert(p, n, t)`	p is a valid iterator in a. n >= 0 && a.size() + n <= a.max_size().	n copies of t are inserted before p. [2] [3] [4]	a.size() is incremented by n. The relative order of elements already in the sequence is unchanged.
Range insert	`a.insert(p, i, j)`	[i,j) is a valid range.	a.size() plus the distance from i to j does not exceed a.max_size(). Inserts a copy of the range [i,j) before p. [1] [2] [3]	a.size() is incremented by the distance from i to j. The relative order of elements already in the sequence is unchanged.
Erase	`a.erase(p)`	p is a dereferenceable iterator in a.	Destroys the element pointed to by p and removes it from a. [3]	a.size() is decremented by 1. The relative order of the other elements in the sequence is unchanged. The return value is an iterator to the element immediately following the one that was erased.
Range erase	`a.erase(p,q)`	[p,q) is a valid range in a.	Destroys the elements in the range [p,q) and removes them from a. [3]	a.size() is decremented by the distance from i to j. The relative order of the other elements in the sequence is unchanged. The return value is an iterator to the element immediately following the ones that were erased.
Clear	`a.clear()`		Equivalent to a.erase(a.begin(), a.end())
Resize	`a.resize(n, t)`	`n <= a.max_size()`	Modifies the container so that it has exactly n elements, inserting elements at the end or erasing elements from the end if necessary. If any elements are inserted, they are copies of t. If n > a.size() , this expression is equivalent to a.insert(a.end(), n – size(), t). If n < a.size() , it is equivalent to a.erase(a.begin() + n, a.end()).	`a.size() == n`
Resize	`a.resize(n)`	`n <= a.max_size()`	Equivalent to a.resize(n, T()).	`a.size() == n`

Complexity guarantees

The fill constructor, default fill constructor, and range constructor are linear.

Front is amortized constant time.

Fill insert, range insert, and range erase are linear.

The complexities of single-element insert and erase are sequence dependent.

Models

• vector [5]

• deque

• list

• slist

Notes

[1] At present (early 1998), not all compilers support "member templates". If your compiler supports member templates then i and j may be of any type that conforms to the Input Iterator requirements. If your compiler does not yet support member templates, however, then i and j must be of type const T* or of type X::const_iterator.

[2] Note that p equal to a.begin() means to insert something at the beginning of a (that is, before any elements already in a ), and p equal to a.end() means to append something to the end of a.

[3] Warning: there is no guarantee that a valid iterator ona is still valid after an insertion or an erasure. In some cases iterators do remain valid, and in other cases they do not. The details are different for each sequence class.

[4] a.insert(p, n, t) is guaranteed to be no slower then calling a.insert(p, t)n times. In some cases it is significantly faster.

[5] Vector is usually preferable to deque and list. Deque is useful in the case of frequent insertions at both the beginning and end of the sequence, and list and slist are useful in the case of frequent insertions in the middle of the sequence. In almost all other situations, vector is more efficient.

Front Insertion Sequence

Category: containers

Component type: concept

Description

A Front Insertion Sequence is a Sequence where it is possible to insert an element at the beginning, or to access the first element, in amortized constant time. Front Insertion Sequences have special member functions as a shorthand for those operations.

Refinement of

Sequence

Associated types

None, except for those of Sequence.

Notation

X A type that is a model of Front Insertion Sequence

a Object of type X

T The value type of X

t Object of type T

Valid expressions

In addition to the expressions defined in Sequence, the following expressions must be valid.

Name	Expression	Type requirements	Return type
Front	`a.front()` [1]		reference if a is mutable, otherwise const_reference.
Push front	`a.push_front(t)`	a is mutable.	`void`
Pop front	`a.pop_front()`	a is mutable.	`void`

Expression semantics

Name	Expression	Precondition	Semantics	Postcondition
Front	`a.front()` [1]	!a.empty()	Equivalent to *(a.begin()).
Push front	a.push_front(t)		Equivalent to a.insert(a.begin(), t) a.size is incremented by 1.	a.front() is a copy of t.
Pop front	`a.pop_front()`	`!a.empty()`	Equivalent to a.erase(a.begin())	a.size() is decremented by 1.

Complexity guarantees

Front, push front, and pop front are amortized constant time. [2]

Invariants

Symmetry of push and pop

push_front() followed by pop_front() is a null operation.

Models

• list

• deque

Notes

[1] Front is actually defined in Sequence, since it is always possible to implement it in amortized constant time. Its definition is repeated here, along with push front and pop front, in the interest of clarity.

[2] This complexity guarantee is the only reason that front(), push_front(), and pop_front() are defined: they provide no additional functionality. Not every sequence must define these operations, but it is guaranteed that they are efficient if they exist at all.

Back Insertion Sequence

Category: containers

Component type: concept

Description

A Back Insertion Sequence is a Sequence where it is possible to append an element to the end, or to access the last element, in amortized constant time. Back Insertion Sequences have special member functions as a shorthand for those operations.

Refinement of

Sequence

Associated types

None, except for those of Sequence.

Notation

X A type that is a model of Back Insertion Sequence

a Object of type X

T The value type of X

t Object of type T

Valid expressions

In addition to the expressions defined in Sequence, the following expressions must be valid.

Name	Expression	Type requirements	Return type
Back	`a.back()`		reference if a is mutable, otherwise const_reference.
Push back	`a.push_back(t)`	a is mutable.	`void`
Pop back	`a.pop_back()`	a is mutable.	`void`

Expression semantics

Name	Expression	Precondition	Semantics	Postcondition
Back	`a.back()`	`!a.empty()`	Equivalent to *(--a.end()).
Push back	`a.push_back(t)`		Equivalent to a.insert(a.end(), t) a.size is incremented by 1.	a.back() is a copy of t.
Pop back	`a.pop_back()`	`!a.empty()`	Equivalent to a.erase(--a.end())	a.size() is decremented by 1.

Complexity guarantees

Back, push back, and pop back are amortized constant time. [1]

Invariants

Symmetry of push and pop

push_back() followed by pop_back() is a null operation.

Models

vector

list

deque

Notes

[1] This complexity guarantee is the only reason that back(), push_back(), and pop_back() are defined: they provide no additional functionality. Not every sequence must define these operations, but it is guaranteed that they are efficient if they exist at all.

Associative Containers

Associative Container

Category: containers

Component type: concept

Description

An Associative Container is a variable-sized Container that supports efficient retrieval of elements (values) based on keys. It supports insertion and removal of elements, but differs from a Sequence in that it does not provide a mechanism for inserting an element at a specific position. [1]

As with all containers, the elements in an Associative Container are of type value_type. Additionally, each element in an Associative Container has a key, of type key_type. In some Associative Containers, Simple Associative Containers, the value_type and key_type are the same: elements are their own keys. In others, the key is some specific part of the value. Since elements are stored according to their keys, it is essential that the key associated with each element is immutable. In Simple Associative Containers this means that the elements themselves are immutable, while in other types of Associative Containers, such as Pair Associative Containers, the elements themselves are mutable but the part of an element that is its key cannot be modified. This means that an Associative Container's value type is not Assignable.

The fact that the value type of an Associative Container is not Assignable has an important consequence: associative containers cannot have mutable iterators. This is simply because a mutable iterator (as defined in the Trivial Iterator requirements) must allow assignment. That is, if i is a mutable iterator and t is an object of i 's value type, then *i = t must be a valid expression.

In Simple Associative Containers, where the elements are the keys, the elements are completely immutable; the nested types iterator and const_iterator are therefore the same. Other types of associative containers, however, do have mutable elements, and do provide iterators through which elements can be modified. Pair Associative Containers, for example, have two different nested types iterator and const_iterator . Even in this case, iterator is not a mutable iterator: as explained above, it does not provide the expression *i = t. It is, however, possible to modify an element through such an iterator: if, for example, i is of type map<int, double> , then (*i).second = 3 is a valid expression.

In some associative containers, Unique Associative Containers, it is guaranteed that no two elements have the same key. [2] In other associative containers, Multiple Associative Containers, multiple elements with the same key are permitted.

Refinement of

Forward Container, Default Constructible

Associated types

One new type is introduced, in addition to the types defined in the Forward Container requirements.

Key type X::key_type The type of the key associated with X::value_type . Note that the key type and value type might be the same.

Notation

X A type that is a model of Associative Container

a Object of type X

t Object of type X::value_type

k Object of type X::key_type

p, q Object of type X::iterator

Definitions

If a is an associative container, then p is a valid iterator in a if it is a valid iterator that is reachable from a.begin().

If a is an associative container, then [p, q) is a valid range in a if [p, q) is a valid range and p is a valid iterator in a.

Valid expressions

In addition to the expressions defined in Forward Container, the following expressions must be valid.

Name	Expression	Return type
Default constructor	`X()X a;`
Erase key	`a.erase(k)`	`size_type`
Erase element	`a.erase(p)`	`void`
Erase range	`a.erase(p, q)`	`void`
Clear	`a.clear()`	`void`
Find	`a.find(k)`	iterator if a is mutable, otherwise const_iterator
Count	`a.count(k)`	`size_type`
Equal range	`a.equal_range(k)`	pair<iterator, iterator> if a is mutable, otherwise pair<const_iterator, const_iterator>.

Expression semantics

Name	Expression	Precondition	Semantics	Postcondition
Default constructor	`X()X a;`		Creates an empty container.	The size of the container is 0.
Erase key	`a.erase(k)`		Destroys all elements whose key is the same as k, and removes them from a. [2] The return value is the number of elements that were erased, i.e. the old value of a.count(k).	a.size() is decremented by a.count(k). a contains no elements with key k.
Erase element	`a.erase(p)`	p is a dereferenceable iterator in a.	Destroys the element pointed to by p, and removes it from a.	a.size() is decremented by 1.
Erase range	`a.erase(p, q)`	[p, q) is a valid range in a.	Destroys the elements in the range [p,q) and removes them from a.	a.size() is decremented by the distance from i to j.
Clear	`a.clear()`		Equivalent to a.erase(a.begin(), a.end())
Find	a.find(k)		Returns an iterator pointing to an element whose key is the same as k, or a.end() if no such element exists.	Either the return value is a.end(), or else the return value has a key that is the same as k.
Count	`a.count(k)`		Returns the number of elements in a whose keys are the same as k.
Equal range	a.equal_range(k)		Returns a pair P such that [P.first, P.second) is a range containing all elements in a whose keys are the same as k. [3] If no elements have the same key as k, the return value is an empty range.	The distance between P.first and P.second is equal to a.count(k) . If p is a dereferenceable iterator in a, then either p lies in the range [P.first, P.second), or else *p has a key that is not the same as k.

Complexity guarantees

Average complexity for erase key is at most O(log(size()) + count(k)).

Average complexity for erase element is constant time.

Average complexity for erase range is at most O(log(size()) + N), where N is the number of elements in the range.

Average complexity for count is at most O(log(size()) + count(k)).

Average complexity for find is at most logarithmic.

Average complexity for equal range is at most logarithmic.

Invariants

Contiguous storage	All elements with the same key are adjacent to each other. That is, if p and q are iterators that point to elements that have the same key, and if p precedes q , then every element in the range [p, q) has the same key as every other element.
Immutability of keys	Every element of an Associative Container has an immutable key. Objects may be inserted and erased, but an element in an Associative Container may not be modified in such a way as to change its key.

Models

• set

• multiset

• hash_set

• hash_multiset

• map

• multimap

• hash_map

• hash_multimap

Notes

[1] The reason there is no such mechanism is that the way in which elements are arranged in an associative container is typically a class invariant; elements in a Sorted Associative Container, for example, are always stored in ascending order, and elements in a Hashed Associative Container are always stored according to the hash function. It would make no sense to allow the position of an element to be chosen arbitrarily.

[2] Keys are not required to be Equality Comparable: associative containers do not necessarily use operator== to determine whether two keys are the same. In Sorted Associative Containers, for example, where keys are ordered by a comparison function, two keys are considered to be the same if neither one is less than the other.

[3] Note the implications of this member function: it means that if two elements have the same key, there must be no elements with different keys in between them. The requirement that elements with the same key be stored contiguously is an associative container invariant.

Simple Associative Container

Category: containers

Component type: concept

Description

A Simple Associative Container is an Associative Container where elements are their own keys. A key in a Simple Associative Container is not associated with any additional value.

Refinement of

Associative Container

Associated types

None, except for those described in the Associative Container requirements. Simple Associative Container, however, introduces two new type restrictions.

Key type	`X::key_type`	The type of the key associated with X::value_type. The types key_type and value_type must be the same type.
Iterator	`X::iterator`	The type of iterator used to iterate through a Simple Associative Container's elements. The types X::iterator and X::const_iterator must be the same type. That is, a Simple Associative Container does not provide mutable iterators. [1]

Notation

X A type that is a model of Simple Associative Container

a Object of type X

k Object of type X::key_type

p, q Object of type X::iterator

Valid expressions

None, except for those defined in the Associative Container requirements.

Invariants

Immutability of Elements

Every element of a Simple Associative Container is immutable. Objects may be inserted and erased, but not modified. [1]

Models

• set

• multiset

• hash_set

• hash_multiset

Notes

[1] This is a consequence of the Immutability of Keys invariant of Associative Container. Keys may never be modified; values in a Simple Associative Container are themselves keys, so it immediately follows that values in a Simple Associative Container may not be modified.

Pair Associative Container

Category: containers

Component type: concept

Description

A Pair Associative Container is an Associative Container that associates a key with some other object. The value type of a Pair Associative Container is pair<const key_type, data_type>. [1]

Refinement of

Associative Container

Associated types

One new type is introduced, in addition to the types defined in the Associative Container requirements. Additionally, Pair Associative Container introduces one new type restriction

Key type	`X::key_type`	The type of the key associated with X::value_type.
Data type	`X::data_type`	The type of the data associated with X::value_type. A Pair Associative Container can be thought of as a mapping from key_type to data_type.
Value type	`X::value_type`	The type of object stored in the container. The value type is required to be pair<const key_type, data_type>.

Notation

X A type that is a model of Pair Associative Container

a Object of type X

t Object of type X::value_type

d Object of type X::data_type

k Object of type X::key_type

p, q Object of type X::iterator

Valid expressions

None, except for those defined in the Associative Container requirements.

Models

• map

• multimap

• hash_map

• hash_multimap

Notes

[1] The value type must be pair<const key_type, data_type>, rather than pair<key_type, data_type>, because of the Associative Container invariant of key immutability. The data_type part of an object in a Pair Associative Container may be modified, but the key_type part may not be. Note the implication of this fact: a Pair Associative Container cannot provide mutable iterators (as defined in the Trivial Iterator requirements), because the value type of a mutable iterator must be Assignable, and pair<const key_type, data_type> is not Assignable. However, a Pair Associative Container can provide iterators that are not completely constant: iterators such that the expression (*i).second = d is valid.

Sorted Associative Container

Category: containers

Component type: concept

Description

A Sorted Associative Container is a type of Associative Container. Sorted Associative Containers use an ordering relation on their keys; two keys are considered to be equivalent if neither one is less than the other. (If the ordering relation is case-insensitive string comparison, for example, then the keys "abcde" and "aBcDe" are equivalent.)

Sorted Associative Containers guarantee that the complexity for most operations is never worse than logarithmic [1], and they also guarantee that their elements are always sorted in ascending order by key.

Refinement of

Reversible Container, Associative Container

Associated types

Two new types are introduced, in addition to the types defined in the Associative Container and Reversible Container requirements.

`X::key_compare`	The type of a Strict Weak Ordering used to compare keys. Its argument type must be X::key_type.
`X::value_compare`	The type of a Strict Weak Ordering used to compare values. Its argument type must be X::value_type, and it compares two objects of value_type by passing the keys associated with those objects to a function object of type key_compare.

Notation

X A type that is a model of Sorted Associative Container

a Object of type X

t Object of type X::value_type

k Object of type X::key_type

p, q Object of type X::iterator

c Object of type X::key_compare

Valid expressions

In addition to the expressions defined in Associative Container and Reversible Container, the following expressions must be valid.

Name	Expression	Return type
Default constructor	`X()X a;`
Constructor with compare	`X(c)X a(c);`
Key comparison	`a.key_comp()`	`X::key_compare`
Value comparison	`a::value_compare()`	`X::value_compare`
Lower bound	`a.lower_bound(k)`	iterator if a is mutable, otherwise const_iterator.
Upper bound	`a.upper_bound(k)`	iterator if a is mutable, otherwise const_iterator.
Equal range	`a.equal_range(k)`	pair<iterator, iterator> if a is mutable, otherwise pair<const_iterator, const_iterator>.

Expression semantics

Name	Expression	Semantics	Postcondition
Default constructor	`X()X a;`	Creates an empty container, using key_compare() as the comparison object.	The size of the container is 0.
Constructor with compare	`X(c)X a(c);`	Creates an empty container, using c as the comparison object.	The size of the container is 0. key_comp() returns a function object that is equivalent to c.
Key comparison	`a.key_comp()`	Returns the key comparison object used by a.
Value comparison	`a::value_compare()`	Returns the value comparison object used by a.	If t1 and t2 are objects of type value_type, and k1 and k2 are the keys associated with them, then a.value_comp()(t1, t2) is equivalent to a.key_comp()(k1, k2).
Lower bound	`a.lower_bound(k)`	Returns an iterator pointing to the first element whose key is not less than k. Returns a.end() if no such element exists.	If a contains any elements that have the same key as k, then the return value of lower_bound points to the first such element.
Upper bound	`a.upper_bound(k)`	Returns an iterator pointing to the first element whose key is greater than k.	Returns a.end() if no such element exists. If a contains any elements that have the same key as k, then the return value of upper_bound points to one past the last such element.
Equal range	`a.equal_range(k)`	Returns a pair whose first element is a.lower_bound(k) and whose second element is a.upper_bound(k).

Complexity guarantees

key_comp() and value_comp() are constant time.

Erase element is constant time.

Erase key is O(log(size()) + count(k)). [1]

Erase range is O(log(size()) + N), where N is the length of the range. [1]

Find is logarithmic. [1]

Count is O(log(size()) + count(k)). [1]

Lower bound, upper bound, and equal range are logarithmic. [1]

Invariants

Definition of value_comp	If t1 and t2 are objects of type X::value_type and k1 and k2 are the keys associated with those objects, then a.value_comp() returns a function object such that a.value_comp()(t1, t2) is equivalent to a.key_comp()(k1, k2).
Ascending order	The elements in a Sorted Associative Container are always arranged in ascending order by key. That is, if a is a Sorted Associative Container, then is_sorted(a.begin(), a.end(), a.value_comp()) is always true.

Models

• set

• multiset

• map

• multimap

Notes

[1] This is a much stronger guarantee than the one provided by Associative Container. The guarantees in Associative Container only apply to average complexity; worst case complexity is allowed to be greater. Sorted Associative Container, however, provides an upper limit on worst case complexity.

[2] This definition is consistent with the semantics described in Associative Container. It is a stronger condition, though: if a contains no elements with the key k , then a.equal_range(k) returns an empty range that indicates the position where those elements would be if they did exist. The Associative Container requirements, however, merely state that the return value is an arbitrary empty range.

Hashed Associative Container

Category: containers

Component type: concept

Description

A Hashed Associative Container is an Associative Container whose implementation is a hash table. [1] The elements of a Hashed Associative Container are not guaranteed to be in any meaningful order; in particular, they are not sorted. The worst case complexity of most operations on Hashed Associative Containers is linear in the size of the container, but the average case complexity is constant time; this means that for applications where values are simply stored and retrieved, and where ordering is unimportant, Hashed Associative Containers are usually much faster than Sorted Associative Containers.

Refinement of

Associative Container

Associated types

The following new types are introduced, in addition to the types defined in the Associative Container requirements.

Hash function	`X::hasher`	A type that is a model of Hash Function. X::hasher 's argument type must be X::key_type.
Key equal	`X::key_equal`	A Binary Predicate whose argument type is X::key_type . An object of type key_equal returns true if its arguments are the same key, and false otherwise. X::key_equal must be an equivalence relation.

Notation

X A type that is a model of Hashed Associative Container

a Object of type X

t Object of type X::value_type

k Object of type X::key_type

p, q Object of type X::iterator

n Object of type X::size_type

h Object of type X::hasher

c Object of type X::key_equal

Definitions

A hash function for a Hashed Associative Container X is a Unary Function whose argument type is X::key_type and whose return type is size_t. A hash function must be deterministic (that is, it must always return the same value whenever it is called with the same argument), but return values of the hash function should be as uniform as possible: ideally, no two keys will hash to the same value. [2]

Elements in a Hashed Associative Container are organized into buckets. A Hashed Associative Container uses the value of the hash function to determine which bucket an element is assigned to.

The number of elements in a Hashed Associative Container divided by the number of buckets is called the load factor. A Hashed Associative Container with a small load factor is faster than one with a large load factor.

Valid expressions

In addition to the expressions defined in Associative Container, the following expressions must be valid.

Name	Expression	Return type
Default constructor	`X()X a;`
Constructor with bucket count	`X(n)X a(n);`
Constructor with hash function	`X(n, h)X a(n, h);`
Constructor with key equal	`X(n, h, k)X a(n, h, k);`
Hash function	`a.hash_funct()`	`X::hasher`
Key equal	`a.key_eq()`	`X::key_equal`
Erase key	`a.erase(k)`	`size_type`
Erase element	`a.erase(p)`	`void`
Erase range	`a.erase(p, q)`	`void`
Find	`a.find(k)`	iterator if a is mutable, otherwise const_iterator
Count	`a.count(k)`	`size_type`
Equal range	`a.equal_range(k)`	pair<iterator, iterator> if a is mutable, otherwise pair<const_iterator, const_iterator>.
Bucket count	`a.bucket_count()`	`X::size_type`
Resize	`a.resize(n)`	`void`

Expression semantics

Name	Expression	Precondition	Semantics	Postcondition
Default constructor	`X()X a;`		Creates an empty container, using hasher() as the hash function and key_equal() as the key equality function.	The size of the container is 0. The bucket count is an unspecified default value. The hash function is hasher(), and the key equality function is key_equal().
Constructor with bucket count	`X(n)X a(n);`		Creates an empty container with at least n buckets, using hasher() as the hash function and key_equal() as the key equality function.	The size of the container is 0. The bucket count is greater than or equal to n. The hash function is hasher(), and the key equality function is key_equal().
Constructor with hash function	`X(n, h)X a(n, h);`		Creates an empty container with at least n buckets, using h as the hash function and key_equal() as the key equality function.	The size of the container is 0. The bucket count is greater than or equal to n. The hash function is h, and the key equality function is key_equal().
Constructor with key equal	`X(n, h, k)X a(n, h, k);`		Creates an empty container with at least n buckets, using h as the hash function and k as the key equality function. The size of the container is 0.	The bucket count is greater than or equal to n. The hash function is h, and the key equality function is k.
Hash function	`a.hash_funct()`		Returns the hash function used by a.
Key equal	`a.key_eq()`		Returns the key equal function used by a.
Erase key	`a.erase(k)`		Destroys all elements whose key is the same as k, and removes them from a. [2]The return value is the number of elements that were erased, i.e. the old value of a.count(k).	a.size() is decremented by a.count(k). a contains no elements with key k.
Erase element	`a.erase(p)`	p is a dereferenceable iterator in a.	Destroys the element pointed to by p, and removes it from a.	a.size() is decremented by 1.
Erase range	`a.erase(p, q)`	[p, q) is a valid range in a.	Destroys the elements in the range [p,q) and removes them from a.	a.size() is decremented by the distance from i to j.
Find	`a.find(k)`		Returns an iterator pointing to an element whose key is the same as k, or a.end() if no such element exists.	Either the return value is a.end(), or else the return value has a key that is the same as k.
Count	`a.count(k)`		Returns the number of elements in a whose keys are the same as k.
Equal range	`a.equal_range(k)`		Returns a pair P such that [P.first, P.second) is a range containing all elements in a whose keys are the same as k. [3] If no elements have the same key as k , the return value is an empty range.	The distance between P.first and P.second is equal to a.count(k). If p is a dereferenceable iterator in a, then either a lies in the range [P.first, P.second), or else *a has a key that is not the same as k.
Bucket count	`a.bucket_count()`		Returns the number of buckets in a.
Resize	`a.resize(n)`		Increases the bucket count of a.	The bucket count of a will be at least n. All iterators pointing to element in a will remain valid. [3]

Complexity guarantees

The default constructor, constructor with bucket count, constructor with hash function, and constructor with key equal, are all amortized constant time.

Hash Function and Key Equal are amortized constant time.

Average complexity for Erase Key is O(count(k)). Worst case is linear in the size of the container.

Erase Element is amortized constant time.

Average complexity for Erase Range is O(N), where N is the length of the range being erased. Worse case is linear in the size of the container.

Average complexity for Find is constant time. Worst case is linear in the size of the container.

Average complexity for Equal Range is O(count(k)). Worst case is linear in the size of the container.

Average complexity for Count is O(count(k)). Worst case is linear in the size of the container.

Bucket Count is amortized constant time.

Resize is linear in the size of the container.

Models

• hash_set

• hash_map

• hash_multiset

• hash_multimap

Notes

[1] There is an extensive literature dealing with hash tables. See, for example, section 6.4 of Knuth. (D. E. Knuth, The Art of Computer Programming. Volume 3: Sorting and Searching. Addison-Wesley, 1975.)

[2] If the hash function is poor (that is, if many different keys hash to the same value) then this will hurt performance. The worst case is where every key hashes to the same value; in this case, run-time complexity of most Hashed Associative Container operations will be linear in the size of the container.

[3] Resizing does not invalidate iterators; however, it does not necessarily preserve the ordering relation between iterators. That is, if i and j are iterators that point into a Hashed Associative Container such that i comes immediately before j, then there is no guarantee that i will still come immediately before j after the container is resized. The only guarantee about about the ordering of elements is the contiguous storage invariant: elements with the same key are always adjacent to each other.

Hash Function

Categories: containers, functors

Component type: concept

Description

A Hash Function is a Unary Function that is used by Hashed Associative Containers: it maps its argument to a result of type size_t. A Hash Function must be deterministic and stateless. That is, the return value must depend only on the argument, and equal arguments must yield equal results.

The performance of a Hashed Associative Container depends crucially on its hash function. It is important for a Hash Function to minimize collisions, where a collision is defined as two different arguments that hash to the same value. It is also important that the distribution of hash values be uniform; that is, the probability that a Hash Function returns any particular value of type size_t should be roughly the same as the probability that it returns any other value. [1]

Refinement of

Unary Function

Associated types

Result type

The type returned when the Hash Function is called. The result type must be size_t.

Valid expressions

None, except for those described in the Unary Function requirements.

Invariants

Deterministic function

The return value depends only on the argument, as opposed to the past history of the Hash Function object. The return value is always the same whenever the argument is the same.

Models

• hash

Notes

[1] Note that both of these requirements make sense only in the context of some specific distribution of input values. To take a simple example, suppose that the values being hashed are the six strings "aardvark", "trombone", "history", "diamond", "forthright", and "solitude". In this case, one reasonable (and efficient) hash function would simply be the first character of each string. On the other hand, suppose that the values being hashed are "aaa0001", "aaa0010", "aaa0011", "aaa0100", "aaa0101", and "aaa0110". In that case, a different hash function would be more appropriate. This is why Hashed Associative Containers are parameterized by the hash function: no one hash function is best for all applications.

Unique Associative Container

Category: containers

Component type: concept

Description

A Unique Associative Container is an Associative Container with the property that each key in the container is unique: no two elements in a Unique Associative Container have the same key.

Refinement of

Associative Container

Associated types

None, except for those defined by Associative Container.

Notation

X A type that is a model of Unique Associative Container

a Object of type X

t Object of type X::value_type

k Object of type X::key_type

p, q Object of type X::iterator

Valid expressions

In addition to the expressions defined in Associative Container, the following expressions must be valid.

Name	Expression	Type requirements	Return type
Range constructor	`X(i, j)X a(i, j);`	i and j are Input Iterators whose value type is convertible to T [1]
Insert element	`a.insert(t)`		`pair<X::iterator, bool>`
Insert range	`a.insert(i, j)`	i and j are Input Iterators whose value type is convertible to X::value_type. [1]	`void`
Count	`a.count(k)`		`size_type`

Expression semantics

Name	Expression	Precondition	Semantics	Postcondition
Range constructor	`X(i, j)X a(i, j);`	[i,j) is a valid range.	Creates an associative container that contains all of the elements in the range [i,j) that have unique keys.	size() is less than or equal to the distance from i to j.
Insert element	`a.insert(t)`		Inserts t into a if and only if a does not already contain an element whose key is the same as the key of t. The return value is a pair P. P.first is an iterator pointing to the element whose key is the same as the key of t. P.second is a bool: it is true if t was actually inserted into a, and false if t was not inserted into a, i.e. if a already contained an element with the same key as t.	P.first is a dereferenceable iterator. (P.first) has the same key as t. The size of a is incremented by 1 if and only if P.second* is true.
Insert range	`a.insert(i, j)`	[i, j) is a valid range.	Equivalent to a.insert(t) for each object t that is pointed to by an iterator in the range [i, j). Each element is inserted into a if and only if a does not already contain an element with the same key.	The size of a is incremented by at most j – i.
Count	`a.count(k)`		Returns the number of elements in a whose keys are the same as k.	The return value is either 0 or 1.

Complexity guarantees

Average complexity for insert element is at most logarithmic.

Average complexity for insert range is at most O(N * log(size() + N)), where N is j – i.

Invariants

Uniqueness

No two elements have the same key. Equivalently, this means that for every object k of type key_type, a.count(k) returns either 0 or 1.

Models

• set

• map

• hash_set

• hash_map

Notes

Multiple Associative Container

Category: containers

Component type: concept

Description

A Multiple Associative Container is an Associative Container in which there may be more than one element with the same key. That is, it is an Associative Container that does not have the restrictions of a Unique Associative Container.

Refinement of

Associative Container

Associated types

None, except for those defined by Associative Container

Notation

X A type that is a model of Multiple Associative Container

a Object of type X

t Object of type X::value_type

k Object of type X::key_type

p, q Object of type X::iterator

Valid expressions

In addition to the expressions defined in Associative Container, the following expressions must be valid.

Name	Expression	Type requirements	Return type
Range constructor	`X(i, j)X a(i, j);`	i and j are Input Iterators whose value type is convertible to T [1]
Insert element	`a.insert(t)`		`X::iterator`
Insert range	`a.insert(i, j)`	i and j are Input Iterators whose value type is convertible to X::value_type.	`void`

Expression semantics

Name	Expression	Precondition	Semantics	Postcondition
Range constructor	`X(i, j)X a(i, j);`	[i,j) is a valid range.	Creates an associative container that contains all elements in the range [i,j).	size() is equal to the distance from i to j. Each element in [i, j) is present in the container.
Insert element	`a.insert(t)`		Inserts t into a.	The size of a is incremented by 1. The value of a.count(t) is incremented by a.
Insert range	`a.insert(i, j)`	[i, j) is a valid range.	Equivalent to a.insert(t) for each object t that is pointed to by an iterator in the range [i, j) . Each element is inserted into a.	The size of a is incremented by j – i.

Complexity guarantees

Average complexity for insert element is at most logarithmic.

Average complexity for insert range is at most O(N * log(size() + N)), where N is j – i.

Models

• multiset

• multimap

• hash_multiset

• hash_multimap

Notes

Unique Sorted Associative Container

Category: containers

Component type: concept

Description

A Unique Sorted Associative Container is a Sorted Associative Container that is also a Unique Associative Container. That is, it is a Sorted Associative Container with the property that no two elements in the container have the same key.

Refinement of

Sorted Associative Container, Unique Associative Container

Associated types

None, except for those described in the Sorted Associative Container and Unique Associative Container requirements.

Notation

X A type that is a model of Unique Sorted Associative Container

a Object of type X

t Object of type X::value_type

k Object of type X::key_type

p, q Object of type X::iterator

c Object of type X::key_compare

Valid expressions

In addition to the expressions defined in Sorted Associative Container and Unique Associative Container, the following expressions must be valid.

Name	Expression	Type requirements	Return type
Range constructor	`X(i, j)X a(i, j);`	i and j are Input Iterators whose value type is convertible to T [1].
Range constructor with compare	`X(i, j, c)X a(i, j, c);`	i and j are Input Iterators whose value type is convertible to T [1]. c is an object of type key_compare.
Insert with hint	`a.insert(p, t)`		`iterator`
Insert range	`a.insert(i, j)`	i and j are Input Iterators whose value type is convertible to X::value_type. [1]	`void`

Expression semantics

Name	Expression	Precondition	Semantics	Postcondition
Range constructor	`X(i, j)X a(i, j);`	[i,j) is a valid range.	Creates an associative container that contains all of the elements in the range [i,j) that have unique keys. The comparison object used by the container is key_compare().	size() is less than or equal to the distance from i to j.
Range constructor with compare	`X(i, j, c)X a(i, j, c);`	[i,j) is a valid range.	Creates an associative container that contains all of the elements in the range [i,j) that have unique keys. The comparison object used by the container is c.	size() is less than or equal to the distance from i to j.
Insert with hint	`a.insert(p, t)`	p is a nonsingular iterator in a.	Inserts t into a if and only if a does not already contain an element whose key is equivalent to t's key. The argument p is a hint: it points to the location where the search will begin. The return value is a dereferenceable iterator that points to the element with a key that is equivalent to that of t.	a contains an element whose key is the same as that of t. The size of a is incremented by either 1 or 0.
Insert range	`a.insert(i, j)`	[i, j) is a valid range.	Equivalent to a.insert(t) for each object t that is pointed to by an iterator in the range [i, j) . Each element is inserted into a if and only if a does not already contain an element with an equivalent key.	The size of a is incremented by at most j – i.

Complexity guarantees

The range constructor, and range constructor with compare, are in general O(N * log(N)), where N is the size of the range. However, they are linear in N if the range is already sorted by value_comp().

Insert with hint is logarithmic in general, but it is amortized constant time if t is inserted immediately before p.

Insert range is in general O(N * log(N)), where N is the size of the range. However, it is linear in N if the range is already sorted by value_comp().

Invariants

Strictly ascending order

The elements in a Unique Sorted Associative Container are always arranged in strictly ascending order by key. That is, if a is a Unique Sorted Associative Container, then is_sorted(a.begin(), a.end(), a.value_comp()) is always true . Furthermore, if i and j are dereferenceable iterators in a such that i precedes j, then a.value_comp()(*i, *j) is always true. [2]

Models

• map

• set

Notes

[2] This is a more stringent invariant than that of Sorted Associative Container. In a Sorted Associative Container we merely know that every element is less than or equal to its successor; in a Unique Sorted Associative Container, however, we know that it must be less than its successor.

Multiple Sorted Associative Container

Category: containers

Component type: concept

Description

A Multiple Sorted Associative Container is a Sorted Associative Container that is also a Multiple Associative Container. That is, it is a Sorted Associative Container

with the property that any number of elements in the container may have equivalent keys.

Refinement of

Sorted Associative Container, Multiple Associative Container

Associated types

None, except for those described in the Sorted Associative Container and Multiple Associative Container requirements.

Notation

X A type that is a model of Multiple Sorted Associative Container

a Object of type X

t Object of type X::value_type

k Object of type X::key_type

p, q Object of type X::iterator

c Object of type X::key_compare

Valid expressions

In addition to the expressions defined in Sorted Associative Container and Multiple Associative Container, the following expressions must be valid.

Name	Expression	Type requirements	Return type
Range constructor	`X(i, j)X a(i, j);`	i and j are Input Iterators whose value type is convertible to T [1].	`X`
Range constructor with compare	`X(i, j, c)X a(i, j, c);`	i and j are Input Iterators whose value type is convertible to T [1]. c is an object of type key_compare.	`X`
Insert with hint	`a.insert(p, t)`		`iterator`
Insert range	`a.insert(i, j)`	i and j are Input Iterators whose value type is convertible to X::value_type. [1]	`void`

Expression semantics

Name	Expression	Precondition	Semantics	Postcondition
Range constructor	`X(i, j)X a(i, j);`[i,j) is a valid range.	Creates an associative container that contains all of the elements in the range [i,j). The comparison object used by the container is key_compare().	size() is equal to the distance from i to j.
Range constructor with compare	`X(i, j, c)X a(i, j, c);`	[i,j) is a valid range.	Creates an associative container that contains all of the elements in the range [i,j) . The comparison object used by the container is c.	size() is equal to the distance from i to j.
Insert with hint	`a.insert(p, t)`	p is a nonsingular iterator in a.	Inserts t into a. The argument p is a hint: it points to the location where the search will begin. The return value is a dereferenceable iterator that points to the element that was just inserted.	a contains an element whose key is the same as that of t. The size of a is incremented by 1.
Insert range	`a.insert(i, j)`	[i, j) is a valid range.	Equivalent to a.insert(t) for each object t that is pointed to by an iterator in the range [i, j). Each element is inserted into a.	The size of a is incremented by j – i.

Complexity guarantees

Insert with hint is logarithmic in general, but it is amortized constant time if t is inserted immediately before p.

Insert range is in general O(N * log(N)) , where N is the size of the range. However, it is linear in N if the range is already sorted by value_comp().

Models

• multimap

• multiset

Notes

Unique Hashed Associative Container

Category: containers

Component type: concept

Description

A Unique Hashed Associative Container is a Hashed Associative Container that is also a Unique Associative Container. That is, it is a Hashed Associative Container with the property that no two elements in the container have the same key.

Refinement of

Hashed Associative Container, Unique Associative Container

Associated types

None, except for those described in the Hashed Associative Container and Unique Associative Container requirements.

Notation

X A type that is a model of Hashed Associative Container

a Object of type X

t Object of type X::value_type

k Object of type X::key_type

p, q Object of type X::iterator

n Object of type X::size_type

h Object of type X::hasher

c Object of type X::key_equal

Valid expressions

In addition to the expressions defined in Hashed Associative Container and Unique Associative Container, the following expressions must be valid.

Name	Expression	Type requirements	Return type
Range constructor	`X(i, j)X a(i, j);`	i and j are Input Iterators whose value type is convertible to T [1].	`X`
Range constructor with bucket count	`X(i, j, n)X a(i, j, n);`	i and j are Input Iterators whose value type is convertible to T [1].	`X`
Range constructor with hash function	`X(i, j, n, h)X a(i, j, n, h);`	i and j are Input Iterators whose value type is convertible to T [1].	`X`
Range constructor with key equal	`X(i, j, n, h, k)X a(i, j, n, h, k);`	i and j are Input Iterators whose value type is convertible to T [1].	`X`

Expression semantics

Name	Expression	Precondition	Semantics	Postcondition
Range constructor	`X(i, j)X a(i, j);`	[i,j) is a valid range.	Creates an associative container that contains all of the elements in the range [i,j) that have unique keys, using hasher() as the hash function and key_equal() as the key equality function.	size() is less than or equal to the distance from i to j. The bucket count is an unspecified default value. The hash function is hasher(), and the key equality function is key_equal().
Range constructor with bucket count	`X(i, j, n)X a(i, j, n);`	[i,j) is a valid range.	Creates an associative container that contains all of the elements in the range [i,j) that have unique keys, using at least n buckets, and using hasher() as the hash function and key_equal() as the key equality function.	size() is less than or equal to the distance from i to j. The bucket count is greater than or equal to n. The hash function is hasher(), and the key equality function is key_equal().
Range constructor with hash function	`X(i, j, n, h)X a(i, j, n, h);`	[i,j) is a valid range.	Creates an associative container that contains all of the elements in the range [i,j) that have unique keys, using at least n buckets, and using h as the hash function and key_equal() as the key equality function.	size() is less than or equal to the distance from i to j. The bucket count is greater than or equal to n. The hash function is h, and the key equality function is key_equal().
Range constructor with key equal	`X(i, j, n, h, k)` `X a(i, j, n, h, k);`	[i,j) is a valid range.	Creates an associative container that contains all of the elements in the range [i,j) that have unique keys, using at least n buckets, and using h as the hash function and k as the key equality function.	size() is less than or equal to the distance from i to j. The bucket count is greater than or equal to n. The hash function is h , and the key equality function is k.

Complexity guarantees

The range constructor, range constructor with bucket count, range constructor with hash function, and range constructor with key equal, are all linear in j – i.

Models

• hash_set

• hash_map

Notes

Multiple Hashed Associative Container

Category: containers

Component type: concept

Description

A Multiple Hashed Associative Container is a Hashed Associative Container that is also a Multiple Associative Container. That is, it is a Hashed Associative Container

with the property that any number of elements in the container may have the same key

Refinement of

Hashed Associative Container, Multiple Associative Container

Associated types

None, except for those described in the Hashed Associative Container and Multiple Associative Container requirements.

Notation

X A type that is a model of Hashed Associative Container

a Object of type X

t Object of type X::value_type

k Object of type X::key_type

p, q Object of type X::iterator

n Object of type X::size_type

h Object of type X::hasher

c Object of type X::key_equal

Valid expressions

In addition to the expressions defined in Hashed Associative Container and and Multiple Associative Container, the following expressions must be valid.

Name	Expression	Type requirements	Return type
Range constructor	`X(i, j)X a(i, j);`	i and j are Input Iterators whose value type is convertible to T [1].	`X`
Range constructor with bucket count	`X(i, j, n)X a(i, j, n);`	i and j are Input Iterators whose value type is convertible to T [1].	`X`
Range constructor with hash function	`X(i, j, n, h)X a(i, j, n, h);`	i and j are Input Iterators whose value type is convertible to T [1].	`X`
Range constructor with key equal	`X(i, j, n, h, k)X a(i, j, n, h, k);`	i and j are Input Iterators whose value type is convertible to T [1].	`X`

Expression semantics

Name	Expression	Precondition	Semantics	Postcondition
Range constructor	`X(i, j)X a(i, j);`	[i,j) is a valid range.	Creates an associative container that contains all elements in the range [i,j), using hasher() as the hash function and key_equal() as the key equality function.	size() is equal to the distance from i to j. The bucket count is an unspecified default value. The hash function is hasher(), and the key equality function is key_equal().
Range constructor with bucket count	`X(i, j, n)X a(i, j, n);`	[i,j) is a valid range.	Creates an associative container that contains all elements in the range [i,j), using at least n buckets, and using hasher() as the hash function and key_equal() as the key equality function.	size() is equal to the distance from i to j. The bucket count is greater than or equal to n. The hash function is hasher(), and the key equality function is key_equal().
Range constructor with hash function	`X(i, j, n, h)X a(i, j, n, h);`	[i,j) is a valid range.	Creates an associative container that contains all elements in the range [i,j), using at least n buckets, and using h as the hash function and key_equal() as the key equality function. size() is equal to the distance from i to j.	The bucket count is greater than or equal to n. The hash function is h, and the key equality function is key_equal().
Range constructor with key equal	`X(i, j, n, h, k)X a(i, j, n, h, k);`	[i,j) is a valid range.	Creates an associative container that contains all elements in the range [i,j) , using at least n buckets, and using h as the hash function and k as the key equality function.	size() is equal to the distance from i to j. The bucket count is greater than or equal to n. The hash function is h , and the key equality function is k.

Complexity guarantees

The range constructor, range constructor with bucket count, range constructor with hash function, and range constructor with key equal, are all linear in j – i.

Models

• hash_multiset

• hash_multimap

Notes

Container classes

Sequences

vector<T, Alloc>

Category: containers

Component type: type

Description

A vector is a Sequence that supports random access to elements, constant time insertion and removal of elements at the end, and linear time insertion and removal of elements at the beginning or in the middle. The number of elements in a vector may vary dynamically; memory management is automatic. Vector is the simplest of the STL container classes, and in many cases the most efficient.

Example

vector<int> V;

V.insert(V.begin(), 3);

assert(V.size() == 1 && V.capacity() >= 1 && V[0] == 3);

Definition

Defined in the standard header vector, and in the nonstandard backward-compatibility header vector.h.

Template parameters

Parameter	Description	Default
`T`	The vector's value type: the type of object that is stored in the vector.
`Alloc`	The vector 's allocator, used for all internal memory management.	`alloc`

Model of

Random Access Container, Back Insertion Sequence.

Type requirements

None, except for those imposed by the requirements of Random Access Container and Back Insertion Sequence.

Public base classes

None.

Members

Member	Where defined	Description
`value_type`	Container	The type of object, T, stored in the vector.
`pointer`	Container	Pointer to T.
`reference`	Container	Reference to T
`const_reference`	Container	Const reference to T
`size_type`	Container	An unsigned integral type.
`difference_type`	Container	A signed integral type.
`iterator`	Container	Iterator used to iterate through a vector.
`const_iterator`	Container	Const iterator used to iterate through a vector.
`reverse_iterator`	Reversible Container	Iterator used to iterate backwards through a vector.
`const_reverse_iterator`	Reversible Container	Const iterator used to iterate backwards through a vector.
`iterator begin()`	Container	Returns an iterator pointing to the beginning of the vector.
`iterator end()`	Container	Returns an iterator pointing to the end of the vector.
`const_iterator begin() const`	Container	Returns a const_iterator pointing to the beginning of the vector.
`const_iterator end() const`	Container	Returns a const_iterator pointing to the end of the vector.
`reverse_iterator rbegin()`	Reversible Container	Returns a reverse_iterator pointing to the beginning of the reversed vector.
`reverse_iterator rend()`	Reversible Container	Returns a reverse_iterator pointing to the end of the reversed vector.
`const_reverse_iterator rbegin() const`	Reversible Container	Returns a const_reverse_iterator pointing to the beginning of the reversed vector.
`const_reverse_iterator rend() const`	Reversible Container	Returns a const_reverse_iterator pointing to the end of the reversed vector.
`size_type size() const`	Container	Returns the size of the vector.
`size_type max_size() const`	Container	Returns the largest possible size of the vector.
`size_type capacity() const`	`vector`	See below.
`bool empty() const`	Container	true if the vector 's size is 0.
`reference operator[](size_type n)`	Random Access Container	Returns the n'th element.
`const_reference operator[](size_type n) const`	Random Access Container	Returns the n'th element.
`vector()`	Container	Creates an empty vector.
`vector(size_type n)`	Sequence	Creates a vector with n elements.
`vector(size_type n, const T& t)`	Sequence	Creates a vector with n copies of t.
`vector(const vector&)`	Container	The copy constructor.
`template <class InputIterator> vector(InputIterator, InputIterator)` [1]	Sequence	Creates a vector with a copy of a range.
`~vector()`	Container	The destructor.
`vector& operator=(const vector&)`	Container	The assignment operator
`void reserve(size_t)`	`vector`	See below.
`vector reference front()`	Sequence	Returns the first element.
`const_reference front() const`	Sequence	Returns the first element.
`reference back()`	Back Insertion Sequence	Returns the last element.
`const_reference back() const`	Back Insertion Sequence	Returns the last element.
`void push_back(const T&)`	Back Insertion Sequence	Inserts a new element at the end.
`void pop_back()`	Back Insertion Sequence	Removes the last element.
`void swap(vector&)`	Container	Swaps the contents of two vectors.
`iterator insert(iterator pos, const T& x)`	Sequence	Inserts x before pos.
`template <class InputIterator> void insert(iterator pos, InputIterator f, InputIterator l)` [1]	Sequence	Inserts the range [first, last) before pos.
`void insert(iterator pos, size_type n, const T& x)`	Sequence	Inserts n copies of x before pos.
`iterator erase(iterator pos)`	Sequence	Erases the element at position pos.
`iterator erase(iterator first, iterator last)`	Sequence	Erases the range [first, last)
`void clear()`	Sequence	Erases all of the elements.
`void resize(n, t = T())`	Sequence	Inserts or erases elements at the end such that the size becomes n.
`bool operator==(const vector&, const vector&)`	Forward Container	Tests two vectors for equality. This is a global function, not a member function.
`bool operator<(const vector&, const vector&)`	Forward Container	Lexicographical comparison. This is a global function, not a member function.

New members

These members are not defined in the Random Access Container and Back Insertion Sequence requirements, but are specific to vector.

Member	Description
`size_type capacity() const`	Number of elements for which memory has been allocated. capacity() is always greater than or equal to size(). [2] [3]
`void reserve(size_type n)`	If n is less than or equal to capacity(), this call has no effect. Otherwise, it is a request for allocation of additional memory. If the request is successful, then capacity() is greater than or equal to n; otherwise, capacity() is unchanged. In either case, size() is unchanged. [2] [4]

Notes

[1] This member function relies on member template functions, which at present (early 1998) are not supported by all compilers. If your compiler supports member templates, you can call this function with any type of input iterator. If your compiler does not yet support member templates, though, then the arguments must be of type const value_type*.

[2] Memory will be reallocated automatically if more than capacity() – size() elements are inserted into the vector. Reallocation does not change size(), nor does it change the values of any elements of the vector. It does, however, increase capacity(), and it invalidates [5] any iterators that point into the vector.

[3] When it is necessary to increase capacity(), vector usually increases it by a factor of two. It is crucial that the amount of growth is proportional to the current capacity() , rather than a fixed constant: in the former case inserting a series of elements into a vector is a linear time operation, and in the latter case it is quadratic.

[4] Reserve() causes a reallocation manually. The main reason for using reserve() is efficiency: if you know the capacity to which your vector must eventually grow, then it is usually more efficient to allocate that memory all at once rather than relying on the automatic reallocation scheme. The other reason for using reserve() is so that you can control the invalidation of iterators. [5]

[5] A vector's iterators are invalidated when its memory is reallocated. Additionally, inserting or deleting an element in the middle of a vector invalidates all iterators that point to elements following the insertion or deletion point. It follows that you can prevent a vector's iterators from being invalidated if you use reserve() to preallocate as much memory as the vector will ever use, and if all insertions and deletions are at the vector's end.

deque<T, Alloc>

Category: containers

Component type: type

Description

A deque [1] is very much like a vector: like vector, it is a sequence that supports random access to elements, constant time insertion and removal of elements at the end of the sequence, and linear time insertion and removal of elements in the middle.

The main way in which deque differs from vector is that deque also supports constant time insertion and removal of elements at the beginning of the sequence [2]. Additionally, deque does not have any member functions analogous to vector 's capacity() and reserve(), and does not provide any of the guarantees on iterator validity that are associated with those member functions. [3]

Example

deque<int> Q;

Q.push_back(3);

Q.push_front(1);

Q.insert(Q.begin() + 1, 2);

Q[2] = 0;

copy(Q.begin(), Q.end(), ostream_iterator<int>(cout, " "));

// The values that are printed are 1 2 0

Definition

Defined in the standard header deque, and in the nonstandard backward-compatibility header deque.h.

Template parameters

Parameter	Description	Default
`T`	The deque's value type: the type of object that is stored in the deque.
`Alloc`	The deque 's allocator, used for all internal memory management.	`alloc`

Model of

Random access container, Front insertion sequence, Back insertion sequence.

Type requirements

None, except for those imposed by the requirements of Random access container, Front insertion sequence, and Back insertion sequence.

Public base classes

None.

Members

Member	Where defined	Description
`value_type`	Container	The type of object, T, stored in the deque.
`pointer`	Container	Pointer to T.
`reference`	Container	Reference to T
`const_reference`	Container	Const reference to T
`size_type`	Container	An unsigned integral type.
`difference_type`	Container	A signed integral type.
`iterator`	Container	Iterator used to iterate through a deque.
`const_iterator`	Container	Const iterator used to iterate through a deque.
`reverse_iterator`	Reversible Container	Iterator used to iterate backwards through a deque.
`const_reverse_iterator`	Reversible Container	Const iterator used to iterate backwards through a deque.
`iterator begin()`	Container	Returns an iterator pointing to the beginning of the deque.
`iterator end()`	Container	Returns an iterator pointing to the end of the deque.
`const_iterator begin() const`	Container	Returns a const_iterator pointing to the beginning of the deque.
`const_iterator end() const`	Container	Returns a const_iterator pointing to the end of the deque.
`reverse_iterator rbegin()`	Reversible Container	Returns a reverse_iterator pointing to the beginning of the reversed deque.
`reverse_iterator rend()`	Reversible Container	Returns a reverse_iterator pointing to the end of the reversed deque.
`const_reverse_iterator rbegin() const`	Reversible Container	Returns a const_reverse_iterator pointing to the beginning of the reversed deque.
`const_reverse_iterator rend() const`	Reversible Container	Returns a const_reverse_iterator pointing to the end of the reversed deque.
`size_type size() const`	Container	Returns the size of the deque.
`size_type max_size() const`	Container	Returns the largest possible size of the deque.
`bool empty() const`	Container	true if the deque 's size is 0.
`reference operator[](size_type n)`	Random Access Container	Returns the n 'th element.
`const_reference operator[](size_type n) const`	Random Access Container	Returns the n'th element.
`deque()`	Container	Creates an empty deque.
`deque(size_type n)`	Sequence	Creates a deque with n elements.
`deque(size_type n, const T& t)`	Sequence	Creates a deque with n copies of t.
`deque(const deque&)`	Container	The copy constructor
`template <class InputIterator> deque(InputIterator f, InputIterator l)` [4]	Sequence	Creates a deque with a copy of a range.
`~deque()`	Container	The destructor.
`deque& operator=(const deque&)`	Container	The assignment operator
`reference front()`	Front Insertion Sequence	Returns the first element.
`const_reference front() const`	Front Insertion Sequence	Returns the first element.
`reference back()`	Back Insertion Sequence	Returns the last element.
`const_reference back() const`	Back Insertion Sequence	Returns the last element.
`void push_front(const T&)`	Front Insertion Sequence	Inserts a new element at the beginning.
`void push_back(const T&)`	Back Insertion Sequence	Inserts a new element at the end.
`void pop_front()`	Front Insertion Sequence	Removes the first element.
`void pop_back()`	Back Insertion Sequence	Removes the last element.
`void swap(deque&)`	Container	Swaps the contents of two deques.
`iterator insert(iterator pos, const T& x)`	Sequence	Inserts x before pos.
`template <class InputIterator> void insert(iterator pos, InputIterator f, InputIterator l)` [4]	Sequence	Inserts the range [f, l) before pos.
`void insert(iterator pos, size_type n, const T& x)`	Sequence	Inserts n copies of x before pos.
`iterator erase(iterator pos)`	Sequence	Erases the element at position pos.
`iterator erase(iterator first, iterator last)`	Sequence	Erases the range [first, last)
`void clear()`	Sequence	Erases all of the elements.
`void resize(n, t = T())`	Sequence	Inserts or erases elements at the end such that the size becomes n.
`bool operator==(const deque&, const deque&)`	Forward Container	Tests two deques for equality. This is a global function, not a member function.
`bool operator<(const deque&, const deque&)`	Forward Container	Lexicographical comparison. This is a global function, not a member function.

New members

All of deque's members are defined in the Random access container, Front insertion sequence, and Back insertion sequence requirements. Deque does not introduce any new members.

Notes

[1] The name deque is pronounced "deck", and stands for "double-ended queue." Knuth (section 2.6) reports that the name was coined by E. J. Schweppe. See section 2.2.1 of Knuth for more information about deques. (D. E. Knuth, The Art of Computer Programming. Volume 1: Fundamental Algorithms, second edition. Addison-Wesley, 1973.)

[2] Inserting an element at the beginning or end of a deque takes amortized constant time. Inserting an element in the middle is linear in n, where n is the smaller of the number of elements from the insertion point to the beginning, and the number of elements from the insertion point to the end.

[3] The semantics of iterator invalidation for deque is as follows. Insert (including push_front and push_back) invalidates all iterators that refer to a deque. Erase in the middle of a deque invalidates all iterators that refer to the deque. Erase at the beginning or end of a deque (including pop_front and pop_back) invalidates an iterator only if it points to the erased element.

[4] This member function relies on member template functions, which at present (early 1998) are not supported by all compilers. If your compiler supports member templates, you can call this function with any type of input iterator. If your compiler does not yet support member templates, though, then the arguments must either be of type const value_type* or of type deque::const_iterator.

list<T, Alloc>

Category: containers

Component type: type

Description

A list is a doubly linked list. That is, it is a Sequence that supports both forward and backward traversal, and (amortized) constant time insertion and removal of elements at the beginning or the end, or in the middle. Lists have the important property that insertion and splicing do not invalidate iterators to list elements, and that even removal invalidates only the iterators that point to the elements that are removed. The ordering of iterators may be changed (that is, list<T>::iterator might have a different predecessor or successor after a list operation than it did before), but the iterators themselves will not be invalidated or made to point to different elements unless that invalidation or mutation is explicit. [1]

Note that singly linked lists, which only support forward traversal, are also sometimes useful. If you do not need backward traversal, then slist may be more efficient than list. Definition Defined in the standard header list, and in the nonstandard backward-compatibility header list.h.

Example

list<int> L;

L.push_back(0);

L.push_front(1);

L.insert(++L.begin(), 2);

copy(L.begin(), L.end(), ostream_iterator<int>(cout, " "));

// The values that are printed are 1 2 0

Template parameters

Parameter	Description	Default
`T`	The list 's value type: the type of object that is stored in the list.
`Alloc`	The list 's allocator, used for all internal memory management.	`alloc`

Model of

Reversible Container, Front Insertion Sequence, Back Insertion Sequence.

Type requirements

None, except for those imposed by the requirements of Reversible Container, Front Insertion Sequence, and Back Insertion Sequence.

Public base classes

None.

Members

Member	Where defined	Description
`value_type`	Container	The type of object, T, stored in the list.
`pointer`	Container	Pointer to T.
`reference`	Container	Reference to T
`const_reference`	Container	Const reference to T
`size_type`	Container	An unsigned integral type.
`difference_type`	Container	A signed integral type.
`iterator`	Container	Iterator used to iterate through a list.
`const_iterator`	Container	Const iterator used to iterate through a list.
`reverse_iterator`	Reversible Container	Iterator used to iterate backwards through a list.
`const_reverse_iterator`	Reversible Container	Const iterator used to iterate backwards through a list.
`iterator begin()`	Container	Returns an iterator pointing to the beginning of the list.
`iterator end()`	Container	Returns an iterator pointing to the end of the list.
`const_iterator begin() const`	Container	Returns a const_iterator pointing to the beginning of the list.
`const_iterator end() const`	Container	Returns a const_iterator pointing to the end of the list.
`reverse_iterator rbegin()`	Reversible	Container Returns a reverse_iterator pointing to the beginning of the reversed list.
`reverse_iterator rend()`	Reversible Container	Returns a reverse_iterator pointing to the end of the reversed list.
`const_reverse_iterator rbegin() const`	Reversible Container	Returns a const_reverse_iterator pointing to the beginning of the reversed list.
`const_reverse_iterator rend() const`	Reversible Container	Returns a const_reverse_iterator pointing to the end of the reversed list.
`size_type size() const`	Container	Returns the size of the list. Note: you should not assume that this function is constant time. It is permitted to be O(N ), where N is the number of elements in the list . If you wish to test whether a list is empty, you should write L.empty() rather than L.size() == 0.
`size_type max_size() const`	Container	Returns the largest possible size of the list.
`bool empty() const`	Container	true if the list 's size is 0.
`list()`	Container	Creates an empty list.
`list(size_type n)`	Sequence	Creates a list with n elements, each of which is a copy of T().
`list(size_type n, const T& t)`	Sequence	Creates a list with n copies of t.
`list(const list&)`	Container	The copy constructor.
`template <class InputIterator> list(InputIterator f, InputIterator l)` [2]	Sequence	Creates a list with a copy of a range.
`~list()`	Container	The destructor.
`list& operator=(const list&)`	Container	The assignment operator
`reference front()`	Front Insertion Sequence	Returns the first element.
`const_reference front() const`	Front Insertion Sequence	Returns the first element.
`reference back()`	Sequence	Returns the last element.
`const_reference back() const`	Back Insertion Sequence	Returns the last element.
`void push_front(const T&)`	Front Insertion Sequence	Inserts a new element at the beginning.
`void push_back(const T&)`	Back Insertion Sequence	Inserts a new element at the end.
`void pop_front()`	Front Insertion Sequence	Removes the first element.
`void pop_back()`	Back Insertion Sequence	Removes the last element.
`void swap(list&)`	Container	Swaps the contents of two lists.
`iterator insert(iterator pos, const T& x)`	Sequence	Inserts x before pos.
`template <class InputIterator> void insert(iterator pos, InputIterator f, InputIterator l)` [2]	Sequence	Inserts the range [f, l) before pos.
`void insert(iterator pos, size_type n, const T& x)`	Sequence	Inserts n copies of x before pos.
`iterator erase(iterator pos)`	Sequence	Erases the element at position pos.
`iterator erase(iterator first, iterator last)`	Sequence	Erases the range [first, last)
`void clear()`	Sequence	Erases all of the elements.
`void resize(n, t = T())`	Sequence	Inserts or erases elements at the end such that the size becomes n.
`void splice(iterator pos, list& L)`	`list`	See below.
`void splice(iterator pos, list& L, iterator i)`	`list`	See below.
`void splice(iterator pos, list& L, iterator f, iterator l)`	`list`	See below.
`void remove(const T& value)`	`list`	See below.
`void unique()`	`list`	See below.
`void merge(list& L)`	`list`	See below.
`void sort()`	`list`	See below.
`bool operator==(const list&, const list&)`	Forward Container	Tests two lists for equality. This is a global function, not a member function.
`bool operator<(const list&, const list&)`	Forward Container	Lexicographical comparison. This is a global function, not a member function.

New members

These members are not defined in the Reversible Container, Front Insertion Sequence, and Back Insertion Sequence requirements, but are specific to list.

Function	Description
`void splice(iterator position, list<T, Alloc>& x);`	position must be a valid iterator in this, and x must be a list that is distinct from this. (That is, it is required that &x != this.) All of the elements of x are inserted before position and removed from x. All iterators remain valid, including iterators that point to elements of x. [3] This function is constant time.
`void splice(iterator position, list<T, Alloc>& x, iterator i);`	position must be a valid iterator in this, and i must be a dereferenceable iterator in x. Splice* moves the element pointed to by i from x to this, inserting it before position. All iterators remain valid, including iterators that point to elements of x. [3] If position == i* or position == ++i, this function is a null operation. This function is constant time.
`void splice(iterator position, list<T, Alloc>& x, iterator f, iterator l);`	position must be a valid iterator in this, and [first, last)* must be a valid range in x. position may not be an iterator in the range [first, last). Splice moves the elements in [first, last) from x to this , inserting them before position*. All iterators remain valid, including iterators that point to elements of x. [3] This function is constant time.
`void remove(const T& val);`	Removes all elements that compare equal to val. The relative order of elements that are not removed is unchanged, and iterators to elements that are not removed remain valid. This function is linear time: it performs exactly size() comparisons for equality.
`template<class Predicate> void remove_if( Predicate p);` [4]	Removes all elements i such that p(i) is true. The relative order of elements that are not removed is unchanged, and iterators to elements that are not removed remain valid. This function is linear time: it performs exactly size() applications of p.
`void unique();`	Removes all but the first element in every consecutive group of equal elements. The relative order of elements that are not removed is unchanged, and iterators to elements that are not removed remain valid. This function is linear time: it performs exactly size() – 1 comparisons for equality.
`template<class BinaryPredicate> void unique( BinaryPredicate p);` [4]	Removes all but the first element in every consecutive group of equivalent elements, where two elements i and j are considered equivalent if p(i, j) is true. The relative order of elements that are not removed is unchanged, and iterators to elements that are not removed remain valid. This function is linear time: it performs exactly size() – 1 comparisons for equality.
`void merge(list<T, Alloc>& x);`	Both this and x must be sorted according to operator<, and they must be distinct. (That is, it is required that &x != this.) This function removes all of x's elements and inserts them in order into this. The merge is stable; that is, if an element from this is equivalent to one from x, then the element from this will precede the one from x. All iterators to elements in this and x remain valid. This function is linear time: it performs at most size() + x.size() – 1* comparisons.
`template<class BinaryPredicate> void merge(list<T, Alloc>& x, BinaryPredicate Comp);` [4]	Comp must be a comparison function that induces a strict weak ordering (as defined in the LessThan Comparable requirements) on objects of type T, and both this and x must be sorted according to that ordering. The lists x and this must be distinct. (That is, it is required that &x != this.) This function removes all of x's elements and inserts them in order into this. The merge is stable; that is, if an element from this is equivalent to one from x, then the element from this will precede the one from x. All iterators to elements in this and x remain valid. This function is linear time: it performs at most size() + x.size() – 1 applications of Comp.
`void reverse();`	Reverses the order of elements in the list. All iterators remain valid and continue to point to the same elements. [5] This function is linear time.
`void sort();`	Sorts this according to operator<* . The sort is stable, that is, the relative order of equivalent elements is preserved. All iterators remain valid and continue to point to the same elements. [6] The number of comparisons is approximately N log N , where N is the list 's size.
`template<class BinaryPredicate> void sort(BinaryPredicate comp);` [4]	Comp must be a comparison function that induces a strict weak ordering (as defined in the LessThan Comparable requirements on objects of type T. This function sorts the list this according to Comp. The sort is stable, that is, the relative order of equivalent elements is preserved. All iterators remain valid and continue to point to the same elements. [6] The number of comparisons is approximately N log N, where N is the list*'s size.

Notes

[1] A comparison with vector is instructive. Suppose that i is a valid vector<T>::iterator. If an element is inserted or removed in a position that precedes i, then this operation will either result in i pointing to a different element than it did before, or else it will invalidate i entirely. (A vector<T>::iterator will be invalidated, for example, if an insertion requires a reallocation.) However, suppose that i and j are both iterators into a vector , and there exists some integer n such that i == j + n. In that case, even if elements are inserted into the vector and i and j point to different elements, the relation between the two iterators will still hold. A list is exactly the opposite: iterators will not be invalidated, and will not be made to point to different elements, but, for list iterators, the predecessor/successor relationship is not invariant.

[2] This member function relies on member template functions, which at present (early 1998) are not supported by all compilers. If your compiler supports member templates, you can call this function with any type of input iterator. If your compiler does not yet support member templates, though, then the arguments must either be of type const value_type* or of type list::const_iterator.

[3] A similar property holds for all versions of insert() and erase(). List<T, Alloc>::insert() never invalidates any iterators, and list<T, Alloc>::erase() only invalidates iterators pointing to the elements that are actually being erased.

[4] This member function relies on member template functions, which at present (early 1998) are not supported by all compilers. You can only use this member function if your compiler supports member templates.

[5] If L is a list, note that L.reverse() and reverse(L.begin(), L.end()) are both correct ways of reversing the list. They differ in that L.reverse() will preserve the value that each iterator into L points to but will not preserve the iterators' predecessor/successor relationships, while reverse(L.begin(), L.end()) will not preserve the value that each iterator points to but will preserve the iterators' predecessor/successor relationships. Note also that the algorithm reverse (L.begin(), L.end()) will use T 's assignment operator, while the member function L.reverse() will not.

[6] The sort algorithm works only for random access iterators . In principle, however, it would be possible to write a sort algorithm that also accepted bidirectional iterators. Even if there were such a version of sort, it would still be useful for list to have a sort member function. That is, sort is provided as a member function not only for the sake of efficiency, but also because of the property that it preserves the values that list iterators point to.

slist<T, Alloc>

Category: containers

Component type: type

Description

An slist is a singly linked list: a list where each element is linked to the next element, but not to the previous element. [1] That is, it is a Sequence that supports forward but not backward traversal, and (amortized) constant time insertion and removal of elements. Slists, like lists, have the important property that insertion and splicing do not invalidate iterators to list elements, and that even removal invalidates only the iterators that point to the elements that are removed. The ordering of iterators may be changed (that is, slist<T>::iterator might have a different predecessor or successor after a list operation than it did before), but the iterators themselves will not be invalidated or made to point to different elements unless that invalidation or mutation is explicit. [2]

The main difference between slist and list is that list's iterators are bidirectional iterators, while slist's iterators are forward iterators. This means that slist is less versatile than list; frequently, however, bidirectional iterators are unnecessary. You should usually use slist unless you actually need the extra functionality of list, because singly linked lists are smaller and faster than double linked lists.

Important performance note: like every other Sequence, slist defines the member functions insert and erase. Using these member functions carelessly, however, can result in disastrously slow programs. The problem is that insert 's first argument is an iterator pos , and that it inserts the new element(s) beforepos . This means that insert must find the iterator just before pos; this is a constant-time operation for list, since list has bidirectional iterators, but for slist it must find that iterator by traversing the list from the beginning up to pos . In other words: insert and erase are slow operations anywhere but near the beginning of the slist.

Slist provides the member functions insert_after and erase_after, which are constant time operations: you should always use insert_after and erase_after whenever possible. If you find that insert_after and erase_after aren't adequate for your needs, and that you often need to use insert and erase in the middle of the list, then you should probably use list instead of slist.

Definition

Defined in the header slist, and in the backward-compatibility header slist.h. The slist class, and the slist header, are an SGI extension; they are not part of the C++ standard.

Example

int main() {

slist<int> L;

L.push_front(0);

L.push_front(1);

L.insert_after(L.begin(), 2);

copy(L.begin(), L.end(), // The output is 1 2 0

ostream_iterator<int>(cout, " "));

cout << endl;

slist<int>::iterator back = L.previous(L.end());

back = L.insert_after(back, 3);

back = L.insert_after(back, 4);

back = L.insert_after(back, 5);

copy(L.begin(), L.end(), // The output is 1 2 0 3 4 5

ostream_iterator<int>(cout, " "));

cout << endl;

}

Template parameters

Parameter	Description	Default
`T`	The slist 's value type: the type of object that is stored in the list.
`Alloc`	The slist 's allocator, used for all internal memory management.	`alloc`

Model of

Front Insertion Sequence

Type requirements

None, except for those imposed by the requirements of Front Insertion Sequence.

Public base classes

None.

Members

Member	Where defined	Description
`value_type`	Container	The type of object, T, stored in the slist.
`pointer`	Container	Pointer to T.
`reference`	Container	Reference to T
`const_reference`	Container	Const reference to T
`size_type`	Container	An unsigned integral type.
`difference_type`	Container	A signed integral type.
`iterator`	Container	Iterator used to iterate through an slist.
`const_iterator`	Container	Const iterator used to iterate through an slist.
`iterator begin()`	Container	Returns an iterator pointing to the beginning of the slist.
`iterator end()`	Container	Returns an iterator pointing to the end of the slist.
`const_iterator begin() const`	Container	Returns a const_iterator pointing to the beginning of the slist.
`const_iterator end() const`	Container	Returns a const_iterator pointing to the end of the slist.
`size_type size() const`	Container	Returns the size of the slist. Note: you should not assume that this function is constant time. It is permitted to be O(N), where N is the number of elements in the slist. If you wish to test whether an slist is empty, you should write L.empty() rather than L.size() == 0.
`size_type max_size() const`	Container	Returns the largest possible size of the slist.
`bool empty() const`	Container	true if the slist's size is 0.
`slist()`	Container	Creates an empty slist.
`slist(size_type n)`	Sequence	Creates an slist with n elements, each of which is a copy of T().
`slist(size_type n, const T& t)`	Sequence	Creates an slist with n copies of t.
`slist(const slist&)`	Container	The copy constructor.
`template <class InputIterator> slist(InputIterator f, InputIterator l)` [3]	Sequence	Creates an slist with a copy of a range.
`~slist()`	Container	The destructor.
`slist& operator=(const slist&)`	Container	The assignment operator
`void swap(slist&)`	Container	Swaps the contents of two slists.
`reference front()`	Front Insertion Sequence	Returns the first element.
`const_reference front() const`	Front Insertion Sequence	Returns the first element.
`void push_front(const T&)`	Front Insertion Sequence	Inserts a new element at the beginning.
`void pop_front()`	Front Insertion Sequence	Removes the first element.
`iterator previous(iterator pos)`	`slist`	See below
`const_iterator previous(const_iterator pos)`	`slist`	See below
`iterator insert(iterator pos, const T& x)`	Sequence	Inserts x before pos.
`template<class InputIterator> void insert(iterator pos, InputIterator f, InputIterator l)` [3]	Sequence	Inserts the range [first, last) before pos.
`void insert(iterator pos, size_type n, const value_type& x)`	Sequence	Inserts n copies of x before pos.
`iterator erase(iterator pos)`	Sequence	Erases the element at position pos.
`iterator erase(iterator first, iterator last)`	Sequence	Erases the range [first, last)
`void clear()`	Sequence	Erases all of the elements.
`void resize(n, t = T())`	Sequence	Inserts or erases elements at the end such that the size becomes n.
`iterator insert_after(iterator pos)`	`slist`	See below.
`iterator insert_after(iterator pos, const value_type& x)`	`slist`	See below.
`template<class InputIterator> void insert_after(iterator pos, InputIterator f, InputIterator l)`	`slist`	See below.
`void insert_after(iterator pos, size_type n, const value_type& x)`	`slist`	See below.
`iterator erase_after(iterator pos)`	`slist`	See below.
`iterator erase_after(iterator before_first, iterator last)`	`slist`	See below.
`void splice(iterator position, slist& L)`	`slist`	See below.
`void splice(iterator position, slist& L, iterator i)`	`slist`	See below.
`void splice(iterator position, slist& L, iterator f, iterator l)`	`slist`	See below.
`void splice_after(iterator pos, iterator prev)`	`slist`	See below.
`void splice_after(iterator pos, iterator before_first, iterator before_last)`	`slist`	See below.
`void remove(const T& value)`	`slist`	See below.
`void unique()`	`slist`	See below.
`void merge(slist& L)`	`slist`	See below.
`void sort()`	`slist`	See below.
`bool operator==(const slist&, const slist&)`	Forward Container	Tests two slists for equality. This is a global function, not a member function.
`bool operator<(const slist&, const slist&)`	Forward Container	Lexicographical comparison. This is a global function, not a member function.

New members

These members are not defined in the Front Insertion Sequence requirements, but are specific to slist:

Function	Description
`iterator previous(iterator pos)`	pos must be a valid iterator in this. The return value is an iterator prev* such that ++prev == pos. Complexity: linear in the number of iterators in the range [begin(), pos).
`const_iterator previous(const_iterator pos)`	pos must be a valid iterator in this. The return value is an iterator prev* such that ++prev == pos. Complexity: linear in the number of iterators in the range [begin(), pos).
`iterator insert_after(iterator pos)`	pos must be a dereferenceable iterator in this. (That is, pos* may not be end().) Inserts a copy of T() immediately followingpos. The return value is an iterator that points to the new element. Complexity: constant time.
`iterator insert_after(iterator pos, const value_type& x)`	pos must be a dereferenceable iterator in this. (That is, pos* may not be end().) Inserts a copy of x immediately followingpos. The return value is an iterator that points to the new element. Complexity: constant time.
`template<class InputIterator> void insert_after(iterator pos, InputIterator f, InputIterator l)`	Inserts elements from the range [f, l) immediately followingpos. Complexity: linear in last – first.
`void insert_after(iterator pos, size_type n, const value_type& x)`	Inserts n copies of x immediately followingpos. Complexity: linear in n.
`iterator erase_after(iterator pos)`	Erases the element pointed to by the iterator followingpos. Complexity: constant time.
`iterator erase_after(iterator before_first, iterator last)`	Erases all elements in the range [before_first + 1, last). Complexity: linear in last – (before_first + 1).
`void splice(iterator position, slist<T, Alloc>& x);`	position must be a valid iterator in this, and x must be an slist that is distinct from this. (That is, it is required that &x != this.) All of the elements of x are inserted before position and removed from x. All iterators remain valid, including iterators that point to elements of x. [4] Complexity: proportional to c1 (position – begin()) + c2(x.size()), where c1 and c2 are unknown constants.
`void splice(iterator position, slist<T, Alloc>& x, iterator i);`	position must be a valid iterator in this, and i must be a dereferenceable iterator in x. Splice* moves the element pointed to by i from x to this, inserting it before position* . All iterators remain valid, including iterators that point to elements of x. [4] If position == i or position == ++i, this function is a null operation. Complexity: proportional to c1(position – begin()) + c2(i – x.begin()), where c1 and c2 are unknown constants.
`void splice(iterator position, slist<T, Alloc>& x, iterator f, iterator l);`	position must be a valid iterator in this , and [first, last)* must be a valid range in x. position may not be an iterator in the range [first, last). Splice moves the elements in [first, last) from x to this, inserting them before position. All iterators remain valid, including iterators that point to elements of x. [4] Complexity: proportional to c1(position – begin()) + c2(f – x.begin()) + c3(l – f)* , where c1, c2, and c3 are unknown constants.
`void remove(const T& val);`	Removes all elements that compare equal to val. The relative order of elements that are not removed is unchanged, and iterators to elements that are not removed remain valid. This function is linear time: it performs exactly size() comparisons for equality.
`void splice_after(iterator pos, iterator prev)`	pos must be a dereferenceable iterator in this, and prev* must be a dereferenceable iterator either in this or in some other slist. (Note: "dereferenceable iterator" implies that neither pos* nor prev may be an off-the-end iterator.) Moves the element followingprev to this, inserting it immediately afterpos*. Complexity: constant time.
`void splice_after(iterator pos, iterator before_first, iterator before_last)`	pos must be a dereferenceable iterator in this, and before_first* and before_last must be dereferenceable iterators either in this or in some other slist. (Note: "dereferenceable iterator" implies that none of these iterators may be off-the-end iterators.) Moves the elements in the range [before_first + 1, before_last + 1)* to this, inserting them immediately afterpos*. Complexity: constant time.
`template<class Predicate> void remove_if(Predicate p);` [5]	Removes all elements i such that p(i) is true. The relative order of elements that are not removed is unchanged, and iterators to elements that are not removed remain valid. This function is linear time: it performs exactly size() applications of p.
`void unique();`	Removes all but the first element in every consecutive group of equal elements. The relative order of elements that are not removed is unchanged, and iterators to elements that are not removed remain valid. This function is linear time: it performs exactly size() – 1 comparisons for equality.
`template<class BinaryPredicate> void unique(BinaryPredicate p);`[5]	Removes all but the first element in every consecutive group of equivalent elements, where two elements i and j are considered equivalent if p(i, j) is true. The relative order of elements that are not removed is unchanged, and iterators to elements that are not removed remain valid. This function is linear time: it performs exactly size() – 1 comparisons for equality.
`void merge(slist<T, Alloc>& x);`	Both this and x must be sorted according to operator<, and they must be distinct. (That is, it is required that &x != this.) This function removes all of x 's elements and inserts them in order into this. The merge is stable; that is, if an element from this is equivalent to one from x, then the element from this will precede the one from x. All iterators to elements in this and x remain valid. This function is linear time: it performs at most size() + x.size() – 1* comparisons.
`template<class BinaryPredicate> void merge(slist<T, Alloc>& x, BinaryPredicate Comp);` [5]	Comp must be a comparison function that induces a strict weak ordering (as defined in the LessThan Comparable requirements) on objects of type T, and both this and x must be sorted according to that ordering. The slists x and this must be distinct. (That is, it is required that &x != this.) This function removes all of x 's elements and inserts them in order into this. The merge is stable; that is, if an element from this is equivalent to one from x, then the element from this will precede the one from x. All iterators to elements in this and x remain valid. This function is linear time: it performs at most size() + x.size() – 1 applications of Comp.
`void reverse();`	Reverses the order of elements in the slist. All iterators remain valid and continue to point to the same elements. [6] This function is linear time.
`void sort();`	Sorts this according to operator<. The sort is stable, that is, the relative order of equivalent elements is preserved. All iterators remain valid and continue to point to the same elements. [7] The number of comparisons is approximately N log N, where N is the slist* 's size.
`template<class BinaryPredicate> void sort(BinaryPredicate comp);` [5]	Comp must be a comparison function that induces a strict weak ordering (as defined in the LessThan Comparable requirements) on objects of type T. This function sorts the slist this according to Comp. The sort is stable, that is, the relative order of equivalent elements is preserved. All iterators remain valid and continue to point to the same elements. [7] The number of comparisons is approximately N log N, where N is the slist* 's size.

Notes

[1] The lists in such languages as Common Lisp, Scheme, and ML are singly linked lists. In some programming languages, almost all data structures are represented as singly linked lists.

[2] A comparison with vector is instructive. Suppose that i is a valid vector<T>::iterator . If an element is inserted or removed in a position that precedes i , then this operation will either result in i pointing to a different element than it did before, or else it will invalidate i entirely. (A vector<T>::iterator will be invalidated, for example, if an insertion requires a reallocation.) However, suppose that i and j are both iterators into a vector, and there exists some integer n such that i == j + n. In that case, even if elements are inserted into the vector and i and j point to different elements, the relation between the two iterators will still hold. An slist is exactly the opposite: iterators will not be invalidated, and will not be made to point to different elements, but, for slist iterators, the predecessor/successor relationship is not invariant.

[3] This member function relies on member template functions, which at present (early 1998) are not supported by all compilers. If your compiler supports member templates, you can call this function with any type of input iterator. If your compiler does not yet support member templates, though, then the arguments must either be of type const value_type* or of type slist::const_iterator.

[4] A similar property holds for all versions of insert() and erase(). Slist<T, Alloc>::insert() never invalidates any iterators, and slist<T, Alloc>::erase() only invalidates iterators pointing to the elements that are actually being erased.

[5] This member function relies on member template functions, which at present (early 1998) are not supported by all compilers. You can only use this member function if your compiler supports member templates.

[6] The reverse algorithm works only for bidirectional iterators. Even if reverse were extended to work with forward iterators, however, it would still be useful to have the reverse member function: it has different iterator invalidation semantics. That is, the reverse member function preserves the value that each iterator points to. Note also that the algorithm reverse(L.begin(), L.end()) uses T 's assignment operator, but the member function L.reverse() does not.

[7] The sort algorithm works only for random access iterators. In principle, however, it would be possible to write a sort algorithm that also accepted forward iterators. Even if there were such a version of sort, it would still be useful for slist to have a sort member function. That is, sort is provided as a member function not only for the sake of efficiency, but also because of the property that it preserves the values that list iterators point to.

bit_vector

Category: containers

Component type: type

Description

A bit_vector is essentially a vector<bool>: it is a Sequence that has the same interface as vector. The main difference is that bit_vector is optimized for space efficiency. A vector always requires at least one byte per element, but a bit_vector only requires one bit per element.

Warning: the name bit_vector will be removed in a future release of the STL. The only reason that bit_vector is a separate class, instead of a template specialization of vector<bool>, is that this would require partial specialization of templates. On compilers that support partial specialization, bit_vector is a specialization of vector<bool>. The name bit_vector is a typedef. This typedef is not defined in the C++ standard, and is retained only for backward compatibility.

Example

bit_vector V(5);

V[0] = true;

V[1] = false;

V[2] = false;

V[3] = true;

V[4] = false;

for (bit_vector::iterator i = V.begin(); i < V.end(); ++i) cout << (*i ? '1' : '0');

cout << endl;

Definition

Defined in the standard header vector, and in the nonstandard backward-compatibility header bvector.h.

Template parameters

None. Bit_vector is not a class template.

Model of

Random access container, Back insertion sequence.

Type requirements

None.

Public base classes

None.

Members

Member	Where defined	Description
`value_type`	Container	The type of object stored in the bit_vector: bool
`reference`	`bit_vector`	A proxy class that acts as a reference to a single bit. See below for details.
const_reference	Container	Const reference to value_type. In bit_vector this is simply defined to be bool.
`size_type`	Container	An unsigned integral type.
`difference_type`	Container	A signed integral type.
`iterator`	Container	Iterator used to iterate through a bit_vector.
`const_iterator`	Container	Const iterator used to iterate through a bit_vector.
`reverse_iterator`	Reversible Container	Iterator used to iterate backwards through a bit_vector.
`const_reverse_iterator`	Reversible Container	Const iterator used to iterate backwards through a bit_vector.
`iterator begin()`	Container	Returns an iterator pointing to the beginning of the bit_vector.
`iterator end()`	Container	Returns an iterator pointing to the end of the bit_vector.
`const_iterator begin() const`	Container	Returns a const_iterator pointing to the beginning of the bit_vector.
`const_iterator end() const`	Container	Returns a const_iterator pointing to the end of the bit_vector.
`reverse_iterator rbegin()`	Reversible Container	Returns a reverse_iterator pointing to the beginning of the reversed bit_vector.
`reverse_iterator rend()`	Reversible Container	Returns a reverse_iterator pointing to the end of the reversed bit_vector.
`const_reverse_iterator rbegin() const`	Reversible	Container Returns a const_reverse_iterator pointing to the beginning of the reversed bit_vector.
`const_reverse_iterator rend() const`	Reversible Container	Returns a const_reverse_iterator pointing to the end of the reversed bit_vector.
`size_type size() const`	Container	Returns the number of elements in the bit_vector.
`size_type max_size() const`	Container	Returns the largest possible size of the bit_vector.
`size_type capacity() const`	`bit_vector`	See below.
`bool empty() const`	Container	true if the bit_vector 's size is 0.
`reference operator[](size_type n)`	Random Access Container	Returns the n'th element.
`const_reference operator[](size_type n) const`	Random Access Container	Returns the n'th element.
`bit_vector()`	Container	Creates an empty bit_vector.
`bit_vector(size_type n)`	Sequence	Creates a bit_vector with n elements.
`bit_vector(size_type n, bool t)`	Sequence	Creates a bit_vector with n copies of t.
`bit_vector(const bit_vector&)`	Container	The copy constructor.
`template <class InputIterator> bit_vector(InputIterator, InputIterator)` [1]	Sequence	Creates a bit_vector with a copy of a range.
`~bit_vector()`	Container	The destructor.
`bit_vector& operator=(const bit_vector&)`	Container	The assignment operator
`void reserve(size_t)`	`bit_vector`	See below.
`reference front()`	Sequence	Returns the first element.
`const_reference front() const`	Sequence	Returns the first element.
`reference back()`	Back Insertion	Sequence Returns the last element.
`const_reference back() const`	Back Insertion Sequence	Returns the last element.
`void push_back(const T&)`	Back Insertion Sequence	Inserts a new element at the end.
`void pop_back()`	Back Insertion Sequence	Removes the last element.
`void swap(bit_vector&)`	Container	Swaps the contents of two bit_vectors.
`void swap(bit_vector::reference x, bit_vector::reference y)`	`bit_vector`	See below.
`iterator insert(iterator pos, bool x)`	Sequence	Inserts x before pos.
`template <class InputIterator> void insert(iterator pos, InputIterator f, InputIterator l)` [1]	Sequence	Inserts the range [f, l) before pos.
`void insert(iterator pos, size_type n, bool x)`	Sequence	Inserts n copies of x before pos.
`void erase(iterator pos)`	Sequence	Erases the element at position pos.
`void erase(iterator first, iterator last)`	Sequence	Erases the range [first, last)
`void clear()`	Sequence	Erases all of the elements.
`bool operator==(const bit_vector&, const bit_vector&)`	Forward Container	Tests two bit_vectors for equality. This is a global function, not a member function.
`bool operator<(const bit_vector&, const bit_vector&)`	Forward Container	Lexicographical comparison. This is a global function, not a member function.

New members

These members are not defined in the Random access container and Back insertion sequence requirements, but are specific to vector.

Member	Description
`reference`	A proxy class that acts as a reference to a single bit; the reason it exists is to allow expressions like V[0] = true. (A proxy class like this is necessary, because the C++ memory model does not include independent addressing of objects smaller than one byte.) The public member functions of reference are operator bool() const, reference& operator=(bool), and void flip(). That is, reference acts like an ordinary reference: you can convert a reference to bool, assign a bool value through a reference, or flip the bit that a reference refers to.
`size_type capacity() const`	Number of bits for which memory has been allocated. capacity() is always greater than or equal to size(). [2] [3]
`void reserve(size_type n)`	If n is less than or equal to capacity(), this call has no effect. Otherwise, it is a request for the allocation of additional memory. If the request is successful, then capacity() is greater than or equal to n; otherwise, capacity() is unchanged. In either case, size() is unchanged. [2] [4]
`void swap(bit_vector::reference x, bit_vector::reference y)`	Swaps the bits referred to by x and y. This is a global function, not a member function. It is necessary because the ordinary version of swap takes arguments of type T&, and bit_vector::reference is a class, not a built-in C++ reference.

Notes

[2] Memory will be reallocated automatically if more than capacity() – size() bits are inserted into the bit_vector. Reallocation does not change size(), nor does it change the values of any bits of the bit_vector. It does, however, increase capacity(), and it invalidates [5] any iterators that point into the bit_vector.

[3] When it is necessary to increase capacity(), bit_vector usually increases it by a factor of two. It is crucial that the amount of growth is proportional to the current capacity(), rather than a fixed constant: in the former case inserting a series of bits into a bit_vector is a linear time operation, and in the latter case it is quadratic.

[4] reserve() is used to cause a reallocation manually. The main reason for using reserve() is efficiency: if you know the capacity to which your bit_vector must eventually grow, then it is probably more efficient to allocate that memory all at once rather than relying on the automatic reallocation scheme. The other reason for using reserve() is to control the invalidation of iterators. [5]

[5] A bit_vector's iterators are invalidated when its memory is reallocated. Additionally, inserting or deleting a bit in the middle of a bit_vector invalidates all iterators that point to bits following the insertion or deletion point. It follows that you can prevent a bit_vector's iterators from being invalidated if you use reserve() to preallocate as much storage as the bit_vector will ever use, and if all insertions and deletions are at the bit_vector's end.

Associative Containers

set<Key, Compare, Alloc>

Category: containers

Component type: type

Description

Set is a Sorted Associative Container that stores objects of type Key. Set is a Simple Associative Container, meaning that its value type, as well as its key type, is Key. It is also a Unique Associative Container, meaning that no two elements are the same.

Set and multiset are particularly well suited to the set algorithms includes, set_union, set_intersection, set_difference, and set_symmetric_difference. The reason for this is twofold. First, the set algorithms require their arguments to be sorted ranges, and, since set and multiset are Sorted Associative Containers, their elements are always sorted in ascending order. Second, the output range of these algorithms is always sorted, and inserting a sorted range into a set or multiset is a fast operation: the Unique Sorted Associative Container and Multiple Sorted Associative Container requirements guarantee that inserting a range takes only linear time if the range is already sorted.

Set has the important property that inserting a new element into a set does not invalidate iterators that point to existing elements. Erasing an element from a set also does not invalidate any iterators, except, of course, for iterators that actually point to the element that is being erased.

Example

struct ltstr {

bool operator()(const char* s1, const char* s2) const {

return strcmp(s1, s2) < 0;

}

};

int main() {

const int N = 6;

const char* a[N] = {"isomer", "ephemeral", "prosaic", "nugatory", "artichoke", "serif"};

const char* b[N] = {"flat", "this", "artichoke", "frigate", "prosaic", "isomer"};

set<const char*, ltstr> A(a, a + N);

set<const char*, ltstr> B(b, b + N);

set<const char*, ltstr> C;

cout << "Set A: ";

copy(A.begin(), A.end(), ostream_iterator<const char*>(cout, " "));

cout << endl;

cout << "Set B: ";

copy(B.begin(), B.end(), ostream_iterator<const char*>(cout, " "));

cout << endl;

cout << "Union: ";

set_union(A.begin(), A.end(), B.begin(), B.end(), ostream_iterator<const char*>(cout, " "), ltstr());

cout << endl;

cout << "Intersection: ";

set_intersection(A.begin(), A.end(), B.begin(), B.end(), ostream_iterator<const char*>(cout, " "), ltstr());

cout << endl;

set_difference(A.begin(), A.end(), B.begin(), B.end(), inserter(C, C.begin()), ltstr());

cout << "Set C (difference of A and B): ";

copy(C.begin(), C.end(), ostream_iterator <const char*>(cout, " "));

cout << endl;

}

Definition

Defined in the standard header set, and in the nonstandard backward-compatibility header set.h.

Template parameters

Parameter	Description	Default
`Key`	The set's key type and value type. This is also defined as set::key_type and set::value_type
`Compare`	The key comparison function, a Strict Weak Ordering whose argument type is key_type; it returns true if its first argument is less than its second argument, and false otherwise. This is also defined as set::key_compare and set::value_compare.	`less<Key>`
`Alloc`	The set 's allocator, used for all internal memory management.	`alloc`

Model of

Unique Sorted Associative Container, Simple Associative Container

Type requirements

• Key is Assignable.

• Compare is a Strict Weak Ordering whose argument type is Key.

• Alloc is an Allocator.

Public base classes

None.

Members

Member	Where defined	Description
`value_type`	Container	The type of object, T, stored in the set.
`key_type`	Associative Container	The key type associated with value_type.
`key_compare`	Sorted Associative	Container Function object that compares two keys for ordering.
`value_compare`	Sorted Associative	Container Function object that compares two values for ordering.
`pointer`	Container	Pointer to T.
`reference`	Container	Reference to T
`const_reference`	Container	Const reference to T
`size_type`	Container	An unsigned integral type.
`difference_type`	Container	A signed integral type.
`iterator`	Container	Iterator used to iterate through a set.
`const_iterator`	Container	Const iterator used to iterate through a set. (Iterator and const_iterator are the same type.)
`reverse_iterator`	Reversible Container	Iterator used to iterate backwards through a set.
`const_reverse_iterator`	Reversible Container	Const iterator used to iterate backwards through a set. (Reverse_iterator and const_reverse_iterator are the same type.)
`iterator begin() const`	Container	Returns an iterator pointing to the beginning of the set.
`iterator end() const`	Container	Returns an iterator pointing to the end of the set.
`reverse_iterator rbegin() const`	Reversible Container	Returns a reverse_iterator pointing to the beginning of the reversed set.
`reverse_iterator rend() const`	Reversible Container	Returns a reverse_iterator pointing to the end of the reversed set.
`size_type size() const`	Container	Returns the size of the set.
`size_type max_size() const`	Container	Returns the largest possible size of the set.
`bool empty() const`	Container	true if the set 's size is 0.
`key_compare key_comp() const`	Sorted Associative Container	Returns the key_compare object used by the set.
`value_compare value_comp() const`	Sorted Associative Container	Returns the value_compare object used by the set.
`set()`	Container	Creates an empty set.
`set(const key_compare& comp)`	Sorted Associative Container	Creates an empty set, using comp as the key_compare object.
`template <class InputIterator> set(InputIterator f, InputIterator l)` [1]	Unique Sorted Associative Container	Creates a set with a copy of a range.
`template <class InputIterator> set(InputIterator f, InputIterator l, const key_compare& comp)` [1]	Unique Sorted Associative Container	Creates a set with a copy of a range, using comp as the key_compare object.
`set(const set&)`	Container	The copy constructor.
`set& operator=(const set&)`	Container	The assignment operator
`void swap(set&)`	Container	Swaps the contents of two sets.
`pair<iterator, bool> insert(const value_type& x)`	Unique Associative Container	Inserts x into the set.
`iterator insert(iterator pos, const value_type& x)`	Unique Sorted Associative Container	Inserts x into the set , using pos as a hint to where it will be inserted.
`template <class InputIterator> void insert(InputIterator, InputIterator)` [1]	Unique Sorted Associative Container	Inserts a range into the set.
`void erase(iterator pos)`	Associative Container	Erases the element pointed to by pos.
`size_type erase(const key_type& k)`	Associative Container	Erases the element whose key is k.
`void erase(iterator first, iterator last)`	Associative Container	Erases all elements in a range.
`void clear()`	Associative Container	Erases all of the elements.
`iterator find(const key_type& k) const`	Associative Container	Finds an element whose key is k.
`size_type count(const key_type& k) const`	Unique Associative Container	Counts the number of elements whose key is k.
`iterator lower_bound(const key_type& k) const`	Sorted Associative Container	Finds the first element whose key is not less than k.
`iterator upper_bound(const key_type& k) const`	Sorted Associative Container	Finds the first element whose key greater than k.
`pair<iterator, iterator> equal_range(const key_type& k) const`	Sorted Associative Container	Finds a range containing all elements whose key is k.
`bool operator==(const set&, const set&)`	Forward Container	Tests two sets for equality. This is a global function, not a member function.
`bool operator<(const set&, const set&)`	Forward Container	Lexicographical comparison. This is a global function, not a member function.

New members

All of set 's members are defined in the Unique Sorted Associative Container and Simple Associative Container requirements. Set does not introduce any new members.

Notes

map<Key, Data, Compare, Alloc>

Category: containers

Component type: type

Description

Map is a Sorted Associative Container that associates objects of type Key with objects of type Data. Map is a Pair Associative Container, meaning that its value type is pair<const Key, Data>. It is also a Unique Associative Container, meaning that no two elements have the same key.

Map has the important property that inserting a new element into a map does not invalidate iterators that point to existing elements. Erasing an element from a map also does not invalidate any iterators, except, of course, for iterators that actually point to the element that is being erased.

Example

struct ltstr {

bool operator()(const char* s1, const char* s2) const {

return strcmp(s1, s2) < 0;

}

};

int main() {

map<const char*, int, ltstr> months;

months["january"] = 31;

months["february"] = 28;

months["march"] = 31;

months["april"] = 30;

months["may"] = 31;

months["june"] = 30;

months["july"] = 31;

months["august"] = 31;

months["september"] = 30;

months["october"] = 31;

months["november"] = 30;

months["december"] = 31;

cout << "june –> " << months["june"] << endl;

map<const char*, int, ltstr>::iterator cur = months.find("june");

map<const char*, int, ltstr>::iterator prev = cur;

map<const char*, int, ltstr>::iterator next = cur;

++next;

--prev;

cout << "Previous (in alphabetical order) is " << (*prev).first << endl;

cout << "Next (in alphabetical order) is " << (*next).first << endl;

}

Definition

Defined in the standard header map, and in the nonstandard backward-compatibility header map.h.

Template parameters

Parameter	Description	Default
`Key`	The map's key type. This is also defined as map::key_type.
`Data`	The map's data type. This is also defined as map::data_type.
`Compare`	The key comparison function, a Strict Weak Ordering whose argument type is key_type; it returns true if its first argument is less than its second argument, and false otherwise. This is also defined as map::key_compare.	`less<Key>`
`Alloc`	The map 's allocator, used for all internal memory management.	`alloc`

Model of

Unique Sorted Associative Container, Pair Associative Container

Type requirements

• Data is Assignable.

• Compare is a Strict Weak Ordering whose argument type is Key.

• Alloc is an Allocator.

Public base classes

None.

Members

Member	Where defined	Description
`key_type`	Associative Container	The map 's key type, Key.
`data_type`	Pair Associative Container	The type of object associated with the keys.
`value_type`	Pair Associative Container	The type of object, pair<const key_type, data_type>, stored in the map.
`key_compare`	Sorted Associative Container	Function object that compares two keys for ordering.
`value_compare`	Sorted Associative Container	Function object that compares two values for ordering.
`pointer`	Container	Pointer to T.
`reference`	Container	Reference to T
`const_reference`	Container	Const reference to T
`size_type`	Container	An unsigned integral type.
`difference_type`	Container	A signed integral type.
`iterator`	Container	Iterator used to iterate through a map. [1]
`const_iterator`	Container	Const iterator used to iterate through a map.
`reverse_iterator`	Reversible Container	Iterator used to iterate backwards through a map. [1]
`const_reverse_iterator`	Reversible Container	Const iterator used to iterate backwards through a map.
`iterator begin()`	Container	Returns an iterator pointing to the beginning of the map.
`iterator end()`	Container	Returns an iterator pointing to the end of the map.
`const_iterator begin() const`	Container	Returns a const_iterator pointing to the beginning of the map.
`const_iterator end() const`	Container	Returns a const_iterator pointing to the end of the map.
`reverse_iterator rbegin()`	Reversible Container	Returns a reverse_iterator pointing to the beginning of the reversed map.
`reverse_iterator rend()`	Reversible Container	Returns a reverse_iterator pointing to the end of the reversed map.
`const_reverse_iterator rbegin() const`	Reversible Container	Returns a const_reverse_iterator pointing to the beginning of the reversed map.
`const_reverse_iterator rend() const`	Reversible Container	Returns a const_reverse_iterator pointing to the end of the reversed map.
`size_type size() const`	Container	Returns the size of the map.
`size_type max_size() const`	Container	Returns the largest possible size of the map.
`bool empty() const`	Container	true if the map 's size is 0.
`key_compare key_comp() const`	Sorted Associative Container	Returns the key_compare object used by the map.
`value_compare value_comp() const`	Sorted Associative Container	Returns the value_compare object used by the map.
`map()`	Container	Creates an empty map.
`map(const key_compare& comp)`	Sorted Associative Container	Creates an empty map , using comp as the key_compare object.
`template <class InputIterator> map(InputIterator f, InputIterator l)` [2]	Unique Sorted Associative Container	Creates a map with a copy of a range.
`template <class InputIterator> map(InputIterator f, InputIterator l, const key_compare& comp)` [2]	Unique Sorted Associative Container	Creates a map with a copy of a range, using comp as the key_compare object.
`map(const map&)`	Container	The copy constructor.
`map& operator=(const map&)`	Container	The assignment operator
`void swap(map&)`	Container	Swaps the contents of two maps.
`pair<iterator, bool> insert(const value_type& x)`	Unique Associative Container	Inserts x into the map.
`iterator insert(iterator pos, const value_type& x)`	Unique Sorted Associative Container	Inserts x into the map, using pos as a hint to where it will be inserted.
`template <class InputIterator> void insert(InputIterator, InputIterator)` [2]	Unique Sorted Associative Container	Inserts a range into the map.
`void erase(iterator pos)`	Associative Container	Erases the element pointed to by pos.
`size_type erase(const key_type& k)`	Associative Container	Erases the element whose key is k.
`void erase(iterator first, iterator last)`	Associative Container	Erases all elements in a range.
`void clear()`	Associative Container	Erases all of the elements.
`iterator find(const key_type& k)`	Associative Container	Finds an element whose key is k.
`const_iterator find(const key_type& k) const`	Associative Container	Finds an element whose key is k.
`size_type count(const key_type& k)`	Unique Associative Container	Counts the number of elements whose key is k.
`iterator lower_bound(const key_type& k)`	Sorted Associative Container	Finds the first element whose key is not less than k.
`const_iterator lower_bound(const key_type& k) const`	Sorted Associative Container	Finds the first element whose key is not less than k.
`iterator upper_bound(const key_type& k)`	Sorted Associative Container	Finds the first element whose key greater than k.
`const_iterator upper_bound(const key_type& k) const`	Sorted Associative Container	Finds the first element whose key greater than k.
`pair<iterator, iterator> equal_range(const key_type& k)`	Sorted Associative Container	Finds a range containing all elements whose key is k.
`pair<const_iterator, const_iterator> equal_range(const key_type& k) const`	Sorted Associative Container	Finds a range containing all elements whose key is k.
`data_type& operator[](const key_type& k)` [3]	map	See below.
`bool operator==(const map&, const map&)`	Forward Container	Tests two maps for equality. This is a global function, not a member function.
`bool operator<(const map&, const map&)`	Forward Container	Lexicographical comparison. This is a global function, not a member function.

New members

These members are not defined in the Unique Sorted Associative Container and Pair Associative Container requirements, but are unique to map:

Member function	Description
`data_type& operator[](const key_type& k)` [3]	Returns a reference to the object that is associated with a particular key. If the map does not already contain such an object, operator[] inserts the default object data_type(). [3]

Notes

[1] Map::iterator is not a mutable iterator, because map::value_type is not Assignable. That is, if i is of type map::iterator and p is of type map::value_type, then *i = p is not a valid expression. However, map::iterator isn't a constant iterator either, because it can be used to modify the object that it points to. Using the same notation as above, (*i).second = p is a valid expression. The same point applies to map::reverse_iterator.

[3] Since operator[] might insert a new element into the map, it can't possibly be a const member function. Note that the definition of operator[] is extremely simple: m[k] is equivalent to (*((m.insert(value_type(k, data_type()))).first)).second. Strictly speaking, this member function is unnecessary: it exists only for convenience.

multiset<Key, Compare, Alloc>

Category: containers

Component type: type

Description

Multiset is a Sorted Associative Container that stores objects of type Key. Multiset is a Simple Associative Container, meaning that its value type, as well as its key type, is Key. It is also a Multiple Associative Container, meaning that two or more elements may be identical.

Multiset has the important property that inserting a new element into a multiset does not invalidate iterators that point to existing elements. Erasing an element from a multiset also does not invalidate any iterators, except, of course, for iterators that actually point to the element that is being erased.

Example

int main() {

const int N = 10;

int a[N] = {4, 1, 1, 1, 1, 1, 0, 5, 1, 0};

int b[N] = {4, 4, 2, 4, 2, 4, 0, 1, 5, 5};

multiset<int> A(a, a + N);

multiset<int> B(b, b + N);

multiset<int> C;

cout << "Set A: ";

copy(A.begin(), A.end(), ostream_iterator<int>(cout, " "));

cout << endl;

cout << "Set B: ";

copy(B.begin(), B.end(), ostream_iterator<int>(cout, " "));

cout << endl;

cout << "Union: ";

set_union(A.begin(), A.end(), B.begin(), B.end(), ostream_iterator<int>(cout, " "));

cout << endl;

cout << "Intersection: ";

set_intersection(A.begin(), A.end(), B.begin(), B.end(), ostream_iterator<int>(cout, " "));

cout << endl;

set_difference(A.begin(), A.end(), B.begin(), B.end(), inserter(C, C.begin()));

cout << "Set C (difference of A and B): ";

copy(C.begin(), C.end(), ostream_iterator<int>(cout, " "));

cout << endl;

}

Definition

Defined in the standard header set, and in the nonstandard backward-compatibility header multiset.h.

Template parameters

Parameter	Description	Default
`Key`	The set's key type and value type. This is also defined as multiset::key_type and multiset::value_type
`Compare`	The key comparison function, a Strict Weak Ordering whose argument type is key_type; it returns true if its first argument is less than its second argument, and false otherwise. This is also defined as multiset::key_compare and multiset::value_compare.	`less<Key>`
`Alloc`	The multiset 's allocator, used for all internal memory management.	`alloc`

Model of

Multiple Sorted Associative Container, Simple Associative Container

Type requirements

• Key is Assignable.

• Compare is a Strict Weak Ordering whose argument type is Key.

• Alloc is an Allocator.

Public base classes

None.

Members

Member	Where defined	Description
`value_type`	Container	The type of object, T, stored in the multiset.
`key_type`	Associative Container	The key type associated with value_type.
`key_compare`	Sorted Associative Container	Function object that compares two keys for ordering.
`value_compare`	Sorted Associative Container	Function object that compares two values for ordering.
`pointer`	Container	Pointer to T.
`reference`	Container	Reference to T
`const_reference`	Container	Const reference to T
`size_type`	Container	An unsigned integral type.
`difference_type`	Container	A signed integral type.
`iterator`	Container	Iterator used to iterate through a multiset.
`const_iterator`	Container	Const iterator used to iterate through a multiset. (Iterator and const_iterator are the same type.)
`reverse_iterator`	Reversible Container	Iterator used to iterate backwards through a multiset.
`const_reverse_iterator`	Reversible Container	Const iterator used to iterate backwards through a multiset. (Reverse_iterator and const_reverse_iterator are the same type.)
`iterator begin() const`	Container	Returns an iterator pointing to the beginning of the multiset.
`iterator end() const`	Container	Returns an iterator pointing to the end of the multiset.
`reverse_iterator rbegin() const`	Reversible Container	Returns a reverse_iterator pointing to the beginning of the reversed multiset.
`reverse_iterator rend() const`	Reversible Container	Returns a reverse_iterator pointing to the end of the reversed multiset.
`size_type size() const`	Container	Returns the size of the multiset.
`size_type max_size() const`	Container	Returns the largest possible size of the multiset.
`bool empty() const`	Container	true if the multiset 's size is 0.
`key_compare key_comp() const`	Sorted Associative Container	Returns the key_compare object used by the multiset.
`value_compare value_comp() const`	Sorted Associative Container	Returns the value_compare object used by the multiset.
`multiset()`	Container	Creates an empty multiset.
`multiset(const key_compare& comp)`	Sorted Associative Container	Creates an empty multiset, using comp as the key_compare object.
`template <class InputIterator> multiset(InputIterator f, InputIterator l)` [1]	Multiple Sorted Associative Container	Creates a multiset with a copy of a range.
`template <class InputIterator> multiset(InputIterator f, InputIterator l, const key_compare& comp)` [1]	Multiple Sorted Associative Container	Creates a multiset with a copy of a range, using comp as the key_compare object.
`multiset(const multiset&)`	Container	The copy constructor.
`multiset& operator=(const multiset&)`	Container	The assignment operator
`void swap(multiset&)`	Container	Swaps the contents of two multisets.
`iterator insert(const value_type& x)`	Multiple Associative Container	Inserts x into the multiset.
`iterator insert(iterator pos, const value_type& x)`	Multiple Sorted Associative Container	Inserts x into the multiset, using pos as a hint to where it will be inserted.
`template <class InputIterator> void insert(InputIterator, InputIterator)` [1]	Multiple Sorted Associative Container	Inserts a range into the multiset.
`void erase(iterator pos)`	Associative Container	Erases the element pointed to by pos.
`size_type erase(const key_type& k)`	Associative Container	Erases the element whose key is k.
`void erase(iterator first, iterator last)`	Associative Container	Erases all elements in a range.
`void clear()`	Associative Container	Erases all of the elements.
`iterator find(const key_type& k) const`	Associative Container	Finds an element whose key is k.
`size_type count(const key_type& k) const`	Associative Container	Counts the number of elements whose key is k.
`iterator lower_bound(const key_type& k) const`	Sorted Associative Container	Finds the first element whose key is not less than k.
`iterator upper_bound(const key_type& k) const`	Sorted Associative Container	Finds the first element whose key greater than k.
`pair<iterator, iterator> equal_range(const key_type& k) const`	Sorted Associative Container	Finds a range containing all elements whose key is k.
`bool operator==(const multiset&, const multiset&)`	Forward Container	Tests two multisets for equality. This is a global function, not a member function.
`bool operator<(const multiset&, const multiset&)`	Forward Container	Lexicographical comparison. This is a global function, not a member function.

New members

All of multiset's members are defined in the Multiple Sorted Associative Container and Simple Associative Container requirements. Multiset does not introduce any new members.

Notes

multimap<Key, Data, Compare, Alloc>

Category: containers

Component type: type

Description

Multimap is a Sorted Associative Container that associates objects of type Key with objects of type Data. multimap is a Pair Associative Container, meaning that its value type is pair<const Key, Data>. It is also a Multiple Associative Container, meaning that there is no limit on the number of elements with the same key.

Multimap has the important property that inserting a new element into a multimap does not invalidate iterators that point to existing elements. Erasing an element from a multimap also does not invalidate any iterators, except, of course, for iterators that actually point to the element that is being erased.

Example

struct ltstr {

bool operator()(const char* s1, const char* s2) const {

return strcmp(s1, s2) < 0;

}

};

int main() {

multimap<const char*, int, ltstr> m;

m.insert(pair<const char* const, int>("a", 1));

m.insert(pair<const char* const, int>("c", 2));

m.insert(pair<const char* const, int>("b", 3));

m.insert(pair<const char* const, int>("b", 4));

m.insert(pair<const char* const, int>("a", 5));

m.insert(pair<const char* const, int>("b", 6));

cout << "Number of elements with key a: " << m.count("a") << endl;

cout << "Number of elements with key b: " << m.count("b") << endl;

cout << "Number of elements with key c: " << m.count("c") << endl;

cout << "Elements in m: " << endl;

for (multimap<const char*, int, ltstr>::iterator it = m.begin(); it != m.end(); ++it)

cout << " [" << (*it).first << ", " << (*it).second << "]" << endl;

}

Definition

Defined in the standard header map, and in the nonstandard backward-compatibility header multimap.h.

Template parameters

Parameter	Description	Default
`Key`	The multimap's key type. This is also defined as multimap::key_type.
`Data`	The multimap's data type. This is also defined as multimap::data_type.
`Compare`	The key comparison function, a Strict Weak Ordering whose argument type is key_type; it returns true if its first argument is less than its second argument, and false otherwise. This is also defined as multimap::key_compare.	`less<Key>`
`Alloc`	The multimap 's allocator, used for all internal memory management.	`alloc`

Model of

Multiple Sorted Associative Container, Pair Associative Container

Type requirements

• Data is Assignable.

• Compare is a Strict Weak Ordering whose argument type is Key.

• Alloc is an Allocator.

Public base classes

None.

Members

Member	Where defined	Description
`key_type`	Associative Container	The multimap 's key type, Key.
`data_type`	Pair Associative Container	The type of object associated with the keys.
`value_type`	Pair Associative Container	The type of object, pair<const key_type, data_type>, stored in the multimap.
`key_compare`	Sorted Associative Container	Function object that compares two keys for ordering.
`value_compare`	Sorted Associative Container	Function object that compares two values for ordering.
`pointer`	Container	Pointer to T.
`reference`	Container	Reference to T
`const_reference`	Container	Const reference to T
`size_type`	Container	An unsigned integral type.
`difference_type`	Container	A signed integral type.
`iterator`	Container	Iterator used to iterate through a multimap. [1]
`const_iterator`	Container	Const iterator used to iterate through a multimap.
`reverse_iterator`	Reversible Container	Iterator used to iterate backwards through a multimap. [1]
`const_reverse_iterator`	Reversible Container	Const iterator used to iterate backwards through a multimap.
`iterator begin()`	Container	Returns an iterator pointing to the beginning of the multimap.
`iterator end()`	Container	Returns an iterator pointing to the end of the multimap.
`const_iterator begin() const`	Container	Returns a const_iterator pointing to the beginning of the multimap.
`const_iterator end() const`	Container	Returns a const_iterator pointing to the end of the multimap.
`reverse_iterator rbegin()`	Reversible Container	Returns a reverse_iterator pointing to the beginning of the reversed multimap.
`reverse_iterator rend()`	Reversible Container	Returns a reverse_iterator pointing to the end of the reversed multimap.
`const_reverse_iterator rbegin() const`	Reversible Container	Returns a const_reverse_iterator pointing to the beginning of the reversed multimap.
`const_reverse_iterator rend() const`	Reversible Container	Returns a const_reverse_iterator pointing to the end of the reversed multimap.
`size_type size() const`	Container	Returns the size of the multimap.
`size_type max_size() const`	Container	Returns the largest possible size of the multimap.
`bool empty() const`	Container	true if the multimap 's size is 0.
`key_compare key_comp() const`	Sorted Associative Container	Returns the key_compare object used by the multimap.
`value_compare value_comp() const`	Sorted Associative Container	Returns the value_compare object used by the multimap.
`multimap()`	Container	Creates an empty multimap.
`multimap(const key_compare& comp)`	Sorted Associative Container	Creates an empty multimap, using comp as the key_compare object.
`template <class InputIterator> multimap(InputIterator f, InputIterator l)` [2]	Multiple Sorted Associative Container	Creates a multimap with a copy of a range.
`template <class InputIterator> multimap(InputIterator f, InputIterator l, const key_compare& comp)` [2]	Multiple Sorted Associative Container	Creates a multimap with a copy of a range, using comp as the key_compare object.
`multimap(const multimap&)`	Container	The copy constructor.
`multimap& operator=(const multimap&)`	Container	The assignment operator
`void swap(multimap&)`	Container	Swaps the contents of two multimaps.
`iterator insert(const value_type& x)`	Multiple Associative Container	Inserts x into the multimap.
`iterator insert(iterator pos, const value_type& x)`	Multiple Sorted Associative Container	Inserts x into the multimap, using pos as a hint to where it will be inserted.
`template <class InputIterator> void insert(InputIterator, InputIterator)` [2]	Multiple Sorted Associative Container	Inserts a range into the multimap.
`void erase(iterator pos)`	Associative Container	Erases the element pointed to by pos.
`size_type erase(const key_type& k)`	Associative Container	Erases the element whose key is k.
`void erase(iterator first, iterator last)`	Associative Container	Erases all elements in a range.
`void clear()`	Associative Container	Erases all of the elements.
`iterator find(const key_type& k)`	Associative Container	Finds an element whose key is k.
`const_iterator find(const key_type& k) const`	Associative Container	Finds an element whose key is k.
`size_type count(const key_type& k)`	Associative Container	Counts the number of elements whose key is k.
`iterator lower_bound(const key_type& k)`	Sorted Associative Container	Finds the first element whose key is not less than k.
`const_iterator lower_bound(const key_type& k) const`	Sorted Associative Container	Finds the first element whose key is not less than k.
`iterator upper_bound(const key_type& k)`	Sorted Associative Container	Finds the first element whose key greater than k.
`const_iterator upper_bound(const key_type& k) const`	Sorted Associative Container	Finds the first element whose key greater than k.
`pair<iterator, iterator> equal_range(const key_type& k)`	Sorted Associative Container	Finds a range containing all elements whose key is k.
`pair<const_iterator, const_iterator> equal_range(const key_type& k) const`	Sorted Associative Container	Finds a range containing all elements whose key is k.
`bool operator==(const multimap&, const multimap&)`	Forward Container	Tests two multimaps for equality. This is a global function, not a member function.
`bool operator<(const multimap&, const multimap&)`	Forward Container	Lexicographical comparison. This is a global function, not a member function.

New members

All of multimap 's members are defined in the Multiple Sorted Associative Container and Pair Associative Container requirements. Multimap does not introduce any new members.

Notes

[1] Multimap::iterator is not a mutable iterator, because multimap::value_type is not Assignable. That is, if i is of type multimap::iterator and p is of type multimap::value_type, then *i = p is not a valid expression. However, multimap::iterator isn't a constant iterator either, because it can be used to modify the object that it points to. Using the same notation as above, (*i).second = p is a valid expression. The same point applies to multimap::reverse_iterator.

hash_set<Key, HashFcn, EqualKey, Alloc>

Category: containers

Component type: type

Description

Hash_set is a Hashed Associative Container that stores objects of type Key. Hash_set is a Simple Associative Container, meaning that its value type, as well as its key type, is Key. It is also a Unique Associative Container, meaning that no two elements compare equal using the Binary Predicate EqualKey.

Hash_set is useful in applications where it is important to be able to search for an element quickly. If it is important for the elements to be in a particular order, however, then set is more appropriate.

Example

struct eqstr {

bool operator()(const char* s1, const char* s2) const {

return strcmp(s1, s2) == 0;

}

};

void lookup(const hash_set<const char*, hash<const char*>, eqstr>& Set, const char* word) {

hash_set<const char*, hash<const char*>, eqstr>::const_iterator it = Set.find(word);

cout << word << ": " << (it != Set.end() ? "present" : "not present") << endl;

}

int main() {

hash_set<const char*, hash<const char*>, eqstr> Set;

Set.insert("kiwi");

Set.insert("plum");

Set.insert("apple");

Set.insert("mango");

Set.insert("apricot");

Set.insert("banana");

lookup(Set, "mango");

lookup(Set, "apple");

lookup(Set, "durian");

}

Definition

Defined in the header hash_set, and in the backward-compatibility header hash_set.h. This class is an SGI extension; it is not part of the C++ standard.

Template parameters

Parameter	Description	Default
`Key`	The hash_set's key type and value type. This is also defined as hash_set::key_type and hash_set::value_type
`HashFcn`	The Hash Function used by the hash_set. This is also defined as hash_set::hasher.	`hash<Key>`
`EqualKey`	The hash_set's key equality function: a binary predicate that determines whether two keys are equal. This is also defined as hash_set::key_equal.	`equal_to<Key>`
`Alloc`	The hash_set 's allocator, used for all internal memory management.	`alloc`

Model of

Unique Hashed Associative Container, Simple Associative Container

Type requirements

• Key is Assignable.

• EqualKey is a Binary Predicate whose argument type is Key.

• EqualKey is an equivalence relation.

• Alloc is an Allocator.

Public base classes

None.

Members

Member	Where defined	Description
`value_type`	Container	The type of object, T, stored in the hash_set.
`key_type`	Associative Container	The key type associated with value_type.
`hasher`	Hashed Associative Container	The hash_set's Hash Function.
`key_equal`	Hashed Associative Container	Function object that compares keys for equality.
`pointer`	Container	Pointer to T.
`reference`	Container	Reference to T
`const_reference`	Container	Const reference to T
`size_type`	Container	An unsigned integral type.
`difference_type`	Container	A signed integral type.
`iterator`	Container	Iterator used to iterate through a hash_set.
`const_iterator`	Container	Const iterator used to iterate through a hash_set. (Iterator and const_iterator are the same type.)
`iterator begin() const`	Container	Returns an iterator pointing to the beginning of the hash_set.
`iterator end() const`	Container	Returns an iterator pointing to the end of the hash_set.
`size_type size() const`	Container	Returns the size of the hash_set.
`size_type max_size() const`	Container	Returns the largest possible size of the hash_set.
`bool empty() const`	Container	true if the hash_set 's size is 0.
`size_type bucket_count() const`	Hashed Associative Container	Returns the number of buckets used by the hash_set.
`void resize(size_type n)`	Hashed Associative Container	Increases the bucket count to at least n.
`hasher hash_funct() const`	Hashed Associative Container	Returns the hasher object used by the hash_set.
`key_equal key_eq() const`	Hashed Associative Container	Returns the key_equal object used by the hash_set.
`hash_set()`	Container	Creates an empty hash_set.
`hash_set(size_type n)`	Hashed Associative Container	Creates an empty hash_set with at least n buckets.
`hash_set(size_type n, const hasher& h)`	Hashed Associative Container	Creates an empty hash_set with at least n buckets, using h as the hash function.
`hash_set(size_type n, const hasher& h, const key_equal& k)`	Hashed Associative Container	Creates an empty hash_set with at least n buckets, using h as the hash function and k as the key equal function.
`template <class InputIterator> hash_set(InputIterator f, InputIterator l)` [1]	Unique Hashed Associative Container	Creates a hash_set with a copy of a range.
`template <class InputIterator> hash_set(InputIterator f, InputIterator l, size_type n)` [1]	Unique Hashed Associative Container	Creates a hash_set with a copy of a range and a bucket count of at least n.
`template <class InputIterator> hash_set(InputIterator f, InputIterator l, size_type n, const hasher& h)` [1]	Unique Hashed Associative Container	Creates a hash_set with a copy of a range and a bucket count of at least n, using h as the hash function.
`hash_set(InputIterator f, InputIterator l, size_type n, const hasher& h, const key_equal& k)` [1]	Unique Hashed Associative Container	Creates a hash_set with a copy of a range and a bucket count of at least n, using h as the hash function and k as the key equal function.
`hash_set(const hash_set&)`	Container	The copy constructor.
`hash_set& operator=(const hash_set&)`	Container	The assignment operator
`void swap(hash_set&)`	Container	Swaps the contents of two hash_sets.
`pair<iterator, bool> insert(const value_type& x)`	Unique Associative Container	Inserts x into the hash_set.
`template <class InputIterator> void insert(InputIterator f, InputIterator l)` [1]	Unique Associative Container	Inserts a range into the hash_set.
`void erase(iterator pos)`	Associative Container	Erases the element pointed to by pos.
`size_type erase(const key_type& k)`	Associative Container	Erases the element whose key is k.
`void erase(iterator first, iterator last)`	Associative Container	Erases all elements in a range.
`void clear()`	Associative Container	Erases all of the elements.
`iterator find(const key_type& k) const`	Associative Container	Finds an element whose key is k.
`size_type count(const key_type& k) const`	Unique Associative Container	Counts the number of elements whose key is k.
`pair<iterator, iterator> equal_range(const key_type& k) const`	Associative Container	Finds a range containing all elements whose key is k.
`bool operator==(const hash_set&, const hash_set&)`	Hashed Associative Container	Tests two hash_sets for equality. This is a global function, not a member function.

New members

All of hash_set's members are defined in the Unique Hashed Associative Container and Simple Associative Container requirements. Hash_set does not introduce any new members.

Notes

hash_map<Key, Data, HashFcn, EqualKey, Alloc>

Category: containers

Component type: type

Description

Hash_map is a Hashed Associative Container that associates objects of type Key with objects of type Data. Hash_map is a Pair Associative Container, meaning that its value type is pair<const Key, Data>. It is also a Unique Associative Container, meaning that no two elements have keys that compare equal using EqualKey.

Looking up an element in a hash_map by its key is efficient, so hash_map is useful for "dictionaries" where the order of elements is irrelevant. If it is important for the elements to be in a particular order, however, then map is more appropriate.

Example

struct eqstr {

bool operator()(const char* s1, const char* s2) const {

return strcmp(s1, s2) == 0;

}

};

int main() {

hash_map<const char*, int, hash<const char*>, eqstr> months;

months["january"] = 31;

months["february"] = 28;

months["march"] = 31;

months["april"] = 30;

months["may"] = 31;

months["june"] = 30;

months["july"] = 31;

months["august"] = 31;

months["september"] = 30;

months["october"] = 31;

months["november"] = 30;

months["december"] = 31;

cout << "september –> " << months["september"] << endl;

cout << "april –> " << months["april"] << endl;

cout << "june –> " << months["june"] << endl;

cout << "november –> " << months["november"] << endl;

}

Definition

Defined in the header hash_map, and in the backward-compatibility header hash_map.h. This class is an SGI extension; it is not part of the C++ standard.

Template parameters

Parameter	Description	Default
`Key`	The hash_map's key type. This is also defined as hash_map::key_type.
`Data`	The hash_map's data type. This is also defined as hash_map::data_type.
`HashFcn`	The hash function used by the hash_map. This is also defined as hash_map::hasher.	`hash<Key>`
`EqualKey`	The hash_map key equality function: a binary predicate that determines whether two keys are equal. This is also defined as hash_map::key_equal.	`equal_to<Key>`
`Alloc`	The hash_map's allocator, used for all internal memory management.	`alloc`

Model of

Unique Hashed Associative Container, Pair Associative Container

Type requirements

• Key is Assignable.

• EqualKey is a Binary Predicate whose argument type is Key.

• EqualKey is an equivalence relation.

• Alloc is an Allocator.

Public base classes

None.

Members

Member	Where defined	Description
`key_type`	Associative Container	The hash_map's key type, Key.
`data_type`	Pair Associative Container	The type of object associated with the keys.
`value_type`	Pair Associative Container	The type of object, pair<const key_type, data_type>, stored in the hash_map.
`hasher`	Hashed Associative Container	The hash_map's hash function.
`key_equal`	Hashed Associative Container	Function object that compares keys for equality.
`pointer`	Container	Pointer to T.
`reference`	Container	Reference to T
`const_reference`	Container	Const reference to T
`size_type`	Container	An unsigned integral type.
`difference_type`	Container	A signed integral type.
`iterator`	Container	Iterator used to iterate through a hash_map. [1]
`const_iterator`	Container	Const iterator used to iterate through a hash_map.
`iterator begin()`	Container	Returns an iterator pointing to the beginning of the hash_map.
`iterator end()`	Container	Returns an iterator pointing to the end of the hash_map.
`const_iterator begin() const`	Container	Returns an const_iterator pointing to the beginning of the hash_map.
`const_iterator end() const`	Container	Returns an const_iterator pointing to the end of the hash_map.
`size_type size() const`	Container	Returns the size of the hash_map.
`size_type max_size() const`	Container	Returns the largest possible size of the hash_map.
`bool empty() const`	Container	true if the hash_map's size is 0.
`size_type bucket_count() const`	Hashed Associative Container	Returns the number of buckets used by the hash_map.
`void resize(size_type n)`	Hashed Associative Container	Increases the bucket count to at least n.
`hasher hash_funct() const`	Hashed Associative Container	Returns the hasher object used by the hash_map.
`key_equal key_eq() const`	Hashed Associative Container	Returns the key_equal object used by the hash_map.
`hash_map()`	Container	Creates an empty hash_map.
`hash_map(size_type n)`	Hashed Associative Container	Creates an empty hash_map with at least n buckets.
`hash_map(size_type n, const hasher& h)`	Hashed Associative Container	Creates an empty hash_map with at least n buckets, using h as the hash function.
`hash_map(size_type n, const hasher& h, const key_equal& k)`	Hashed Associative Container	Creates an empty hash_map with at least n buckets, using h as the hash function and k as the key equal function.
`template <class InputIterator> hash_map(InputIterator f, InputIterator l)` [2]	Unique Hashed Associative Container	Creates a hash_map with a copy of a range.
`template <class InputIterator> hash_map(InputIterator f, InputIterator l, size_type n)` [2]	Unique Hashed Associative Container	Creates a hash_map with a copy of a range and a bucket count of at least n.
`template <class InputIterator> hash_map(InputIterator f, InputIterator l, size_type n, const hasher& h)` [2]	Unique Hashed Associative Container	Creates a hash_map with a copy of a range and a bucket count of at least n , using h as the hash function.
`template <class InputIterator> hash_map(InputIterator f, InputIterator l, size_type n, const hasher& h, const key_equal& k)` [2]	Unique Hashed Associative Container	Creates a hash_map with a copy of a range and a bucket count of at least n , using h as the hash function and k as the key equal function.
`hash_map(const hash_map&)`	Container	The copy constructor.
`hash_map& operator=(const hash_map&)`	Container	The assignment operator
`void swap(hash_map&)`	Container	Swaps the contents of two hash_maps.
`pair<iterator, bool> insert(const value_type& x)`	Unique Associative Container	Inserts x into the hash_map.
`template <class InputIterator> void insert(InputIterator f, InputIterator l)` [2]	Unique Associative Container	Inserts a range into the hash_map.
`void erase(iterator pos)`	Associative Container	Erases the element pointed to by pos.
`size_type erase(const key_type& k)`	Associative Container	Erases the element whose key is k.
`void erase(iterator first, iterator last)`	Associative Container	Erases all elements in a range.
`void clear()`	Associative Container	Erases all of the elements.
`const_iterator find(const key_type& k) const`	Associative Container	Finds an element whose key is k.
`iterator find(const key_type& k)`	Associative Container	Finds an element whose key is k.
`size_type count(const key_type& k) const`	Unique Associative Container	Counts the number of elements whose key is k.
`pair<const_iterator, const_iterator> equal_range(const key_type& k) const`	Associative Container	Finds a range containing all elements whose key is k.
`pair<iterator, iterator> equal_range(const key_type& k)`	Associative Container	Finds a range containing all elements whose key is k.
`data_type& operator[](const key_type& k)` [3]	`hash_map`	See below.
`bool operator==(const hash_map&, const hash_map&)`	Hashed Associative Container	Tests two hash_maps for equality. This is a global function, not a member function.

New members

These members are not defined in the Unique Hashed Associative Container and Pair Associative Container requirements, but are specific to hash_map.

Member	Description
`data_type& operator[](const key_type& k)` [3]	Returns a reference to the object that is associated with a particular key. If the hash_map does not already contain such an object, operator[] inserts the default object data_type(). [3]

Notes

[1] Hash_map::iterator is not a mutable iterator, because hash_map::value_type is not Assignable. That is, if i is of type hash_map::iterator and p is of type hash_map::value_type, then *i = p is not a valid expression. However, hash_map::iterator isn't a constant iterator either, because it can be used to modify the object that it points to. Using the same notation as above, (*i).second = p is a valid expression.

[3] Since operator[] might insert a new element into the hash_map, it can't possibly be a const member function. Note that the definition of operator[] is extremely simple: m[k] is equivalent to (*((m.insert(value_type(k, data_type()))).first)).second. Strictly speaking, this member function is unnecessary: it exists only for convenience.

hash_multiset<Key, HashFcn, EqualKey, Alloc>

Category: containers

Component type: type

Description

Hash_multiset is a Hashed Associative Container that stores objects of type Key. Hash_multiset is a simple associative container, meaning that its value type, as well as its key type, is Key. It is also a Multiple Associative Container, meaning that two or more elements may compare equal using the Binary Predicate EqualKey.

Hash_multiset is useful in applications where it is important to be able to search for an element quickly. If it is important for the elements to be in a particular order, however, then multiset is more appropriate.

Example

struct eqstr {

bool operator()(const char* s1, const char* s2) const {

return strcmp(s1, s2) == 0;

}

};

void lookup(const hash_multiset<const char*, hash<const char*>, eqstr>& Set, const char* word) {

int n_found = Set.count(word);

cout << word << ": " << n_found << " " << (n_found == 1 ? "instance" : "instances") << endl;

}

int main() {

hash_multiset<const char*, hash<const char*>, eqstr> Set;

Set.insert("mango");

Set.insert("kiwi");

Set.insert("apple");

Set.insert("kiwi");

Set.insert("mango");

Set.insert("apricot");

Set.insert("banana");

Set.insert("mango");

lookup(Set, "mango");

lookup(Set, "apple");

lookup(Set, "durian");

}

Definition

Defined in the header hash_set, and in the backward-compatibility header hash_set.h. This class is an SGI extension; it is not part of the C++ standard.

Template parameters

Parameter	Description	Default
`Key`	The hash_multiset's key type and value type. This is also defined as hash_multiset::key_type and hash_multiset::value_type
`HashFcn`	The Hash Function used by the hash_multiset. This is also defined as hash_multiset::hasher.	`hash<Key>`
EqualKey	The hash_multiset's key equality function: a binary predicate that determines whether two keys are equal. This is also defined as hash_multiset::key_equal.	`equal_to<Key>`
`Alloc`	The hash_multiset's allocator, used for all internal memory management.	`alloc`

Model of

Multiple Hashed Associative Container, Simple Associative Container

Type requirements

• Key is assignable.

• EqualKey is a Binary Predicate whose argument type is Key.

• EqualKey is an equivalence relation.

• Alloc is an Allocator.

Public base classes

None.

Members

Member	Where defined	Description
`value_type`	Container	The type of object, T, stored in the hash_multiset.
`key_type`	Associative Container	The key type associated with value_type.
`hasher`	Hashed Associative Container	The hash_multiset's Hash Function.
`key_equal`	Hashed Associative Container	Function object that compares keys for equality.
`pointer`	Container	Pointer to T.
`reference`	Container	Reference to T
`const_reference`	Container	Const reference to T
`size_type`	Container	An unsigned integral type.
`difference_type`	Container	A signed integral type.
`iterator`	Container	Iterator used to iterate through a hash_multiset.
`const_iterator`	Container	Const iterator used to iterate through a hash_multiset. (Iterator and const_iterator are the same type.)
`iterator begin() const`	Container	Returns an iterator pointing to the beginning of the hash_multiset.
`iterator end() const`	Container	Returns an iterator pointing to the end of the hash_multiset.
`size_type size() const`	Container	Returns the size of the hash_multiset.
`size_type max_size() const`	Container	Returns the largest possible size of the hash_multiset.
`bool empty() const`	Container	true if the hash_multiset's size is 0.
`size_type bucket_count() const`	Hashed Associative Container	Returns the number of buckets used by the hash_multiset.
`void resize(size_type n)`	Hashed Associative Container	Increases the bucket count to at least n.
`hasher hash_funct() const`	Hashed Associative Container	Returns the hasher object used by the hash_multiset.
`key_equal key_eq() const`	Hashed Associative Container	Returns the key_equal object used by the hash_multiset.
`hash_multiset()`	Container	Creates an empty hash_multiset.
`hash_multiset(size_type n)`	Hashed Associative Container	Creates an empty hash_multiset with at least n buckets.
`hash_multiset(size_type n, const hasher& h)`	Hashed Associative Container	Creates an empty hash_multiset with at least n buckets, using h as the hash function.
`hash_multiset(size_type n, const hasher& h, const key_equal& k)`	Hashed Associative Container	Creates an empty hash_multiset with at least n buckets, using h as the hash function and k as the key equal function.
`template <class InputIterator> hash_multiset(InputIterator, InputIterator)` [1]	Multiple Hashed Associative Container	Creates a hash_multiset with a copy of a range.
`template <class InputIterator> hash_multiset(InputIterator, InputIterator, size_type n)` [1]	Multiple Hashed Associative Container	Creates a hash_multiset with a copy of a range and a bucket count of at least n.
`template <class InputIterator> hash_multiset(InputIterator, InputIterator, size_type n, const hasher& h)` [1]	Multiple Hashed Associative Container	Creates a hash_multiset with a copy of a range and a bucket count of at least n, using h as the hash function.
`template <class InputIterator> hash_multiset(InputIterator, InputIterator, size_type n, const hasher& h, const key_equal& k)` [1]	Multiple Hashed Associative Container	Creates a hash_multiset with a copy of a range and a bucket count of at least n, using h as the hash function and k as the key equal function.
`hash_multiset(const hash_multiset&)`	Container	The copy constructor.
`hash_multiset& operator=(const hash_multiset&)`	Container	The assignment operator
`void swap(hash_multiset&)`	Container	Swaps the contents of two hash_multisets.
`iterator insert(const value_type& x)`	Multiple Associative Container	Inserts x into the hash_multiset.
`template <class InputIterator> void insert(InputIterator, InputIterator)` [1]	Multiple Associative Container	Inserts a range into the hash_multiset.
`void erase(iterator pos)`	Associative Container	Erases the element pointed to by pos.
`size_type erase(const key_type& k)`	Associative Container	Erases the element whose key is k.
`void erase(iterator first, iterator last)`	Associative Container	Erases all elements in a range.
`void clear()`	Associative Container	Erases all of the elements.
`iterator find(const key_type& k) const`	Associative Container	Finds an element whose key is k.
`size_type count(const key_type& k) const`	Associative Container	Counts the number of elements whose key is k.
`pair<iterator, iterator> equal_range(const key_type& k) const`	Associative Container	Finds a range containing all elements whose key is k.
`bool operator==(const hash_multiset&, const hash_multiset&)`	Hashed Associative Container	Tests two hash_multisets for equality. This is a global function, not a member function.

New members

All of hash_multiset's members are defined in the Multiple Hashed Associative Container and Simple Associative Container requirements. Hash_multiset does not introduce any new members.

Notes

hash_multimap<Key, Data, HashFcn, EqualKey, Alloc>

Category: containers

Component type: type

Description

Hash_multimap is a Hashed Associative Container that associates objects of type Key with objects of type Data. Hash_multimap is a Pair Associative Container, meaning that its value type is pair<const Key, Data>. It is also a Multiple Associative Container, meaning that there is no limit on the number of elements whose keys may compare equal using EqualKey.

Looking up an element in a hash_multimap by its key is efficient, so hash_multimap is useful for "dictionaries" where the order of elements is irrelevant. If it is important for the elements to be in a particular order, however, then multimap is more appropriate.

Example

struct eqstr {

bool operator()(const char* s1, const char* s2) const {

return strcmp(s1, s2) == 0;

}

};

typedef hash_multimap<const char*, int, hash<const char*>, eqstr> map_type;

void lookup(const map_type& Map, const char* str) {

cout << str << ": ";

pair<map_type::const_iterator, map_type::const_iterator> p = Map.equal_range(str);

for (map_type::const_iterator i = p.first; i != p.second; ++i) cout << (*i).second << " ";

cout << endl;

}

int main() {

map_type M;

M.insert(map_type::value_type("H", 1));

M.insert(map_type::value_type("H", 2));

M.insert(map_type::value_type("C", 12));

M.insert(map_type::value_type("C", 13));

M.insert(map_type::value_type("O", 16));

M.insert(map_type::value_type("O", 17));

M.insert(map_type::value_type("O", 18));

M.insert(map_type::value_type("I", 127));

lookup(M, "I");

lookup(M, "O");

lookup(M, "Rn");

}

Definition

Defined in the header hash_map, and in the backward-compatibility header hash_map.h. This class is an SGI extension; it is not part of the C++ standard.

Template parameters

Parameter	Description	Default
`Key`	The hash_multimap's key type. This is also defined as hash_multimap::key_type.
`Data`	The hash_multimap's data type. This is also defined as hash_multimap::data_type.
`HashFcn`	The hash function used by the hash_multimap. This is also defined as hash_multimap::hasher.	`hash<Key>`
`EqualKey`	The hash_multimap's key equality function: a binary predicate that determines whether two keys are equal. This is also defined as hash_multimap::key_equal.	`equal_to<Key>`
`Alloc`	The hash_set's allocator, used for all internal memory management.	`alloc`

Model of

Multiple Hashed Associative Container, Pair Associative Container

Type requirements

• Key is Assignable.

• EqualKey is a Binary Predicate whose argument type is Key.

• EqualKey is an equivalence relation.

• Alloc is an Allocator.

Public base classes

None.

Members

Member	Where defined	Description
`key_type`	Associative Container	The hash_multimap's key type, Key.
`data_type`	Pair Associative Container	The type of object associated with the keys.
`value_type`	Pair Associative Container	The type of object, pair<const key_type, data_type>, stored in the hash_multimap.
`hasher`	Hashed Associative Container	The hash_multimap's hash function.
`key_equal`	Hashed Associative Container	Function object that compares keys for equality.
`pointer`	Container	Pointer to T.
`reference`	Container	Reference to T
`const_reference`	Container	Const reference to T
`size_type`	Container	An unsigned integral type.
`difference_type`	Container	A signed integral type.
`iterator`	Container	Iterator used to iterate through a hash_multimap. [1]
`const_iterator`	Container	Const iterator used to iterate through a hash_multimap.
`iterator begin()`	Container	Returns an iterator pointing to the beginning of the hash_multimap.
`iterator end()`	Container	Returns an iterator pointing to the end of the hash_multimap.
`const_iterator begin() const`	Container	Returns an const_iterator pointing to the beginning of the hash_multimap.
`const_iterator end() const`	Container	Returns an const_iterator pointing to the end of the hash_multimap.
`size_type size() const`	Container	Returns the size of the hash_multimap.
`size_type max_size() const`	Container	Returns the largest possible size of the hash_multimap.
`bool empty() const`	Container	true if the hash_multimap's size is 0.
`size_type bucket_count() const`	Hashed Associative Container	Returns the number of buckets used by the hash_multimap.
`void resize(size_type n)`	Hashed Associative Container	Increases the bucket count to at least n.
`hasher hash_funct() const`	Hashed Associative Container	Returns the hasher object used by the hash_multimap.
`key_equal key_eq() const`	Hashed Associative Container	Returns the key_equal object used by the hash_multimap.
`hash_multimap()`	Container	Creates an empty hash_multimap.
`hash_multimap(size_type n)`	Hashed Associative Container	Creates an empty hash_multimap with at least n buckets.
`hash_multimap(size_type n, const hasher& h)`	Hashed Associative Container	Creates an empty hash_multimap with at least n buckets, using h as the hash function.
`hash_multimap(size_type n, const hasher& h, const key_equal& k)`	Hashed Associative Container	Creates an empty hash_multimap with at least n buckets, using h as the hash function and k as the key equal function.
`template <class InputIterator> hash_multimap(InputIterator, InputIterator)` [2]	Multiple Hashed Associative Container	Creates a hash_multimap with a copy of a range.
`template <class InputIterator> hash_multimap(InputIterator, InputIterator, size_type n)` [2]	Multiple Hashed Associative Container	Creates a hash_multimap with a copy of a range and a bucket count of at least n.
`template <class InputIterator> hash_multimap(InputIterator, InputIterator, size_type n, const hasher& h)` [2]	Multiple Hashed Associative Container	Creates a hash_multimap with a copy of a range and a bucket count of at least n, using h as the hash function.
`template <class InputIterator> hash_multimap(InputIterator, InputIterator, size_type n, const hasher& h, const key_equal& k)` [2]	Multiple Hashed Associative Container	Creates a hash_multimap with a copy of a range and a bucket count of at least n, using h as the hash function and k as the key equal function.
`hash_multimap(const hash_multimap&)`	Container	The copy constructor.
`hash_multimap& operator=(const hash_multimap&)`	Container	The assignment operator
`void swap(hash_multimap&)`	Container	Swaps the contents of two hash_multimaps.
`iterator insert(const value_type& x)`	Multiple Associative Container	Inserts x into the hash_multimap.
`template <class InputIterator> void insert(InputIterator, InputIterator)` [2]	Multiple Associative Container	Inserts a range into the hash_multimap.
`void erase(iterator pos)`	Associative Container	Erases the element pointed to by pos.
`size_type erase(const key_type& k)`	Associative Container	Erases the element whose key is k.
`void erase(iterator first, iterator last)`	Associative Container	Erases all elements in a range.
`void clear()`	Associative Container	Erases all of the elements.
`const_iterator find(const key_type& k) const`	Associative Container	Finds an element whose key is k.
`iterator find(const key_type& k)`	Associative Container	Finds an element whose key is k.
`size_type count(const key_type& k) const`	Associative Container	Counts the number of elements whose key is k.
`pair<const_iterator, const_iterator> equal_range(const key_type& k) const`	Associative Container	Finds a range containing all elements whose key is k.
`pair<iterator, iterator> equal_range(const key_type& k)`	Associative Container	Finds a range containing all elements whose key is k.
`bool operator==(const hash_multimap&, const hash_multimap&)`	Hashed Associative Container	Tests two hash_multimaps for equality. This is a global function, not a member function.

New members

All of hash_multimap's members are defined in the Multiple Hashed Associative Container and Pair Associative Container requirements. Hash_multimap does not introduce any new members.

Notes

[1] Hash_multimap::iterator is not a mutable iterator, because hash_multimap::value_type is not Assignable. That is, if i is of type hash_multimap::iterator and p is of type hash_multimap::value_type, then *i = p is not a valid expression. However, hash_multimap::iterator isn't a constant iterator either, because it can be used to modify the object that it points to. Using the same notation as above, (*i).second = p is a valid expression.

hash<T>

Categories: containers, functors

Component type: type

Description

The function object hash<T> is a Hash Function; it is used as the default hash function by all of the Hashed Associative Containers that are included in the STL.

The hash<T> template is only defined for template arguments of type char*, const char*, crope, wrope, and the built-in integral types. [1] If you need a Hash Function with a different argument type, you must either provide your own template specialization or else use a different Hash Function.

Example

int main() {

hash<const char*> H;

cout << "foo –> " << H("foo") << endl;

cout << "bar –> " << H("bar") << endl;

}

Definition

Defined in the headers hash_map and hash_set, and in the backward-compatibility headers hash_map.h and hash_set.h. This class is an SGI extension; it is not part of the C++ standard.

Template parameters

Parameter	Description
`T`	The argument type. That is, the type of object that is being hashed.

Model of

Hash Function

Type requirements

T must be a type for which a specialization of hash has been defined. The STL defines the following specializations:

• char*

• const char*

• crope

• wrope

• char

• signed char

• unsigned char

• short

• unsigned short

• int

• unsigned int

• long

• unsigned long

Public base classes

None.

Members

Member	Where defined	Description
`size_t operator()(const T& x)`	Hash Function	Returns x's hash value.

New members

All of hash's members are defined in the Hash Function requirements. Hash does not introduce any new members.

Notes

[1] Technically, what this means is that the actual template hash<T> is an empty class; the member function operator() is defined only in the various specializations.

String package

Character Traits

Category: utilities

Component type: concept

Description

Several library components, including strings, need to perform operations on characters. A Character Traits class is similar to a function object: it encapsulates some information about a particular character type, and some operations on that type.

Note that every member of a Character Traits class is static. There is never any need to create a Character Traits object, and, in fact, there is no guarantee that creating such objects is possible.

Refinement of

Character Traits is not a refinement of any other concept.

Associated types

Value type	`X::char_type`	The character type described by this Character Traits type.
Int type	`X::int_type`	A type that is capable of representing every valid value of type char_type, and, additionally an end-of-file value. For char, for example, the int type may be int, and for wchar_t it may be wint_t.
Position type	`X::pos_type`	A type that can represent the position of a character of type char_type within a file. This type is usually streampos.
Offset type	`X::off_type`	An integer type that can represent the difference between two pos_type values. This type is usually streamoff.
State type	`X::state_type`	A type that can represent a state in a multibyte encoding scheme. This type, if used at all, is usually mbstate_t.

Notation

X A type that is a model of Character Traits.

c, c1, c2 A value of X's value type, X::char_type.

e, e1, e2 A value of X's int type, X::int_type.

n A value of type size_t.

p, p1, p2 A non-null pointer of type const X::char_type*.

s A non-null pointer of type X::char_type*.

Valid Expressions

Name	Expression	Type requirements	Return type
Character assignment	`X::assign(c1, c2)`	c1 is a modifiable lvalue.	`void`
Character equality	`X::eq(c1, c2)`		`bool`
Character comparison	`X::lt(c1, c2)`		`bool`
Range comparison	`X::compare(p1, p2, n)`		`int`
Length	`X::length(p)`		`size_t`
Find	`X::find(p, n, c)`		`const X::char_type*`
Move	`X::move(s, p, n)`		`X::char_type*`
Copy	`X::copy(s, p, n)`		`X::char_type*`
Range assignment	`X::assign(s, n, c)`		`X::char_type*`
EOF value	`X::eof()`		`X::int_type`
Not EOF	`X::not_eof(e)`		`X::int_type`
Convert to value type	`X::to_char_type(e)`		`X::char_type`
Convert to int type	`X::to_int_type(c)`		`X::int_type`
Equal int type values	`X::eq_int_type(e1, e2)`		`bool`

Expression semantics

Name	Expression	Precondition	Semantics	Postcondition
Character assignment	`X::assign(c1, c2)`		Performs the assignment c1 = c2	X::eq(c1, c2) is true.
Character equality	`X::eq(c1, c2)`		Returns true if and only if c1 and c2 are equal.
Character comparison	`X::lt(c1, c2)`		Returns true if and only if c1 is less than c2 . Note that for any two value values c1 and c2 , exactly one of X::lt(c1, c2), X::lt(c2, c1) , and X::eq(c1, c2) should be true.
Range comparison	`X::compare(p1, p2, n)`	[p1, p1+n) and [p2, p2+n) are valid ranges.	Generalization of strncmp. Returns 0 if every element in [p1, p1+n) is equal to the corresponding element in [p2, p2+n), a negative value if there exists an element in [p1, p1+n) less than the corresponding element in [p2, p2+n) and all previous elements are equal, and a positive value if there exists an element in [p1, p1+n) greater than the corresponding element in [p2, p2+n) and all previous elements are equal.
Length	`X::length(p)`		Generalization of strlen. Returns the smallest non-negative number n such that X::eq(p+n, X::char_type()) is true. Behavior is undefined if no such n exists.
Find	`X::find(p, n, c)`	[p, p+n) is a valid range.	Generalization of strchr. Returns the first pointer q in [p, p+n) such that X::eq(q, c)* is true. Returns a null pointer if no such pointer exists. (Note that this method for indicating a failed search differs from that is find.)
Move	`X::move(s, p, n)`	[p, p+n) and [s, s+n) are valid ranges (possibly overlapping).	Generalization of memmove. Copies values from the range [p, p+n) to the range [s, s+n), and returns s.
Copy	`X::copy(s, p, n)`	[p, p+n) and [s, s+n) are valid ranges which do not overlap.	Generalization of memcpy. Copies values from the range [p, p+n) to the range [s, s+n), and returns s.
Range assignment	`X::assign(s, n, c)`	[s, s+n) is a valid range.	Generalization of memset. Assigns the value c to each pointer in the range [s, s+n), and returns s.
EOF value	`X::eof()`		Returns a value that can represent EOF.	X::eof() is distinct from every valid value of type X::char_type. That is, there exists no value c such that X::eq_int_type(X::to_int_type(c), X::eof()) is true.
Not EOF	`X::not_eof(e)`		Returns e if e represents a valid char_type value, and some non-EOF value if e is X::eof().
Convert to value type	`X::to_char_type(e)`		Converts e to X's int type. If e is a representation of some char_type value then it returns that value; if e is X::eof() then the return value is unspecified.
Convert to int type	`X::to_int_type(c)`		Converts c to X's int type.	X::to_char_type(X::to_int_type(c)) is a null operation.
Equal int type values	`X::eq_int_type(e1, e2)`		Compares two int type values. If there exist values of type X::char_type such that e1 is X::to_int_type(c1)) and e2 is X::to_int_type(c2)), then X::eq_int_type(e1, e2) is the same as X::eq(c1, c2). Otherwise, eq_int_type returns true if e1 and e2 are both EOF and false if one of e1 and e2 is EOF and the other is not.

Complexity guarantees

length, find, move, copy, and the range version of assign are linear in n.

All other operations are constant time.

Models

• char_traits<char>

• char_traits<wchar_t>

char_traits

Category: utilities

Component type: type

Description

The char_traits class is the default Character Traits class used by the library; it is the only predefined Character Traits class.

Example

The char_traits class is of no use by itself. It is used as a template parameter of other classes, such as the basic_string template.

Definition

Defined in the standard header string.

Template parameters

Parameter	Description
charT	char_traits 's value type, i.e.char_traits<>::char_type.

Model of

Character Traits

Type requirements

charT is either char or wchar_t.

(All of char_traits 's member functions are defined for arbitrary types, but some of char_traits 's members must be explicitly specialized if char_traits is to be useful for other types than char and wchar_t.)

Public base classes

None.

Members

All of char_traits 's members are static. There is never any reason to create an object of type char_traits.

Member	Where defined	Description
`char_type`	Character Traits	char_traits's value type: charT.
`int_type`	Character Traits	char_traits's int type.
`pos_type`	Character Traits	char_traits's position type.
`off_type`	Character Traits	char_traits's offset type
`state_type`	Character Traits	char_traits's state type.
`static void assign(char_type& c1, const char_type& c2)`	Character Traits	Assigns c2 to c1.
`static bool eq(const char_type& c1, const char_type& c2)`	Character Traits	Character equality.
`static bool lt(const char_type& c1, const char_type& c2)`	Character Traits	Returns true if c1 is less than c2.
`static int compare(const char_type* p1, const char_type* p2, size_t n)`	Character Traits	Three-way lexicographical comparison, much like strncmp.
`static size_t length(const char* p)`	Character Traits	Returns length of a null-terminated array of characters.
`static const char_type* find(const char_type* p, size_t n, const char_type& c)`	Character Traits	Finds c in [p, p+n) , returning 0 if not found.
`static char_type* move(char_type* s, const char_type* p, size_t n)`	Character Traits	Copies characters from [p, p+n) to the (possibly overlapping) range [s, s+n).
`static char_type* copy(char_type* s, const char_type* p, size_t n)`	Character Traits	Copies characters from [p, p+n) to the (non-overlapping) range [s, s+n).
`static char_type* assign(char_type* s, size_t n, char_type c)`	Character Traits	Assigns the value c to every element in the range [s, s+n).
`static int_type eof()`	Character Traits	Returns the value used as an EOF indicator.
`static int_type not_eof(const int_type& c)`	Character Traits	Returns a value that is not equal to eof() . Returns c unless c is equal to eof().
`static char_type to_char_type(const int_type& c)`	Character Traits	Returns the char_type value corresponding to c, if such a value exists.
`static int_type to_int_type(const char_type& c)`	Character Traits	Returns a int_type representation of c.
`static bool eq_int_type(cosnt int_type& c1, const int_type& c1)`	Character Traits	Tests whether two int_type values are equal. If the values can also be represented as char_type, then eq and eq_int_type must be consistent with each other.

New members

None. All of char_traits's members are defined in the Character Traits requirements.

basic_string<charT, traits, Alloc>

Category: containers

Component type: type

Description

The basic_string class represents a Sequence of characters. It contains all the usual operations of a Sequence, and, additionally, it contains standard string operations such as search and concatenation.

The basic_string class is parameterized by character type, and by that type's Character Traits. Most of the time, however, there is no need to use the basic_string template directly. The types string and wstring are typedefs for, respectively, basic_string<char> and basic_string<wchar_t>.

Some of basic_string's member functions use an unusual method of specifying positions and ranges. In addition to the conventional method using iterators, many of basic_string's member functions use a single value pos of type size_type to represent a position (in which case the position is begin() + pos, and many of basic_string's member functions use two values, pos and n, to represent a range. In that case pos is the beginning of the range and n is its size. That is, the range is [begin() + pos, begin() + pos + n).

Note that the C++ standard does not specify the complexity of basic_string operations. In this implementation, basic_string has performance characteristics very similar to those of vector: access to a single character is O(1), while copy and concatenation are O(N). By contrast, rope has very different performance characteristics: most rope operations have logarithmic complexity.

Note also that, according to the C++ standard, basic_string has very unusual iterator invalidation semantics. Iterators may be invalidated by swap, reserve, insert , and erase (and by functions that are equivalent to insert and/or erase , such as clear, resize, append , and replace). Additionally, however, the first call to any non-const member function, including the non-const version of begin() or operator[], may invalidate iterators. (The intent of these iterator invalidation rules is to give implementors greater freedom in implementation techniques.) In this implementation, begin(), end(), rbegin(), rend(), operator[], c_str(), and data() do not invalidate iterators. In this implementation, iterators are only invalidated by member functions that explicitly change the string's contents.

Example

int main() {

string s(10u, ' '); // Create a string of ten blanks.

const char* A = "this is a test";

s += A;

cout << "s = " << (s + '\n');

cout << "As a null-terminated sequence: " << s.c_str() << endl;

cout << "The sixteenth character is " << s[15] << endl;

reverse(s.begin(), s.end());

s.push_back('\n');

cout << s;

}

Definition

Defined in the standard header string.

Template parameters

Parameter	Description	Default
`charT`	The string's value type: the type of character it contains.
`traits`	The Character Traits type, which encapsulates basic character operations.	`char_traits<charT>`
`Alloc`	The string's allocator, used for internal memory management.	`alloc`

Model of

Random Access Container, Sequence.

Type requirements

In addition to the type requirements imposed by Random Access Container and Sequence:

• charT is a POD ("plain ol' data") type.

• traits is a Character Traits type whose value type is charT

Public base classes

None.

Members

Member	Where defined	Description
`value_type`	Container	The type of object, CharT, stored in the string.
`pointer`	Container	Pointer to CharT.
`reference`	Container	Reference to CharT
`const_reference`	Container	Const reference to CharT
`size_type`	Container	An unsigned integral type.
`difference_type`	Container	A signed integral type.
`static const size_type npos`	`basic_string`	The largest possible value of type size_type. That is, size_type(-1).
`iterator`	Container	Iterator used to iterate through a string. A basic_string supplies Random Access Iterators.
`const_iterator`	Container Const	iterator used to iterate through a string.
`reverse_iterator`	Reversible Container	Iterator used to iterate backwards through a string.
`const_reverse_iterator`	Reversible Container	Const iterator used to iterate backwards through a string.
`iterator begin()`	Container	Returns an iterator pointing to the beginning of the string.
`iterator end()`	Container	Returns an iterator pointing to the end of the string.
`const_iterator begin()`	`const`	Container Returns a const_iterator pointing to the beginning of the string.
`const_iterator end() const`	Container	Returns a const_iterator pointing to the end of the string.
`reverse_iterator rbegin()`	Reversible Container	Returns a reverse_iterator pointing to the beginning of the reversed string.
`reverse_iterator rend()`	Reversible Container	Returns a reverse_iterator pointing to the end of the reversed string.
`const_reverse_iterator rbegin() const`	Reversible Container	Returns a const_reverse_iterator pointing to the beginning of the reversed string.
`const_reverse_iterator rend() const`	Reversible Container	Returns a const_reverse_iterator pointing to the end of the reversed string.
`size_type size() const`	Container	Returns the size of the string.
`size_type length() const`	`basic_string`	Synonym for size().
`size_type max_size() const`	Container	Returns the largest possible size of the string.
`size_type capacity() const`	`basic_string`	See below.
`bool empty() const`	Container	true if the string's size is 0.
`reference operator[](size_type n)`	Random Access Container	Returns the n'th character.
`const_reference operator[](size_type n) const`	Random Access Container	Returns the n'th character.
`const charT* c_str() const`	`basic_string`	Returns a pointer to a null-terminated array of characters representing the string's contents.
`const charT* data() const`	`basic_string`	Returns a pointer to an array of characters (not necessarily null-terminated) representing the string's contents.
`basic_string()`	Container	Creates an empty string.
`basic_string(const basic_string& s, size_type pos = 0, size_type n = npos)`	Container, basic_string	Generalization of the copy constructor.
`basic_string(const charT*)`	`basic_string`	Construct a string from a null-terminated character array.
`basic_string(const charT* s, size_type n)`	`basic_string`	Construct a string from a character array and a length.
`basic_string(size_type n, charT c)`	Sequence	Create a string with n copies of c.
`template <class InputIterator> basic_string(InputIterator first, InputIterator last)`	Sequence	Create a string from a range.
`~basic_string()`	Container	The destructor.
`basic_string& operator=(const basic_string&)`	Container	The assignment operator
`basic_string& operator=(const charT* s)`	`basic_string`	Assign a null-terminated character array to a string.
`basic_string& operator=(charT c)`	`basic_string`	Assign a single character to a string.
`void reserve(size_t)`	`basic_string`	See below.
`void swap(basic_string&)`	Container	Swaps the contents of two strings.
`iterator insert(iterator pos, const T& x)`	Sequence	Inserts x before pos.
`template <class InputIterator > void insert(iterator pos, InputIterator f, InputIterator l)` [1]	Sequence	Inserts the range [first, last) before pos.
`void insert(iterator pos, size_type n, const T& x)`	Sequence	Inserts n copies of x before pos.
`basic_string& insert(size_type pos, const basic_string& s)`	`basic_string`	Inserts s before pos.
`basic_string& insert(size_type pos, const basic_string& s, size_type pos1, size_type n)`	`basic_string`	Inserts a substring of s before pos.
`basic_string& insert(size_type pos, const charT* s)`	`basic_string`	Inserts s before pos.
`basic_string& insert(size_type pos, const charT* s, size_type n)`	`basic_string`	Inserts the first n characters of s before pos.
`basic_string& insert(size_type pos, size_type n, charT c)`	`basic_string`	Inserts n copies of c before pos.
`basic_string& append(const basic_string& s)`	`basic_string`	Append s to *this.
`basic_string& append(const basic_string& s, size_type pos, size_type n)`	`basic_string`	Append a substring of s to *this.
`basic_string& append(const charT* s)`	`basic_string`	Append s to *this.
`basic_string& append(const charT* s, size_type n)`	`basic_string`	Append the first n characters of s to *this.
`basic_string& append(size_type n, charT c)`	`basic_string`	Append n copies of c to *this.
`template <class InputIterator> basic_string& append(InputIterator first, InputIterator last)`	`basic_string`	Append a range to *this.
`void push_back(charT c)`	`basic_string`	Append a single character to *this.
`basic_string& operator+=(const basic_string& s)`	`basic_string`	Equivalent to append(s).
`basic_string& operator+=(const charT* s)`	`basic_string`	Equivalent to append(s)
`basic_string& operator+=(charT c)`	`basic_string`	Equivalent to push_back(c)
`iterator erase(iterator p)`	Sequence	Erases the character at position p
`iterator erase(iterator first, iterator last)`	Sequence	Erases the range [first, last)
`basic_string& erase(size_type pos = 0, size_type n = npos)`	`basic_string`	Erases a range.
`void clear()`	Sequence	Erases the entire container.
`void resize(size_type n, charT c = charT())`	Sequence	Appends characters, or erases characters from the end, as necessary to make the string's length exactly n characters.
`basic_string& assign(const basic_string&)`	`basic_string`	Synonym for operator=
`basic_string& assign(const basic_string& s, size_type pos, size_type n)`	`basic_string`	Assigns a substring of s to *this
`basic_string& assign(const charT* s, size_type n)`	`basic_string`	Assigns the first n characters of s to *this.
`basic_string& assign(const charT* s)`	`basic_string`	Assigns a null-terminated array of characters to *this.
`basic_string& assign(size_type n, charT c)`	Sequence	Erases the existing characters and replaces them by n copies of c.
`template <class InputIterator> basic_string& assign(InputIterator first, InputIterator last)`	Sequence	Erases the existing characters and replaces them by [first, last)
`basic_string& replace(size_type pos, size_type n, const basic_string& s)`	`basic_string`	Replaces a substring of *this with the string s.
`basic_string& replace(size_type pos, size_type n, const basic_string& s, size_type pos1, size_type n1)`	`basic_string`	Replaces a substring of *this with a substring of s.
`basic_string& replace(size_type pos, size_type n, const charT* s, size_type n1)`	`basic_string`	Replaces a substring of *this with the first n1 characters of s.
`basic_string& replace(size_type pos, size_type n, const charT* s)`	`basic_string`	Replaces a substring of *this with a null-terminated character array.
`basic_string& replace(size_type pos, size_type n, size_type n1, charT c)`	`basic_string`	Replaces a substring of *this with n1 copies of c.
`basic_string& replace(iterator first, iterator last, const basic_string& s)`	`basic_string`	Replaces a substring of *this with the string s.
`basic_string& replace(iterator first, iterator last, const charT* s, size_type n)`	`basic_string`	Replaces a substring of *this with the first n characters of s.
`basic_string& replace(iterator first, iterator last, const charT* s)`	`basic_string`	Replaces a substring of *this with a null-terminated character array.
`basic_string& replace(iterator first, iterator last, size_type n, charT c)`	`basic_string`	Replaces a substring of *this with n copies of c.
`template <class InputIterator> basic_string& replace(iterator first, iterator last, InputIterator f, InputIterator l)`	`basic_string`	Replaces a substring of this with the range [f, l)*
`size_type copy(charT* buf, size_type n, size_type pos = 0) const`	`basic_string`	Copies a substring of *this to a buffer.
`size_type find(const basic_string& s, size_type pos = 0) const`	`basic_string`	Searches for s as a substring of this, beginning at character pos* of *this.
`size_type find(const charT* s, size_type pos, size_type n) const`	`basic_string`	Searches for the first n characters of s as a substring of this, beginning at character pos* of *this.
`size_type find(const charT* s, size_type pos = 0) const`	`basic_string`	Searches for a null-terminated character array as a substring of this, beginning at character pos* of *this.
`size_type find(charT c, size_type pos = 0) const`	`basic_string`	Searches for the character c, beginning at character position pos.
`size_type rfind(const basic_string& s, size_type pos = npos) const`	`basic_string`	Searches backward for s as a substring of this, beginning at character position min(pos, size())*
`size_type rfind(const charT* s, size_type pos, size_type n) const`	`basic_string`	Searches backward for the first n characters of s as a substring of this, beginning at character position min(pos, size())*
`size_type rfind(const charT* s, size_type pos = npos) const`	`basic_string`	Searches backward for a null-terminated character array as a substring of this, beginning at character min(pos, size())*
`size_type rfind(charT c, size_type pos = npos) const`	`basic_string`	Searches backward for the character c, beginning at character position min(pos, size().
`size_type find_first_of(const basic_string& s, size_type pos = 0) const`	`basic_string`	Searches within this, beginning at pos*, for the first character that is equal to any character within s.
`size_type find_first_of(const charT* s, size_type pos, size_type n) const`	`basic_string`	Searches within this, beginning at pos*, for the first character that is equal to any character within the first n characters of s.
`size_type find_first_of(const charT* s, size_type pos = 0) const`	`basic_string`	Searches within this, beginning at pos*, for the first character that is equal to any character within s.
`size_type find_first_of(charT c, size_type pos = 0) const`	`basic_string`	Searches within this, beginning at pos*, for the first character that is equal to c.
`size_type find_first_not_of(const basic_string& s, size_type pos = 0) const`	`basic_string`	Searches within this, beginning at pos*, for the first character that is not equal to any character within s.
`size_type find_first_not_of(const charT* s, size_type pos, size_type n) const`	`basic_string`	Searches within this, beginning at pos*, for the first character that is not equal to any character within the first n characters of s.
`size_type find_first_not_of(const charT* s, size_type pos = 0) const`	`basic_string`	Searches within this, beginning at pos*, for the first character that is not equal to any character within s.
`size_type find_first_not_of(charT c, size_type pos = 0) const`	`basic_string`	Searches within this, beginning at pos*, for the first character that is not equal to c.
`size_type find_last_of(const basic_string& s, size_type pos = npos) const`	`basic_string`	Searches backward within this, beginning at min(pos, size())*, for the first character that is equal to any character within s.
`size_type find_last_of(const charT* s, size_type pos, size_type n) const`	`basic_string`	Searches backward within this, beginning at min(pos, size())*, for the first character that is equal to any character within the first n characters of s.
`size_type find_last_of(const charT* s, size_type pos = npos) const`	`basic_string`	Searches backward this, beginning at min(pos, size())*, for the first character that is equal to any character within s.
`size_type find_last_of(charT c, size_type pos = npos) const`	`basic_string`	Searches backward this, beginning at min(pos, size())*, for the first character that is equal to c.
`size_type find_last_not_of(const basic_string& s, size_type pos = npos) const`	`basic_string`	Searches backward within this, beginning at min(pos, size())*, for the first character that is not equal to any character within s.
`size_type find_last_not_of(const charT* s, size_type pos, size_type n) const`	`basic_string`	Searches backward within this, beginning at min(pos, size())*, for the first character that is not equal to any character within the first n characters of s.
`size_type find_last_not_of(const charT* s, size_type pos = npos) const`	`basic_string`	Searches backward this, beginning at min(pos, size())*, for the first character that is not equal to any character within s.
`size_type find_last_not_of(charT c, size_type pos = npos) const`	`basic_string`	Searches backward this, beginning at min(pos, size())*, for the first character that is not equal to c.
`basic_string substr(size_type pos = 0, size_type n = npos) const`	`basic_string`	Returns a substring of *this.
`int compare(const basic_string& s) const`	`basic_string`	Three-way lexicographical comparison of s and *this.
`int compare(size_type pos, size_type n, const basic_string& s) const`	`basic_string`	Three-way lexicographical comparison of s and a substring of *this.
`int compare(size_type pos, size_type n, const basic_string& s, size_type pos1, size_type n1) const`	`basic_string`	Three-way lexicographical comparison of a substring of s and a substring of *this
`int compare(const charT* s) const`	`basic_string`	Three-way lexicographical comparison of s and *this.
`int compare(size_type pos, size_type n, const charT* s, size_type len = npos) const`	`basic_string`	Three-way lexicographical comparison of the first min(len, traits::length(s)) characters of s and a substring of *this.
`template<class charT, class traits, class Alloc> basic_string<charT, traits, Alloc> operator+(const basic_string<charT, traits, Alloc>& s1, const basic_string<charT, traits, Alloc>& s2)`	`basic_string`	String concatenation. A global function, not a member function.
`template<class charT, class traits, class Alloc> basic_string<charT, traits, Alloc> operator+(const charT* s1, const basic_string<charT, traits, Alloc>& s2)`	`basic_string`	String concatenation. A global function, not a member function.
`template<class charT, class traits, class Alloc> basic_string<charT, traits, Alloc> operator+(const basic_string<charT, traits, Alloc>& s1, const charT* s2)`	`basic_string`	String concatenation. A global function, not a member function.
`template<class charT, class traits, class Alloc> basic_string<charT, traits, Alloc> operator+(charT c, const basic_string<charT, traits, Alloc>& s2)`	`basic_string`	String concatenation. A global function, not a member function.
`template<class charT, class traits, class Alloc> basic_string<charT, traits, Alloc> operator+(const basic_string<charT, traits, Alloc>& s1, charT c)`	`basic_string`	String concatenation. A global function, not a member function.
`template<class charT, class traits, class Alloc> bool operator==(const basic_string<charT, traits, Alloc>& s1, const basic_string<charT, traits, Alloc>& s2)`	Container	String equality. A global function, not a member function.
`template<class charT, class traits, class Alloc> bool operator==(const charT* s1, const basic_string<charT, traits, Alloc>& s2)`	`basic_string`	String equality. A global function, not a member function.
`template<class charT, class traits, class Alloc> bool operator==(const basic_string<charT, traits, Alloc>& s1, const charT* s2)`	`basic_string`	String equality. A global function, not a member function.
`template<class charT, class traits, class Alloc> bool operator!=(const basic_string<charT, traits, Alloc>& s1, const basic_string<charT, traits, Alloc>& s2)`	Container	String inequality. A global function, not a member function.
`template<class charT, class traits, class Alloc> bool operator!=(const charT* s1, const basic_string<charT, traits, Alloc>& s2)`	`basic_string`	String inequality. A global function, not a member function.
`template<class charT, class traits, class Alloc> bool operator!=(const basic_string<charT, traits, Alloc>& s1, const charT* s2)`	`basic_string`	String inequality. A global function, not a member function.
`template<class charT, class traits, class Alloc> bool operator<(const basic_string<charT, traits, Alloc>& s1, const basic_string<charT, traits, Alloc>& s2)`	Container	String comparison. A global function, not a member function.
`template<class charT, class traits, class Alloc> bool operator<(const charT* s1, const basic_string<charT, traits, Alloc>& s2)`	`basic_string`	String comparison. A global function, not a member function.
`template<class charT, class traits, class Alloc> bool operator<(const basic_string<charT, traits, Alloc>& s1, const charT* s2)`	`basic_string`	String comparison. A global function, not a member function.
`template<class charT, class traits, class Alloc> void swap(basic_string<charT, traits, Alloc>& s1, basic_string<charT, traits, Alloc>& s2)`	Container	Swaps the contents of two strings.
`template<class charT, class traits, class Alloc> basic_istream<charT, traits>& operator>>(basic_istream<charT, traits>& is, basic_string<charT, traits, Alloc>& s)`	`basic_string`	Reads s from the input stream is
`template<class charT, class traits, class Alloc> basic_ostream<charT, traits>& operator<<(basic_istream<charT, traits>& os, const basic_string<charT, traits, Alloc>& s)`	`basic_string`	Writes s to the output stream os
`template<class charT, class traits, class Alloc> basic_istream<charT, traits>& getline(basic_istream<charT, traits>& is, basic_string<charT, traits, Alloc>& s, charT delim)`	`basic_string`	Reads a string from the input stream is, stopping when it reaches delim
`template<class charT, class traits, class Alloc> basic_istream<charT, traits>& getline(basic_istream<charT, traits>& is, basic_string<charT, traits, Alloc>& s)`	`basic_string`	Reads a single line from the input stream is

New members

These members are not defined in the Random Access Container and Sequence: requirements, but are specific to basic_string.

Member	Description
`static const size_type npos`	The largest possible value of type size_type. That is, size_type(-1).
`size_type length() const`	Equivalent to size().
size_type capacity() const	Number of elements for which memory has been allocated. That is, the size to which the string can grow before memory must be reallocated. capacity() is always greater than or equal to size().
`const charT* c_str() const`	Returns a pointer to a null-terminated array of characters representing the string's contents. For any string s it is guaranteed that the first s.size() characters in the array pointed to by s.c_str() are equal to the character in s, and that s.c_str()[s.size()] is a null character. Note, however, that it not necessarily the first null character. Characters within a string are permitted to be null.
`const charT* data() const`	Returns a pointer to an array of characters, not necessarily null-terminated, representing the string's contents. data() is permitted, but not required, to be identical to c_str(). The first size() characters of that array are guaranteed to be identical to the characters in this. The return value of data()* is never a null pointer, even if size() is zero.
`basic_string(const basic_string& s, size_type pos = 0, size_type n = npos)`	Constructs a string from a substring of s. The substring begins at character position pos and terminates at character position pos + n or at the end of s, whichever comes first. This constructor throws out_of_range if pos > s.size(). Note that when pos and n have their default values, this is just a copy constructor.
`basic_string(const charT* s)`	Equivalent to basic_string(s, s + traits::length(s)).
`basic_string(const charT* s, size_type n)`	Equivalent to basic_string(s, s + n).
`basic_string& operator=(const charT* s)`	Equivalent to operator=(basic_string(s)).
`basic_string& operator=(charT c)`	Assigns to *this a string whose size is 1 and whose contents is the single character c.
`void reserve(size_t n)`	Requests that the string's capacity be changed; the postcondition for this member function is that, after it is called, capacity() >= n. You may request that a string decrease its capacity by calling reserve() with an argument less than the current capacity. (If you call reserve() with an argument less than the string's size, however, the capacity will only be reduced to size(). A string's size can never be greater than its capacity.) reserve() throws length_error if n > max_size().
`basic_string& insert(size_type pos, const basic_string& s)`	If pos > size(), throws out_of_range. Otherwise, equivalent to insert(begin() + pos, s.begin(), s.end()).
`basic_string& insert(size_type pos, const basic_string& s, size_type pos1, size_type n)`	If pos > size() or pos1 > s.size(), throws out_of_range. Otherwise, equivalent to insert(begin() + pos, s.begin() + pos1, s.begin() + pos1 + min(n, s.size() – pos1)).
`basic_string& insert(size_type pos, const charT* s)`	If pos > size(), throws out_of_range. Otherwise, equivalent to insert(begin() + pos, s, s + traits::length(s))
`basic_string& insert(size_type pos, const charT* s, size_type n)`	If pos > size(), throws out_of_range. Otherwise, equivalent to insert(begin() + pos, s, s + n).
`basic_string& insert(size_type pos, size_type n, charT c)`	If pos > size(), throws out_of_range. Otherwise, equivalent to insert(begin() + pos, n, c).
`basic_string& append(const basic_string& s)`	Equivalent to insert(end(), s.begin(), s.end()).
`basic_string& append(const basic_string& s, size_type pos, size_type n)`	If pos > s.size(), throws out_of_range. Otherwise, equivalent to insert(end(), s.begin() + pos, s.begin() + pos + min(n, s.size() – pos)).
`basic_string& append(const charT* s)`	Equivalent to insert(end(), s, s + traits::length(s)).
`basic_string& append(const charT* s, size_type n)`	Equivalent to insert(end(), s, s + n).
`basic_string& append(size_type n, charT c)`	Equivalent to insert(end(), n, c).
`template<class InputIterator> basic_string& append(InputIterator first, InputIterator last)`	Equivalent to insert(end(), first, last).
`void push_back(charT c)`	Equivalent to insert(end(), c)
`basic_string& operator+=(const basic_string& s)`	Equivalent to append(s).
`basic_string& operator+=(const charT* s)`	Equivalent to append(s)
`basic_string& operator+=(charT c)`	Equivalent to push_back(c)
`basic_string& erase(size_type pos = 0, size_type n = npos)`	If pos > size(), throws out_of_range. Otherwise, equivalent to erase(begin() + pos, begin() + pos + min(n, size() – pos)).
`basic_string& assign(const basic_string& s)`	Synonym for operator=
`basic_string& assign(const basic_string& s, size_type pos, size_type n)`	Equivalent to (but probably faster than) clear() followed by insert(0, s, pos, n).
`basic_string& assign(const charT* s, size_type n)`	Equivalent to (but probably faster than) clear() followed by insert(0, s, n).
`basic_string& assign(const charT* s)`	Equivalent to (but probably faster than) clear() followed by insert(0, s).
`basic_string& replace(size_type pos, size_type n, const basic_string& s)`	Equivalent to erase(pos, n) followed by insert(pos, s).
`basic_string& replace(size_type pos, size_type n, const basic_string& s, size_type pos1, size_type n1)`	Equivalent to erase(pos, n) followed by insert(pos, s, pos1, n1).
`basic_string& replace(size_type pos, size_type n, const charT* s, size_type n1)`	Equivalent to erase(pos, n) followed by insert(pos, s, n1).
`basic_string& replace(size_type pos, size_type n, const charT* s)`	Equivalent to erase(pos, n) followed by insert(pos, s).
`basic_string& replace(size_type pos, size_type n, size_type n1, charT c)`	Equivalent to erase(pos, n) followed by insert(pos, n1, c).
`basic_string& replace(iterator first, iterator last, const basic_string& s)`	Equivalent to insert(erase(first, last), s.begin(), s.end()).
`basic_string& replace(iterator first, iterator last, const charT* s, size_type n)`	Equivalent to insert(erase(first, last), s, s + n).
`basic_string& replace(iterator first, iterator last, const charT* s)`	Equivalent to insert(erase(first, last), s, s + traits::length(s)).
basic_string& replace(iterator first, iterator last, size_type n, charT c)	Equivalent to insert(erase(first, last), n, c).
`template<class InputIterator> basic_string& replace(iterator first, iterator last, InputIterator f, InputIterator l)`	Equivalent to insert(erase(first, last), f, l).
`size_type copy(charT* buf, size_type n, size_type pos = 0) const`	Copies at most n characters from this to a character array. Throws out_of_range* if pos > size(). Otherwise, equivalent to copy(begin() + pos, begin() + pos + min(n, size()), buf). Note that this member function does nothing other than copy characters from this to buf; in particular, it does not terminate buf* with a null character.
`size_type find(const basic_string& s, size_type pos = 0) const`	Searches for s as a substring of this, beginning at character position pos. It is almost the same as search, except that search* tests elements for equality using operator== or a user-provided function object, while this member function uses traits::eq. Returns the lowest character position N such that pos <= N and pos + s.size() <= size() and such that, for every i less than s.size(), (this)[N + i]* compares equal to s[i]. Returns npos if no such position N exists. Note that it is legal to call this member function with arguments such that s.size() > size() – pos, but such a search will always fail.
`size_type find(const charT* s, size_type pos, size_type n) const`	Searches for the first n characters of s as a substring of this, beginning at character pos* of this. This is equivalent to find(basic_string(s, n), pos)*.
`size_type find(const charT* s, size_type pos = 0) const`	Searches for a null-terminated character array as a substring of this, beginning at character pos* of this. This is equivalent to find(basic_string(s), pos)*.
`size_type find(charT c, size_type pos = 0) const`	Searches for the character c, beginning at character position pos. That is, returns the first character position N greater than or equal to pos, and less than size(), such that (this)[N]* compares equal to c. Returns npos if no such character position N exists.
`size_type rfind(const basic_string& s, size_type pos = npos) const`	Searches backward for s as a substring of this. It is almost the same as find_end, except that find_end* tests elements for equality using operator== or a user-provided function object, while this member function uses traits::eq. This member function returns the largest character position N such that N <= pos and N + s.size() <= size(), and such that, for every i less than s.size(), (this)[N + i]* compares equal to s[i]. Returns npos if no such position N exists. Note that it is legal to call this member function with arguments such that s.size() > size(), but such a search will always fail.
`size_type rfind(const charT* s, size_type pos, size_type n) const`	Searches backward for the first n characters of s as a substring of this. Equivalent to rfind(basic_string(s, n), pos)*.
`size_type rfind(const charT* s, size_type pos = npos) const`	Searches backward for a null-terminated character array as a substring of this. Equivalent to rfind(basic_string(s), pos)*.
`size_type rfind(charT c, size_type pos = npos) const`	Searches backward for the character c. That is, returns the largest character position N such that N <= pos and N < size(), and such that (this)[N]* compares equal to c. Returns npos if no such character position exists.
`size_type find_first_of(const basic_string& s, size_type pos = 0) const`	Searches within this, beginning at pos, for the first character that is equal to any character within s. This is similar to the standard algorithm find_first_of, but differs because find_first_of* compares characters using operator== or a user-provided function object, while this member function uses traits::eq. Returns the smallest character position N such that pos <= N < size(), and such that (this)[N]* compares equal to some character within s. Returns npos if no such character position exists.
`size_type find_first_of(const charT* s, size_type pos, size_type n) const`	Searches within this, beginning at pos, for the first character that is equal to any character within the range [s, s+n). That is, returns the smallest character position N such that pos <= N < size(), and such that (this)[N] compares equal to some character in [s, s+n). Returns npos if no such character position exists.
`size_type find_first_of(const charT* s, size_type pos = 0) const`	Equivalent to find_first_of(s, pos, traits::length(s)).
`size_type find_first_of(charT c, size_type pos = 0) const`	Equivalent to find(c, pos).
`size_type find_first_not_of(const basic_string& s, size_type pos = 0) const`	Searches within this, beginning at pos, for the first character that is not equal to any character within s. Returns the smallest character position N such that pos <= N < size(), and such that (this)[N] does not compare equal to any character within s. Returns npos if no such character position exists.
`size_type find_first_not_of(const charT* s, size_type pos, size_type n) const`	Searches within this, beginning at pos, for the first character that is not equal to any character within the range [s, s+n). That is, returns the smallest character position N such that pos <= N < size(), and such that (this)[N] does not compare equal to any character in [s, s+n). Returns npos if no such character position exists.
`size_type find_first_not_of(const charT* s, size_type pos = 0) const`	Equivalent to find_first_not_of(s, pos, traits::length(s)).
`size_type find_first_not_of(charT c, size_type pos = 0) const`	Returns the smallest character position N such that pos <= N < size(), and such that (this)[N]* does not compare equal to c. Returns npos if no such character position exists.
`size_type find_last_of(const basic_string& s, size_type pos = npos) const`	Searches backward within this for the first character that is equal to any character within s. That is, returns the largest character position N such that N <= pos* and N < size(), and such that (this)[N]* compares equal to some character within s. Returns npos if no such character position exists.
`size_type find_last_of(const charT* s, size_type pos, size_type n) const`	Searches backward within this for the first character that is equal to any character within the range [s, s+n). That is, returns the largest character position N such that N <= pos* and N < size(), and such that (this)[N]* compares equal to some character within [s, s+n). Returns npos if no such character position exists.
`size_type find_last_of(const charT* s, size_type pos = npos) const`	Equivalent to find_last_of(s, pos, traits::length(s)).
`size_type find_last_of(charT c, size_type pos = npos) const`	Equivalent to rfind(c, pos).
size_type find_last_not_of(const basic_string& s, size_type pos = npos) const	Searches backward within this for the first character that is not equal to any character within s. That is, returns the largest character position N such that N <= pos* and N < size(), and such that (this)[N]* does not compare equal to any character within s. Returns npos if no such character position exists.
`size_type find_last_not_of(const charT* s, size_type pos, size_type n) const`	Searches backward within this for the first character that is not equal to any character within [s, s+n). That is, returns the largest character position N such that N <= pos* and N < size(), and such that (this)[N]* does not compare equal to any character within [s, s+n). Returns npos if no such character position exists.
`size_type find_last_not_of(const charT* s, size_type pos = npos) const`	Equivalent to find_last_of(s, pos, traits::length(s)).
`size_type find_last_not_of(charT c, size_type pos = npos) const`	Searches backward this for the first character that is not equal to c. That is, returns the largest character position N such that N <= pos* and N < size(), and such that (this)[N]* does not compare equal to c.
`basic_string substr(size_type pos = 0, size_type n = npos) const`	Equivalent to basic_string(this, pos, n)*.
`int compare(const basic_string& s) const`	Three-way lexicographical comparison of s and this, much like strcmp. If traits::compare(data, s.data(), min(size(), s.size()))* is nonzero, then it returns that nonzero value. Otherwise returns a negative number if size() < s.size(), a positive number if size() > s.size(), and zero if the two are equal.
`int compare(size_type pos, size_type n, const basic_string& s) const`	Three-way lexicographical comparison of s and a substring of this. Equivalent to basic_string(this, pos, n).compare(s).
`int compare(size_type pos, size_type n, const basic_string& s, size_type pos1, size_type n1) const`	Three-way lexicographical comparison of a substring of s and a substring of this. Equivalent to basic_string(this, pos, n).compare(basic_string(s, pos1, n1)).
`int compare(const charT* s) const`	Three-way lexicographical comparison of s and this. Equivalent to compare(basic_string(s))*.
`int compare(size_type pos, size_type n, const charT* s, size_type len = npos) const`	Three-way lexicographical comparison of the first min(len, traits::length(s) characters of s and a substring of this. Equivalent to basic_string(this, pos, n).compare(basic_string(s, min(len, traits::length(s)))).
`template<class charT, class traits, class Alloc> basic_string<charT, traits, Alloc> operator+(const basic_string<charT, traits, Alloc>& s1, const basic_string<charT, traits, Alloc>& s2)`	String concatenation. Equivalent to creating a temporary copy of s, appending s2, and then returning the temporary copy.
`template<class charT, class traits, class Alloc> basic_string<charT, traits, Alloc> operator+(const charT* s1, const basic_string<charT, traits, Alloc>& s2)`	String concatenation. Equivalent to creating a temporary basic_string object from s1, appending s2, and then returning the temporary object.
`template<class charT, class traits, class Alloc> basic_string<charT, traits, Alloc> operator+(const basic_string<charT, traits, Alloc>& s1, const charT* s2)`	String concatenation. Equivalent to creating a temporary copy of s, appending s2, and then returning the temporary copy.
`template<class charT, class traits, class Alloc> basic_string<charT, traits, Alloc> operator+(charT c, const basic_string<charT, traits, Alloc>& s2)`	String concatenation. Equivalent to creating a temporary object with the constructor basic_string(1, c), appending s2, and then returning the temporary object.
`template<class charT, class traits, class Alloc> basic_string<charT, traits, Alloc> operator+(const basic_string<charT, traits, Alloc>& s1, charT c)`	String concatenation. Equivalent to creating a temporary object, appending c with push_back, and then returning the temporary object.
`template<class charT, class traits, class Alloc> bool operator==(const charT* s1, const basic_string<charT, traits, Alloc>& s2)`	String equality. Equivalent to basic_string(s1).compare(s2) == 0.
`template<class charT, class traits, class Alloc> bool operator==(const basic_string<charT, traits, Alloc>& s1, const charT* s2)`	String equality. Equivalent to basic_string(s1).compare(s2) == 0.
`template<class charT, class traits, class Alloc> bool operator!=(const charT* s1, const basic_string<charT, traits, Alloc>& s2)`	String inequality. Equivalent to basic_string(s1).compare(s2) == 0.
`template<class charT, class traits, class Alloc> bool operator!=(const basic_string<charT, traits, Alloc>& s1, const charT* s2)`	String inequality. Equivalent to !(s1 == s2).
`template<class charT, class traits, class Alloc> bool operator<(const charT* s1, const basic_string<charT, traits, Alloc>& s2)`	String comparison. Equivalent to !(s1 == s2).
`template<class charT, class traits, class Alloc> bool operator<(const basic_string<charT, traits, Alloc>& s1, const charT* s2)`	String comparison. Equivalent to !(s1 == s2).
`template<class charT, class traits, class Alloc> basic_istream<charT, traits>& operator>>(basic_istream<charT, traits>& is, basic_string<charT, traits, Alloc>& s)`	Reads s from the input stream is. Specifically, it skips whitespace, and then replaces the contents of s with characters read from the input stream. It continues reading characters until it encounters a whitespace character (in which case that character is not extracted), or until end-of-file, or, if is.width() is nonzero, until it has read is.width() characters. This member function resets is.width() to zero.
`template<class charT, class traits, class Alloc> basic_ostream<charT, traits>& operator>>(basic_istream<charT, traits>& is, const basic_string<charT, traits, Alloc>& s)`	Writes s to the output stream is. It writes max(s.size(), is.width()) characters, padding as necessary. This member function resets is.width() to zero.
`template<class charT, class traits, class Alloc> basic_istream<charT, traits>& getline(basic_istream<charT, traits>& is, basic_string<charT, traits, Alloc>& s, charT delim)`	Replaces the contents of s with characters read from the input stream. It continues reading characters until it encounters the character delim (in which case that character is extracted but not stored in s ), or until end of file. Note that getline , unlike operator>>, does not skip whitespace. As the name suggests, it is most commonly used to read an entire line of text precisely as the line appears in an input file.
`template<class charT, class traits, class Alloc> basic_istream<charT, traits>& getline(basic_istream<charT, traits>& is, basic_string<charT, traits, Alloc>& s)`	Equivalent to getline(is, s, is.widen('\n\)).

rope<T, Alloc>

Category: containers

Component type: tye

Description

Ropes are a scalable string implementation: they are designed for efficient operation that involve the string as a whole. Operations such as assignment, concatenation, and substring take time that is nearly independent of the length of the string. Unlike C strings, ropes are a reasonable representation for very long strings such as edit buffers or mail messages. [1]

Though rope s can be treated as Containers of characters, and are almost Sequences, this is rarely the most efficient way to accomplish a task. Replacing an individual character in a rope is slow: each character replacement essentially consists of two substring operations followed by two concatenation operations. Rope s primarily target a more functional programming style.

They differ from vector<char> or reference-counted string implementations in the following ways.

Advantages:

• Much faster concatenation and substring operations involving long strings. Inserting a character in the middle of a 10 megabyte rope should take on the order of 10s of microseconds, even if a copy of the original is kept, e.g. as part of an edit history. In contrast, this would take on the order of a second for conventional "flat" string representation. The time required for concatenation can be viewed as constant for most applications. It is perfectly reasonable to use a rope as the representation of a file inside a text editor.

• Potentially much better space performance. Minor modifications of a rope can share memory with the original. Rope s are allocated in small chunks, significantly reducing memory fragmentation problems introduced by large blocks.

• Assignment is simply a (possibly reference counted) pointer assignment. Unlike reference-counted copy-on-write implementations, this remains largely true even if one of the copies is subsequently slightly modified. It is very inexpensive to checkpoint old versions of a string, e.g. in an edit history.

• It is possible to view a function producing characters as a rope. Thus a piece of a rope may be a 100MByte file, which is read only when that section of the string is examined. Concatenating a string to the end of such a file does not involve reading the file. (Currently the implementation of this facility is incomplete.)

Disadvantages:

• Single character replacements in a rope are expensive. A character update requires time roughly logarithmic in the length of the string. It is implemented as two substring operations followed by two concatenations.

• A rope can be examined a character at a time through a const_iterator in amortized constant time, as for vector<char>. However this is slower than for vector<char> by a significant constant factor (roughly a factor of 5 or 10 if little processing is done on each character and the string is long). Nonconst iterators involve additional checking, and are hence a bit slower still. (We expect that eventually some common algorithms will be specialized so that this cost is not encountered. Currently only output, conversion to a C string, and the single-character find member function are treated in this way.)

• Iterators are on the order of a dozen words in size. This means that copying them, though not tremendously expensive, is not a trivial operation. Avoid postincrementing iterators; use preincrement whenever possible. (The interface also provides primitives for indexing into a string using integer character positions. Passing positions around is clearly much cheaper, but this makes the indexing operation expensive, again roughly logarithmic in the length of the rope.)

Experience with previous implementations for other programming languages suggests that rope s are a good choice as the normal or default representation of strings in a program. It will occasionally be necessary to use some type of character array, such as vector<char>, in places that are particularly sensitive to the performance of traversals or in-place updates. But the use of rope s minimizes the number of cases in which program running times become intolerable due to unexpectedly long string inputs.

A rope is almost, but not quite, a Sequence. It supports random access const_iterators. Forward or backward traversals take constant time per operation. Nonconstant iterators are also provided. However, assignment through a nonconst iterator is an expensive operation (basically logarithmic time, but with a large constant). It should be avoided in frequently executed code.

In order to discourage accidental use of expensive operations, the begin and end member functions on ropes return const_iterator. If non-const iterators are desired, the member functions mutable_begin and mutable_end should be used.

Any modification of a rope invalidates const iterators referring to the rope. Mutable iterators refer to the same position in the same rope after an update. (This may be surprising if the iterators refers to a position after an insertion point.) They remain valid unless the iterator refers to a position that is more than one past the end of the resulting rope.

Definition

Defined in the header rope, and in the backward-compatibility header rope.h. The rope class, and the rope header, are SGI extensions; they are not part of the C++ standard.

Example

crope r(1000000, 'x'); // crope is rope<char>. wrope is rope<wchar_t>

// Builds a rope containing a million 'x's.

// Takes much less than a MB, since the

// different pieces are shared.

crope r2 = r + "abc" + r; // concatenation; takes on the order of 100s

// of machine instructions; fast

crope r3 = r2.substr(1000000, 3); // yields "abc"; fast.

crope r4 = r2.substr(1000000, 1000000); // also fast.

reverse(r2.mutable_begin(), r2.mutable_end()); // correct, but slow; may take a

// minute or more.

Template parameters

Parameter	Description	Default
`T`	The rope 's value type: usually char or wchar_t. [2]
`Alloc`	The rope 's allocator, used for all internal memory management.	`alloc`

Model of

Random Access Container. Almost, but not quite, a model of Front Insertion Sequence and Back Insertion Sequence.

Type requirements

None, except for those imposed by the requirements of Random Access Container.

Public base classes

None.

Members

Member	Where defined	Description
`value_type`	Container	The rope's value type T, usually char or wchar_t.
`difference_type`	Container	A signed integral type.
`size_type`	Container	An unsigned integral type.
reference	Container	Reference to a rope element. [3]
`const_reference`	Container	Const reference to T. [3]
`pointer`	Container	Pointer to T. [3]
`const_pointer`	Container	Const pointer to T. [3]
`const_reverse_iterator`	Reversible	Container Const iterator used to iterate backwards through a rope.
`reverse_iterator`	Reversible	Container Mutable iterator used to iterate backwards through a rope.
`iterator`	Container	Mutable random access iterator used to iterate through a rope.
`const_iterator`	Container	Const random access iterator used to iterate through a rope.
`rope(const charT* s)`	`rope`	Constructs a rope from a C string.
`rope(const charT* s, size_t n)`	`rope`	Constructs a rope from a (not necessarily null-terminated) array of charT.
`rope(const const_iterator& f, const const_iterator& l)`	Sequence	Creates a rope with a copy of a range.
`rope(const iterator& f, const iterator& l)`	Sequence	Creates a rope with a copy of a range.
`rope(const charT* f, const charT* l)`	Sequence	Creates a rope with a copy of a range.
`rope(charT c)`	`rope`	Single-character constructor.
`rope()`	Container	Default constructor.
`rope(char_producer<charT>*, size_t, bool)`	`rope`	See below.
`rope(const rope& x)`	Container	The copy constructor.
`~rope()`	Container	The destructor.
`rope& operator=(const rope&x)`	Container	The assignment operator.
`void swap(rope& x)`	Container	Swaps the contents of two ropes.
`size_type size() const`	Container	Returns the size of the rope.
`size_type length() const`	`rope`	Same as size
size_type max_size() const	Container	Size of longest rope guaranteed to be representable.
`bool empty() const`	Container	Equivalent to size() == 0.
`const_iterator begin() const`	Container	Returns an const_iterator pointing to the beginning of the rope.
`const_iterator end() const`	Container	Returns an const_iterator pointing to the end of the rope.
`iterator mutable_begin()`	`rope`	Returns an iterator pointing to the beginning of the rope.
`iterator mutable_end()`	`rope`	Returns an iterator pointing to the end of the rope.
`const_reverse_iterator rbegin() const`	Reversible Container	Returns a const_reverse_iterator pointing to the beginning of the reversed rope
`const_reverse_iterator rend() const`	Reversible Container	Returns a const_reverse_iterator pointing to the end of the reversed rope
`iterator mutable_rbegin()`	`rope`	Returns a reverse_iterator pointing to the beginning of the reversed rope.
`iterator mutable_rend()`	`rope`	Returns a reverse_iterator pointing to the end of the reversed rope.
`charT operator[](size_type n) const`	Random Access	Container Returns the n'th element.
`charT at(size_type pos) const`	Random Access	Container Returns the n'th element.
`reference mutable_reference_at(size_type n)`	`rope`	Returns a reference to the n th element.
`int compare(const rope&) const`	`rope`	Three-way comparison. See below.
`charT front() const`	Sequence	Returns the first element.
`charT back() const`	Back Insertion Sequence	Returns the last element.
`void push_front()`	Front Insertion Sequence	Inserts a new element at the front.
`void push_back(charT)`	Back Insertion Sequence	Inserts a new element at the end.
`void pop_front()`	Front Insertion Sequence	Removes the first element.
`void pop_back()`	Back Insertion Sequence	Removes the last element.
`iterator insert(const iterator& p, const rope& x)`	`rope`	Inserts the contents of x before p.
`iterator insert(const iterator& p, charT c)`	Sequence	Inserts c before p.
`iterator insert(const iterator& p)`	Sequence	Inserts charT() before p.
`iterator insert(const iterator& p, size_t n, charT c)`	Sequence	Inserts n copies of c before p.
`iterator insert(const iterator& p, const charT* s)`	rope	Inserts a C string before p.
`iterator insert(const iterator& p, const charT* s, size_t n)`	`rope`	Inserts a (not necessarily null-terminated) array of charT before p.
`iterator insert(const iterator& p, const charT* f, const char* l)`	Sequence	Inserts the range [f, l) before p.
`iterator insert(const iterator& p, const const_iterator& f, const const_iterator& l)`	Sequence	Inserts the range [f, l) before p.
`iterator insert(const iterator& p, const iterator& f, const iterator& l)`	Sequence	Inserts the range [f, l) before p.
`void insert(size_t i, const rope& x)`	`rope`	Inserts the contents of x before the ith element.
`void insert(size_t i, charT c)`	`rope`	Inserts the character c before the ith element.
`void insert(size_t i)`	`rope`	Inserts the character charT() before the ith element.
`void insert(size_t i, size_t n, charT c)`	`rope`	Inserts n copies of c before the ith element.
`void insert(size_t i, const charT* s)`	`rope`	Inserts a C string before the ith element.
`void insert(size_t i, const charT* s, size_t n)`	`rope`	Inserts a (not necessarily null-terminated) array of charT before the ith element.
`void insert(size_t i, const charT* f, const charT* l)`	`rope`	Inserts the range [f, l) before the ith element.
`void insert(size_t i, const const_iterator& f, const const_iterator& l)`	`rope`	Inserts the range [f, l) before the ith element.
`void insert(size_t i, const iterator& f, const iterator& l)`	`rope`	Inserts the range [f, l) before the ith element.
`void erase(const iterator& p)`	Sequence	Erases the element pointed to by p.
`void erase(const iterator& f, const iterator& l)`	Sequence	Erases the range [f, l).
`void erase(size_t i, size_t n)`	`rope`	Erases n elements, starting with the ith element.
`append(const charT* s)`	`rope`	Appends a C string.
`append(const charT* s, size_t)`	`rope`	Appends a (not necessarily null-terminated) array of charT.
`append(const charT* f, const charT* l)`	`rope`	Appends a range.
`append(charT c)`	`rope`	Appends the character c.
`append()`	`rope`	Appends the character charT().
`append(size_t n, charT c)`	`rope`	Appends n copies of c.
`append(const rope& x)`	`rope`	Appends the rope x.
`void replace(const iterator& f, const iterator& l, const rope&)`	`rope`	See below.
`void replace(const iterator& f, const iterator& l, charT)`	`rope`	See below.
`void replace(const iterator& f, const iterator& l, const charT* s)`	`rope`	See below.
`void replace(const iterator& f, const iterator& l, const charT* s, size_t n)`	`rope`	See below.
`void replace(const iterator& f1, const iterator& l1, const charT* f2, const charT* l2)`	`rope`	See below.
`void replace(const iterator& f1, const iterator& l1, const const_iterator& f2, const const_iterator& l2)`	`rope`	See below.
`void replace(const iterator& f1, const iterator& l1, const iterator& f2, const iterator& l2)`	`rope`	See below.
`void replace(const iterator& p, const rope& x)`	`rope`	See below.
`void replace(const iterator& p, charT c)`	`rope`	See below.
`void replace(const iterator& p, const charT* s)`	`rope`	See below.
`void replace(const iterator& p, const charT* s, size_t n)`	`rope`	See below.
`void replace(const iterator& p, const charT* f, const charT* l)`	`rope`	See below.
`void replace(const iterator& p, const_iterator f, const_iterator l)`	`rope`	See below.
`void replace(const iterator& p, iterator f, iterator l)`	`rope`	See below.
`void replace(size_t i, size_t n, const rope& x)`	`rope`	See below.
`void replace(size_t i, size_t n, const charT* s, size_t n)`	`rope`	See below.
`void replace(size_t i, size_t n, charT c)`	`rope`	See below.
`void replace(size_t i, size_t n, const charT* s)`	`rope`	See below.
`void replace(size_t i, size_t n, const charT* f, const charT* l)`	`rope`	See below.
`void replace(size_t i, size_t n, const const_iterator& f, const const_iterator& l)`	`rope`	See below.
`void replace(size_t i, size_t n, const iterator& f, const iterator& l)`	`rope`	See below.
`void replace(size_t i, charT c)`	`rope`	See below.
`void replace(size_t i, const rope& x)`	`rope`	See below.
`void replace(size_t i, const charT* s)`	`rope`	See below.
`void replace(size_t i, const charT* s, size_t n)`	`rope`	See below.
`void replace(size_t i, const charT* f, const charT* l)`	`rope`	See below.
`void replace(size_t i, const const_iterator& f, const const_iterator& l)`	`rope`	See below.
`void replace(size_t i, const iterator& f, const iterator& l)`	`rope`	See below.
`rope substr(iterator f) const`	`rope`	See below.
`rope substr(const_iterator f) const`	`rope`	See below.
`rope substr(iterator f, iterator l) const`	`rope`	See below.
`rope substr(const_iterator f, const_iterator l) const`	`rope`	See below.
`rope substr(size_t i, size_t n = 1) const`	`rope`	See below.
`void copy(charT* buf) const`	`rope`	Copies a rope into an array of charT.
`size_type copy(size_type pos, size_type n, charT* buf)`	`rope`	Copies a rope into an array of charT.
`const charT* c_str() const`	`rope`	See below.
`void delete_c_str()`	`rope`	See below.
`rope operator+(const rope& L, const rope&R)`	`rope`	Concatenates L and R. This is a global function, not a member function.
`rope& operator+=(rope& L, const rope& R)`	`rope`	Appends R to L. This is a global function, not a member function.
`rope operator+(const rope& L, const charT* s)`	`rope`	Concatenates L and s. This is a global function, not a member function.
`rope& operator+=(rope& L, const charT* s)`	`rope`	Appends s to L. This is a global function, not a member function.
`rope operator+(const rope& L, charT c)`	`rope`	Concatenates L and c. This is a global function, not a member function.
`rope& operator+=(rope& L, charT c)`	`rope`	Appends c to L. This is a global function, not a member function.
`bool operator<(const rope&, const rope&)`	Forward Container	Lexicographical comparison. This is a global function, not a member function.
`bool operator==(const rope&, const rope*)`	Forward Container	Tests two ropes for equality. This is a global function, not a member function.
`ostream& operator<<(ostream& os, rope x)`	`rope`	Outputs x to the stream os. This is a global function, not a member function.

New members

These members are not defined in the Random Access Container requirements, but are specific to rope:

Function	Description
`rope(const charT* s)`	Constructs a rope from a C string. The rope consists of the sequence of characters starting with *s up to, but not including, the first null character.
`rope(const charT* s, size_t n)`	Constructs a rope from an array of charT. The rope consists of the characters in the range [s, s + n). Note that this range is permitted to contain embedded null characters.
`rope(charT c)`	Constructs a rope consisting of the single character c.
`rope(char_producer<charT>* cp, size_t n, bool destroy)`	Constructs a rope of size n, whose characters are computed as needed by cp. The object cp must be valid as long as any reference to the resulting rope, or a rope* derived from it, may be used. If destroy is true, then delete cp will be executed automatically once cp is no longer needed. Typically destroy will be true unless cp is a pointer to statically allocated storage. It is rarely safe to allocate *cp on the stack.
`size_type length() const`	Synonym for size
`iterator mutable_begin()`	Returns an iterator pointing to the beginning of the rope. This member function exists because mutable rope iterators are much more expensive than constant rope iterators.
`iterator mutable_end()`	Returns an iterator pointing to the end of the rope. This member function exists because mutable rope iterators are much more expensive than constant rope iterators.
`iterator mutable_rbegin()`	Returns a reverse_iterator pointing to the beginning of the reversed rope. This member function exists because mutable rope iterators are much more expensive than constant rope iterators.
`iterator mutable_rend()`	Returns a reverse_iterator pointing to the end of the reversed rope. This member function exists because mutable rope iterators are much more expensive than constant rope iterators.
`reference mutable_reference_at(size_type n)`	Returns a reference to the n th element. This member function exists because mutable references to rope elements have fairly high overhead.
`int compare(const rope& x)`	Three-way comparison, much like the function strcmp from the standard C library. Returns a negative number if this is lexicographically less than x, a positive number if this is lexicographically greater than x, and zero if neither rope is lexicographically less than the other.
`iterator insert(const iterator& p, const rope& x)`	Inserts the contents of the ropex immediately before the position p.
`iterator insert(const iterator& p, const charT* s)`	Inserts a C string immediately before the position p. The elements that are inserted are the sequence of characters starting with *s and up to, but not including, the first null character.
`iterator insert(const iterator& p, const charT* s, size_t n)`	Inserts an array of charT. The elements that are inserted are the range [s, s + n). Note that this range is permitted to contain embedded null characters.
`void insert(size_t i, const rope& x)`	Inserts the contents of the rope x immediately before the ith element.
`void insert(size_t i, size_t n, charT c)`	Inserts n copies of c immediately before the ith element.
`void insert(size_t i, const charT* s)`	Inserts a C string immediately before the ith element. The elements that are inserted are the sequence of characters starting with *s and up to, but not including, the first null character.
`void insert(size_t i, const charT* s, size_t n)`	Inserts an array of charT immediately before the ith element. The elements that are inserted are the range [s, s + n). Note that this range is permitted to contain embedded null characters.
`void insert(size_t i, charT c)`	Inserts the character c immediately before the ith element.
`void insert(size_t i)`	Inserts the character charT() immediately before the ith element.
`void insert(size_t i, const charT* f, const charT* l)`	Inserts the range [f, l) immediately before the ith element.
`void insert(size_t i, const const_iterator& f, const const_iterator& l)`	Inserts the range [f, l) immediately before the ith element.
`void insert(size_t i, const iterator& f, const iterator& l)`	Inserts the range [f, l) immediately before the ith element.
`void erase(size_t i, size_t n)`	Erases n elements, starting with the ith element.
`append(const charT* s)`	Adds a C string to the end of the rope. The elements that are inserted are the sequence of characters starting with *s and up to, but not including, the first null character.
`append(const charT* s, size_ nt)`	Adds an array of charT to the end of the rope. The elements that are inserted are the range [s, s + n). Note that this range is permitted to contain embedded null characters.
`append(const charT* f, const charT* l)`	Adds the elements in the range [f, l) to the end of the rope.
`append(charT c)`	Adds the character c to the end of the rope.
`append()`	Adds the character charT() to the end of the rope.
`append(const rope& x)`	Adds the contents of the rope x to the end of *this.
`append(size_t n, charT c)`	Adds n copies of c to the end of *this.
`void replace(const iterator& f, const iterator& l, const rope& x)`	Replaces the elements in the range [f, l) with the elements in x.
`void replace(const iterator& f, const iterator& l, charT c)`	Replaces the elements in the range [f, l) with the single character c.
`void replace(const iterator& f, const iterator& l, const charT* s)`	Replaces the elements in the range [f, l) with a C string: the sequence of characters beginning with *s and up to, but not including, the first null character.
`void replace(const iterator& f, const iterator& l, const charT* s, size_t n)`	Replaces the elements in the range [f, l) with the elements in the range [s, s + n).
`void replace(const iterator& f1, const iterator& l1, const charT* f2, const charT* l2)`	Replaces the elements in the range [f1, l1) with the elements in the range [f2, l2).
`void replace(const iterator& f1, const iterator& l1, const const_iterator& f2, const const_iterator& l2)`	Replaces the elements in the range [f1, l1) with the elements in the range [f2, l2).
`void replace(const iterator& f1, const iterator& l1, const iterator& f2, const iterator& l2)`	Replaces the elements in the range [f1, l1) with the elements in the range [f2, l2).
`void replace(const iterator& p, const rope& x)`	Replaces the element pointed to by p with the elements in x.
`void replace(const iterator& p, charT c)`	Replaces the element pointed to by p with the single character c.
`void replace(const iterator& p, const charT* s)`	Replaces the element pointed to by p with a C string: the sequence of characters beginning with *s and up to, but not including, the first null character.
`void replace(const iterator& p, const charT* s, size_t n)`	Replaces the element pointed to by p with the elements in the range [s, s + n).
`void replace(const iterator& p, const charT* f, const charT* l)`	Replaces the element pointed to by p with the elements in the range [f, l).
`void replace(const iterator& p, const_iterator f, const_iterator l)`	Replaces the element pointed to by p with the elements in the range [f, l).
`void replace(const iterator& p, iterator f, iterator l)`	Replaces the element pointed to by p with the elements in the range [f, l).
`void replace(size_t i, size_t n, const rope& x)`	Replaces the n elements beginning with the ith element with the elements in x.
`void replace(size_t i, size_t n, charT c)`	Replaces the n elements beginning with the ith element with the single character c.
`void replace(size_t i, size_t n, const charT* s)`	Replaces the n elements beginning with the ith element with an array of charT: the sequence of characters beginning with *s and up to, but not including, the first null character.
`void replace(size_t i, size_t n1, const charT* s, size_t n2)`	Replaces the n1 elements beginning with the ith element with the elements in the range [s, s + n2).
`void replace(size_t i, size_t n, const charT* f, const charT* l)`	Replaces the n elements beginning with the ith element with the characters in the range [f, l).
`void replace(size_t i, size_t n, const const_iterator& f, const const_iterator& l)`	Replaces the n elements beginning with the ith element with the characters in the range [f, l).
`void replace(size_t i, size_t n, const iterator& f, const iterator& l)`	Replaces the n elements beginning with the ith element with the characters in the range [f, l).
`void replace(size_t i, charT c)`	Replaces the ith element with the character c.
`void replace(size_t i, const rope& x)`	Replaces the ith element with elements from the rope x.
`void replace(size_t i, const charT* s)`	Replaces the ith element with a C string: the sequence of characters beginning with *s and up to, but not including, the first null character.
`void replace(size_t i, const charT* s, size_t n)`	Replaces the ith element with the elements in the range [s, s + n).
`void replace(size_t i, const charT* f, const charT* l)`	Replaces the ith element with the range [f, l).
`void replace(size_t i, const const_iterator& f, const const_iterator& l)`	Replaces the ith element with the range [f, l).
`void replace(size_t i, const iterator& f, const iterator& l)`	Replaces the ith element with the range [f, l).
`rope substr(iterator f) const`	Returns a new rope with a single element, *f. [4]
`rope substr(const_iterator f) const`	Returns a new rope with a single element, *f. [4]
rope substr(iterator f, iterator l) const	Returns a new rope that consists of the range [f, l). [4]
`rope substr(const_iterator f, const_iterator l) const`	Returns a new rope that consists of the range [f, l). [4]
`rope substr(size_t i, size_t n = 1) const`	Returns a new rope whose elements are the n characters starting at the position i. [4].
`void copy(charT* buf) const`	Copies the characters in a rope into buf.
`size_type copy(size_type pos, size_type n, charT* buf)`	Copies n characters, starting at position pos in the rope, into buf. If the rope contains fewer than pos + n characters, then instead it only copies size() – pos characters.
`const charT* c_str() const`	Returns a pointer to a null-terminated sequence of characters that contains all of the characters in a rope. [5] [6] The resulting sequence of characters is valid at least as long as the rope remains valid and unchanged. Note that the first invocation of this operation on long strings is slow: it is linear in the length of the rope.
`void delete_c_str()`	Reclaims the internal storage used by c_str. Note that this invalidates the pointer that c_str returns.
`rope operator+(const rope& L, const rope& R)`	Returns a new rope consisting of the concatenation of L and R. This is a global function, not a member function.
`rope& operator+=(rope& L, const rope& R)`	Modifies L by appending R, and returns L. This is a global function, not a member function.
`rope operator+(const rope& L, const charT* s)`	Returns a new rope consisting of the concatenation of L and all of the characters from s up to, but not including, the first null character. This is a global function, not a member function.
`rope& operator+=(rope& L, const charT* s)`	Modifies L by appending the characters from s up to, but not including, the first null character. The return value is L. This is a global function, not a member function.
`rope operator+(const rope& L, charT c)`	Returns a new rope consisting of L with the character c appended to it. This is a global function, not a member function.
`rope& operator+=(rope& L, charT c)`	Modifies L by appending the character c. This is a global function, not a member function.
`ostream& operator<<(ostream& os, rope x)`	Outputs x to the stream os. This is a global function, not a member function.

Notes

[1] For a detailed discussion of the rope data structure, see H.-J. Boehm, R. Atkinson, and M. Plass, "Ropes: An Alternative to Strings", Software Practice and Experience 25(12):1315, 1995.

[2] Since the value type is usually either char or wchar_t, the library introduces two abbreviations: crope is a typedef for rope<char>, and wrope is a typedef for rope<wchar_t>.

[3] Rope::reference is not value_type&, but a proxy type. In fact, reference is a typedef for the nested class charT_ref_proxy. Const_reference, however, is simply const value_type&. Similarly, const_pointer is just const value_type* but pointer is a proxy type. If r is an object of type reference, then &r is of type pointer.

[4] Note that the return value of substr is conceptually a distinct rope: the two rope s may share storage, but this is a hidden implementation detail. If you modify a rope returned by substr, this will not change the value of the original rope.

[5] The final const qualifier in the member function c_str() is conceptually slightly inaccurate in the interest of conformance to the basic_string interface in the draft C++ standard; the rope is updated to cache the converted string.

[6] Concurrent calls to c_str() are allowed; the cache is updated atomically.

Container adaptors

stack<T, Sequence>

Categories: containers, adaptors

Component type: type

Description

A stack is an adaptor that provides a restricted subset of Container functionality: it provides insertion, removal, and inspection of the element at the top of the stack. Stack is a "last in first out" (LIFO) data structure: the element at the top of a stack is the one that was most recently added. [1] Stack does not allow iteration through its elements. [2]

Stack is a container adaptor, meaning that it is implemented on top of some underlying container type. By default that underlying type is deque, but a different type may be selected explicitly.

Example

int main() {

stack<int> S;

S.push(8);

S.push(7);

S.push(4);

assert(S.size() == 3);

assert(S.top() == 4);

S.pop();

assert(S.top() == 7);

S.pop();

assert(S.top() == 8);

S.pop();

assert(S.empty());

}

Definition

Defined in the standard header stack, and in the nonstandard backward-compatibility header stack.h.

Template parameters

Parameter	Description	Default
`T`	The type of object stored in the stack.
`Sequence`	The type of the underlying container used to implement the stack.	`deque<T>`

Model of

Assignable, Default Constructible

Type requirements

• T is a model of Assignable.

• Sequence is a model of Back Insertion Sequence.

• Sequence::value_type is the same type as T.

• If operator== is used, then T is a model of Equality Comparable

• If operator< is used, then T is a model of LessThan Comparable.

Public base classes

None.

Members

Member	Where defined	Description
`value_type`	`stack`	See below.
`size_type`	`stack`	See below.
`stack()`	Default Constructible	The default constructor. Creates an empty stack.
`stack(const stack&)`	Assignable	The copy constructor.
`stack& operator=(const stack&)`	Assignable	The assignment operator.
`bool empty() const`	`stack`	See below.
`size_type size() const`	`stack`	See below.
`value_type& top()`	`stack`	See below.
`const value_type& top() const`	`stack`	See below.
`void push(const value_type&)`	`stack`	See below.
`void pop()` [3]	`stack`	See below.
`bool operator==(const stack&, const stack&)`	`stack`	See below.
`bool operator<(const stack&, const stack&)`	`stack`	See below.

New members

These members are not defined in the Assignable and Default Constructible requirements, but are specific to stack.

Member	Description
`value_type`	The type of object stored in the stack. This is the same as T and Sequence::value_type.
`size_type`	An unsigned integral type. This is the same as Sequence::size_type.
`bool empty() const`	Returns true if the stack contains no elements, and false otherwise. S.empty() is equivalent to S.size() == 0.
`size_type size() const`	Returns the number of elements contained in the stack.
`value_type& top()`	Returns a mutable reference to the element at the top of the stack. Precondition: empty() is false.
`const value_type& top() const`	Returns a const reference to the element at the top of the stack. Precondition: empty() is false.
`void push(const value_type& x)`	Inserts x at the top of the stack. Postconditions: size() will be incremented by 1, and top() will be equal to x.
`void pop()`	Removes the element at the top of the stack. [3] Precondition: empty() is false. Postcondition: size() will be decremented by 1.
`bool operator==(const stack&, const stack&)`	Compares two stacks for equality. Two stacks are equal if they contain the same number of elements and if they are equal element-by-element. This is a global function, not a member function.
`bool operator<(const stack&, const stack&)`	Lexicographical ordering of two stacks. This is a global function, not a member function.

Notes

[1] Stacks are a standard data structure, and are discussed in all algorithm books. See, for example, section 2.2.1 of Knuth. (D. E. Knuth, The Art of Computer Programming. Volume 1: Fundamental Algorithms, second edition. Addison-Wesley, 1973.)

[2] This restriction is the only reason for stack to exist at all. Note that any Front Insertion Sequence or Back Insertion Sequence can be used as a stack; in the case of vector, for example, the stack operations are the member functions back, push_back, and pop_back. The only reason to use the container adaptor stack instead is to make it clear that you are performing only stack operations, and no other operations.

[3] One might wonder why pop() returns void, instead of value_type. That is, why must one use top() and pop() to examine and remove the top element, instead of combining the two in a single member function? In fact, there is a good reason for this design. If pop() returned the top element, it would have to return by value rather than by reference: return by reference would create a dangling pointer. Return by value, however, is inefficient: it involves at least one redundant copy constructor call. Since it is impossible for pop() to return a value in such a way as to be both efficient and correct, it is more sensible for it to return no value at all and to require clients to use top() to inspect the value at the top of the stack.

queue<T, Sequence>

Categories: containers, adaptors

Component type: type

Description

A queue is an adaptor that provides a restricted subset of Container functionality A queue is a "first in first out" (FIFO) data structure. [1] That is, elements are added to the back of the queue and may be removed from the front; Q.front() is the element that was added to the queue least recently. Queue does not allow iteration through its elements. [2]

Queue is a container adaptor, meaning that it is implemented on top of some underlying container type. By default that underlying type is deque, but a different type may be selected explicitly.

Example

int main() {

queue<int> Q;

Q.push(8);

Q.push(7);

Q.push(6);

Q.push(2);

assert(Q.size() == 4);

assert(Q.back() == 2);

assert(Q.front() == 8);

Q.pop();

assert(Q.front() == 7);

Q.pop();

assert(Q.front() == 6);

Q.pop();

assert(Q.front() == 2);

Q.pop();

assert(Q.empty());

}

Definition

Defined in the standard header queue, and in the nonstandard backward-compatibility header stack.h.

Template parameters

Parameter	Description	Default
`T`	The type of object stored in the queue.
`Sequence`	The type of the underlying container used to implement the queue.	`deque<T>`

Model of

Assignable, Default Constructible

Type requirements

• T is a model of Assignable.

• Sequence is a model of Front Insertion Sequence.

• Sequence is a model of Back Insertion Sequence.

• Sequence::value_type is the same type as T.

• If operator== is used, then T is a model of Equality Comparable

• If operator< is used, then T is a model of LessThan Comparable.

Public base classes

None.

Members

Member	Where defined	Description
`value_type`	`queue`	See below.
`size_type`	`queue`	See below.
`queue()`	Default Constructible	The default constructor. Creates an empty queue.
`queue(const queue&)`	Assignable	The copy constructor.
`queue& operator=(const queue&)`	Assignable	The assignment operator.
`bool empty() const`	`queue`	See below.
`size_type size() const`	`queue`	See below.
`value_type& front()`	`queue`	See below.
`const value_type& front() const`	`queue`	See below.
`value_type& back()`	`queue`	See below.
`const value_type& back() const`	`queue`	See below.
`void push(const value_type&)`	`queue`	See below.
`void pop()` [3]	`queue`	See below.
`bool operator==(const queue&, const queue&)`	`queue`	See below.
`bool operator<(const queue&, const queue&)`	`queue`	See below.

New members

These members are not defined in the Assignable and Default Constructible requirements, but are specific to queue.

Member	Description
`value_type`	The type of object stored in the queue. This is the same as T and Sequence::value_type.
`size_type`	An unsigned integral type. This is the same as Sequence::size_type.
`bool empty() const`	Returns true if the queue contains no elements, and false otherwise. Q.empty() is equivalent to Q.size() == 0.
size_type size() const	Returns the number of elements contained in the queue.
`value_type& front()`	Returns a mutable reference to the element at the front of the queue, that is, the element least recently inserted. Precondition: empty() is false.
`const value_type& front() const`	Returns a const reference to the element at the front of the queue, that is, the element least recently inserted. Precondition: empty() is false.
`value_type& back()`	Returns a mutable reference to the element at the back of the queue, that is, the element most recently inserted. Precondition: empty() is false.
`const value_type& back() const`	Returns a const reference to the element at the back of the queue, that is, the element most recently inserted. Precondition: empty() is false.
`void push(const value_type& x)`	Inserts x at the back of the queue. Postconditions: size() will be incremented by 1, and back() will be equal to x.
`void pop()`	Removes the element at the front of the queue. [3] Precondition: empty() is false. Postcondition: size() will be decremented by 1.
`bool operator==(const queue&, const queue&)`	Compares two queues for equality. Two queues are equal if they contain the same number of elements and if they are equal element-by-element. This is a global function, not a member function.
`bool operator<(const queue&, const queue&)`	Lexicographical ordering of two queues. This is a global function, not a member function.

Notes

[1] Queues are a standard data structure, and are discussed in all algorithm books. See, for example, section 2.2.1 of Knuth. (D. E. Knuth, The Art of Computer Programming. Volume 1: Fundamental Algorithms, second edition. Addison-Wesley, 1973.)

[2] This restriction is the only reason for queue to exist at all. Any container that is both a front insertion sequence and a back insertion sequence can be used as a queue; deque, for example, has member functions front, back, push_front, push_back, pop_front, and pop_back The only reason to use the container adaptor queue instead of the container deque is to make it clear that you are performing only queue operations, and no other operations.

[3] One might wonder why pop() returns void, instead of value_type. That is, why must one use front() and pop() to examine and remove the element at the front of the queue, instead of combining the two in a single member function? In fact, there is a good reason for this design. If pop() returned the front element, it would have to return by value rather than by reference: return by reference would create a dangling pointer. Return by value, however, is inefficient: it involves at least one redundant copy constructor call. Since it is impossible for pop() to return a value in such a way as to be both efficient and correct, it is more sensible for it to return no value at all and to require clients to use front() to inspect the value at the front of the queue.

priority_queue<T, Sequence, Compare>

Categories: containers, adaptors

Component type: type

Description

A priority_queue is an adaptor that provides a restricted subset of Container functionality: it provides insertion of elements, and inspection and removal of the top element. It is guaranteed that the top element is the largest element in the priority_queue, where the function object Compare is used for comparisons. [1] Priority_queue does not allow iteration through its elements. [2]

Priority_queue is a container adaptor, meaning that it is implemented on top of some underlying container type. By default that underlying type is vector, but a different type may be selected explicitly.

Example

int main() {

priority_queue<int> Q;

Q.push(1);

Q.push(4);

Q.push(2);

Q.push(8);

Q.push(5);

Q.push(7);

assert(Q.size() == 6);

assert(Q.top() == 8);

Q.pop();

assert(Q.top() == 7);

Q.pop();

assert(Q.top() == 5);

Q.pop();

assert(Q.top() == 4);

Q.pop();

assert(Q.top() == 2);

Q.pop();

assert(Q.top() == 1);

Q.pop();

assert(Q.empty());

}

Definition

Defined in the standard header queue, and in the nonstandard backward-compatibility header stack.h.

Template parameters

Parameter	Description	Default
`T`	The type of object stored in the priority queue.
`Sequence`	The type of the underlying container used to implement the priority queue.	`vector<T>`
`Compare`	The comparison function used to determine whether one element is smaller than another element. If Compare(x,y) is true, then x is smaller than y. The element returned by Q.top() is the largest element in the priority queue. That is, it has the property that, for every other element x in the priority queue, Compare(Q.top(), x) is false.	`less<T>`

Model of

Assignable, Default Constructible

Type requirements

• T is a model of Assignable.

• Sequence is a model of Sequence.

• Sequence is a model of Random Access Container.

• Sequence::value_type is the same type as T.

• Compare is a model of Binary Predicate.

• Compare induces a strict weak ordering, as defined in the LessThan Comparable requirements, on its argument type.

• T is convertible to Compare's argument type.

Public base classes

None.

Members

Member	Where defined	Description
`value_type`	`priority_queue`	See below.
`size_type`	`priority_queue`	See below.
`priority_queue()`	Default Constructible	The default constructor. Creates an empty priority_queue, using Compare() as the comparison function.
`priority_queue(const priority_queue&)`	Assignable	The copy constructor.
`priority_queue(const Compare&)`	`priority_queue`	See below.
`priority_queue(const value_type, const value_type)`	`priority_queue`	See below.
`priority_queue(const value_type, const value_type, const Compare&)`	`priority_queue`	See below.
`priority_queue& operator=(const priority_queue&)`	Assignable	The assignment operator.
`bool empty() const`	`priority_queue`	See below.
`size_type size() const`	`priority_queue`	See below.
`const value_type& top() const`	`priority_queue`	See below.
`void push(const value_type&)`	`priority_queue`	See below.
`void pop()` [3]	`priority_queue`	See below.

New members

These members are not defined in the Assignable and Default Constructible requirements, but are specific to priority_queue.

Member	Description
`value_type`	The type of object stored in the priority_queue. This is the same as T and Sequence::value_type.
`size_type`	An unsigned integral type. This is the same as Sequence::size_type.
`priority_queue(const Compare& comp)`	The constructor. Creates an empty priority_queue, using comp as the comparison function. The default constructor uses Compare() as the comparison function.
`priority_queue(const value_type* first, const value_type* last)`	The constructor. Creates a priority_queue initialized to contain the elements in the range [first, last), and using Compare() as the comparison function.
`priority_queue(const value_type* first, const value_type* last, const Compare& comp)`	The constructor. Creates a priority_queue initialized to contain the elements in the range [first, last), and using comp as the comparison function.
`bool empty() const`	Returns true if the priority_queue contains no elements, and false otherwise. S.empty() is equivalent to S.size() == 0.
`size_type size() const`	Returns the number of elements contained in the priority_queue.
`const value_type& top() const`	Returns a const reference to the element at the top of the priority_queue. The element at the top is guaranteed to be the largest element in the priority queue, as determined by the comparison function Compare. That is, for every other element x in the priority_queue, Compare(Q.top(), x) is false. Precondition: empty() is false.
`void push(const value_type& x)`	Inserts x into the priority_queue. Postcondition: size() will be incremented by 1.
`void pop()`	Removes the element at the top of the priority_queue, that is, the largest element in the priority_queue. [3] Precondition: empty() is false. Postcondition: size() will be decremented by 1.

Notes

[1] Priority queues are a standard concept, and can be implemented in many different ways; this implementation uses heaps. Priority queues are discussed in all algorithm books; see, for example, section 5.2.3 of Knuth. (D. E. Knuth, The Art of Computer Programming. Volume 3: Sorting and Searching. Addison-Wesley, 1975.)

[2] This restriction is the only reason for priority_queue to exist at all. If iteration through elements is important, you can either use a vector that is maintained in sorted order, or a set, or a vector that is maintained as a heap using make_heap, push_heap, and pop_heap. Priority_queue is, in fact, implemented as a random access container that is maintained as a heap. The only reason to use the container adaptor priority_queue , instead of performing the heap operations manually, is to make it clear that you are never performing any operations that might violate the heap invariant.

[3] One might wonder why pop() returns void, instead of value_type. That is, why must one use top() and pop() to examine and remove the element at the top of the priority_queue, instead of combining the two in a single member function? In fact, there is a good reason for this design. If pop() returned the top element, it would have to return by value rather than by reference: return by reference would create a dangling pointer. Return by value, however, is inefficient: it involves at least one redundant copy constructor call. Since it is impossible for pop() to return a value in such a way as to be both efficient and correct, it is more sensible for it to return no value at all and to require clients to use top() to inspect the value at the top of the priority_queue.

bitset<N>

Category: containers

Component type: type

Description

Bitset is very similar to vector<bool> (also known as bit_vector): it contains a collection of bits, and provides constant-time access to each bit. There are two main differences between bitset and vector<bool>. First, the size of a bitset cannot be changed: bitset's template parameter N, which specifies the number of bits in the bitset, must be an integer constant. Second, bitset is not a Sequence; in fact, it is not an STL Container at all. It does not have iterators, for example, or begin() and end() member functions. Instead, bitset's interface resembles that of unsigned integers. It defines bitwise arithmetic operators such as &=, |= , and ^=.

In general, bit 0 is the least significant bit and bit N-1 is the most significant bit.

Example

int main() {

const bitset<12> mask(2730ul);

cout << "mask = " << mask << endl;

bitset<12> x;

cout << "Enter a 12-bit bitset in binary: " << flush;

if (cin >> x) {

cout << "x = " << x << endl;

cout << "As ulong: " << x.to_ulong() << endl;

cout << "And with mask: " << (x & mask) << endl;

cout << "Or with mask: " << (x | mask) << endl;

}

Definition

Defined in the standard header bitset.

Template parameters

Parameter	Description
`N`	A nonzero constant of type size_t : the number of bits that the bitset contains.

Model of

Assignable, Default Constructible, Equality Comparable

Type requirements

N is a constant integer expression of a type convertible to size_t, and N is a positive number.

Public base classes

None.

Members

Member	Where defined	Description
`reference`	`bitset`	A proxy class that acts as a reference to a single bit.
`bitset()`	Default Constructible	The default constructor. All bits are initially zero.
`bitset(unsigned long val)`	`bitset`	Conversion from unsigned long.
`bitset(const bitset&)`	Assignable	Copy constructor.
`bitset& operator=(const bitset&)`	Assignable	Assignment operator.
`template<class Char, class Traits, class Alloc> explicit bitset(const basic_string<Char,Traits,Alloc>& s, size_t pos = 0, size_t n = basic_string <Char,Traits,Alloc>::npos)`	`bitset`	Conversion from string.
`bitset& operator&=(const bitset&)`	`bitset`	Bitwise and.
`bitset& operator\|=(const bitset&)`	`bitset`	Bitwise inclusive or.
`bitset& operator^=(const bitset&)`	`bitset`	Bitwise exclusive or.
`bitset& operator<<=(size_t)`	`bitset`	Left shift.
`bitset& operator>>=(size_t)`	`bitset`	Right shift.
`bitset operator<<(size_t n) const`	`bitset`	Returns a copy of *this shifted left by n bits.
`bitset operator>>(size_t n) const`	`bitset`	Returns a copy of *this shifted right by n bits.
`bitset& set()`	`bitset`	Sets every bit.
`bitset& flip()`	`bitset`	Flips the value of every bit.
`bitset operator~() const`	`bitset`	Returns a copy of *this with all of its bits flipped.
`bitset& reset()`	`bitset`	Clears every bit.
`bitset& set(size_t n, int val = 1)`	`bitset`	Sets bit n if val is nonzero, and clears bit n if val is zero.
`bitset& reset(size_t n)`	`bitset`	Clears bit n.
`bitset flip(size_t n)`	`bitset`	Flips bit n.
`size_t size() const`	`bitset`	Returns N.
`size_t count() const`	`bitset`	Returns the number of bits that are set.
`bool any() const`	`bitset`	Returns true if any bits are set.
`bool none() const`	`bitset`	Returns true if no bits are set.
`bool test(size_t n) const`	`bitset`	Returns true if bit n is set.
`reference operator[](size_t n)`	`bitset`	Returns a reference to bit n.
`bool operator[](size_t n) const`	`bitset`	Returns true if bit n is set.
`unsigned long to_ulong() const`	`bitset`	Returns an unsigned long corresponding to the bits in *this.
`template<class Char, class Traits, class Alloc> basic_string <Char,Traits,Alloc> to_string() const`	`bitset`	Returns a string representation of *this.
`bool operator==(const bitset&) const`	Equality Comparable	The equality operator.
`bool operator!=(const bitset&) const`	Equality Comparable	The inequality operator.
`bitset operator&(const bitset&, const bitset&)`	`bitset`	Bitwise and of two bitsets. This is a global function, not a member function.
`bitset operator\|(const bitset&, const bitset&)`	`bitset`	Bitwise or of two bitsets. This is a global function, not a member function.
`bitset operator^(const bitset&, const bitset&)`	`bitset`	Bitwise exclusive or of two bitsets. This is a global function, not a member function.
`template<class Char, class Traits, size_t N> basic_istream<Char,Traits>& operator>>(basic_istream<Char,Traits>&, bitset<N>&)`	`bitset`	Extract a bitset from an input stream.
`template<class Char, class Traits, size_t N> basic_ostream<Char,Traits>& operator>>(basic_ostream<Char,Traits>&, const bitset<N>&)`	`bitset`	Output a bitset to an output stream.

New members

These members are not defined in the Assignable, Default Constructible, or Equality Comparable requirements, but are specific to bitset.

Member	Description
`reference`	A proxy class that acts as a reference to a single bit. It contains an assignment operator, a conversion to bool, an operator~, and a member function flip. It exists only as a helper class for bitset's operator[]. That is, it supports the expressions x = b[i], b[i] = x, b[i] = b[j], x = ~b[i] , and b[i].flip(). (Where b is a bitset and x is a bool.)
`bitset(unsigned long val)`	Conversion from unsigned long. Constructs a bitset, initializing the first min(N, sizeof(unsigned long) CHAR_BIT)* bits to the corresponding bits in val and all other bits, if any, to zero.
`template<class Char, class Traits, class Alloc> explicit bitset(const basic_string<Char,Traits,Alloc>& s, size_t pos = 0, size_t n = basic_string<Char,Traits,Alloc>::npos)`	Conversion from string. Constructs a bitset, initializing the first M bits to the corresponding characters in s, where M is defined as min(N, min(s.size() – pos, n)). Note that the highest character position in s, not the lowest, corresponds to the least significant bit. That is, character position pos + M – 1 – i corresponds to bit i. So, for example, bitset(string("1101")) is the same as bitset(13ul). This function throws out_of_range if pos > s.size(), and invalid_argument if any of the characters used to initialize the bits are anything other than 0 or 1.
`bitset& operator&=(const bitset&)`	Bitwise and.
`bitset& operator\|=(const bitset&)`	Bitwise inclusive or.
`bitset& operator^=(const bitset&)`	Bitwise exclusive or.
`bitset& operator<<=(size_t n)`	Left shift, where bit 0 is considered the least significant bit. Bit i takes on the previous value of bit i – n, or zero if no such bit exists.
`bitset& operator>>=(size_t n)`	Right shift, where bit 0 is considered the least significant bit. Bit i takes on the previous value of bit i + n, or zero if no such bit exists.
`bitset operator<<(size_t n) const`	Returns a copy of this shifted left by n bits. Note that the expression b << n* is equivalent to constructing a temporary copy of b and then using operator<<=.
`bitset operator>>(size_t n) const`	Returns a copy of this shifted right by n bits. Note that the expression b >> n* is equivalent to constructing a temporary copy of b and then using operator>>=.
`bitset& set()`	Sets every bit.
`bitset& flip()`	Flips the value of every bit.
`bitset operator~() const`	Returns a copy of *this with all of its bits flipped.
`bitset& reset()`	Clears every bit.
`bitset& set(size_t n, int val = 1)`	Sets bit n if val is nonzero, and clears bit n if val is zero. Throws out_of_range if n >= N.
`bitset& reset(size_t n)`	Clears bit n. Throws out_of_range if n >= N.
`bitset flip(size_t n)`	Flips bit n. Throws out_of_range if n >= N.
`size_t size() const`	Returns N.
`size_t count() const`	Returns the number of bits that are set.
`bool any() const`	Returns true if any bits are set.
`bool none() const`	Returns true if no bits are set.
`bool test(size_t n) const`	Returns true if bit n is set. Throws out_of_range if n >= N.
`reference operator[](size_t n)`	Returns a reference to bit n. Note that reference is a proxy class with an assignment operator and a conversion to bool, which allows you to use operator[] for assignment. That is, you can write both x = b[n] and b[n] = x.
`bool operator[](size_t n) const`	Returns true if bit n is set.
`unsigned long to_ulong() const`	Returns an unsigned long corresponding to the bits in this. Throws overflow_error* if it is impossible to represent this as an unsigned long. (That is, if N is larger than the number of bits in an unsigned long* and if any of the high-order bits are set.
`template<class Char, class Traits, class Alloc> basic_string <Char,Traits,Alloc> to_string() const`	Returns a string representation of this: each character is 1 if the corresponding bit is set, and 0 if it is not. In general, character position i corresponds to bit position N – 1 – i. Note that this member function relies on two language features, member templates* and explicit function template argument specification, that are not yet universally available; this member function is disabled for compilers that do not support those features. Note also that the syntax for calling this member function is somewhat cumbersome. To convert a bitset b to an ordinary string, you must write b.template to_string<char, char_traits<char>, allocator<char> >()
`bitset operator&(const bitset&, const bitset&)`	Bitwise and of two bitsets. This is a global function, not a member function. Note that the expression b1 & b2 is equivalent to creating a temporary copy of b1, using operator&=, and returning the temporary copy.
`bitset operator\|(const bitset&, const bitset&)`	Bitwise or of two bitsets. This is a global function, not a member function. Note that the expression b1 \| b2 is equivalent to creating a temporary copy of b1, using operator\|=, and returning the temporary copy.
`bitset operator^(const bitset&, const bitset&)`	Bitwise exclusive or of two bitsets. This is a global function, not a member function. Note that the expression b1 ^ b2 is equivalent to creating a temporary copy of b1, using operator^=, and returning the temporary copy.
`template<class Char, class Traits, size_t N> basic_istream<Char, Traits>& operator>>(basic_istream<Char,Traits>& is, bitset<N>& x)`	Extract a bitset from an input stream. This function first skips whitespace, then extracts up to N characters from the input stream. It stops either when it has successfully extracted N character, or when extraction fails, or when it sees a character that is something other than 1 (in which case it does not extract that character). It then assigns a value to the bitset in the same way as if it were initializing the bitset from a string. So, for example, if the input stream contains the characters "1100abc", it will assign the value 12ul to the bitset, and the next character read from the input stream will be a.
`template<class Char, class Traits, size_t N> basic_ostream<Char,Traits>& operator>>(basic_ostream<Char,Traits>& os, const bitset<N>& x)`	Output a bitset to an output stream. This function behaves as if it converts the bitset to a string and then writes that string to the output stream. That is, it is equivalent to os << x.template to_string<Char,Traits,allocator<Char> >()

Standard Template Library Programmers Guide - читать онлайн бесплатно полную версию книги . Страница 3

Containers

Concepts

General concepts

Container

Description

Refinement of

Associated types

Notation

Definitions

Valid expressions

Expression semantics

Complexity guarantees

Invariants

Models

Notes

See also

Forward Container

Description

Associated types

Notation

Valid expressions

Expression semantics

Complexity guarantees

Invariants

Models

See also

Reversible Container

Description

Refinement of

Associated types

Notation

Valid expressions

Expression semantics

Complexity guarantees

Invariants

Models

Notes

See also

Random Access Container

Description

Refinement of

Associated types

Notation

Valid expressions

Expression semantics

Complexity guarantees

Invariants

Models

See also

Sequences

Sequence

Description

Refinement of

Associated types

Notation

Definitions

Valid expressions

Expression semantics

Complexity guarantees

Models

Notes

See also

Front Insertion Sequence

Description

Refinement of

Associated types

Notation

Valid expressions

Expression semantics

Complexity guarantees

Invariants

Models

Notes

See also

Back Insertion Sequence

Description

Refinement of

Associated types

Notation