______________________________________________________________________
23 Containers library [lib.containers]
______________________________________________________________________
1 This clause describes components that C++ programs may use to organize
collections of information.
2 The following subclauses describe container requirements, and compo
nents for sequences and associative containers, as summarized in Table
1:
Table 1--Containers library summary
+------------------------------------------------------+
| Subclause Header(s) |
+------------------------------------------------------+
|_lib.container.requirements_ Requirements |
+------------------------------------------------------+
| <bitset> |
| <deque> |
|_lib.sequences_ Sequences <list> |
| <queue> |
| <stack> |
| <vector> |
+------------------------------------------------------+
|_lib.associative_ Associative containers <map> |
| <set> |
+------------------------------------------------------+
23.1 Container requirements [lib.container.requirements]
1 Containers are objects that store other objects. They control alloca
tion and deallocation of these objects through constructors, destruc
tors, insert and erase operations.
2 The type of objects stored in these components must meet the require
ments of CopyConstructible types (_lib.copyconstructible_), and the
additional requirements of Assignable types.
3 In Table 2, T is the type used to instantiate the container, t is a
value of T, and u is a value of (possibly const) T.
Table 2--Assignable requirements
+-------------------------------------------------------------+
|expression return type post-condition complexity |
+-------------------------------------------------------------+
|t = u T& t is equivalent to u constant |
+-------------------------------------------------------------+
4 In Table 3, X denotes a container class containing objects of type T,
A denotes the allocator type of X, a and b denote values of type X, u
denotes an identifier and r denotes a value of X&.
Table 3--Container requirements
--------------------------------------------------------------------------------------------------------
expression return type assertion/note complexity
pre/post-condition
--------------------------------------------------------------------------------------------------------
X::value_type T T is Assignable compile time
--------------------------------------------------------------------------------------------------------
X::reference lvalue of T compile time
--------------------------------------------------------------------------------------------------------
X::const_reference const lvalue of T compile time
--------------------------------------------------------------------------------------------------------
X::iterator iterator type pointing to T any iterator category except compile time
output iterator.
--------------------------------------------------------------------------------------------------------
X::const_iterator iterator type pointing to any iterator category except compile time
const T output iterator.
--------------------------------------------------------------------------------------------------------
X::difference_type signed integral type is identical to the distance compile time
type of X::iterator and
X::const_iterator
--------------------------------------------------------------------------------------------------------
X::size_type unsigned integral type size_type can represent any compile time
non-negative value of differ
ence_type
--------------------------------------------------------------------------------------------------------
X::allocator_type const lvalue of A compile time
--------------------------------------------------------------------------------------------------------
a.get_allocator() allocator_type returns the allocator object constant
used to construct a
--------------------------------------------------------------------------------------------------------
X u; post: u.size() == 0. constant
--------------------------------------------------------------------------------------------------------
X(); X().size() == 0. constant
--------------------------------------------------------------------------------------------------------
X(a); a == X(a). linear
--------------------------------------------------------------------------------------------------------
X u(a); post: u == a. linear
X u = a; Equivalent to: X u; u = a;
--------------------------------------------------------------------------------------------------------
(&a)->~X(); void post: a.size() == 0. linear
note: the destructor is ap
plied to every element of a;
all the memory is returned.
--------------------------------------------------------------------------------------------------------
a.begin(); iterator; constant
const_iterator
for constant a
--------------------------------------------------------------------------------------------------------
a.end(); iterator; constant
| |
| |
| |
| |
| const_iterator |
| for constant a |
+------------------------------------------------------------------------------------------------------+
|a == b convertible to bool == is an equivalence relation. linear |
| a.size()==b.size() |
| && equal(a.begin(), |
| a.end(), b.begin()) |
+------------------------------------------------------------------------------------------------------+
|a != b convertible to bool Equivalent to: !(a == b) linear |
+------------------------------------------------------------------------------------------------------+
|a.swap(b); void swap(a,b) linear in gen |
| eral, |
| constant if |
| a.get_allocator() |
| == |
| b.get_allocator() |
+------------------------------------------------------------------------------------------------------+
+----------------------------------------------------------------------------------+
| expression return type operational assertion/note complexity |
| semantics pre/post-condition |
+----------------------------------------------------------------------------------+
|r = a X& if (&r != &a) { post: r == a. linear |
| (&r)->X::~X(); |
| new (&r) X(a); |
| } return r; |
+----------------------------------------------------------------------------------+
|a.size() size_type a.end()-a.begin() constant |
+----------------------------------------------------------------------------------+
|a.max_size() size_type size() of the constant |
| largest possible |
| container. |
+----------------------------------------------------------------------------------+
|a.empty() convertible to bool a.size() == 0 constant |
+----------------------------------------------------------------------------------+
|a < b convertible to bool lexicographical_ pre: < is defined linear |
| com for values of T. |
| pare(a.begin(), < is a total or |
| a.end(),b.begin(), dering relation. |
| b.end()) |
+----------------------------------------------------------------------------------+
|a > b convertible to bool b < a linear |
+----------------------------------------------------------------------------------+
|a <= b convertible to bool !(a > b) linear |
+----------------------------------------------------------------------------------+
|a >= b convertible to bool !(a < b) linear |
+----------------------------------------------------------------------------------+
Notes: the algorithms swap(), equal() and lexicographical_compare()
are defined in Clause _lib.algorithms_.
5 The member function size() returns the number of elements in the con
tainer. Its semantics is defined by the rules of constructors,
inserts, and erases.
6 begin() returns an iterator referring to the first element in the con
tainer. end() returns an iterator which is the past-the-end value for
the container. If the container is empty, then begin() == end();
7 Copy constructors for all container types defined in this clause copy
the allocator argument from their respective first parameters. All
other constructors for container types take an Allocator& argument
(_lib.allocator.requirements_). A copy of this argument is used for
any memory allocation performed, by these constructors and by all mem
ber functions, during the lifetime of each container object.
8 If the iterator type of a container belongs to the bidirectional or
random access iterator categories (_lib.iterator.requirements_), the
container is called reversible and satisfies the additional require
ments in Table 4:
Table 4--Reversible container requirements
+-------------------------------------------------------------------------------------+
|expression return type assertion/note complexity |
| pre/post-condition |
+-------------------------------------------------------------------------------------+
|X::reverse_ iterator type pointing to T re compile time |
|iterator verse_iterator<iterator, |
| value_type, reference, |
| difference_type> for ran |
| dom access iterator, re |
| verse_bidirectional_ it |
| erator<iterator, val |
| ue_type, reference, dif |
| ference_type> for bidi |
| rectional iterator. |
+-------------------------------------------------------------------------------------+
|X::const_ iterator type pointing to reverse_iterator< con compile time |
|reverse_ const T st_iterator, value_type, |
|iterator const_reference, differ |
| ence_type> for random ac |
| cess iterator, re |
| verse_bidirectional_ it |
| erator<const_iterator, |
| value_type, con |
| st_reference, differ |
| ence_type> for bidirec |
| tional iterator. |
+-------------------------------------------------------------------------------------+
|a.rbegin() reverse_iterator; con reverse_iterator(end()) constant |
| st_reverse_ iterator for |
| constant a |
+-------------------------------------------------------------------------------------+
|a.rend() reverse_iterator; con reverse_iterator(begin()) constant |
| st_reverse_ iterator for |
| constant a |
+-------------------------------------------------------------------------------------+
23.1.1 Sequences [lib.sequence.reqmts]
1 A sequence is a kind of container that organizes a finite set of
objects, all of the same type, into a strictly linear arrangement.
The library provides three basic kinds of sequence containers: vector,
list, and deque. It also provides container adaptors that make it
easy to construct abstract data types, such as stacks or queues, out
of the basic sequence kinds (or out of other kinds of sequences that
the user might define).
2 vector, list, and deque offer the programmer different complexity
trade-offs and should be used accordingly. vector is the type of
sequence that should be used by default. list should be used when
there are frequent insertions and deletions from the middle of the
sequence. deque is the data structure of choice when most insertions
and deletions take place at the beginning or at the end of the
sequence.
3 In Tables 5 and 6, X denotes a sequence class, a denotes value of X, i
and j denote iterators satisfying input iterator requirements,
4 vector, list, and deque offer the programmer different complexity
trade-offs and should be used accordingly. vector is the type of
sequence that should be used by default. list should be used when
there are frequent insertions and deletions from the middle of the
sequence. deque is the data structure of choice when most insertions
and deletions take place at the beginning or at the end of the
sequence.
5 vector, list, and deque offer the programmer different complexity
trade-offs and should be used accordingly. vector is the type of
sequence that should be used by default. list should be used when
there are frequent insertions and deletions from the middle of the
sequence. deque is the data structure of choice when most insertions
and deletions take place at the beginning or at the end of the
sequence. [i, j) denotes a valid range, n denotes a value of
X::size_type, p and q2 denote valid iterators to a, q and q1 denote
valid dereferenceable iterators to a, [q1, q2) denotes a valid range,
and t denotes a value of X::value_type.
6 The complexities of the expressions are sequence dependent.
Table 5--Sequence requirements (in addition to container)
+------------------------------------------------------------------------------------+
| expression return type assertion/note |
| pre/post-condition |
+------------------------------------------------------------------------------------+
|X(n, t) post: size() == n. |
|X a(n, t); constructs a sequence with n copies of t. |
+------------------------------------------------------------------------------------+
|X(i, j) post: size() == distance between i and j. |
|X a(i, j); constructs a sequence equal to the range [i,j). |
+------------------------------------------------------------------------------------+
|a.insert(p,t) iterator inserts a copy of t before p. |
+------------------------------------------------------------------------------------+
|a.insert(p,n,t) void inserts n copies of t before p. |
+------------------------------------------------------------------------------------+
|a.insert(p,i,j) void inserts copies of elements in [i,j) before p. |
+------------------------------------------------------------------------------------+
|a.erase(q) iterator erases the element pointed to by q. |
+------------------------------------------------------------------------------------+
|a.erase(q1,q2) iterator erases the elements in the range [q1,q2). |
+------------------------------------------------------------------------------------+
|a.clear() void erase(s.begin(), s.end()) |
| post: size() == 0. |
+------------------------------------------------------------------------------------+
7 iterator and const_iterator types for sequences must be at least of
the forward iterator category.
8 The iterator returned from a.insert(p,t) points to the copy of t
inserted into a.
9 The iterator returned from a.erase(q) points to the element immedi
ately following q prior to the element being erased. If no such ele
ment exists, a.end() is returned.
10The iterator returned by a.erase(q1,q2) points to the element pointed
to by q2 prior to any elements being erased. If no such element
exists, a.end() is returned.
11The operations in Table 6 are provided only for the containers for
which they take constant time:
Table 6--Optional sequence operations
+-----------------------------------------------------------------------------+
| expression return type operational container |
| semantics |
+-----------------------------------------------------------------------------+
|a.front() T&; const T& *a.begin() vector, list, deque |
| for constant a |
+-----------------------------------------------------------------------------+
|a.back() T&; const T& *--a.end() vector, list, deque |
| for constant a |
+-----------------------------------------------------------------------------+
|a.push_front(x) void a.insert(a.begin(),x) list, deque |
+-----------------------------------------------------------------------------+
|a.push_back(x) void a.insert(a.end(),x) vector, list, deque |
+-----------------------------------------------------------------------------+
|a.pop_front() void a.erase(a.begin()) list, deque |
+-----------------------------------------------------------------------------+
|a.pop_back() void a.erase(--a.end()) vector, list, deque |
+-----------------------------------------------------------------------------+
|a[n] T&; const T& *(a.begin() + n) vector, deque |
| for constant a |
+-----------------------------------------------------------------------------+
|a.at(n) T&; const T& *(a.begin() + n) vector, deque |
| for constant a |
+-----------------------------------------------------------------------------+
12The member function at() provides bounds-checked access to container
elements. at() throws out_of_range if n >= a.size().
23.1.2 Associative containers [lib.associative.reqmts]
1 Associative containers provide an ability for fast retrieval of data
based on keys. The library provides four basic kinds of associative
containers: set, multiset, map and multimap.
2 Each associative containers is parameterized on Key and an ordering
relation Compare that induces a total ordering on elements of Key. In
addition, map and multimap associate an arbitrary type T with the Key.
The object of type Compare is called the comparison object of a con
tainer.
3 The phrase ``equality of keys'' means the equivalence relation imposed
by the comparison and not the operator== on keys. That is, two keys
k1 and k2 are considered to be equal if for the comparison object
comp, comp(k1, k2) == false && comp(k2, k1) == false.
4 An associative container supports unique keys if it may contain at
most one element for each key. Otherwise, it supports equal keys.
set and map support unique keys. multiset and multimap support equal
keys.
5 For set and multiset the value type is the same as the key type. For
map and multimap it is equal to pair<const Key, T>.
6 iterator of an associative container is of the bidirectional iterator
category.
7 In Table 7, X is an associative container class, a is a value of X,
a_uniq is a value of X when X supports unique keys, and a_eq is a
value of X when X supports multiple keys, i and j satisfy input itera
tor requirements and refer to elements of value_type, [i, j) is a
valid range, p and q2 are valid iterators to a, q and q1 are valid
dereferenceable iterators to a, [q1, q2) is a valid range, t is a
value of X::value_type and k is a value of X::key_type.
Table 7--Associative container requirements (in addition to container)
+-----------------------------------------------------------------------------------+
| expression return type assertion/note complexity |
| pre/post-condition |
+-----------------------------------------------------------------------------------+
|X::key_type Key Key is Assignable compile time |
+-----------------------------------------------------------------------------------+
|X::key_compare Compare defaults to less<key_type> compile time |
+-----------------------------------------------------------------------------------+
|X:: val a binary pred is the same as key_compare for set compile time |
|ue_compare icate type and multiset; is an ordering relation |
| on pairs induced by the first compo |
| nent (i.e. Key) for map and multimap. |
+-----------------------------------------------------------------------------------+
|X(c) constructs an empty container; constant |
|X a(c); uses c as a comparison object |
+-----------------------------------------------------------------------------------+
|X() constructs an empty container; constant |
|X a; uses Compare() as a comparison object |
+-----------------------------------------------------------------------------------+
|X(i,j,c); constructs an empty container and in NlogN in gen |
|X a(i,j,c); serts elements from the range [i, j) eral (N is the |
| into it; uses c as a comparison ob distance from |
| ject i to j); |
| linear if [i, |
| j) is sorted |
| with val |
| ue_comp() |
+-----------------------------------------------------------------------------------+
|X(i, j) same as above, but uses Compare() as same as above |
| a comparison object. |
|X a(i, j); |
+-----------------------------------------------------------------------------------+
|a.key_comp() X::key_compare returns the comparison object out of constant |
| which a was constructed. |
+-----------------------------------------------------------------------------------+
|a.value_comp() X:: val returns an object of value_compare constant |
| ue_compare constructed out of the comparison ob |
| ject |
+-----------------------------------------------------------------------------------+
|a_uniq. in pair<iterator, inserts t if and only if there is no logarithmic |
|sert(t) bool> element in the container with key |
| equal to the key of t. The bool com |
| ponent of the returned pair indicates |
| whether the insertion takes place and |
| the iterator component of the pair |
| points to the element with key equal |
| to the key of t. |
+-----------------------------------------------------------------------------------+
-----------------------------------------------------------------------------------------
expression return type assertion/note complexity
pre/post-condition
-----------------------------------------------------------------------------------------
a_eq.insert(t) iterator inserts t and returns the iterator logarithmic
pointing to the newly inserted ele
ment.
-----------------------------------------------------------------------------------------
a.insert(p,t) iterator inserts t if and only if there is logarithmic in
no element with key equal to the general, but amor
key of t in containers with unique tized constant if
keys; always inserts t in contain t is inserted
ers with equal keys. always re right after p.
turns the iterator pointing to the
element with key equal to the key
of t. iterator p is a hint point
ing to where the insert should
start to search.
-----------------------------------------------------------------------------------------
a.insert(i,j) void inserts the elements from the range Nlog(size()+N) (N
[i, j) into the container. is the distance
from i to j) in
general;
linear if [i, j)
is sorted accord
ing to val
ue_comp()
-----------------------------------------------------------------------------------------
a.erase(k) size_type erases all the elements in the con log(size()) +
tainer with key equal to k. re count(k)
turns the number of erased ele
ments.
-----------------------------------------------------------------------------------------
a.erase(q) void erases the element pointed to by q. amortized constant
-----------------------------------------------------------------------------------------
a.erase(q1,q2) void erases all the elements in the log(size())+ N
range [q1, q2). where N is the
distance from q1
to q2.
-----------------------------------------------------------------------------------------
a.clear() void erase(s.begin, s.end)) log(size()) + N
post: size == 0
-----------------------------------------------------------------------------------------
a.find(k) iterator; con returns an iterator pointing to an logarithmic
st_iterator element with the key equal to k, or
for constant a a.end() if such an element is not
found.
-----------------------------------------------------------------------------------------
a.count(k) size_type returns the number of elements with log(size()) +
key equal to k count(k)
-----------------------------------------------------------------------------------------
a.lower_bound(k) iterator; con returns an iterator pointing to the logarithmic
st_iterator first element with key not less
for constant a than k.
| |
| |
| |
| |
+---------------------------------------------------------------------------------------+
|a.upper_bound(k) iterator; con returns an iterator pointing to the logarithmic |
| st_iterator first element with key greater than |
| for constant a k. |
+---------------------------------------------------------------------------------------+
|a.equal_range(k) pair< itera equivalent to make_pair( logarithmic |
| tor,iterator>; a.lower_bound(k), |
| pair< con a.upper_bound(k)). |
| st_iterator, |
| con |
| st_iterator> |
| for constant a |
+---------------------------------------------------------------------------------------+
8 The fundamental property of iterators of associative containers is
that they iterate through the containers in the non-descending order
of keys where non-descending is defined by the comparison that was
used to construct them. For any two dereferenceable iterators i and j
such that distance from i to j is positive,
value_comp(*j, *i) == false
9 For associative containers with unique keys the stronger condition
holds,
value_comp(*i, *j) == true.
23.2 Sequences [lib.sequences]
1 Headers <bitset>, <deque>, <list>, <queue>, <stack>, and <vector>.
Header <bitset> synopsis
#include <cstddef> // for size_t
#include <string>
#include <stdexcept> // for invalid_argument, out_of_range, overflow_error
#include <iosfwd> // for istream, ostream
namespace std {
template <size_t N> class bitset;
// _lib.bitset.operators_ bitset operations:
template <size_t N> bitset<N> operator&(const bitset<N>&, const bitset<N>&);
template <size_t N> bitset<N> operator|(const bitset<N>&, const bitset<N>&);
template <size_t N> bitset<N> operator^(const bitset<N>&, const bitset<N>&);
template <class charT, class traits, size_t N>
basic_istream<charT, traits>&
operator>>(basic_istream<charT, traits>& is, bitset<N>& x);
template <class charT, class traits, size_t N>
basic_ostream<charT, traits>&
operator<<(basic_ostream<charT, traits>& os, const bitset<N>& x);
}
Header <deque> synopsis
#include <memory> // for allocator
namespace std {
template <class T, class Allocator = allocator> class deque;
template <class T, class Allocator>
bool operator==(const deque<T,Allocator>& x, const deque<T,Allocator>& y);
template <class T, class Allocator>
bool operator< (const deque<T,Allocator>& x, const deque<T,Allocator>& y);
template <class T, class Allocator>
void swap(deque<T,Allocator>& x, deque<T,Allocator>& y);
}
Header <list> synopsis
#include <memory> // for allocator
namespace std {
template <class T, class Allocator = allocator> class list;
template <class T, class Allocator>
bool operator==(const list<T,Allocator>& x, const list<T,Allocator>& y);
template <class T, class Allocator>
bool operator< (const list<T,Allocator>& x, const list<T,Allocator>& y);
template <class T, class Allocator>
void swap(list<T,Allocator>& x, list<T,Allocator>& y);
}
Header <queue> synopsis
#include <functional> // for less
namespace std {
template <class T, class Container = deque<T>,
class Allocator = allocator> class queue;
template <class T, class Container, class Allocator>
bool operator==(const queue<T, Container, Allocator>& x,
const queue<T, Container, Allocator>& y);
template <class T, class Container, class Allocator>
bool operator< (const queue<T, Container, Allocator>& x,
const queue<T, Container, Allocator>& y);
template <class T, class Container = vector<T>,
class Compare = less<Container::value_type>,
class Allocator = allocator> class priority_queue;
}
Header <stack> synopsis
namespace std {
template <class T, class Container = deque<T>,
class Allocator = allocator> class stack;
template <class T, class Container, class Allocator>
bool operator==(const stack<T, Container, Allocator>& x,
const stack<T, Container, Allocator>& y);
template <class T, class Container, class Allocator>
bool operator< (const stack<T, Container, Allocator>& x,
const stack<T, Container, Allocator>& y);
}
Header <vector> synopsis
#include <memory> // for allocator
namespace std {
template <class T, class Allocator = allocator> class vector;
template <class T, class Allocator>
bool operator==(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
template <class T, class Allocator>
bool operator< (const vector<T,Allocator>& x, const vector<T,Allocator>& y);
template <class T, class Allocator>
void swap(vector<T,Allocator>& x, vector<T,Allocator>& y);
template <class Allocator = allocator> class vector<bool,Allocator>;
template <class Allocator>
bool operator==(const vector<bool,Allocator>& x,
const vector<bool,Allocator>& y);
template <class Allocator>
bool operator< (const vector<bool,Allocator>& x,
const vector<bool,Allocator>& y);
template <class Allocator>
void swap(vector<bool,Allocator>& x, vector<bool,Allocator>& y);
}
23.2.1 Template class bitset [lib.template.bitset]
1 The header <bitset> defines a template class and several related func
tions for representing and manipulating fixed-size sequences of bits.
namespace std {
template<size_t N> class bitset {
public:
// bit reference:
class reference {
friend class bitset;
reference();
public:
~reference();
reference& operator=(bool x); // for b[i] = x;
reference& operator=(const reference&); // for b[i] = b[j];
bool operator~() const; // flips the bit
operator bool() const; // for x = b[i];
reference& flip(); // for b[i].flip();
};
// _lib.bitset.cons_ constructors:
bitset();
bitset(unsigned long val);
explicit bitset(const string& str, size_t pos = 0, size_t n = size_t(-1));
// _lib.bitset.members_ bitset operations:
bitset<N>& operator&=(const bitset<N>& rhs);
bitset<N>& operator|=(const bitset<N>& rhs);
bitset<N>& operator^=(const bitset<N>& rhs);
bitset<N>& operator<<=(size_t pos);
bitset<N>& operator>>=(size_t pos);
bitset<N>& set();
bitset<N>& set(size_t pos, int val = true);
bitset<N>& reset();
bitset<N>& reset(size_t pos);
bitset<N> operator~() const;
bitset<N>& flip();
bitset<N>& flip(size_t pos);
// element access:
reference operator[](size_t pos); // for b[i];
unsigned long to_ulong() const;
template <class charT, class traits, class Allocator>
basic_string<charT, traits, Allocator> to_string() const;
size_t count() const;
size_t size() const;
bool operator==(const bitset<N>& rhs) const;
bool operator!=(const bitset<N>& rhs) const;
bool test(size_t pos) const;
bool any() const;
bool none() const;
bitset<N> operator<<(size_t pos) const;
bitset<N> operator>>(size_t pos) const;
};
}
2 The template class bitset<N> describes an object that can store a
sequence consisting of a fixed number of bits, N.
3 Each bit represents either the value zero (reset) or one (set). To
toggle a bit is to change the value zero to one, or the value one to
zero. Each bit has a non-negative position pos. When converting
between an object of class bitset<N> and a value of some integral
type, bit position pos corresponds to the bit value 1 << pos. The
integral value corresponding to two or more bits is the sum of their
bit values.
4 The functions described in this subclause can report three kinds of
errors, each associated with a distinct exception:
--an invalid-argument error is associated with exceptions of type
invalid_argument (_lib.invalid.argument_);
--an out-of-range error is associated with exceptions of type
out_of_range (_lib.out.of.range_);
--an overflow error is associated with exceptions of type over
flow_error (_lib.overflow.error_).
23.2.1.1 bitset constructors [lib.bitset.cons]
bitset();
Effects:
Constructs an object of class bitset<N>, initializing all bits to
zero.
bitset(unsigned long val);
Effects:
Constructs an object of class bitset<N>, initializing the first M
bit positions to the corresponding bit values in val. M is the
smaller of N and the value CHAR_BIT * sizeof (unsigned long).1)
If M < N, remaining bit positions are initialized to zero.
template <class charT, class traits, class Allocator>
explicit
bitset(const basic_string<charT, traits, Allocator>& str,
basic_string<charT, traits, Allocator>::size_type pos = 0,
basic_string<charT, traits, Allocator>::size_type n =
basic_string<charT, traits, Allocator>::npos);
Requires:
pos <= str.size().
Throws:
out_of_range if pos > str.size().
Effects:
Determines the effective length rlen of the initializing string as
the smaller of n and str.size() - pos.
The function then throws invalid_argument if any of the rlen charac
ters in str beginning at position pos is other than 0 or 1.
Otherwise, the function constructs an object of class bitset<N>,
initializing the first M bit positions to values determined from the
corresponding characters in the string str. M is the smaller of N
and rlen.
1 An element of the constructed string has value zero if the correspond
ing character in str, beginning at position pos, is 0. Otherwise, the
element has the value one. Character position pos + M - 1 corresponds
to bit position zero. Subsequent decreasing character positions cor
respond to increasing bit positions.
2 If M < N, remaining bit positions are initialized to zero.
_________________________
1) The macro CHAR_BIT is defined in <climits> (_lib.support.limits_).
23.2.1.2 bitset members [lib.bitset.members]
bitset<N>& operator&=(const bitset<N>& rhs);
Effects:
Clears each bit in *this for which the corresponding bit in rhs is
clear, and leaves all other bits unchanged.
Returns:
*this.
bitset<N>& operator|=(const bitset<N>& rhs);
Effects:
Sets each bit in *this for which the corresponding bit in rhs is
set, and leaves all other bits unchanged.
Returns:
*this.
bitset<N>& operator^=(const bitset<N>& rhs);
Effects:
Toggles each bit in *this for which the corresponding bit in rhs is
set, and leaves all other bits unchanged.
Returns:
*this.
bitset<N>& operator<<=(size_t pos);
Effects:
Replaces each bit at position I in *this with a value determined as
follows:
--If I < pos, the new value is zero;
--If I >= pos, the new value is the previous value of the bit at posi
tion I - pos.
Returns:
*this.
bitset<N>& operator>>=(size_t pos);
Effects:
Replaces each bit at position I in *this with a value determined as
follows:
--If pos >= N - I, the new value is zero;
--If pos < N - I, the new value is the previous value of the bit at
position I + pos.
Returns:
*this.
bitset<N>& set();
Effects:
Sets all bits in *this.
Returns:
*this.
bitset<N>& set(size_t pos, int val = 1);
Requires:
pos is valid
Throws:
out_of_range if pos does not correspond to a valid bit position.
Effects:
Stores a new value in the bit at position pos in *this. If val is
nonzero, the stored value is one, otherwise it is zero.
Returns:
*this.
bitset<N>& reset();
Effects:
Resets all bits in *this.
Returns:
*this.
bitset<N>& reset(size_t pos);
Requires:
pos is valid
Throws:
out_of_range if pos does not correspond to a valid bit position.
Effects:
Resets the bit at position pos in *this.
Returns:
*this.
bitset<N> operator~() const;
Effects:
Constructs an object x of class bitset<N> and initializes it with
*this.
Returns:
x.flip().
bitset<N>& flip();
Effects:
Toggles all bits in *this.
Returns:
*this.
bitset<N>& flip(size_t pos);
Requires:
pos is valid
Throws:
out_of_range if pos does not correspond to a valid bit position.
Effects:
Toggles the bit at position pos in *this.
Returns:
*this.
unsigned long to_ulong() const;
Throws:
overflow_error if the integral value x corresponding to the bits in
*this cannot be represented as type unsigned long.
Returns:
x.
template <class charT, class traits, class Allocator>
basic_string<charT, traits, Allocator> to_string() const;
Effects:
Constructs a string object of the appropriate type and initializes
it to a string of length N characters. Each character is determined
by the value of its corresponding bit position in *this. Character
position N - 1 corresponds to bit position zero. Subsequent
decreasing character positions correspond to increasing bit posi
tions. Bit value zero becomes the character 0, bit value one
becomes the character 1.
Returns:
The created object.
size_t count() const;
Returns:
A count of the number of bits set in *this.
size_t size() const;
Returns:
N.
bool operator==(const bitset<N>& rhs) const;
Returns:
A nonzero value if the value of each bit in *this equals the value
of the corresponding bit in rhs.
bool operator!=(const bitset<N>& rhs) const;
Returns:
A nonzero value if !(*this == rhs).
bool test(size_t pos) const;
Requires:
pos is valid
Throws:
out_of_range if pos does not correspond to a valid bit position.
Returns:
true if the bit at position pos in *this has the value one.
bool any() const;
Returns:
true if any bit in *this is one.
bool none() const;
Returns:
true if no bit in *this is one.
bitset<N> operator<<(size_t pos) const;
Returns:
bitset<N>(*this) <<= pos.
bitset<N> operator>>(size_t pos) const;
Returns:
bitset<N>(*this) >>= pos.
23.2.1.3 bitset operators [lib.bitset.operators]
bitset<N> operator&(const bitset<N>& lhs, const bitset<N>& rhs);
Returns:
bitset<N>(lhs) &= rhs.
bitset<N> operator|(const bitset<N>& lhs, const bitset<N>& rhs);
Returns:
bitset<N>(lhs) |= rhs.
bitset<N> operator^(const bitset<N>& lhs, const bitset<N>& rhs);
Returns:
bitset<N>(lhs) ^= rhs.
template <class charT, class traits, size_t N>
basic_istream<charT, traits>&
operator>>(basic_istream<charT, traits>& is, bitset<N>& x);
1 A formatted input function (_lib.istream.formatted_).
Effects:
Extracts up to N (single-byte) characters from is. Stores these
characters in a temporary object str of type string, then evaluates
the expression x = bitset<N>(str). Characters are extracted and
stored until any of the following occurs:
--N characters have been extracted and stored;
--end-of-file occurs on the input sequence;
--the next input character is neither 0 or 1 (in which case the input
character is not extracted).
2 If no characters are stored in str, calls is.setstate(ios::failbit)
(which may throw ios_base::failure (_lib.iostate.flags_).
Returns:
is.
template <class charT, class traits, size_t N>
basic_ostream<charT, traits>&
operator<<(basic_ostream<charT, traits>& os, const bitset<N>& x);
Returns:
os << x.to_string() (_lib.ostream.formatted_).
23.2.2 Template class deque [lib.deque]
1 A deque is a kind of sequence that, like a vector (_lib.vector_), sup
ports random access iterators. In addition, it supports constant time
insert and erase operations at the beginning or the end; insert and
erase in the middle take linear time. That is, a deque is especially
optimized for pushing and popping elements at the beginning and end.
As with vectors, storage management is handled automatically.
namespace std {
template <class T, class Allocator = allocator>
class deque {
public:
// _lib.deque.types_ types:
typedef typename Allocator::types<T>::reference reference;
typedef typename Allocator::types<T>::const_reference const_reference;
typedef implementation defined iterator;
typedef implementation defined const_iterator;
typedef typename Allocator::size_type size_type;
typedef typename Allocator::difference_type difference_type;
typedef T value_type;
typedef Allocator allocator_type;
typedef reverse_iterator<iterator, value_type,
reference, difference_type> reverse_iterator;
typedef reverse_iterator<const_iterator, value_type,
const_reference, difference_type> const_reverse_iterator;
// _lib.deque.cons_ construct/copy/destroy:
explicit deque(const Allocator& = Allocator());
explicit deque(size_type n, const T& value = T(),
const Allocator& = Allocator());
template <class InputIterator>
deque(InputIterator first, InputIterator last,
const Allocator& = Allocator());
deque(const deque<T,Allocator>& x);
~deque();
deque<T,Allocator>& operator=(const deque<T,Allocator>& x);
template <class InputIterator>
void assign(InputIterator first, InputIterator last);
template <class Size, class T>
void assign(Size n, const T& t = T());
allocator_type get_allocator() const;
// _lib.deque.iterators_ iterators:
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
reverse_iterator rend();
const_reverse_iterator rend() const;
// _lib.deque.capacity_ capacity:
size_type size() const;
size_type max_size() const;
void resize(size_type sz, T c = T());
bool empty() const;
// _lib.deque.access_ element access:
reference operator[](size_type n);
const_reference operator[](size_type n) const;
reference at(size_type n);
const_reference at(size_type n) const;
reference front();
const_reference front() const;
reference back();
const_reference back() const;
// _lib.deque.modifiers_ modifiers:
void push_front(const T& x);
void push_back(const T& x);
iterator insert(iterator position, const T& x = T());
void insert(iterator position, size_type n, const T& x);
template <class InputIterator>
void insert (iterator position, InputIterator first, InputIterator last);
void pop_front();
void pop_back();
iterator erase(iterator position);
iterator erase(iterator first, iterator last);
void swap(deque<T,Allocator>&);
void clear();
};
template <class T, class Allocator>
bool operator==(const deque<T,Allocator>& x, const deque<T,Allocator>& y);
template <class T, class Allocator>
bool operator< (const deque<T,Allocator>& x, const deque<T,Allocator>& y);
// specialized algorithms:
template <class T, class Allocator>
void swap(deque<T,Allocator>& x, deque<T,Allocator>& y);
}
23.2.2.1 deque types [lib.deque.types]
23.2.2.2 deque constructors, copy, and [lib.deque.cons]
assignment
template <class InputIterator>
void assign(InputIterator first, InputIterator last);
Effects:
erase(begin(), end());
insert(begin(), first, last);
template <class Size, class T> void assign(Size n, const T& t = T());
Effects:
erase(begin(), end());
insert(begin(), n, t);
23.2.2.3 deque iterator support [lib.deque.iterators]
23.2.2.4 deque capacity [lib.deque.capacity]
void resize(size_type sz, T c = T());
Effects:
if (sz > size())
insert(end(), sz-size(), c);
else if (sz < size())
erase(begin()+sz, s.end());
else
; // do nothing
23.2.2.5 deque element access [lib.deque.access]
23.2.2.6 deque modifiers [lib.deque.modifiers]
iterator insert(iterator position, const T& x = T());
void insert(iterator position, size_type n, const T& x);
template <class InputIterator>
void insert(iterator position,
InputIterator first, InputIterator last);
Effects:
An insert in the middle of the deque invalidates all the iterators
and references to elements of the deque. An insert at either end of
the deque invalidates all the iterators to the deque, but has no
effect on the validity of references to elements of the deque.
Complexity:
In the worst case, inserting a single element into a deque takes
time linear in the minimum of the distance from the insertion point
to the beginning of the deque and the distance from the insertion
point to the end of the deque. Inserting a single element either at
the beginning or end of a deque always takes constant time and
causes a single call to the copy constructor of T.
iterator erase(iterator position);
iterator erase(iterator first, iterator last);
Effects:
An erase in the middle of the deque invalidates all the iterators
and references to elements of the deque. An erase at either end of
the deque invalidates only the iterators and the references to the
erased elements.
Complexity:
The number of calls to the destructor is the same as the number of
elements erased, but the number of the calls to the assignment oper
ator is equal to the minimum of the number of elements before the
erased elements and the number of element after the erased elements.
23.2.2.7 deque specialized algorithms [lib.deque.special]
template <class T, class Allocator>
void swap(deque<T,Allocator>& x, deque<T,Allocator>& y);
Effects:
x.swap(y);
23.2.3 Template class list [lib.list]
1 A list is a kind of sequence that supports bidirectional iterators and
allows constant time insert and erase operations anywhere within the
sequence, with storage management handled automatically. Unlike vec
tors (_lib.vector_) and deques (_lib.deque_), fast random access to
list elements is not supported, but many algorithms only need sequen
tial access anyway.
namespace std {
template <class T, class Allocator = allocator>
class list {
public:
// _lib.list.types_ types:
typedef typename Allocator::types<T>::reference reference;
typedef typename Allocator::types<T>::const_reference const_reference;
typedef implementation defined iterator;
typedef implementation defined const_iterator;
typedef typename Allocator::size_type size_type;
typedef typename Allocator::difference_type difference_type;
typedef T value_type;
typedef Allocator allocator_type;
typedef reverse_bidirectional_iterator<iterator, value_type,
reference, difference_type> reverse_iterator;
typedef reverse_bidirectional_iterator<const_iterator, value_type,
const_reference, difference_type> const_reverse_iterator;
// _lib.list.cons_ construct/copy/destroy:
explicit list(const Allocator& = Allocator());
explicit list(size_type n, const T& value = T(),
const Allocator& = Allocator());
template <class InputIterator>
list(InputIterator first, InputIterator last,
const Allocator& = Allocator());
list(const list<T,Allocator>& x);
~list();
list<T,Allocator>& operator=(const list<T,Allocator>& x);
template <class InputIterator>
void assign(InputIterator first, InputIterator last);
template <class Size, class T>
void assign(Size n, const T& t = T());
allocator_type get_allocator() const;
// _lib.list.iterators_ iterators:
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
reverse_iterator rend();
const_reverse_iterator rend() const;
// _lib.list.capacity_ capacity:
bool empty() const;
size_type size() const;
size_type max_size() const;
void resize(size_type sz, T c = T());
// element access:
reference front();
const_reference front() const;
reference back();
const_reference back() const;
// _lib.list.modifiers_ modifiers:
void push_front(const T& x);
void pop_front();
void push_back(const T& x);
void pop_back();
iterator insert(iterator position, const T& x = T());
void insert(iterator position, size_type n, const T& x);
template <class InputIterator>
void insert(iterator position, InputIterator first,
InputIterator last);
iterator erase(iterator position);
iterator erase(iterator position, iterator last);
void swap(list<T,Allocator>&);
void clear();
// _lib.list.ops_ list operations:
void splice(iterator position, list<T,Allocator>& x);
void splice(iterator position, list<T,Allocator>& x, iterator i);
void splice(iterator position, list<T,Allocator>& x, iterator first,
iterator last);
void remove(const T& value);
template <class Predicate> void remove_if(Predicate pred);
void unique();
template <class BinaryPredicate> void unique(BinaryPredicate binary_pred);
void merge(list<T,Allocator>& x);
template <class Compare> void merge(list<T,Allocator>& x, Compare comp);
void sort();
template <class Compare> void sort(Compare comp);
void reverse();
};
template <class T, class Allocator>
bool operator==(const list<T,Allocator>& x, const list<T,Allocator>& y);
template <class T, class Allocator>
bool operator< (const list<T,Allocator>& x, const list<T,Allocator>& y);
// specialized algorithms:
template <class T, class Allocator>
void swap(list<T,Allocator>& x, list<T,Allocator>& y);
}
23.2.3.1 list types [lib.list.types]
23.2.3.2 list constructors, copy, and assignment [lib.list.cons]
template <class InputIterator>
void assign(InputIterator first, InputIterator last);
Effects:
erase(begin(), end());
insert(begin(), first, last);
template <class Size, class T> void assign(Size n, const T& t = T());
Effects:
erase(begin(), end());
insert(begin(), n, t);
23.2.3.3 list iterator support [lib.list.iterators]
23.2.3.4 list capacity [lib.list.capacity]
void resize(size_type sz, T c = T());
Effects:
if (sz > size())
insert(end(), sz-size(), c);
else if (sz < size())
erase(begin()+sz, s.end());
else
; // do nothing
23.2.3.5 list element access [lib.list.access]
23.2.3.6 list modifiers [lib.list.modifiers]
iterator insert(iterator position, const T& x = T());
void insert(iterator position, size_type n, const T& x);
template <class InputIterator>
void insert(iterator position, InputIterator first,
InputIterator last);
Notes:
Does not affect the validity of iterators and references.
Complexity:
Insertion of a single element into a list takes constant time and
exactly one call to the copy constructor of T. Insertion of multi
ple elements into a list is linear in the number of elements
inserted, and the number of calls to the copy constructor of T is
exactly equal to the number of elements inserted.
iterator erase(iterator position);
iterator erase(iterator first, iterator last);
Effects:
Invalidates only the iterators and references to the erased ele
ments.
Complexity:
Erasing a single element is a constant time operation with a single
call to the destructor of T. Erasing a range in a list is linear
time in the size of the range and the number of calls to the
destructor of type T is exactly equal to the size of the range.
23.2.3.7 list operations [lib.list.ops]
1 Since lists allow fast insertion and erasing from the middle of a
list, certain operations are provided specifically for them.
2 list provides three splice operations that destructively move elements
from one list to another.
void splice(iterator position, list<T,Allocator>& x);
Requires:
&x != this.
Effects:
Inserts the contents of x before position and x becomes empty.
Complexity:
Constant time.
void splice(iterator position, list<T,Allocator>& x, iterator i);
Effects:
Inserts an element pointed to by i from list x before position and
removes the element from x. The result is unchanged if position ==
i or position == ++i.
Requires:
i is a valid dereferenceable iterator of x.
Complexity:
Constant time.
void splice(iterator position, list<T,Allocator>& x, iterator first,
iterator last);
Effects:
Inserts elements in the range [first, last) before position and
removes the elements from x.
Requires:
[first, last) is a valid range in x. The result is undefined if
position is an iterator in the range [first, last).
Complexity:
Constant time if &x == this; otherwise, linear time.
void remove(const T& value);
template <class Predicate> void remove_if(Predicate pred);
Effects:
Erases all the elements in the list referred by a list iterator i
for which the following conditions hold: *i == value, pred(*i) ==
true.
Notes:
Stable: the relative order of the elements that are not removed is
the same as their relative order in the original list.
Complexity:
Exactly size() applications of the corresponding predicate.
void unique();
template <class BinaryPredicate> void unique(BinaryPredicate binary_pred);
Effects:
Erases all but the first element from every consecutive group of
equal elements in the list.
Complexity:
Exactly size() - 1 applications of the corresponding binary predi
cate.
void merge(list<T,Allocator>& x);
template <class Compare> void merge(list<T,Allocator>& x, Compare comp);
Effects:
Merges the argument list into the list (both are assumed to be
sorted).
Notes:
Stable: for equal elements in the two lists, the elements from the
list always precede the elements from the argument list. x is empty
after the merge.
Complexity:
At most size() + x.size() - 1 comparisons.
void reverse();
Effects:
Reverses the order of the elements in the list.
Complexity:
Linear time.
void sort();
template <class Compare> void sort(Compare comp);
Effects:
Sorts the list according to the operator< or a compare function
object.
Notes:
Stable: the relative order of the equal elements is preserved.
Complexity:
Approximately NlogN comparisons, where N == size().
23.2.3.8 list specialized algorithms [lib.list.special]
template <class T, class Allocator>
void swap(list<T,Allocator>& x, list<T,Allocator>& y);
Effects:
x.swap(y);
23.2.4 Container adapters [lib.container.adapters]
23.2.4.1 Template class queue [lib.queue]
1 Any sequence supporting operations front(), back(), push_back() and
pop_front() can be used to instantiate queue. In particular, list
(_lib.list_) and deque (_lib.deque_) can be used.
nmespace std {
template <class T, class Container = deque<T>,
class Allocator = allocator>
class queue {
public:
typedef typename Container::value_type value_type;
typedef typename Container::size_type size_type;
protected:
Container c;
public:
explicit queue(const Allocator& = Allocator());
allocator_type get_allocator() const;
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
value_type& front() { return c.front(); }
const value_type& front() const { return c.front(); }
value_type& back() { return c.back(); }
const value_type& back() const { return c.back(); }
void push(const value_type& x) { c.push_back(x); }
void pop() { c.pop_front(); }
};
template <class T, class Container, class Allocator>
bool operator==(const queue<T, Container, Allocator>& x,
const queue<T, Container, Allocator>& y);
template <class T, class Container, class Allocator>
bool operator< (const queue<T, Container, Allocator>& x,
const queue<T, Container, Allocator>& y);
}
operator==
Returns:
x.c == y.c.
operator<
Returns:
x.c < y.c.
23.2.4.2 Template class priority_queue [lib.priority.queue]
1 Any sequence with random access iterator and supporting operations
front(), push_back() and pop_back() can be used to instantiate prior
ity_queue. In particular, vector (_lib.vector_) and deque
(_lib.deque_) can be used.
namespace std {
template <class T, class Container = vector<T>,
class Compare = less<Container::value_type>,
class Allocator = allocator>
class priority_queue {
public:
typedef typename Container::value_type value_type;
typedef typename Container::size_type size_type;
protected:
Container c;
Compare comp;
public:
explicit priority_queue(const Compare& x = Compare(),
const Allocator& = Allocator());
template <class InputIterator>
priority_queue(InputIterator first, InputIterator last,
const Compare& x = Compare());
allocator_type get_allocator() const;
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
const value_type& top() const { return c.front(); }
void push(const value_type& x);
void pop();
};
// no equality is provided
}
23.2.4.2.1 priority_queue constructors [lib.priqueue.cons]
priority_queue(const Compare& x = Compare());
Effects:
Initializes comp with x.
template <class InputIterator>
priority_queue(InputIterator first, InputIterator last,
const Compare& x = Compare());
Effects:
: c(first, last), comp(x) {
make_heap(c.begin(), c.end(), comp);
}
23.2.4.2.2 priority_queue members [lib.priqueue.members]
void push(const value_type& x);
Effects:
c.push_back(x);
push_heap(c.begin(), c.end(), comp);
void pop();
Effects:
pop_heap(c.begin(), c.end(), comp);
c.pop_back();
23.2.4.3 Template class stack [lib.stack]
1 Any sequence supporting operations back(), push_back() and pop_back()
can be used to instantiate stack. In particular, vector
(_lib.vector_), list (_lib.list_) and deque (_lib.deque_) can be used.
namespace std {
template <class T, class Container = deque<T>,
class Allocator = allocator>
class stack {
public:
typedef typename Container::value_type value_type;
typedef typename Container::size_type size_type;
protected:
Container c;
public:
explicit stack(const Allocator& = Allocator());
allocator_type get_allocator() const;
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
value_type& top() { return c.back(); }
const value_type& top() const { return c.back(); }
void push(const value_type& x) { c.push_back(x); }
void pop() { c.pop_back(); }
};
template <class T, class Container, class Allocator>
bool operator==(const stack<T, Container, Allocator>& x,
const stack<T, Container, Allocator>& y);
template <class T, class Container, class Allocator>
bool operator< (const stack<T, Container, Allocator>& x,
const stack<T, Container, Allocator>& y);
}
operator==
Returns:
x.c == y.c. operator<
Returns:
x.c < y.c.
23.2.5 Template class vector [lib.vector]
1 A vector is a kind of sequence that supports random access iterators.
In addition, it supports (amortized) constant time insert and erase
operations at the end; insert and erase in the middle take linear
time. Storage management is handled automatically, though hints can
be given to improve efficiency.
namespace std {
template <class T, class Allocator = allocator>
class vector {
public:
// _lib.vector.types_ types:
typedef typename Allocator::types<T>::reference reference;
typedef typename Allocator::types<T>::const_reference const_reference;
typedef implementation defined iterator;
typedef implementation defined const_iterator;
typedef typename Allocator::size_type size_type;
typedef typename Allocator::difference_type difference_type;
typedef T value_type;
typedef Allocator allocator_type;
typedef reverse_iterator<iterator, value_type,
reference, difference_type> reverse_iterator;
typedef reverse_iterator<const_iterator, value_type,
const_reference, difference_type> const_reverse_iterator;
// _lib.vector.cons_ construct/copy/destroy:
explicit vector(const Allocator& = Allocator());
explicit vector(size_type n, const T& value = T(),
const Allocator& = Allocator());
template <class InputIterator>
vector(InputIterator first, InputIterator last,
const Allocator& = Allocator());
vector(const vector<T,Allocator>& x);
~vector();
vector<T,Allocator>& operator=(const vector<T,Allocator>& x);
template <class InputIterator>
void assign(InputIterator first, InputIterator last);
template <class Size, class T> void assign(Size n, const T& t = T());
allocator_type get_allocator() const;
// _lib.vector.iterators_ iterators:
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
reverse_iterator rend();
const_reverse_iterator rend() const;
// _lib.vector.capacity_ capacity:
size_type size() const;
size_type max_size() const;
void resize(size_type sz, T c = T());
size_type capacity() const;
bool empty() const;
void reserve(size_type n);
// _lib.vector.access_ element access:
reference operator[](size_type n);
const_reference operator[](size_type n) const;
const_reference at(size_type n) const;
reference at(size_type n);
reference front();
const_reference front() const;
reference back();
const_reference back() const;
// _lib.vector.modifiers_ modifiers:
void push_back(const T& x);
void pop_back();
iterator insert(iterator position, const T& x = T());
void insert(iterator position, size_type n, const T& x);
template <class InputIterator>
void insert(iterator position, InputIterator first, InputIterator last);
iterator erase(iterator position);
iterator erase(iterator first, iterator last);
void swap(vector<T,Allocator>&);
void clear();
};
template <class T, class Allocator>
bool operator==(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
template <class T, class Allocator>
bool operator< (const vector<T,Allocator>& x, const vector<T,Allocator>& y);
// specialized algorithms:
template <class T, class Allocator>
void swap(vector<T,Allocator>& x, vector<T,Allocator>& y);
}
23.2.5.1 vector types [lib.vector.types]
23.2.5.2 vector constructors, copy, and [lib.vector.cons]
assignment
vector(const Allocator& = Allocator());
explicit vector(size_type n, const T& value = T(),
const Allocator& = Allocator());
template <class InputIterator>
vector(InputIterator first, InputIterator last,
const Allocator& = Allocator());
vector(const vector<T,Allocator>& x);
Complexity:
The constructor template <class InputIterator> vector(InputIterator
first, InputIterator last) makes only N calls to the copy construc
tor of T (where N is the distance between first and last) and no
reallocations if iterators first and last are of forward, bidirec
tional, or random access categories. It does at most 2N calls to
the copy constructor of T and logN reallocations if they are just
input iterators, since it is impossible to determine the distance
between first and last and then do copying.
template <class InputIterator>
void assign(InputIterator first, InputIterator last);
Effects:
erase(begin(), end());
insert(begin(), first, last);
template <class Size, class T> void assign(Size n, const T& t = T());
Effects:
erase(begin(), end());
insert(begin(), n, t);
23.2.5.3 vector iterator support [lib.vector.iterators]
23.2.5.4 vector capacity [lib.vector.capacity]
size_type capacity() const;
Returns:
The size of the allocated storage in the vector.
void reserve(size_type n);
Effects:
A directive that informs a vector of a planned change in size, so
that it can manage the storage allocation accordingly. After
reserve(), capacity() is greater or equal to the argument of reserve
if reallocation happens; and equal to the previous value of capac
ity() otherwise. Reallocation happens at this point if and only if
the current capacity is less than the argument of reserve().
Complexity:
It does not change the size of the sequence and takes at most linear
time in the size of the sequence.
Notes:
Reallocation invalidates all the references, pointers, and iterators
referring to the elements in the sequence. It is guaranteed that no
reallocation takes place during the insertions that happen after
reserve() takes place till the time when the size of the vector
reaches the size specified by reserve().
void resize(size_type sz, T c = T());
Effects:
if (sz > size())
insert(end(), sz-size(), c);
else if (sz < size())
erase(begin()+sz, s.end());
else
; // do nothing
23.2.5.5 vector element access [lib.vector.access]
23.2.5.6 vector modifiers [lib.vector.modifiers]
iterator insert(iterator position, const T& x = T());
void insert(iterator position, size_type n, const T& x);
template <class InputIterator>
void insert(iterator position, InputIterator first, InputIterator last);
Notes:
Causes reallocation if the new size is greater than the old capac
ity. If no reallocation happens, all the iterators and references
before the insertion point remain valid.
Complexity:
Inserting a single element into a vector is linear in the distance
from the insertion point to the end of the vector.
The amortized complexity over the lifetime of a vector of inserting
a single element at its end is constant. Insertion of multiple ele
ments into a vector with a single call of the insert member function
is linear in the sum of the number of elements plus the distance to
the end of the vector.2)
iterator erase(iterator position);
iterator erase(iterator first, iterator last);
Effects:
Invalidates all the iterators and references after the point of the
erase.
Complexity:
The destructor of T is called the number of times equal to the num
ber of the elements erased, but the assignment operator of T is
called the number of times equal to the number of elements in the
vector after the erased elements.
_________________________
2) In other words, it is much faster to insert many elements into the
middle of a vector at once than to do the insertion one at a time.
The insert template member function preallocates enough storage for
the insertion if the iterators first and last are of forward, bidirec
tional or random access category. Otherwise, it does insert elements
one by one and should not be used for inserting into the middle of
vectors.
23.2.5.7 vector specialized algorithms [lib.vector.special]
template <class T, class Allocator>
void swap(vector<T,Allocator>& x, vector<T,Allocator>& y);
Effects:
x.swap(y);
23.2.6 Class vector<bool> [lib.vector.bool]
1 To optimize space allocation, a specialization of vector for bool ele
ments is provided:3)
namespace std {
template <class Allocator = allocator>
class vector<bool, Allocator> {
public:
// types:
typedef const reference const_reference;
typedef implementation defined iterator;
typedef implementation defined const_iterator;
typedef typename Allocator::size_type size_type;
typedef typename Allocator::difference_type difference_type;
typedef bool value_type;
typedef Allocator allocator_type;
typedef reverse_iterator<iterator, value_type,
reference, difference_type> reverse_iterator;
typedef reverse_iterator<const_iterator, value_type,
const_reference, difference_type> const_reverse_iterator;
// bit reference:
class reference {
friend class vector;
reference();
public:
~reference();
operator bool() const;
reference& operator=(const bool x);
void flip(); // flips the bit
};
_________________________
3) An implementation is expected to provide specializations of vec
tor<bool> for all supported memory models.
// construct/copy/destroy:
explicit vector(const Allocator& = Allocator());
explicit vector(size_type n, const bool& value = bool(),
const Allocator& = Allocator());
template <class InputIterator>
vector(InputIterator first, InputIterator last,
const Allocator& = Allocator());
vector(const vector<bool,Allocator>& x);
~vector();
vector<bool,Allocator>& operator=(const vector<bool,Allocator>& x);
template <class InputIterator>
void assign(InputIterator first, InputIterator last);
template <class Size, class T> void assign(Size n, const T& t = T());
allocator_type get_allocator() const;
// iterators:
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
reverse_iterator rend();
const_reverse_iterator rend() const;
// capacity:
size_type size() const;
size_type max_size() const;
void resize(size_type sz, bool c = false);
size_type capacity() const;
bool empty() const;
void reserve(size_type n);
// element access:
reference operator[](size_type n);
const_reference operator[](size_type n) const;
const_reference at(size_type n) const;
reference at(size_type n);
reference front();
const_reference front() const;
reference back();
const_reference back() const;
// modifiers:
void push_back(const bool& x);
void pop_back();
iterator insert(iterator position, const bool& x = bool());
void insert (iterator position, size_type n, const bool& x);
template <class InputIterator>
void insert (iterator position, InputIterator first, InputIterator last);
iterator erase(iterator position);
iterator erase(iterator first, iterator last);
void swap(vector<bool,Allocator>&);
static void swap(reference x, reference y);
void flip(); // flips all bits
void clear();
};
template <class Allocator>
bool operator==(const vector<bool,Allocator>& x,
const vector<bool,Allocator>& y);
template <class Allocator>
bool operator< (const vector<bool,Allocator>& x,
const vector<bool,Allocator>& y);
// specialized algorithms:
template <class Allocator>
void swap(vector<bool,Allocator>& x, vector<bool,Allocator>& y);
}
2 reference is a class that simulates the behavior of references of a
single bit in vector<bool>.
23.3 Associative containers [lib.associative]
1 Headers <map> and <set>:
Header <map> synopsis
#include <memory> // for allocator
#include <utility> // for pair
#include <functional> // for less
namespace std {
template <class Key, class T, class Compare = less<Key>,
class Allocator = allocator>
class map;
template <class Key, class T, class Compare, class Allocator>
bool operator==(const map<Key,T,Compare,Allocator>& x,
const map<Key,T,Compare,Allocator>& y);
template <class Key, class T, class Compare, class Allocator>
bool operator< (const map<Key,T,Compare,Allocator>& x,
const map<Key,T,Compare,Allocator>& y);
template <class Key, class T, class Compare, class Allocator>
void swap(map<Key,T,Compare,Allocator>& x,
map<Key,T,Compare,Allocator>& y);
template <class Key, class T, class Compare = less<Key>,
class Allocator = allocator>
class multimap;
template <class Key, class T, class Compare, class Allocator>
bool operator==(const multimap<Key,T,Compare,Allocator>& x,
const multimap<Key,T,Compare,Allocator>& y);
template <class Key, class T, class Compare, class Allocator>
bool operator< (const multimap<Key,T,Compare,Allocator>& x,
const multimap<Key,T,Compare,Allocator>& y);
template <class Key, class T, class Compare, class Allocator>
void swap(multimap<Key,T,Compare,Allocator>& x,
multimap<Key,T,Compare,Allocator>& y);
}
Header <set> synopsis
#include <memory> // for allocator
#include <utility> // for pair
#include <functional> // for less
namespace std {
template <class Key, class Compare = less<Key>, class Allocator = allocator>
class set;
template <class Key, class Compare, class Allocator>
bool operator==(const set<Key,Compare,Allocator>& x,
const set<Key,Compare,Allocator>& y);
template <class Key, class Compare, class Allocator>
bool operator< (const set<Key,Compare,Allocator>& x,
const set<Key,Compare,Allocator>& y);
template <class Key, class Compare, class Allocator>
void swap(set<Key,Compare,Allocator>& x,
set<Key,Compare,Allocator>& y);
template <class Key, class Compare = less<Key>, class Allocator = allocator>
class multiset;
template <class Key, class Compare, class Allocator>
bool operator==(const multiset<Key,Compare,Allocator>& x,
const multiset<Key,Compare,Allocator>& y);
template <class Key, class Compare, class Allocator>
bool operator< (const multiset<Key,Compare,Allocator>& x,
const multiset<Key,Compare,Allocator>& y);
template <class Key, class Compare, class Allocator>
void swap(multiset<Key,Compare,Allocator>& x,
multiset<Key,Compare,Allocator>& y);
}
23.3.1 Template class map [lib.map]
1 A map is a kind of associative container that supports unique keys
(contains at most one of each key value) and provides for fast
retrieval of values of another type T based on the keys. Map supports
bidirectional iterators.
namespace std {
template <class Key, class T, class Compare = less<Key>,
class Allocator = allocator>
class map {
public:
// _lib.map.types_ types:
typedef Key key_type;
typedef T mapped_type;
typedef pair<const Key, T> value_type;
typedef Compare key_compare;
typedef Allocator allocator_type;
typedef typename Allocator::types<value_type>::reference reference;
typedef typename Allocator::types<value_type>::const_reference
const_reference;
typedef implementation defined iterator;
typedef implementation defined const_iterator;
typedef typename Allocator::size_type size_type;
typedef typename Allocator::difference_type difference_type;
typedef reverse_iterator<iterator, value_type,
reference, difference_type> reverse_iterator;
typedef reverse_iterator<const_iterator, value_type,
const_reference, difference_type> const_reverse_iterator;
class value_compare
: public binary_function<value_type,value_type,bool> {
friend class map;
protected:
Compare comp;
value_compare(Compare c) : comp(c) {}
public:
bool operator()(const value_type& x, const value_type& y) {
return comp(x.first, y.first);
}
};
// _lib.map.cons_ construct/copy/destroy:
explicit map(const Compare& comp = Compare(), const Allocator& = Allocator());
template <class InputIterator>
map(InputIterator first, InputIterator last,
const Compare& comp = Compare(), const Allocator& = Allocator());
map(const map<Key,T,Compare,Allocator>& x);
~map();
map<Key,T,Compare,Allocator>&
operator=(const map<Key,T,Compare,Allocator>& x);
// _lib.map.iterators_ iterators:
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
reverse_iterator rend();
const_reverse_iterator rend() const;
// _lib.map.capacity_ capacity:
bool empty() const;
size_type size() const;
size_type max_size() const;
// _lib.map.access_ element access:
mapped_type& operator[](const key_type& x);
const mapped_type& operator[](const key_type& x) const;
// _lib.map.modifiers_ modifiers:
pair<iterator, bool> insert(const value_type& x);
iterator insert(iterator position, const value_type& x);
template <class InputIterator>
void insert(InputIterator first, InputIterator last);
void erase(iterator position);
size_type erase(const key_type& x);
void erase(iterator first, iterator last);
void swap(map<Key,T,Compare,Allocator>&);
void clear();
// _lib.map.observers_ observers:
key_compare key_comp() const;
value_compare value_comp() const;
// _lib.map.ops_ map operations:
iterator find(const key_type& x);
const_iterator find(const key_type& x) const;
size_type count(const key_type& x) const;
iterator lower_bound(const key_type& x);
const_iterator lower_bound(const key_type& x) const;
iterator upper_bound(const key_type& x);
const_iterator upper_bound(const key_type& x) const;
pair<iterator,iterator> equal_range(const key_type& x);
pair<const_iterator,const_iterator> equal_range(const key_type& x) const;
};
template <class Key, class T, class Compare, class Allocator>
bool operator==(const map<Key,T,Compare,Allocator>& x,
const map<Key,T,Compare,Allocator>& y);
template <class Key, class T, class Compare, class Allocator>
bool operator< (const map<Key,T,Compare,Allocator>& x,
const map<Key,T,Compare,Allocator>& y);
// specialized algorithms:
template <class Key, class T, class Compare, class Allocator>
void swap(map<Key,T,Compare,Allocator>& x,
map<Key,T,Compare,Allocator>& y);
}
23.3.1.1 map types [lib.map.types]
23.3.1.2 map constructors, copy, and assignment [lib.map.cons]
23.3.1.3 map iterator support [lib.map.iterators]
23.3.1.4 map capacity [lib.map.capacity]
23.3.1.5 map element access [lib.map.access]
T& operator[](const key_type& x);
Returns:
(*((insert(make_pair(x, T()))).first)).second.
23.3.1.6 map modifiers [lib.map.modifiers]
23.3.1.7 map observers [lib.map.observers]
23.3.1.8 map operations [lib.map.ops]
23.3.1.9 map specialized algorithms [lib.map.special]
template <class Key, class T, class Compare, class Allocator>
void swap(map<Key,T,Compare,Allocator>& x,
map<Key,T,Compare,Allocator>& y);
Effects:
x.swap(y);
23.3.2 Template class multimap [lib.multimap]
1 A multimap is a kind of associative container that supports equal keys
(possibly contains multiple copies of the same key value) and provides
for fast retrieval of values of another type T based on the keys.
Multimap supports bidirectional iterators.
namespace std {
template <class Key, class T, class Compare = less<Key>,
class Allocator = allocator>
class multimap {
public:
// types:
typedef Key key_type;
typedef T mapped_type;
typedef pair<const Key,T> value_type;
typedef Compare key_compare;
typedef Allocator allocator_type;
class value_compare
: public binary_function<value_type,value_type,bool> {
friend class multimap;
protected:
Compare comp;
value_compare(Compare c) : comp(c) {}
public:
bool operator()(const value_type& x, const value_type& y) {
return comp(x.first, y.first);
}
};
typedef typename Allocator::types<value_type>::reference reference;
typedef typename Allocator::types<value_type>::const_reference
const_reference;
typedef implementation defined iterator;
typedef implementation defined const_iterator;
typedef typename Allocator::size_type size_type;
typedef typename Allocator::difference_type difference_type;
typedef reverse_iterator<iterator, value_type,
reference, difference_type> reverse_iterator;
typedef reverse_iterator<const_iterator, value_type,
const_reference, difference_type> const_reverse_iterator;
// construct/copy/destroy:
explicit multimap(const Compare& comp = Compare(),
const Allocator& = Allocator());
template <class InputIterator>
multimap(InputIterator first, InputIterator last,
const Compare& comp = Compare(), const Allocator& = Allocator());
multimap(const multimap<Key,T,Compare,Allocator>& x);
~multimap();
multimap<Key,T,Compare,Allocator>&
operator=(const multimap<Key,T,Compare,Allocator>& x);
allocator_type get_allocator() const;
// iterators:
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
reverse_iterator rend();
const_reverse_iterator rend() const;
// capacity:
bool empty() const;
size_type size() const;
size_type max_size() const;
// modifiers:
iterator insert(const value_type& x);
iterator insert(iterator position, const value_type& x);
template <class InputIterator>
void insert(InputIterator first, InputIterator last);
void erase(iterator position);
size_type erase(const key_type& x);
void erase(iterator first, iterator last);
void swap(multimap<Key,T,Compare,Allocator>&);
void clear();
// observers:
key_compare key_comp() const;
value_compare value_comp() const;
// map operations:
iterator find(const key_type& x);
const_iterator find(const key_type& x) const;
size_type count(const key_type& x) const;
iterator lower_bound(const key_type& x);
const_iterator lower_bound(const key_type& x) const;
iterator upper_bound(const key_type& x);
const_iterator upper_bound(const key_type& x) const;
pair<iterator,iterator> equal_range(const key_type& x);
pair<const_iterator,const_iterator> equal_range(const key_type& x) const;
};
template <class Key, class T, class Compare, class Allocator>
bool operator==(const multimap<Key,T,Compare,Allocator>& x,
const multimap<Key,T,Compare,Allocator>& y);
template <class Key, class T, class Compare, class Allocator>
bool operator< (const multimap<Key,T,Compare,Allocator>& x,
const multimap<Key,T,Compare,Allocator>& y);
// specialized algorithms:
template <class Key, class T, class Compare, class Allocator>
void swap(multimap<Key,T,Compare,Allocator>& x,
multimap<Key,T,Compare,Allocator>& y);
}
23.3.2.1 multimap specialized algorithms [lib.multimap.special]
template <class Key, class T, class Compare, class Allocator>
void swap(multimap<Key,T,Compare,Allocator>& x,
multimap<Key,T,Compare,Allocator>& y);
Effects:
x.swap(y);
23.3.3 Template class set [lib.set]
1 A set is a kind of associative container that supports unique keys
(contains at most one of each key value) and provides for fast
retrieval of the keys themselves. Set supports bidirectional itera
tors.
namespace std {
template <class Key, class Compare = less<Key>, class Allocator = allocator>
class set {
public:
// _lib.set.types_ types:
typedef Key key_type;
typedef Key value_type;
typedef Compare key_compare;
typedef Compare value_compare;
typedef Allocator allocator_type;
typedef typename Allocator::types<Key>::reference reference;
typedef typename Allocator::types<Key>::const_reference const_reference;
typedef implementation defined iterator;
typedef implementation defined const_iterator;
typedef typename Allocator::size_type size_type;
typedef typename Allocator::difference_type difference_type;
typedef reverse_iterator<iterator, value_type,
reference, difference_type> reverse_iterator;
typedef reverse_iterator<const_iterator, value_type,
const_reference, difference_type> const_reverse_iterator;
// _lib.set.cons_ construct/copy/destroy:
explicit set(const Compare& comp = Compare(), const Allocator& = Allocator());
template <class InputIterator>
set(InputIterator first, InputIterator last,
const Compare& comp = Compare(), const Allocator& = Allocator());
set(const set<Key,Compare,Allocator>& x);
~set();
set<Key,Compare,Allocator>& operator=(const set<Key,Compare,Allocator>& x);
allocator_type get_allocator() const;
// _lib.set.iterators_ iterators:
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
reverse_iterator rend();
const_reverse_iterator rend() const;
// _lib.set.capacity_ capacity:
bool empty() const;
size_type size() const;
size_type max_size() const;
// _lib.set.modifiers_ modifiers:
pair<iterator,bool> insert(const value_type& x);
iterator insert(iterator position, const value_type& x);
template <class InputIterator>
void insert(InputIterator first, InputIterator last);
void erase(iterator position);
size_type erase(const key_type& x);
void erase(iterator first, iterator last);
void swap(set<Key,Compare,Allocator>&);
void clear();
// _lib.set.observers_ observers:
key_compare key_comp() const;
value_compare value_comp() const;
// _lib.set.ops_ set operations:
iterator find(const key_type& x) const;
size_type count(const key_type& x) const;
iterator lower_bound(const key_type& x) const;
iterator upper_bound(const key_type& x) const;
pair<iterator,iterator> equal_range(const key_type& x) const;
};
template <class Key, class Compare, class Allocator>
bool operator==(const set<Key,Compare,Allocator>& x,
const set<Key,Compare,Allocator>& y);
template <class Key, class Compare, class Allocator>
bool operator< (const set<Key,Compare,Allocator>& x,
const set<Key,Compare,Allocator>& y);
// specialized algorithms:
template <class Key, class Compare, class Allocator>
void swap(set<Key,Compare,Allocator>& x,
set<Key,Compare,Allocator>& y);
}
23.3.3.1 set types [lib.set.types]
23.3.3.2 set constructors, copy, and assignment [lib.set.cons]
23.3.3.3 set iterator support [lib.set.iterators]
23.3.3.4 set capacity [lib.set.capacity]
23.3.3.5 set modifiers [lib.set.modifiers]
23.3.3.6 set observers [lib.set.observers]
23.3.3.7 set operations [lib.set.ops]
23.3.3.8 set specialized algorithms [lib.set.special]
template <class Key, class Compare, class Allocator>
void swap(set<Key,Compare,Allocator>& x,
set<Key,Compare,Allocator>& y);
Effects:
x.swap(y);
23.3.4 Template class multiset [lib.multiset]
1 A multiset is a kind of associative container that supports equal keys
(possibly contains multiple copies of the same key value) and provides
for fast retrieval of the keys themselves. Multiset supports bidirec
tional iterators.
namespace std {
template <class Key, class Compare = less<Key>, class Allocator = allocator>
class multiset {
public:
// types:
typedef Key key_type;
typedef Key value_type;
typedef Compare key_compare;
typedef Compare value_compare;
typedef Allocator allocator_type;
typedef typename Allocator::types<Key>::reference reference;
typedef typename Allocator::types<Key>::const_reference const_reference;
typedef implementation defined iterator;
typedef implementation defined const_iterator;
typedef typename Allocator::size_type size_type;
typedef typename Allocator::difference_type difference_type;
typedef reverse_iterator<iterator, value_type,
reference, difference_type> reverse_iterator;
typedef reverse_iterator<const_iterator, value_type,
const_reference, difference_type> const_reverse_iterator;
// construct/copy/destroy:
explicit multiset(const Compare& comp = Compare(),
const Allocator& = Allocator());
template <class InputIterator>
multiset(InputIterator first, InputIterator last,
const Compare& comp = Compare(), const Allocator& = Allocator());
multiset(const multiset<Key,Compare,Allocator>& x);
~multiset();
multiset<Key,Compare,Allocator>&
operator=(const multiset<Key,Compare,Allocator>& x);
allocator_type get_allocator() const;
// iterators:
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
reverse_iterator rend();
const_reverse_iterator rend() const;
// capacity:
bool empty() const;
size_type size() const;
size_type max_size() const;
// modifiers:
iterator insert(const value_type& x);
iterator insert(iterator position, const value_type& x);
template <class InputIterator>
void insert(InputIterator first, InputIterator last);
void erase(iterator position);
size_type erase(const key_type& x);
void erase(iterator first, iterator last);
void swap(multiset<Key,Compare,Allocator>&);
void clear();
// observers:
key_compare key_comp() const;
value_compare value_comp() const;
// set operations:
iterator find(const key_type& x) const;
size_type count(const key_type& x) const;
iterator lower_bound(const key_type& x) const;
iterator upper_bound(const key_type& x) const;
pair<iterator,iterator> equal_range(const key_type& x) const;
};
template <class Key, class Compare, class Allocator>
bool operator==(const multiset<Key,Compare,Allocator>& x,
const multiset<Key,Compare,Allocator>& y);
template <class Key, class Compare, class Allocator>
bool operator< (const multiset<Key,Compare,Allocator>& x,
const multiset<Key,Compare,Allocator>& y);
// specialized algorithms:
template <class Key, class Compare, class Allocator>
void swap(multiset<Key,Compare,Allocator>& x,
multiset<Key,Compare,Allocator>& y);
}
23.3.4.1 multiset specialized algorithms [lib.multiset.special]
template <class Key, class Compare, class Allocator>
void swap(multiset<Key,Compare,Allocator>& x,
multiset<Key,Compare,Allocator>& y);
Effects:
x.swap(y);