______________________________________________________________________
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 |
+------------------------------------------------------+
| <bits> |
| <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 In the following Table 2, we assume X is a container class containing
objects of type T, a and b are values of X, u is an identifier and r
is a value of X&.
Table 2--Container requirements
---------------------------------------------------------------------------------------------------
expression return type assertion/note complexity
pre/post-condition
---------------------------------------------------------------------------------------------------
X::value_type 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 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)-> result is not used post: a.size() == 0. linear
~X() 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 |
+-------------------------------------------------------------------------------------------------+
+---------------------------------------------------------------------------------+
|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_type size() of the constant |
| largest possible |
| container. |
|size() |
+---------------------------------------------------------------------------------+
|a.empty() convertible to bool a.size() == 0 constant |
+---------------------------------------------------------------------------------+
|a < b convertible to bool lexicographical_ pre: < is defined linear |
| compare (a.begin(), for values of T. |
| a.end(), < is a total or |
| 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: equal and lexicographical_compare are defined in Clause
(_lib.algorithms_).
3 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.
4 begin() returns an iterator referring to the first element in the con
tainer. end() returns an iterator which is the past-the-end value.
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 stack s or queue s, out
of the basic sequence kinds (or out of other kinds of sequences that
the user might define).
2 In the following Table 3, X is a sequence class, a is value of X, i
and j satisfy input iterator requirements, [i, j) is a valid range, n
is a value of X::size_type, p is a valid iterator to a, q, q1, q2 are
valid dereferenceable iterators to a, [q1, q2) is a valid range, t is
a value of X::value_type.
3 The complexities of the expressions are sequence dependent.
Table 3--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) result is not used inserts n copies of t before p. |
+----------------------------------------------------------------------------------------------+
|a.insert(p, i, j) result is not used inserts copies of elements in [i, j) before p. |
+----------------------------------------------------------------------------------------------+
|a.erase(q) result is not used erases the element pointed to by q. |
+----------------------------------------------------------------------------------------------+
|a.erase(q1, q2) result is not used erases the elements in the range [q1, q2). |
+----------------------------------------------------------------------------------------------+
4 vector, 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 fre
quent 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 iterator and const_iterator types for sequences have to be at least of
the forward iterator category.
6 Table 4:
Table 4--Optional sequence operations
+-----------------------------------------------------------------------+
| expression return type operational container |
| semantics |
+-----------------------------------------------------------------------+
|a.front() T&; const T& *a.begin() vector, list, |
| for constant a deque |
+-----------------------------------------------------------------------+
|a.back() T&; const T& *a.end() vector, list, |
| for constant a deque |
+-----------------------------------------------------------------------+
|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 |
+-----------------------------------------------------------------------+
7 All the operations in the above table are provided only for the con
tainers for which they take constant time.
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 All of them are 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 container.
3 In this section when we talk about equality of keys we mean the equiv
alence 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 the following Table 5, 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 iterator requirements and refer to elements of value_type, [i,
j) is a valid range, p is a valid iterator to a, q, q1, q2 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 5--Associative container requirements (in addition to container)
+--------------------------------------------------------------------------------------+
| expression return type assertion/note complexity |
| pre/post-condition |
+--------------------------------------------------------------------------------------+
|X::key_type Key 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 and compile time |
|ue_compare icate type multiset; is an ordering relation on |
| pairs induced by the first component |
| (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); lin |
| ear if [i, j) |
| is sorted with |
| value_comp() |
+--------------------------------------------------------------------------------------+
|X(i, j) same as above, but uses Compare() as a same as |
|X a(i, j); comparison object. above |
+--------------------------------------------------------------------------------------+
|a.key_comp() X:: returns the comparison object out of constant |
| key_compare 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.insert(t) pair<iterator, inserts t if and only if there is no logarithmic |
| 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) result is not used 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
according 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) result is not used erases the element pointed to by q. amortized constant
---------------------------------------------------------------------------------------------
a.erase(q1, q2) result is not used erases all the elements in the log(size())+ N
range [q1, q2). where N is the
distance from q1
to q2.
---------------------------------------------------------------------------------------------
a.find(k) iterator; con returns an iterator pointing to an logarithmic
st_iterator for element with the key equal to k, or
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 for first element with key not less
constant a than k.
---------------------------------------------------------------------------------------------
a.upper_bound(k) iterator; con returns an iterator pointing to the logarithmic
st_iterator for first element with key greater than
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 <bits>, <deque>, <list>, <queue>, <stack>, and <vector>.
Header <bits> 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 bits;
template <size_t N>
istream& operator>>(istream& is, bits<N>& x);
template <size_t N>
ostream& operator<<(ostream& os, const bits<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);
}
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);
}
Header <queue> synopsis
#include <functional> // for less
namespace std {
template <class Container> class queue;
template <class Container>
bool operator==(const queue<Container>& x, const queue<Container>& y);
template <class Container, class Compare = less<Container::value_type> >
class priority_queue;
}
Header <stack> synopsis
namespace std {
template <class Container> class stack;
template <class Container>
bool operator==(const stack<Container>& x, const stack<Container>& 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);
class vector<bool,allocator>;
bool operator==(const vector<bool,allocator>& x,
const vector<bool,allocator>& y);
bool operator< (const vector<bool,allocator>& x,
const vector<bool,allocator>& y);
}
23.2.1 Template class bits [lib.template.bits]
1 The header <bits> 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 bits {
public:
bits();
bits(unsigned long val);
bits(const string& str, size_t pos = 0, size_t n = NPOS);
bits<N>& operator&=(const bits<N>& rhs);
bits<N>& operator|=(const bits<N>& rhs);
bits<N>& operator^=(const bits<N>& rhs);
bits<N>& operator<<=(size_t pos);
bits<N>& operator>>=(size_t pos);
bits<N>& set();
bits<N>& set(size_t pos, int val = 1);
bits<N>& reset();
bits<N>& reset(size_t pos);
bits<N> operator~() const;
bits<N>& toggle();
bits<N>& toggle(size_t pos);
unsigned short to_ushort() const;
unsigned long to_ulong() const;
string to_string() const;
size_t count() const;
size_t length() const;
bool operator==(const bits<N>& rhs) const;
bool operator!=(const bits<N>& rhs) const;
bool test(size_t pos) const;
bool any() const;
bool none() const;
bits<N> operator<<(size_t pos) const;
bits<N> operator>>(size_t pos) const;
private:
// char array[N]; exposition only
};
}
2 The template class bits<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 bits<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 val
ues.
+------- BEGIN BOX 1 -------+
For the sake of exposition, the maintained data is presented here as:
--char array[N], the sequence of bits, stored one bit per element.1)
+------- END BOX 1 -------+
_________________________
1) An implementation is free to store the bit sequence more efficient
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;
--an out-of-range error is associated with exceptions of type
out_of_range;
--an overflow error is associated with exceptions of type over
flow_error.
23.2.1.1 bits constructors [lib.cons.bits]
bits();
Effects:
Constructs an object of class bits<N>, initializing all bits to
zero.
bits(unsigned long val);
Effects:
Constructs an object of class bits<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).2)
If M < N, remaining bit positions are initialized to zero.
bits(const string& str, size_t pos = 0, size_t n = NPOS);
Requires:
pos<=
Throws:
out_of_range if pos > str.len.
Effects:
Determines the effective length rlen of the initializing string as
the smaller of n and str.len - 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 bits<N>, ini
tializing 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.
_________________________
ly.
2) The macro CHAR_BIT is defined in <climits>(_lib.support.limits_).
2 If M < N, remaining bit positions are initialized to zero.
23.2.1.2 bits::operator&= [lib.bits::op&=.bt]
bits<N>& operator&=(const bits<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.
23.2.1.3 bits::operator|= [lib.bits::op|=.bt]
bits<N>& operator|=(const bits<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.
23.2.1.4 bits::operator^= [lib.bits::op^=.bt]
bits<N>& operator^=(const bits<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.
23.2.1.5 bits::operator<<= [lib.bits::op.lsh=]
bits<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.
23.2.1.6 bits::operator>>= [lib.bits::op.rsh=]
bits<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.
23.2.1.7 bits::set [lib.bits::set]
bits<N>& set();
Effects:
Sets all bits in *this.
Returns:
*this.
bits<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.
23.2.1.8 bits::reset [lib.bits::reset]
bits<N>& reset();
Effects:
Resets all bits in *this.
Returns:
*this.
bits<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.
23.2.1.9 bits::operator~ [lib.bits::op~]
bits<N> operator~() const;
Effects:
Constructs an object x of class bits<N> and initializes it with
*this.
Returns:
x.toggle().
23.2.1.10 bits::toggle [lib.bits::toggle]
bits<N>& toggle();
Effects:
Toggles all bits in *this.
Returns:
*this.
bits<N>& toggle(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.
23.2.1.11 bits::to_ushort [lib.bits::to.ushort]
unsigned short to_ushort() const;
Throws:
overflow_error if the integral value x corresponding to the bits in
*this cannot be represented as type unsigned short.
Returns:
x.
23.2.1.12 bits::to_ulong [lib.bits::to.ulong]
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.
23.2.1.13 bits::to_string [lib.bits::to.string]
string to_string() const;
Effects:
Constructs an object of type string 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 positions. Bit value zero
becomes the character 0, bit value one becomes the character 1.
Returns:
The created object.
23.2.1.14 bits::count [lib.bits::count]
size_t count() const;
Returns:
A count of the number of bits set in *this.
23.2.1.15 bits::length [lib.bits::length]
size_t length() const;
Returns:
N.
23.2.1.16 bits::operator== [lib.bits::op==.bt]
bool operator==(const bits<N>& rhs) const;
Returns:
A nonzero value if the value of each bit in *this equals the value
of the corresponding bit in rhs.
23.2.1.17 bits::operator!= [lib.bits::op!=.bt]
bool operator!=(const bits<N>& rhs) const;
Returns:
A nonzero value if !(*this == rhs).
23.2.1.18 bits::test [lib.bits::test]
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.
23.2.1.19 bits::any [lib.bits::any]
bool any() const;
Returns:
true if any bit in *this is one.
23.2.1.20 bits::none [lib.bits::none]
bool none() const;
Returns:
true if no bit in *this is one.
23.2.1.21 bits::operator<< [lib.bits::op.lsh]
bits<N> operator<<(size_t pos) const;
Returns:
bits<N>(*this) <<= pos.
23.2.1.22 bits::operator>> [lib.bits::op.rsh]
bits<N> operator>>(size_t pos) const;
Returns:
bits<N>(*this) >>= pos.
23.2.1.23 operator& [lib.bits::op&]
bits<N> operator&(const bits<N>& lhs, const bits<N>& rhs);
Returns:
bits<N>(lhs) &= pos.
23.2.1.24 operator| [lib.bits::op|]
bits<N> operator|(const bits<N>& lhs, const bits<N>& rhs);
Returns:
bits<N>(lhs) |= pos.
23.2.1.25 operator^ [lib.bits::op^]
bits<N> operator^(const bits<N>& lhs, const bits<N>& rhs);
Returns:
bits<N>(lhs) ^= pos.
23.2.1.26 operator>> [lib.bits::ext]
template <size_t N>
istream& operator>>(istream& is, bits<N>& x);
1 A formatted input function.
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 = bits<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).
Returns:
is.
23.2.1.27 operator<< [lib.bits::ins]
template <size_t N>
ostream& operator<<(ostream& os, const bits<N>& x);
Returns:
os << x.to_string().
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:
// types:
typedef Allocator::types<T>::pointer iterator;
typedef Allocator::types<T>::const_pointer const_iterator;
typedef Allocator::size_type size_type;
typedef Allocator::difference_type difference_type;
typedef T value_type;
// construct/copy/destroy:
deque();
deque(size_type n, const T& value = T());
deque(const deque<T,Allocator>& x);
template <class InputIterator>
deque(InputIterator first, InputIterator last);
~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());
// observers:
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
size_type size() const;
size_type max_size() const;
void resize(size_type sz, T c = T());
bool empty() const;
T& operator[](size_type n);
const T& operator[](size_type n) const;
const T& at(size_type n) const;
T& at(size_type n);
T& front();
const T& front() const;
T& back();
const T& back() const;
// 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 = T());
template <class InputIterator>
void insert (iterator position, InputIterator first, InputIterator last);
void pop_front();
void pop_back();
void erase(iterator position);
void erase(iterator first, iterator last);
};
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);
}
23.2.2.1 deque members [lib.deque.members]
23.2.2.1.1 assign [lib.deque.assign]
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.1.2 insert [lib.deque.insert]
iterator insert(iterator position, const T& x = T());
void insert(iterator position, size_type n, const T& x = T());
template <class InputIterator>
void insert(iterator position,
InputIterator first, InputIterator last);
Effects:
Invalidates all the iterators and references to the deque if the
insertion pointer is not at either end. Insertion at either end
does not affect iterators and references.
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.
23.2.2.1.3 erase [lib.deque.erase]
void erase(iterator position);
void erase(iterator first, iterator last);
Effects:
Invalidates all the iterators and references to the deque if the
erasing point is not at either end. Erasing at either end does not
affect iterators and references. 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 operator is equal to the mini
mum of the number of elements before the erased elements and the
number of element after the erased elements.
23.2.2.1.4 resize [lib.deque.resize]
void resize(size_type sz, T c = T());
Effects:
if (sz > size())
s.insert(s.end(), s.size()-sz, v);
else if (sz < size())
s.erase(s.begin()+sz, s.end());
else
???
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:
// types:
typedef Allocator::types<T>::pointer iterator;
typedef Allocator::types<T>::const_pointer const_iterator;
typedef Allocator::size_type size_type;
typedef Allocator::difference_type difference_type;
typedef T value_type;
// construct/copy/destroy:
list();
list(size_type n, const T& value = T());
template <class InputIterator>
list(InputIterator first, InputIterator last);
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());
// observers:
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
bool empty() const;
size_type size() const;
size_type max_size() const;
void resize(size_type sz, T c = T());
T& front();
const T& front() const;
T& back();
const T& back() const;
// 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 = T());
template <class InputIterator>
void insert(iterator position, InputIterator first,
InputIterator last);
void erase(iterator position);
void erase(iterator position, iterator last);
// special mutative operations on list:
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);
}
23.2.3.1 list members [lib.list.members]
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.
23.2.3.1.1 assign [lib.list.assign]
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.1.2 insert [lib.list.insert]
iterator insert(iterator position, const T& x = T());
void insert(iterator position, size_type n, const T& x = T());
template <class InputIterator>
void insert(iterator position, InputIterator first,
InputIterator last);
Notes:
1 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.
23.2.3.1.3 erase [lib.list.erase]
void erase(iterator position);
void 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.1.4 resize [lib.list.resize]
void resize(size_type sz, T c = T());
Effects:
if (sz > size())
s.insert(s.end(), s.size()-sz, v);
else if (sz < size())
s.erase(s.begin()+sz, s.end());
else
???
23.2.3.1.5 splice [lib.list.splice]
void splice(iterator position, list<T,Allocator>& x);
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.
Requires:
i is a valid 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.
Complexity:
Linear time.
23.2.3.1.6 remove [lib.list.remove]
void remove(const T& value);
template <class Predicate> void remove_if(Predicate pred);
Effects:
Erases all the elements in the list referred by the 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.
23.2.3.1.7 unique [lib.list.unique]
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.
23.2.3.1.8 merge [lib.list.merge]
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.
23.2.3.1.9 reverse [lib.list.reverse]
void reverse();
Effects:
Reverses the order of the elements in the list.
Complexity:
Linear time.
23.2.3.1.10 sort [lib.list.sort]
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.4 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 Container>
class queue {
public:
typedef Container::value_type value_type;
typedef Container::size_type size_type;
protected:
Container c;
public:
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 Container>
bool operator==(const queue<Container>& x, const queue<Container>& y);
}
operator==
Returns:
x.c == y.c.
23.2.5 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 Container, class Compare = less<Container::value_type> >
class priority_queue {
public:
typedef Container::value_type value_type;
typedef Container::size_type size_type;
protected:
Container c;
Compare comp;
public:
priority_queue(const Compare& x = Compare());
template <class InputIterator>
priority_queue(InputIterator first, InputIterator last,
const Compare& x = Compare());
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.6 priority_queue members [lib.priority.queue.members]
23.2.6.1 priority_queue constructors [lib.priqueue.cons]
priority_queue(const Compare& x = Compare());
Effects:
: c(), comp(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.6.2 push [lib.priqueue.push]
void push(const value_type& x);
Effects:
c.push_back(x);
push_heap(c.begin(), c.end(), comp);
23.2.6.3 pop [lib.priqueue.pop]
void pop();
Effects:
pop_heap(c.begin(), c.end(), comp);
c.pop_back();
23.2.7 Template class stack [lib.stack]
1 Any sequence supporting operations back(), push_back() and pop_back()
can be used to instantiate stack. In particular, vec
tor(_lib.vector_), list(_lib.list_) and deque(_lib.deque_) can be
used.
2 For example, stack<vector<int> > is an integer stack made out of vec
tor, and stack<deque<char> > is a character stack made out of deque.
namespace std {
template <class Container>
class stack {
public:
typedef Container::value_type value_type;
typedef Container::size_type size_type;
protected:
Container c;
public:
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 Container>
bool operator==(const stack<Container>& x, const stack<Container>& y);
}
operator==
Returns:
x.c == y.c.
23.2.8 Template class vector [lib.vector]
1 A vector is a kind of sequence supports random access iterators. In
addition, it supports (amortized) constant time insert and erase oper
ations 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:
// types:
typedef Allocator::types<T>::pointer iterator;
typedef Allocator::types<T>::const_pointer const_iterator;
typedef Allocator::size_type size_type;
typedef Allocator::difference_type difference_type;
typedef T value_type;
// construct/copy/destroy:
vector();
vector(size_type n, const T& value = T());
vector(const vector<T,Allocator>& x);
template <class InputIterator>
vector(InputIterator first, InputIterator last);
~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());
void reserve(size_type n);
// observers:
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
size_type size() const;
size_type max_size() const;
void resize(size_type sz, T c = T());
size_type capacity() const;
bool empty() const;
T& operator[](size_type n);
const T& operator[](size_type n) const;
const T& at(size_type n) const;
T& at(size_type n);
T& front();
const T& front() const;
T& back();
const T& back() const;
// 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 = T());
template <class InputIterator>
void insert(iterator position, InputIterator first, InputIterator last);
void erase(iterator position);
void erase(iterator first, iterator last);
};
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);
}
23.2.8.1 vector members [lib.vector.members]
23.2.8.1.1 vector constructor [lib.vector.cons]
vector();
vector(size_type n, const T& value = T());
vector(const vector<T,Allocator>& x);
template <class InputIterator>
vector(InputIterator first, InputIterator last);
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.
23.2.8.1.2 assign [lib.vector.assign]
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.8.1.3 capacity [lib.vector.capacity]
size_type capacity() const;
Returns:
The size of the allocated storage in the vector.
23.2.8.1.4 reserve [lib.vector.reserve]
void reserve(size_type n);
Effects:
A directive that informs vector of a planned change in size, so that
it can manage the storage allocation accordingly. It does not
change the size of the sequence and takes at most linear time in the
size of the sequence. Reallocation happens at this point if and
only if the current capacity is less than the argument of reserve.
After reserve, capacity is greater or equal to the argument of
reserve if reallocation happens; and equal to the previous value of
capacity otherwise. 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 inser
tions that happen after reserve takes place till the time when the
size of the vector reaches the size specified by reserve.
23.2.8.1.5 resize [lib.vector.resize]
void resize(size_type sz, T c = T());
Effects:
if (sz > size())
s.insert(s.end(), s.size()-sz, v);
else if (sz < size())
s.erase(s.begin()+sz, s.end());
else
???
23.2.8.1.6 insert [lib.vector.insert]
iterator insert(iterator position, const T& x = T());
void insert(iterator position, size_type n, const T& x = T());
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.3)
23.2.8.1.7 erase [lib.vector.erase]
void erase(iterator position);
void erase(iterator first, iterator last);
Effects:
Invalidates all the iterators and references after the point of the
erase. The destructor of T is called the number of times equal to
the number 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.
23.2.9 Class vector<bool> [lib.vector.bool]
1 To optimize space allocation, a specialization for bool is provided:4)
_________________________
3) 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.
4) Every implementation is expected to provide specializations of vec
tor<bool> for all supported memory models.
namespace std {
class vector<bool,allocator> {
public:
// bit reference:
class reference {
public:
~reference();
operator bool() const;
reference& operator=(const bool x);
void flip(); // flips the bit
};
// types:
typedef Allocator::types<T>::pointer iterator;
typedef Allocator::types<T>::const_pointer const_iterator;
typedef Allocator::size_type size_type;
typedef Allocator::difference_type difference_type;
typedef bool value_type;
// construct/copy/destroy:
vector();
vector(size_type n, const bool& value = bool());
vector(const vector<bool,allocator>& x);
template <class InputIterator>
vector(InputIterator first, InputIterator last);
~vector();
vector<bool,allocator>& operator=(const vector<bool,allocator>& x);
void reserve(size_type n);
// observers:
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
size_type size() const;
size_type max_size() const;
size_type capacity() const;
bool empty() const;
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 = bool());
template <class InputIterator>
void insert (iterator position, InputIterator first, InputIterator last);
void erase(iterator position);
void erase(iterator first, iterator last);
};
bool operator==(const vector<bool,allocator>& x,
const vector<bool,allocator>& y);
bool operator< (const vector<bool,allocator>& x,
const 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 = 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);
}
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 = 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);
}
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.
namespace std {
template <class Key, class T, class Compare = less<Key>,
class Allocator = allocator>
class map {
public:
// types:
typedef Key key_type;
typedef pair<const Key, T> value_type;
typedef Compare key_compare;
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);
}
};
ISSUE Are these typedefs correct?
typedef Allocator::types<T>::pointer iterator;
typedef Allocator::types<T>::const_pointer const_iterator;
typedef Allocator::size_type size_type;
typedef Allocator::difference_type difference_type;
// construct/copy/destroy:
map(const Compare& comp = Compare());
template <class InputIterator>
map(InputIterator first, InputIterator last,
const Compare& comp = Compare());
map(const map<Key,T,Compare,Allocator>& x);
~map();
map<Key,T,Compare,Allocator>&
operator=(const map<Key,T,Compare,Allocator>& x);
// observers:
key_compare key_comp() const;
value_compare value_comp() const;
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
bool empty() const;
size_type size() const;
size_type max_size() const;
T& operator[](const key_type& x);
// 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);
// 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);
}
23.3.1.1 map members [lib.map.members]
+------- BEGIN BOX 2 -------+
To Be Specified
+------- END BOX 2 -------+
23.3.1.1.1 operator[] lib.map::subscript
T& operator[](const key_type& x);
Effects:
(*((m.insert(make_pair(k, T()))).first)).second.
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.
namespace std {
template <class Key, class T, class Compare = less<Key>,
class Allocator = allocator>
class multimap {
public:
// types:
typedef Key key_type;
typedef pair<const Key,T> value_type;
typedef Compare key_compare;
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);
}
};
ISSUE Are these typedefs correct?
typedef Allocator::types<T>::pointer iterator;
typedef Allocator::types<T>::const_pointer const_iterator;
typedef Allocator::size_type size_type;
typedef Allocator::difference_type difference_type;
// construct/copy/destroy:
multimap(const Compare& comp = Compare());
template <class InputIterator>
multimap(InputIterator first, InputIterator last,
const Compare& comp = Compare());
multimap(const multimap<Key,T,Compare,Allocator>& x);
~multimap();
multimap<Key,T,Compare,Allocator>&
operator=(const multimap<Key,T,Compare,Allocator>& x);
// observers:
key_compare key_comp() const;
value_compare value_comp() const;
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
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);
// multimap 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);
}
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.
namespace std {
template <class Key, class Compare = less<Key>, class Allocator = allocator>
class set {
public:
// types:
typedef Key key_type;
typedef Key value_type;
typedef Compare key_compare;
typedef Compare value_compare;
typedef Allocator::types<T>::pointer iterator;
typedef Allocator::types<T>::const_pointer const_iterator;
typedef Allocator::size_type size_type;
typedef Allocator::difference_type difference_type;
// construct/copy/destroy:
set(const Compare& comp = Compare());
template <class InputIterator>
set(InputIterator first, InputIterator last,
const Compare& comp = Compare());
set(const set<Key,Compare,Allocator>& x);
~set();
set<Key,Compare,Allocator>& operator=(const set<Key,Compare,Allocator>& x);
// observers:
key_compare key_comp() const;
value_compare value_comp() const;
iterator begin() const;
iterator end() const;
bool empty() const;
size_type size() const;
size_type max_size() const;
// 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);
// 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);
}
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.
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::types<T>::pointer iterator;
typedef Allocator::types<T>::const_pointer const_iterator;
typedef Allocator::size_type size_type;
typedef Allocator::difference_type difference_type;
// construct/copy/destroy:
multiset(const Compare& comp = Compare());
template <class InputIterator>
multiset(InputIterator first, InputIterator last,
const Compare& comp = Compare());
multiset(const multiset<Key,Compare,Allocator>& x);
~multiset();
multiset<Key,Compare,Allocator>&
operator=(const multiset<Key,Compare,Allocator>& x);
// observers:
key_compare key_comp() const;
value_compare value_comp() const;
iterator begin() const;
iterator end() const;
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);
// multiset 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);
}