______________________________________________________________________
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 components for sequences
(_lib.sequences_) and associative containers (_lib.associative_).
23.1 Sequences [lib.sequences]
1 Headers:
--<bits>
--<bitstring>
--<dynarray>
--<ptrdynarray>
--<stl containers (TBD)>
2 Table 1:
Table 1--Header <bits> synopsis
+----------------------------------------------------------+
| Type Name(s) |
+----------------------------------------------------------+
|Template class: bits |
+----------------------------------------------------------+
|Operator functions: |
|operator& (bits) operator>> (bits) operator| (bits) |
|operator<< (bits) operator^ (bits) |
+----------------------------------------------------------+
3 Table 2:
Table 2--Header <bitstring> synopsis
+----------------------------------------------------------+
| Type Name(s) |
+----------------------------------------------------------+
|Class: bitstring |
+----------------------------------------------------------+
|Operator functions: |
|operator& (bit_string) operator>> (bit_string) |
|operator+ (bit_string) operator^ (bit_string) |
|operator<< (bit_string) operator| (bit_string) |
+----------------------------------------------------------+
4 Table 3:
Table 3--Header <dynarray> synopsis
+------------------------------------------------+
| Type Name(s) |
+------------------------------------------------+
|Template class: dyn_array |
+------------------------------------------------+
|Operator function: operator+ (dyn_array) [3] |
+------------------------------------------------+
5 Table 4:
Table 4--Header <ptrdynarray> synopsis
+----------------------------------------------------+
| Type Name(s) |
+----------------------------------------------------+
|Class: ptr_dyn_array |
+----------------------------------------------------+
|Operator function: operator+ (ptr_dyn_array) [3] |
+----------------------------------------------------+
6 Table 5:
Table 5--Header <stl containers (TBD)> synopsis
+------------------------------------------------------------------------------+
| Type Name(s) |
+------------------------------------------------------------------------------+
|Template classes: |
|deque multimap queue vector |
|list multiset set |
|map priority_queue stack |
+------------------------------------------------------------------------------+
|Template operators: |
|operator< (deque) operator< (vector) operator== (queue) |
|operator< (list) operator== (deque) operator== (set) |
|operator< (map) operator== (list) operator== (stack) |
|operator< (multimap) operator== (map) operator== (vector) |
|operator< (multiset) operator== (multimap) |
|operator< (set) operator== (multiset) |
+------------------------------------------------------------------------------+
|Class: vector<bool,allocator> |
+------------------------------------------------------------------------------+
|Operator functions: operator< (vector<bool,allocator>) |
| operator== (vector<bool,allocator>) |
+------------------------------------------------------------------------------+
23.1.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.
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.
4 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)
5 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.1.1.1 bits constructors [lib.cons.bits]
bits();
1 Constructs an object of class bits<N>, initializing all bits to zero.
bits(unsigned long val);
_________________________
1) An implementation is free to store the bit sequence more efficient
ly.
2 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).
3 The macro CHAR_BIT is defined in <climits>
4 If M < N, remaining bit positions are initialized to zero.
bits(const string& str, size_t pos = 0, size_t n = NPOS);
5 Throws out_of_range if pos > str.len. Otherwise, the function deter
mines the effective length rlen of the initializing string as the
smaller of n and str.len - pos.
6 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.
7 Otherwise, the function constructs an object of class bits<N>, ini
tializing the first M bit positions to values determined from the cor
responding characters in the string str. M is the smaller of N and
rlen.
8 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.
9 If M < N, remaining bit positions are initialized to zero.
23.1.1.2 bits::operator&= [lib.bits::op&=.bt]
bits<N>& operator&=(const bits<N>& rhs);
1 Clears each bit in *this for which the corresponding bit in rhs is
clear, and leaves all other bits unchanged.
2 Returns *this.
23.1.1.3 bits::operator|= [lib.bits::op|=.bt]
bits<N>& operator|=(const bits<N>& rhs);
1 Sets each bit in *this for which the corresponding bit in rhs is set,
and leaves all other bits unchanged.
2 Returns *this.
23.1.1.4 bits::operator^= [lib.bits::op^=.bt]
bits<N>& operator^=(const bits<N>& rhs);
1 Toggles each bit in *this for which the corresponding bit in rhs is
set, and leaves all other bits unchanged.
2 Returns *this.
23.1.1.5 bits::operator<<= [lib.bits::op.lsh=]
bits<N>& operator<<=(size_t pos);
1 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.
2 Returns *this.
23.1.1.6 bits::operator>>= [lib.bits::op.rsh=]
bits<N>& operator>>=(size_t pos);
1 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.
2 Returns *this.
23.1.1.7 bits::set [lib.bits::set]
bits<N>& set();
1 Sets all bits in *this.
2 Returns *this.
bits<N>& set(size_t pos, int val = 1);
3 Throws out_of_range if pos does not correspond to a valid bit posi
tion. Otherwise, the function stores a new value in the bit at posi
tion pos in *this. If val is nonzero, the stored value is one, other
wise it is zero.
4 Returns *this.
23.1.1.8 bits::reset [lib.bits::reset]
bits<N>& reset();
1 Resets all bits in *this.
2 Returns *this.
bits<N>& reset(size_t pos);
3 Throws out_of_range if pos does not correspond to a valid bit posi
tion. Otherwise, the function resets the bit at position pos in
*this.
4 Returns *this.
23.1.1.9 bits::operator~ [lib.bits::op~]
bits<N> operator~() const;
1 Constructs an object x of class bits<N> and initializes it with *this.
2 Returns x.toggle().
23.1.1.10 bits::toggle [lib.bits::toggle]
bits<N>& toggle();
1 Toggles all bits in *this.
2 Returns *this.
bits<N>& toggle(size_t pos);
3 Throws out_of_range if pos does not correspond to a valid bit posi
tion. Otherwise, the function toggles the bit at position pos in
*this.
4 Returns *this.
23.1.1.11 bits::to_ushort [lib.bits::to.ushort]
unsigned short to_ushort() const;
1 If the integral value x corresponding to the bits in *this cannot be
represented as type unsigned short, throws overflow_error.
2 Otherwise, returns x.
23.1.1.12 bits::to_ulong [lib.bits::to.ulong]
unsigned long to_ulong() const;
1 If the integral value x corresponding to the bits in *this cannot be
represented as type unsigned long, throws overflow_error.
2 Otherwise, returns x.
23.1.1.13 bits::to_string [lib.bits::to.string]
string to_string() const;
1 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 corre
sponds to bit position zero. Subsequent decreasing character posi
tions correspond to increasing bit positions. Bit value zero becomes
the character 0, bit value one becomes the character 1.
2 Returns the created object.
23.1.1.14 bits::count [lib.bits::count]
size_t count() const;
1 Returns a count of the number of bits set in *this.
23.1.1.15 bits::length [lib.bits::length]
size_t length() const;
1 Returns N.
23.1.1.16 bits::operator== [lib.bits::op==.bt]
bool operator==(const bits<N>& rhs) const;
1 Returns a nonzero value if the value of each bit in *this equals the
value of the corresponding bit in rhs.
23.1.1.17 bits::operator!= [lib.bits::op!=.bt]
bool operator!=(const bits<N>& rhs) const;
1 Returns a nonzero value if !(*this == rhs).
23.1.1.18 bits::test [lib.bits::test]
bool test(size_t pos) const;
1 Throws out_of_range if pos does not correspond to a valid bit posi
tion.
2 Otherwise, returns a nonzero value if the bit at position pos in *this
has the value one.
23.1.1.19 bits::any [lib.bits::any]
bool any() const;
1 Returns a nonzero value if any bit in *this is one.
23.1.1.20 bits::none [lib.bits::none]
bool none() const;
1 Returns a nonzero value if no bit in *this is one.
23.1.1.21 bits::operator<< [lib.bits::op.lsh]
bits<N> operator<<(size_t pos) const;
1 Returns bits<N>(*this) <<= pos.
23.1.1.22 bits::operator>> [lib.bits::op.rsh]
bits<N> operator>>(size_t pos) const;
1 Returns bits<N>(*this) >>= pos.
23.1.1.23 operator& [lib.op&.bt.bt]
bits<N> operator&(const bits<N>& lhs, const bits<N>& rhs);
1 Returns bits<N>(lhs) &= pos.
23.1.1.24 operator| [lib.op|.bt.bt]
bits<N> operator|(const bits<N>& lhs, const bits<N>& rhs);
1 Returns bits<N>(lhs) |= pos.
23.1.1.25 operator^ [lib.op^.bt.bt]
bits<N> operator^(const bits<N>& lhs, const bits<N>& rhs);
1 Returns bits<N>(lhs) ^= pos.
23.1.1.26 operator>> [lib.ext.bt]
istream& operator>>(istream& is, bits<N>& x);
1 A formatted input function, extracts up to N (single-byte) characters
from is. The function 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, the function calls
is.setstate(ios::failbit).
3 Returns is.
23.1.1.27 operator<< [lib.ins.bt]
ostream& operator<<(ostream& os, const bits<N>& x);
1 Returns os << x.to_string().
23.1.2 Class bit_string [lib.bit.string]
1 The header <bitstring> defines a class and several function signatures
for representing and manipulating varying-length sequences of bits.
class bit_string {
public:
bit_string();
bit_string(unsigned long val, size_t n);
bit_string(const bit_string& str, size_t pos = 0, size_t n = NPOS);
bit_string(const string& str, size_t pos = 0, size_t n = NPOS);
bit_string& operator+=(const bit_string& rhs);
bit_string& operator&=(const bit_string& rhs);
bit_string& operator|=(const bit_string& rhs);
bit_string& operator^=(const bit_string& rhs);
bit_string& operator<<=(size_t pos);
bit_string& operator>>=(size_t pos);
bit_string& append(const bit_string& str, pos = 0, n = NPOS);
bit_string& assign(const bit_string& str, pos = 0, n = NPOS);
bit_string& insert(size_t pos1, const bit_string& str,
size_t pos2 = 0, size_t n = NPOS);
bit_string& remove(size_t pos = 0, size_t n = NPOS);
bit_string& replace(size_t pos1, size_t n1, const bit_string& str,
size_t pos2 = 0, size_t n2 = NPOS);
bit_string& set();
bit_string& set(size_t pos, bool val = 1);
bit_string& reset();
bit_string& reset(size_t pos);
bit_string& toggle();
bit_string& toggle(size_t pos);
string to_string() const;
size_t count() const;
size_t length() const;
size_t resize(size_t n, bool val = 0);
size_t trim();
size_t find(bool val, size_t pos = 0, size_t n = NPOS) const;
size_t rfind(bool val, size_t pos = 0, size_t n = NPOS) const;
bit_string substr(size_t pos, size_t n = NPOS) const;
bool operator==(const bit_string& rhs) const;
bool operator!=(const bit_string& rhs) const;
bool test(size_t pos) const;
bool any() const;
bool none() const;
bit_string operator<<(size_t pos) const;
bit_string operator>>(size_t pos) const;
bit_string operator~() const;
private:
// char* ptr; exposition only
// size_t len; exposition only
};
2 The class bit_string describes an object that can store a sequence
consisting of a varying number of bits. Such a sequence is also
called a bit string (or simply a string if the type of the elements is
clear from context). Storage for the string is allocated and freed as
necessary by the member functions of class bit_string.
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 bit_string of length len and a value of
some integral type, bit position pos corresponds to the bit value 1 <<
(len - pos - 1).2) The integral value corresponding to two or more
_________________________
2) Note that bit position zero is the most-significant bit for an ob
bits is the sum of their bit values.
4 For the sake of exposition, the maintained data is presented here as:
--char* ptr, points to the sequence of bits, stored one bit per
element;3)
--size_t len, the length of the bit sequence.
5 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;
--a length error is associated with exceptions of type length_error;
--an out-of-range error is associated with exceptions of type
out_of_range.
23.1.2.1 bit_string constructors [lib.cons.bit.string]
bit_string();
1 Constructs an object of class bit_string, initializing:
--ptr to an unspecified value;
--len to zero.
bit_string(unsigned long val, size_t n);
2 Throws length_error if n equals NPOS. Otherwise, the function con
structs an object of class bit_string and determines its initial
string value from val. If val is zero, the corresponding string is
the empty string. Otherwise, the corresponding string is the shortest
sequence of bits with the same bit value as val. If the corresponding
string is shorter than n, the string is extended with elements whose
values are all zero. Thus, the function initializes:
--ptr to point at the first element of the string;
--len to the length of the string.
bit_string(const bit_string& str, size_t pos = 0, size_t n = NPOS);
3 Throws out_of_range if pos > str.len. Otherwise, the function con
structs an object of class bit_string and determines the effective
length rlen of the initial string value as the smaller of n and
str.len - pos. Thus, the uunction initializes:
_________________________
ject of class bit_string, while it is the least-significant bit for an
object of class bits<N>.
3) An implementation is, of course, free to store the bit sequence
more efficiently.
--ptr to point at the first element of an allocated copy of rlen ele
ments of the string controlled by str beginning at position pos;
--len to rlen.
bit_string(const string& str, size_t pos = 0, size_t n = NPOS);
4 Throws out_of_range if pos > str.len. Otherwise, the function deter
mines the effective length rlen of the initializing string as the
smaller of n and str.len - pos.
5 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.
6 Otherwise, the function constructs an object of class bit_string and
determines its initial string value from str. The length of the con
structed string is rlen. An element of the constructed string has
value zero if the corresponding character in str, beginning at posi
tion pos, is 0. Otherwise, the element has the value one.
7 Thus, the function initializes:
--ptr to point at the first element of the string;
--len to rlen.
23.1.2.2 bit_string::operator+= [lib.bit.string::op+=.bs]
bit_string& operator+=(const bit_string& rhs);
1 Throws length_error if len >= NPOS - rhs.len.
2 Otherwise, the function replaces the string controlled by *this with a
string of length len + rhs.len whose first len elements are a copy of
the original string controlled by *this and whose remaining elements
are a copy of the elements of the string controlled by rhs.
3 Returns *this.
23.1.2.3 bit_string::operator&= [lib.bit.string::op&=.bs]
bit_string& operator&=(const bit_string& rhs);
1 Determines a length rlen which is the larger of len and rhs.len, then
behaves as if the shorter of the two strings controlled by *this and
rhs were temporarily extended to length rlen by adding elements all
with value zero. The function then replaces the string controlled by
*this with a string of length rlen whose elements have the value one
only if both of the corresponding elements of *this and rhs are one.
2 Returns *this.
23.1.2.4 bit_string::operator|= [lib.bit.string::op|=.bs]
bit_string& operator|=(const bit_string& rhs);
1 Determines a length rlen which is the larger of len and rhs.len, then
behaves as if the shorter of the two strings controlled by *this and
rhs were temporarily extended to length rlen by adding elements all
with value zero. The function then replaces the string controlled by
*this with a string of length rlen whose elements have the value one
only if either of the corresponding elements of *this and rhs are one.
2 Returns *this.
23.1.2.5 bit_string::operator^= [lib.bit.string::op^=.bs]
bit_string& operator^=(const bit_string& rhs);
1 Determines a length rlen which is the larger of len and rhs.len, then
behaves as if the shorter of the two strings controlled by *this and
rhs were temporarily extended to length rlen by adding elements all
with value zero. The function then replaces the string controlled by
*this with a string of length rlen whose elements have the value one
only if the corresponding elements of *this and rhs have different
values.
2 Returns *this.
23.1.2.6 bit_string::operator<<= [lib.bit.string::op.lsh=]
bit_string& operator<<=(size_t pos);
1 Replaces each element at position I in the string controlled by *this
with a value determined as follows:
--If pos >= len - I, the new value is zero;
--If pos < len - I, the new value is the previous value of the element
at position I + pos.
2 Returns *this.
23.1.2.7 bit_string::operator>>= [lib.bit.string::op.rsh=]
bit_string& operator>>=(size_t pos);
1 Replaces each element at position I in the string controlled by *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 element at
position I - pos.
23.1.2.8 bit_string::append [lib.bit.string::append]
bit_string& append(const bit_string& str, size_t pos = 0,
size_t n = NPOS);
1 Throws out_of_range if pos > str.len. Otherwise, the function deter
mines the effective length rlen of the string to append as the smaller
of n and str.len - pos.
2 The function then throws length_error if len >= NPOS - rlen.
3 Otherwise, the function replaces the string controlled by *this with a
string of length len + rlen whose first len elements are a copy of the
original string controlled by *this and whose remaining elements are a
copy of the initial elements of the string controlled by str beginning
at position pos.
4 Returns *this.
23.1.2.9 bit_string::assign [lib.bit.string::assign]
bit_string& assign(const bit_string& str, size_t pos = 0,
size_t n = NPOS);
1 Throws out_of_range if pos > str.len. Otherwise, the function deter
mines the effective length rlen of the string to assign as the smaller
of n and str.len - pos.
2 The function then replaces the string controlled by *this with a
string of length rlen whose elements are a copy of the string con
trolled by str beginning at position pos.
3 Returns *this.
23.1.2.10 bit_string::insert [lib.bit.string::insert]
bit_string& insert(size_t pos1, const bit_string& str, size_t pos2 = 0,
size_t n = NPOS);
1 Throws out_of_range if pos1 > len or pos2 > str.len. Otherwise, the
function determines the effective length rlen of the string to insert
as the smaller of n and str.len - pos2.
2 The function then throws length_error if len >= NPOS - rlen.
3 Otherwise, the function replaces the string controlled by *this with a
string of length len + rlen whose first pos1 elements are a copy of
the initial elements of the original string controlled by *this, whose
next rlen elements are a copy of the elements of the string controlled
by str beginning at position pos2, and whose remaining elements are a
copy of the remaining elements of the original string controlled by
*this.
4 Returns *this.
23.1.2.11 bit_string::remove [lib.bit.string::remove]
bit_string& remove(size_t pos = 0, size_t n = NPOS);
1 Throws out_of_range if pos > len. Otherwise, the function determines
the effective length xlen of the string to be removed as the smaller
of n and len - pos.
2 The function then replaces the string controlled by *this with a
string of length len - xlen whose first pos elements are a copy of the
initial elements of the original string controlled by *this, and whose
remaining elements are a copy of the elements of the original string
controlled by *this beginning at position pos + xlen.
3 Returns *this.
23.1.2.12 bit_string::replace [lib.bit.string::replace]
bit_string& replace(size_t pos1, size_t n1, const bit_string& str,
size_t pos2 = 0, size_t n2 = NPOS);
1 Throws out_of_range if pos1 > len or pos2 > str.len. Otherwise, the
function determines the effective length xlen of the string to be
removed as the smaller of n1 and len - pos1. It also determines the
effective length rlen of the string to be inserted as the smaller of
n2 and str.len - pos2.
2 The function then throws length_error if len - xlen >= NPOS - rlen.
3 Otherwise, the function replaces the string controlled by *this with a
string of length len - xlen + rlen whose first pos1 elements are a
copy of the initial elements of the original string controlled by
*this, whose next rlen elements are a copy of the initial elements of
the string controlled by str beginning at position pos2, and whose
remaining elements are a copy of the elements of the original string
controlled by *this beginning at position pos1 + xlen.
4 Returns *this.
23.1.2.13 bit_string::set [lib.bit.string::set]
bit_string& set();
1 Sets all elements of the string controlled by *this.
2 Returns *this.
bit_string& set(size_t pos, bool val = 1);
3 Throws out_of_range if pos > len. Otherwise, if pos == len, the func
tion replaces the string controlled by *this with a string of length
len + 1 whose first len elements are a copy of the original string and
whose remaining element is set according to val.
4 Otherwise, the function sets the element at position pos in the string
controlled by *this. If val is nonzero, the stored value is one, oth
erwise it is zero.
5 Returns *this.
23.1.2.14 bit_string::reset [lib.bit.string::reset]
bit_string& reset();
1 Resets all elements of the string controlled by *this.
2 Returns *this.
bit_string& reset(size_t pos);
3 Throws out_of_range if pos > len. Otherwise, if pos == len, the func
tion replaces the string controlled by *this with a string of length
len + 1 whose first len elements are a copy of the original string and
whose remaining element is zero. Otherwise, the function resets the
element at position pos in the string controlled by *this.
23.1.2.15 bit_string::toggle [lib.bit.string::toggle]
bit_string& toggle();
1 Toggles all elements of the string controlled by *this.
2 Returns *this.
bit_string& toggle(size_t pos);
3 Throws out_of_range if pos >= len. Otherwise, the function toggles
the element at position pos in *this.
23.1.2.16 bit_string::to_string [lib.bit.string::to.string]
string to_string() const;
1 Creates an object of type string and initializes it to a string of
length len characters. Each character is determined by the value of
its corresponding element in the string controlled by *this. Bit
value zero becomes the character 0, bit value one becomes the charac
ter 1.
2 Returns the created object.
23.1.2.17 bit_string::count [lib.bit.string::count]
size_t count() const;
1 Returns a count of the number of elements set in the string controlled
by *this.
23.1.2.18 bit_string::length [lib.bit.string::length]
size_t length() const;
1 Returns len.
23.1.2.19 bit_string::resize [lib.bit.string::resize]
size_t resize(size_t n, bool val = 0);
1 Throws length_error if n equals NPOS. Otherwise, the function alters
the length of the string controlled by *this as follows:
--If n <= len, the function replaces the string controlled by *this
with a string of length n whose elements are a copy of the initial
elements of the original string controlled by *this.
--If n > len, the function replaces the string controlled by *this
with a string of length n whose first len elements are a copy of the
original string controlled by *this, and whose remaining elements
all have the value one if val is nonzero, or zero otherwise.
2 Returns the previous value of len.
23.1.2.20 bit_string::trim [lib.bit.string::trim]
size_t trim();
1 Determines the highest position pos of an element with value one in
the string controlled by *this, if possible. If no such position
exists, the function replaces the string with an empty string (len is
zero). Otherwise, the function replaces the string with a string of
length pos + 1 whose elements are a copy of the initial elements of
the original string controlled by *this.
2 Returns the new value of len.
23.1.2.21 bit_string::find [lib.bit.string::find]
size_t find(bool val, size_t pos = 0, size_t n = NPOS) const;
1 Returns NPOS if pos >= len. Otherwise, the function determines the
effective length rlen of the string to be scanned as the smaller of n
and len - pos. The function then determines the lowest position xpos,
if possible, such that both of the following conditions obtain:
--pos <= xpos;
--The element at position xpos in the string controlled by *this is
one if val is nonzero, or zero otherwise.
2 Returns xpos if the function can determine such a value for xpos.
Otherwise, returns NPOS.
23.1.2.22 bit_string::rfind [lib.bit.string::rfind]
size_t rfind(bool val, size_t pos = 0, size_t n = NPOS) const;
1 Returns NPOS if pos >= len. Otherwise, the function determines the
effective length rlen of the string to be scanned as the smaller of n
and len - pos. The function then determines the highest position
xpos, if possible, such that both of the following conditions obtain:
--pos <= xpos;
--The element at position xpos in the string controlled by *this is
one if val is nonzero, or zero otherwise.
2 Returns xpos if the function can determine such a value for xpos.
Otherwise, returns NPOS.
23.1.2.23 bit_string::substr [lib.bit.string::substr]
bit_string substr(size_t pos, size_t n = NPOS) const;
1 Returns bit_string(*this, pos, n).
23.1.2.24 bit_string::operator== [lib.bit.string::op==.bs]
bool operator==(const bit_string& rhs) const;
1 Returns zero if len != rhs.len or if the value of any element of the
string controlled by *this differs from the value of the corresponding
element of the string controlled by rhs.
23.1.2.25 bit_string::operator!= [lib.bit.string::op!=.bs]
bool operator!=(const bit_string& rhs) const;
1 Returns a nonzero value if !(*this == rhs).
23.1.2.26 bit_string::test [lib.bit.string::test]
bool test(size_t pos) const;
1 Throws out_of_range if pos >= len. Otherwise, the function returns a
nonzero value if the element at position pos in the string controlled
by *this is one.
23.1.2.27 bit_string::any [lib.bit.string::any]
bool any() const;
1 Returns a nonzero value if any bit is set in the string controlled by
*this.
23.1.2.28 bit_string::none [lib.bit.string::none]
bool none() const;
1 Returns a nonzero value if no bit is set in the string controlled by
*this.
23.1.2.29 bit_string::operator<< [lib.bit.string::op.lsh]
bit_string operator<<(size_t pos) const;
1 Constructs an object x of class bit_string and initializes it with
*this.
2 Returns x <<= pos.
23.1.2.30 bit_string::operator>> [lib.bit.string::op.rsh]
bit_string operator>>(size_t pos) const;
1 Constructs an object x of class bit_string and initializes it with
*this.
2 Returns x >>= pos.
23.1.2.31 bit_string::operator~ [lib.bit.string::op~]
bit_string operator~() const;
1 Constructs an object x of class bit_string and initializes it with
*this.
2 Returns x.toggle().
23.1.2.32 operator+ [lib.op+.bs.bs]
bit_string operator+(const bit_string& lhs, const bit_string& rhs);
1 Constructs an object x of class bit_string and initializes it with
lhs.
2 Returns x += rhs.
23.1.2.33 operator& [lib.op&.bs.bs]
bit_string operator&(const bit_string& lhs, const bit_string& rhs);
1 Constructs an object x of class bit_string and initializes it with
lhs.
2 Returns x &= rhs.
23.1.2.34 operator| [lib.op|.bs.bs]
bit_string operator|(const bit_string& lhs, const bit_string& rhs);
1 Constructs an object x of class bit_string and initializes it with
lhs.
2 Returns x |= rhs.
23.1.2.35 operator^ [lib.op^.bs.bs]
bit_string operator^(const bit_string& lhs, const bit_string& rhs);
1 Constructs an object x of class bit_string and initializes it with
lhs.
2 Returns x ^= rhs.
23.1.2.36 operator>> [lib.ext.bs]
istream& operator>>(istream& is, bit_string& x);
1 A formatted input function, extracts up to NPOS - 1 (single-byte)
characters from is. The function behaves as if it stores these char
acters in a temporary object str of type string, then evaluates the
expression x = bit_string(str). Characters are extracted and stored
until any of the following occurs:
--NPOS - 1 characters have been extracted and stored;
--end-of-file occurs on the input sequence;
--the next character to read is neither 0 or 1 (in which case the
input character is not extracted).
2 If no characters are stored in str, the function calls
is.setstate(ios::failbit).
3 Returns is.
23.1.2.37 operator<< [lib.ins.bs]
ostream& operator<<(ostream& os, const bit_string& x);
1 Returns os << x.to_string().
23.1.3 Template class dyn_array [lib.template.dyn.array]
1 The header <dynarray> defines a template class and several related
functions for representing and manipulating varying-size sequences of
some object type T.
template<class T> class dyn_array {
public:
dyn_array();
dyn_array(size_t size, capacity cap);
dyn_array(const dyn_array<T>& arr);
dyn_array(const T& obj, size_t rep = 1);
dyn_array(const T* parr, size_t n);
dyn_array<T>& operator+=(const dyn_array<T>& rhs);
dyn_array<T>& operator+=(const T& obj);
dyn_array<T>& append(const T& obj, size_t rep = 1);
dyn_array<T>& append(const T* parr, size_t n = 1);
dyn_array<T>& assign(const T& obj, size_t rep = 1);
dyn_array<T>& assign(const T* parr, size_t n = 1);
dyn_array<T>& insert(size_t pos, const dyn_array<T>& arr);
dyn_array<T>& insert(size_t pos, const T& obj, size_t rep = 1);
dyn_array<T>& insert(size_t pos, const T* parr, size_t n = 1);
dyn_array<T>& remove(size_t pos = 0, size_t n = NPOS);
dyn_array<T>& sub_array(dyn_array<T>& arr, size_t pos,
size_t n = NPOS);
void swap(dyn_array<T>& arr);
const T& get_at(size_t pos) const;
void put_at(size_t pos, const T& obj);
T& operator[](size_t pos);
const T& operator[](size_t pos) const;
T* data();
const T* data() const;
size_t length() const;
void resize(size_t n);
void resize(size_t n, const T& obj);
size_t reserve() const;
void reserve(size_t res_arg);
private:
// T* ptr; exposition only
// size_t len, res; exposition only
};
2 The template class dyn_array<T> describes an object that can store a
sequence consisting of a varying number of objects of type T. The
first element of the sequence is at position zero. Such a sequence is
also called a dynamic array. An object of type T shall have:
--a default constructor T();
--a copy constructor T(const T&);
--an assignment operator T& operator=(const T&);
--a destructor ~T().
3 For the function signatures described in this subclause:
--it is unspecified whether an operation described in this subclause
as initializing an object of type T with a copy calls its copy con
structor, calls its default constructor followed by its assignment
operator, or does nothing to an object that is already properly ini
tialized;
--it is unspecified how many times objects of type T are copied, or
constructed and destroyed.4)
4 For the sake of exposition, the maintained data is presented here as:
--T *ptr, points to the sequence of objects;
--size_t len, counts the number of objects currently in the sequence;
--size_t res, for an unallocated sequence, holds the recommended allo
cation size of the sequence, while for an allocated sequence,
becomes the currently allocated size.
5 In all cases, len <= res.
6 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;
--a length error is associated with exceptions of type length_error.
--an out-of-range error is associated with exceptions of type
out_of_range;
23.1.3.1 dyn_array constructors [lib.cons.dyn.array]
dyn_array();
1 Constructs an object of class dyn_array<T>, initializing:
--ptr to an unspecified value;
--len to zero;
--res to an unspecified value.
dyn_array(size_t size, capacity cap);
_________________________
4) Objects that cannot tolerate this uncertainty, or that fail to meet
the stated requirements, can sometimes be organized into dynamic ar
rays through the intermediary of an object of class ptrdyn_array<T>.
2 Throws length_error if size equals NPOS and cap is default_size. Oth
erwise, the function constructs an object of class dyn_array<T>. If
cap is default_size, the function initializes:
--ptr to point at the first element of an allocated array of size ele
ments of type T, each initialized with the default constructor for
type T;
--len to size;
--res to a value at least as large as len.
3 Otherwise, cap shall be reserve and the function initializes:
--ptr to an unspecified value;
--len to zero;
--res to size.
dyn_array(const dyn_array<T>& arr);
4 Constructs an object of class dyn_array<T> and determines its initial
dynamic array value by copying the elements from the dynamic array
designated by arr. Thus, the function initializes:
--ptr to point at the first element of an allocated array of arr.len
elements of type T, each initialized with a copy of the correspond
ing element from the dynamic array designated by arr;
--len to arr.len;
--res to a value at least as large as len.
dyn_array(const T& obj, size_t rep = 1);
5 Throws length_error if rep equals NPOS. Otherwise, the function con
structs an object of class dyn_array<T> and determines its initial
dynamic array value by copying obj into all rep values. Thus, the
function initializes:
--ptr to point at the first element of an allocated array of rep ele
ments of type T, each initialized by copying obj;
--len to rep;
--res to a value at least as large as len.
dyn_array(const T* parr, size_t n);
6 Throws length_error if n equals NPOS. Otherwise, throws
invalid_argument if parr is a null pointer. Otherwise, parr shall
designate the first element of an array of at least n elements of type
T.
7 The function then constructs an object of class dyn_array<T> and
determines its initial dynamic array value by copying the elements
from the array designated by parr. Thus, the function initializes:
--ptr to point at the first element of an allocated array of n ele
ments of type T, each initialized with a copy of the corresponding
element from the array designated by parr;
--len to n;
--res to a value at least as large as len.
23.1.3.2 dyn_array::operator+= [lib.dyn.array::op+=]
dyn_array<T>& operator+=(const dyn_array<T>& rhs);
1 Throws length_error if len >= NPOS - rhs.len. Otherwise, the function
replaces the dynamic array designated by *this with a dynamic array of
length len + rhs.len whose first len elements are a copy of the origi
nal dynamic array designated by *this and whose remaining elements are
a copy of the elements of the dynamic array designated by rhs.
2 Returns *this.
dyn_array<T>& operator+=(const T& obj);
3 Returns append(obj).
23.1.3.3 dyn_array::append [lib.dyn.array::append]
dyn_array<T>& append(const T& obj, size_t rep = 1);
1 Throws length_error if len >= NPOS - rep. Otherwise, the function
replaces the dynamic array designated by *this with a dynamic array of
length len + rep whose first len elements are a copy of the original
dynamic array designated by *this and whose remaining elements are
each a copy of obj.
2 Returns *this.
dyn_array<T>& append(const T* parr, size_t n = 1);
3 Throws length_error if len >= NPOS - n. Otherwise, the function
throws invalid_argument if n > 0 and parr is a null pointer. Other
wise, parr shall designate the first element of an array of at least n
elements of type T.
4 The function then replaces the dynamic array designated by *this with
a dynamic array of length len + n whose first len elements are a copy
of the original dynamic array designated by *this and whose remaining
elements are a copy of the initial elements of the array designated by
parr.
5 Returns *this.
23.1.3.4 dyn_array::assign [lib.dyn.array::assign]
dyn_array<T>& assign(const T& obj, size_t rep = 1);
1 Throws length_error if rep == NPOS. Otherwise, the function replaces
the dynamic array designated by *this with a dynamic array of length
rep each of whose elements is a copy of obj.
2 Returns *this.
dyn_array<T>& assign(const T* parr, size_t n = 1);
3 Throws length_error if n == NPOS. Otherwise, the function throws
invalid_argument if n > 0 and parr is a null pointer.
4 Otherwise, parr shall designate the first element of an array of at
least n elements of type T.
5 The function then replaces the dynamic array designated by *this with
a dynamic array of length n whose elements are a copy of the initial
elements of the array designated by parr.
6 Returns *this.
23.1.3.5 dyn_array::insert [lib.dyn.array::insert]
dyn_array<T>& insert(size_t pos, const dyn_array<T>& arr);
1 Throws out_of_range if pos > len. Otherwise, the function throws
length_error if len >= NPOS - arr.len.
2 Otherwise, the function replaces the dynamic array designated by *this
with a dynamic array of length len + arr.len whose first pos elements
are a copy of the initial elements of the original dynamic array des
ignated by *this, whose next arr.len elements are a copy of the ini
tial elements of the dynamic array designated by arr, and whose
remaining elements are a copy of the remaining elements of the origi
nal dynamic array designated by *this.
3 Returns *this.
dyn_array<T>& insert(size_t pos, const T& obj, size_t rep = 1);
4 Throws out_of_range if pos > len. Otherwise, the function throws
length_error if len >= NPOS - rep.
5 Otherwise, the function replaces the dynamic array designated by *this
with a dynamic array of length len + rep whose first pos elements are
a copy of the initial elements of the original dynamic array desig
nated by *this, whose next rep elements are each a copy of obj, and
whose remaining elements are a copy of the remaining elements of the
original dynamic array designated by *this.
6 Returns *this.
dyn_array<T>& insert(size_t pos, const T* parr, size_t n = 1);
7 Throws out_of_range if pos > len. Otherwise, the function throws
length_error if len >= NPOS - n. Otherwise, the function throws
invalid_argument if n > 0 and parr is a null pointer. Otherwise, parr
shall designate the first element of an array of at least n elements
of type T.
8 The function then replaces the dynamic array designated by *this with
a dynamic array of length len + n whose first pos elements are a copy
of the initial elements of the original dynamic array designated by
*this, whose next n elements are a copy of the initial elements of the
array designated by parr, and whose remaining elements are a copy of
the remaining elements of the original dynamic array designated by
*this.
9 Returns *this.
23.1.3.6 dyn_array::remove [lib.dyn.array::remove]
dyn_array<T>& remove(size_t pos = 0, size_t n = NPOS);
1 Throws out_of_range if pos > len. Otherwise, the function determines
the effective length xlen of the sequence to be removed as the smaller
of n and len - pos.
2 The function then replaces the dynamic array designated by *this with
a dynamic array of length len - xlen whose first pos elements are a
copy of the initial elements of the original dynamic array designated
by *this, and whose remaining elements are a copy of the elements of
the original dynamic array designated by *this beginning at position
pos + xlen. The original xlen elements beginning at position pos are
destroyed.
3 Returns *this.
23.1.3.7 dyn_array::sub_array [lib.dyn.array::sub.array]
dyn_array<T>& sub_array(dyn_array<T>& arr, size_t pos, size_t n = NPOS);
1 Throws out_of_range if pos > len. Otherwise, the function determines
the effective length rlen of the dynamic array designated by *this as
the smaller of n and arr.len - pos.
2 The function then replaces the dynamic array designated by arr with a
dynamic array of length rlen whose elements are a copy of the elements
of the dynamic array designated by *this beginning at position pos.
3 Returns arr.
23.1.3.8 dyn_array::swap [lib.dyn.array::swap]
void swap(dyn_array<T>& arr);
1 Replaces the dynamic array designated by *this with the dynamic array
designated by arr, and replaces the dynamic array designated by arr
with the dynamic array originally designated by *this.5)
_________________________
5) Presumably, this operation occurs with no actual copying of array
elements.
23.1.3.9 dyn_array::get_at [lib.dyn.array::get.at]
const T& get_at(size_t pos) const;
1 Throws out_of_range if pos >= len. Otherwise, returns ptr[pos].
2 The reference returned is invalid after a subsequent call to any mem
ber function for the object.
23.1.3.10 dyn_array::put_at [lib.dyn.array::put.at]
void put_at(size_t pos, const T& obj);
1 Throws out_of_range if pos >= len. Otherwise, the function assigns
obj to the element at position pos in the dynamic array designated by
*this.
23.1.3.11 dyn_array::operator[] [lib.dyn.array::op.array]
T& operator[](size_t pos);
const T& operator[](size_t pos) const;
1 If pos < len, returns the element at position pos in the dynamic array
designated by *this. Otherwise, the behavior is undefined.
2 The reference returned is invalid after a subsequent call to any mem
ber function for the object.
23.1.3.12 dyn_array::data [lib.dyn.array::data]
T* data();
const T* data() const;
1 Returns ptr if len is nonzero, otherwise a null pointer. The program
shall not alter any of the values stored in the dynamic array. Nor
shall the program treat the returned value as a valid pointer value
after any subsequent call to a non-const member function of the class
dyn_array<T> that designates the same object as this.
23.1.3.13 dyn_array::length [lib.dyn.array::length]
size_t length() const;
1 Returns len.
23.1.3.14 dyn_array::resize [lib.dyn.array::resize]
void resize(size_t n);
1 Throws length_error if n equals NPOS. Otherwise, if n != len the
function alters the length of the dynamic array designated by *this as
follows:
--If n < len, the function replaces the dynamic array designated by
*this with a dynamic array of length n whose elements are a copy of
the initial elements of the original dynamic array designated by
*this. Any remaining elements are destroyed.
--If n > len, the function replaces the dynamic array designated by
*this with a dynamic array of length n whose first len elements are
a copy of the original dynamic array designated by *this, and whose
remaining elements are all initialized with the default constructor
for class T.
void resize(size_t n, const T& obj);
2 Throws length_error if n equals NPOS. Otherwise, if n != len the
function alters the length of the dynamic array designated by *this as
follows:
--If n < len, the function replaces the dynamic array designated by
*this with a dynamic array of length n whose elements are a copy of
the initial elements of the original dynamic array designated by
*this. Any remaining elements are destroyed.
--If n > len, the function replaces the dynamic array designated by
*this with a dynamic array of length n whose first len elements are
a copy of the original dynamic array designated by *this, and whose
remaining elements are all initialized by copying obj.
23.1.3.15 dyn_array::reserve [lib.dyn.array::reserve]
size_t reserve() const;
1 Returns res.
void reserve(size_t res_arg);
2 If no dynamic array is allocated, assigns res_arg to res. Otherwise,
whether or how the function alters res is unspecified.
23.1.3.16 operator+ [lib.op+.da.da]
dyn_array<T> operator+(const dyn_array<T>& lhs,
const dyn_array<T>& rhs);
1 Returns dyn_array<T>(lhs) += rhs.
dyn_array<T> operator+(const dyn_array<T>& lhs, const T& obj);
2 Returns dyn_array<T>(lhs) += rhs.
dyn_array<T> operator+(const T& obj, const dyn_array<T>& rhs);
3 Returns dyn_array<T>(lhs) += rhs.
23.1.4 Template class ptr_dyn_array [lib.template.ptr.dyn.array]
1 The header <ptrdynarray> defines a template and several related func
tions for representing and manipulating varying-size sequences of
pointers to some object type T.
template<class T> class ptr_dyn_array : public dyn_array<void*> {
public:
ptr_dyn_array();
ptr_dyn_array(size_t size, capacity cap);
ptr_dyn_array(const ptr_dyn_array<T>& arr);
ptr_dyn_array(T* obj, size_t rep = 1);
ptr_dyn_array(T** parr, size_t n = 1);
ptr_dyn_array<T>& operator+=(const ptr_dyn_array<T>& rhs);
ptr_dyn_array<T>& operator+=(T* obj);
ptr_dyn_array<T>& append(T* obj, size_t rep = 1);
ptr_dyn_array<T>& append(T** parr, size_t n = 1);
ptr_dyn_array<T>& assign(T* obj, size_t rep = 1);
ptr_dyn_array<T>& assign(T** parr, size_t n = 1);
ptr_dyn_array<T>& insert(size_t pos, const ptr_dyn_array<T>& arr);
ptr_dyn_array<T>& insert(size_t pos, T* obj, size_t rep = 1);
ptr_dyn_array<T>& insert(size_t pos, T** parr, size_t n = 1);
ptr_dyn_array<T>& remove(size_t pos = 0, size_t n = NPOS);
ptr_dyn_array<T>& sub_array(ptr_dyn_array<T>& arr, size_t pos,
size_t n = NPOS);
void swap(ptr_dyn_array<T>& arr);
T* get_at(size_t pos) const;
void put_at(size_t pos, T* obj);
T*& operator[](size_t pos);
T* const& operator[](size_t pos) const;
T** data();
const T** data() const;
size_t length() const;
void resize(size_t n);
void resize(size_t n, T* obj);
size_t reserve() const;
void reserve(size_t res_arg);
};
2 The template class ptr_dyn_array<T> describes an object that can store
a sequence consisting of a varying number of objects of type pointer
to T. Such a sequence is also called a dynamic pointer array. Objects
of type T are never created, destroyed, copied, assigned, or otherwise
accessed by the function signatures described in this subclause.
23.1.4.1 ptr_dyn_array constructors [lib.cons.ptr.dyn.array]
ptr_dyn_array();
1 Constructs an object of class ptr_dyn_array<T>, initializing the base
class with dyn_array<void*>().
ptr_dyn_array(size_t size, capacity cap);
2 Constructs an object of class ptr_dyn_array<T>, initializing the base
class with dyn_array<void*>(size, cap).
ptr_dyn_array(const ptr_dyn_array<T>& arr);
3 Constructs an object of class ptr_dyn_array<T>, initializing the base
class with dyn_array<void*>(arr).
ptr_dyn_array(T* obj, size_t rep = 1);
4 Constructs an object of class ptr_dyn_array<T>, initializing the base
class with dyn_array<void*>((void*)obj, rep).
ptr_dyn_array(const T** parr, size_t n);
5 Constructs an object of class ptr_dyn_array<T>, initializing the base
class with dyn_array<void*>((void**)parr, n).
23.1.4.2 ptr_dyn_array::operator+= [lib.ptr.dyn.array::op+=]
ptr_dyn_array<T>& operator+=(const ptr_dyn_array<T>& rhs);
1 Returns (ptr_dyn_array<T>&)dyn_array<void*>::operator+=((const
dyn_array<void*>&)rhs).
ptr_dyn_array<T>& operator+=(T* obj);
2 Returns (ptr_dyn_array<T>&)dyn_array<void*>:: operator+=((void*)obj).
23.1.4.3 ptr_dyn_array::append [lib.ptr.dyn.array::append]
ptr_dyn_array<T>& append(T* obj, size_t rep = 1);
1 Returns (ptr_dyn_array<T>&)dyn_array<void*>::append((void*)obj, rep).
ptr_dyn_array<T>& append(T** parr, size_t n = 1);
2 Returns (ptr_dyn_array<T>&)dyn_array<void*>::append((void**)parr, n).
23.1.4.4 ptr_dyn_array::assign [lib.ptr.dyn.array::assign]
ptr_dyn_array<T>& assign(T* obj, size_t rep = 1);
1 Returns (ptr_dyn_array<T>&)dyn_array<void*>::assign((void*)obj, rep).
ptr_dyn_array<T>& assign(T** parr, size_t n = 1);
2 Returns (ptr_dyn_array<T>&)dyn_array<void*>::assign((void**)parr, n).
23.1.4.5 ptr_dyn_array::insert [lib.ptr.dyn.array::insert]
ptr_dyn_array<T>& insert(size_t pos, const ptr_dyn_array<T>& arr);
1 Returns (ptr_dyn_array<T>&)dyn_array<void*>::insert(pos, (const
dyn_array<void*>&)arr).
ptr_dyn_array<T>& insert(size_t pos, T*obj, size_t rep = 1);
2 Returns (ptr_dyn_array<T>&)dyn_array<void*>::insert(pos, (void*)obj,
rep).
ptr_dyn_array<T>& insert(size_t pos, T**parr, size_t n = 1);
3 Returns (ptr_dyn_array<T>&)dyn_array<void*>::insert(pos, (void**)parr,
n).
23.1.4.6 ptr_dyn_array::remove [lib.ptr.dyn.array::remove]
ptr_dyn_array<T>& remove(size_t pos = 0, size_t n = NPOS);
1 Returns (ptr_dyn_array<T>&)dyn_array<void*>::remove(pos, n).
23.1.4.7 ptr_dyn_array::sub_array [lib.ptr.dyn.array::sub.array]
ptr_dyn_array<T>& sub_array(ptr_dyn_array<T>& arr, size_t pos,
size_t n = NPOS);
1 Returns (ptr_dyn_array<T>&)dyn_array<void*>::sub_array(arr, pos, n).
23.1.4.8 ptr_dyn_array::swap [lib.ptr.dyn.array::swap]
void swap(ptr_dyn_array<T>& arr);
1 Calls dyn_array<void*>::swap(arr).
23.1.4.9 ptr_dyn_array::get_at [lib.ptr.dyn.array::get.at]
T* get_at(size_t pos) const;
1 Returns (T*)dyn_array<void*>::get_at(pos).
23.1.4.10 ptr_dyn_array::put_at [lib.ptr.dyn.array::put.at]
void put_at(size_t pos, T* obj);
1 Calls dyn_array<void*>::put_at(pos, (void*)obj).
23.1.4.11 [lib.ptr.dyn.array::op.array]
ptr_dyn_array::operator[]
T*& operator[](size_t pos);
T* const& operator[](size_t pos) const;
1 Returns (T*&)dyn_array<void*>::operator[](pos).
23.1.4.12 ptr_dyn_array::data [lib.ptr.dyn.array::data]
T** data();
const T** data() const;
1 Returns (T*)dyn_array<void*>::data().
23.1.4.13 ptr_dyn_array::length [lib.ptr.dyn.array::length]
size_t length() const;
1 Returns dyn_array<void*>::length().
23.1.4.14 ptr_dyn_array::resize [lib.ptr.dyn.array::resize]
void resize(size_t n);
1 Calls dyn_array<void*>::resize(n).
void resize(size_t n, T* obj);
2 Calls dyn_array<void*>::resize(n, (void*)obj).
23.1.4.15 ptr_dyn_array::reserve [lib.ptr.dyn.array::reserve]
size_t reserve() const;
1 Returns dyn_array<void*>::reserve().
void reserve(size_t res_arg);
2 Returns dyn_array<void*>::reserve(res_arg).
23.1.4.16 operator+ [lib.op+.pda.pda]
ptr_dyn_array<T> operator+(const ptr_dyn_array<T>& lhs,
const ptr_dyn_array<T>& rhs);
1 Returns ptr_dyn_array<T><T>(lhs) += rhs).
ptr_dyn_array<T> operator+(const ptr_dyn_array<T>& lhs, T* obj);
2 Returns ptr_dyn_array<T><T>(lhs) += rhs).
ptr_dyn_array<T> operator+(T* obj, const ptr_dyn_array<T>& rhs);
3 Returns ptr_dyn_array<T><T>(lhs) += rhs).
23.1.5 Template class vector [lib.vector]
1 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.
template <class T, template <class U> class Allocator = allocator>
class vector {
public:
// typedefs:
typedef ? iterator;
typedef ? const_iterator;
typedef ? size_type;
typedef ? difference_type;
typedef T value_type;
// allocation/deallocation:
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);
void reserve(size_type n);
// accessors:
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;
T& operator[](size_type n);
const T& operator[](size_type n) const;
T& front();
const T& front() const;
T& back();
const T& back() const;
// insert/erase:
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.1.5.1 Typedefs [lib.vector.typedefs]
1 iterator is a random access iterator referring to T. The exact type
is implementation dependent and determined by Allocator.
2 const_iterator is a constant random access iterator referring to const
T. The exact type is implementation dependent and determined by Allo
cator. It is guaranteed that there is a constructor for
const_iterator out of iterator.
3 size_type is an unsigned integral type. The exact type is implementa
tion dependent and determined by Allocator.
4 difference_type is a signed integral type. The exact type is imple
mentation dependent and determined by Allocator.
23.1.5.2 Constructors [lib.vector.cons]
1 The constructor template <class InputIterator> vector(InputIterator
first, InputIterator last) makes only N calls to the copy constructor
of T (where N is the distance between first and last) and no realloca
tions if iterators first and last are of forward, bidirectional, or
random access categories. It does at most 2N calls to the copy con
structor 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.1.5.3 Member functions [lib.vector.members]
1 The member function capacity returns the size of the allocated storage
in the vector. The member function reserve is 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 insertions that happen after reserve takes
place till the time when the size of the vector reaches the size spec
ified by reserve.
2 insert causes reallocation if the new size is greater than the old
capacity. If no reallocation happens, all the iterators and refer
ences before the insertion point remain valid. 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 con
stant. Insertion of multiple elements 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. 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, bidirectional or ran
dom access category. Otherwise, it does insert elements one by one
and should not be used for inserting into the middle of vectors.
3 erase 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 vec
tor after the erased elements.
23.1.6 Class vector<bool> [lib.vector.bool]
1 To optimize space allocation, a specialization for bool is provided:
class vector<bool, allocator> {
public:
// bit reference:
class reference {
public:
~reference();
operator bool() const;
reference& operator=(const bool x);
void flip(); // flips the bit
};
// typedefs:
typedef ? iterator;
typedef ? const_iterator;
typedef size_t size_type;
typedef ptrdiff_t difference_type ;
typedef bool value_type;
// allocation/deallocation:
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);
// accessors:
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;
reference front();
const reference front() const;
reference back();
const reference back() const;
// insert/erase:
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>.
3 Every implementation is expected to provide specializations of vec
tor<bool> for all supported memory models.
+------- BEGIN BOX 1 -------+
At present, it is not possible to templatize a specialization. That
is, we cannot write:
template <template <class U> class Allocator = allocator>
class vector<bool, Allocator> { /* ... */ };
Therefore, only vector<bool, allocator> is provided.
+------- END BOX 1 -------+
23.1.7 Template class list [lib.list]
1 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 and deques, fast random access to list elements is not supported,
but many algorithms only need sequential access anyway.
template <class T, template <class U> class Allocator = allocator>
class list {
public:
// typedefs:
typedef ? iterator;
typedef ? const_iterator;
typedef ? size_type;
typedef ? difference_type;
typedef T value_type;
// allocation/deallocation:
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);
// accessors:
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& front();
const T& front() const;
T& back();
const T& back() const;
// insert/erase:
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 first, 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.1.7.1 Typedefs [lib.list.typedefs]
1 iterator is a bidirectional iterator referring to T. The exact type
is implementation dependent and determined by Allocator.
2 const_iterator is a constant bidirectional iterator referring to const
T. The exact type is implementation dependent and determined by Allo
cator. It is guaranteed that there is a constructor for
const_iterator out of iterator.
3 size_type is an unsigned integral type. The exact type is implementa
tion dependent and determined by Allocator.
4 difference_type is a signed integral type. The exact type is imple
mentation dependent and determined by Allocator.
23.1.7.2 Member functions [lib.list.members]
1 insert does not affect the validity of iterators and references.
Insertion of a single element into a list takes constant time and
exactly one call to the copy constructor of T. Insertion of multiple
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.
2 erase invalidates only the iterators and references to the erased ele
ments. 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 lin
ear 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.
3 Since lists allow fast insertion and erasing from the middle of a
list, certain operations are provided specifically for them:
4 list provides three splice operations that destructively move elements
from one list to another:
5 void splice(iterator position, list<T, Allocator>& x) inserts the con
tents of x before position and x becomes empty. It takes constant
time.
6 void splice(iterator position, list<T, Allocator>& x, iterator i)
inserts an element pointed to by i from list x before position and
removes the element from x. It takes constant time. i is a valid
iterator of x.
7 void splice(iterator position, list<T, Allocator>& x, iterator first,
iterator last) inserts elements in the range [first, last) before
position and removes the elements from x. It takes linear time.
[first, last) is a valid range in x.
8 remove erases all the elements in the list referred by the list itera
tor i for which the following conditions hold: *i == value, pred(*i)
== true. remove is stable, that is, the relative order of the ele
ments that are not removed is the same as their relative order in the
original list. Exactly size() applications of the corresponding pred
icate are done.
9 unique erases all but the first element from every consecutive group
of equal elements in the list. Exactly size() - 1 applications of the
corresponding binary predicate are done.
10merge merges the argument list into the list (both are assumed to be
sorted). The merge is stable, that is, 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. At most size() + x.size()
- 1 comparisons are done.
11reverse reverses the order of the elements in the list. It is linear
time.
12sort sorts the list according to the operator< or a compare function
object. It is stable, that is, the relative order of the equal ele
ments is preserved. Approximately NlogN comparisons are done where N
is equal to size().
23.1.8 Template class deque [lib.deque]
1 deque is a kind of sequence that, like a vector, supports 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. As with vectors, storage management is han
dled automatically.
template <class T, template <class U> class Allocator = allocator>
class deque {
public:
// typedefs:
typedef ? iterator;
typedef ? const_iterator;
typedef ? size_type;
typedef ? difference_type;
typedef T value_type;
// allocation/deallocation:
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);
// accessors:
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
size_type size() const;
size_type max_size() const;
bool empty() const;
T& operator[](size_type n);
const T& operator[](size_type n) const;
T& front();
const T& front() const;
T& back();
const T& back() const;
// insert/erase:
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.1.8.1 Typedefs [lib.deque.typedefs]
1 iterator is a random access iterator referring to T. The exact type
is implementation dependent and determined by Allocator.
2 const_iterator is a constant random access iterator referring to const
T. The exact type is implementation dependent and determined by Allo
cator. It is guaranteed that there is a constructor for
const_iterator out of iterator.
3 size_type is an unsigned integral type. The exact type is implementa
tion dependent and determined by Allocator.
4 difference_type is a signed integral type. The exact type is imple
mentation dependent and determined by Allocator.
23.1.8.2 Member functions [lib.deque.members]
1 insert 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. In the worst case, insert
ing 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 con
structor of T. That is, a deque is especially optimized for pushing
and popping elements at the beginning and end.
2 erase 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 destruc
tor is the same as the number of elements erased, but the number of
the calls to the assignment operator is equal to the minimum of the
number of elements before the erased elements and the number of ele
ment after the erased elements.
23.1.9 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, list and deque can
be used.
template <class Container>
class stack {
friend bool operator==(const stack<Container>& x, const stack<Container>& y);
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) {
return x.c == y.c;
}
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.
23.1.10 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 and
deque can be used.
template <class Container>
class queue {
friend bool operator==(const queue<Container>& x, const queue<Container>& y);
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) {
return x.c == y.c;
}
23.1.11 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 and deque can be used.
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()) : c(), comp(x) {}
template <class InputIterator>
priority_queue(InputIterator first, InputIterator last,
const Compare& x = Compare())
: c(first, last), comp(x) {
make_heap(c.begin(), c.end(), comp);
}
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) {
c.push_back(x);
push_heap(c.begin(), c.end(), comp);
}
void pop() {
pop_heap(c.begin(), c.end(), comp);
c.pop_back();
}
};
// no equality is provided
23.2 Associative containers [lib.associative]
23.2.1 Template class set [lib.set]
1 set is a kind of associative container that supports unique keys (con
tains at most one of each key value) and provides for fast retrieval
of the keys themselves.
template <class Key, class Compare = less<Key>,
template <class U> class Allocator = allocator>
class set {
public:
// typedefs:
typedef Key key_type;
typedef Key value_type;
typedef Compare key_compare;
typedef Compare value_compare;
typedef ? iterator;
typedef iterator const_iterator;
typedef ? size_type;
typedef ? difference_type;
// allocation/deallocation:
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);
// accessors:
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;
// insert/erase:
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.2.1.1 Typedefs [lib.set.typedefs]
1 iterator is a constant bidirectional iterator referring to const
value_type. The exact type is implementation dependent and determined
by Allocator.
2 const_iterator is the same type as iterator.
3 size_type is an unsigned integral type. The exact type is implementa
tion dependent and determined by Allocator.
4 difference_type is a signed integral type. The exact type is imple
mentation dependent and determined by Allocator.
23.2.2 Template class multiset [lib.multiset]
1 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.
template <class Key, class Compare = less<Key>,
template <class U> class Allocator = allocator>
class multiset {
public:
// typedefs:
typedef Key key_type;
typedef Key value_type;
typedef Compare key_compare;
typedef Compare value_compare;
typedef ? iterator;
typedef iterator const_iterator;
typedef ? size_type;
typedef ? difference_type;
// allocation/deallocation:
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);
// accessors:
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;
// insert/erase:
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);
23.2.2.1 Typedefs [lib.multiset.typedefs]
1 iterator is a constant bidirectional iterator referring to const
value_type. The exact type is implementation dependent and determined
by Allocator.
2 const_iterator is the same type as iterator.
3 size_type is an unsigned integral type. The exact type is implementa
tion dependent and determined by Allocator.
4 difference_type is a signed integral type. The exact type is imple
mentation dependent and determined by Allocator.
23.2.3 Template class map [lib.map]
1 map is a kind of associative container that supports unique keys (con
tains at most one of each key value) and provides for fast retrieval
of values of another type T based on the keys.
template <class Key, class T, class Compare = less<Key>,
template <class U> class Allocator = allocator>
class map {
public:
// typedefs:
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);
}
};
typedef ? iterator;
typedef ? const_iterator;
typedef ? size_type;
typedef ? difference_type;
// allocation/deallocation:
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);
// accessors:
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);
// insert/erase:
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.2.3.1 Typedefs [lib.map.typedefs]
1 iterator is a bidirectional iterator referring to value_type. The
exact type is implementation dependent and determined by Allocator.
2 const_iterator is the a constant bidirectional iterator referring to
const value_type. The exact type is implementation dependent and
determined by Allocator. It is guaranteed that there is a constructor
for const_iterator out of iterator.
3 size_type is an unsigned integral type. The exact type is implementa
tion dependent and determined by Allocator.
4 difference_type is a signed integral type. The exact type is imple
mentation dependent and determined by Allocator.
23.2.3.2 Member functions [lib.map.members]
1 In addition to the standard set of member functions of associative
containers, map provides T& operator[](const key_type&). For a map m
and key k, m[k] is semantically equivalent to
(*((m.insert(make_pair(k, T()))).first)).second.
23.2.4 Template class multimap [lib.multimap]
1 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.
template <class Key, class T, class Compare = less<Key>,
template <class U> class Allocator = allocator>
class multimap {
public:
// typedefs:
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);
}
};
typedef ? iterator;
typedef ? const_iterator;
typedef ? size_type;
typedef ? difference_type;
// allocation/deallocation:
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);
// accessors:
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;
// insert/erase:
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.2.4.1 Typedefs [lib.multimap.typedefs]
1 iterator is a bidirectional iterator referring to value_type. The
exact type is implementation dependent and determined by Allocator.
2 const_iterator is the a constant bidirectional iterator referring to
const value_type. The exact type is implementation dependent and
determined by Allocator. It is guaranteed that there is a constructor
for const_iterator out of iterator.
3 size_type is an unsigned integral type. The exact type is implementa
tion dependent and determined by Allocator.
4 difference_type is a signed integral type. The exact type is imple
mentation dependent and determined by Allocator.