ZeePedia

Standard Template Library C++:adjacent_find, copy_backward, lexicographical_compare

<< Standard C++ Library Header Files:bitset, conj, cos, showpoint, streampos
Appendix. Type Traits:Helper Class, Primary Type Categories, Binary Type Traits >>
img
..................................................................
Chapter 13. Standard Template Library C++
<algorithm>
adjacent_find (page 253) · binary_search (page 254) · copy (page 254) ·
copy_backward (page 254) · count (page 254) · count_if (page 255) · equal (page
255) · equal_range (page 255) · fill (page 255) · fill_n (page 256) · find (page 256) ·
find_end (page 256) · find_first_of (page 256) · find_if (page 257) · for_each (page
257) · generate (page 257) · generate_n (page 257) · includes (page 257) ·
inplace_merge (page 258) · iter_swap (page 258) · lexicographical_compare (page
258) · lower_bound (page 259) · make_heap (page 259) · max (page 259) ·
max_element (page 259) · merge (page 260) · min (page 260) · min_element (page
261) · mismatch (page 261) · next_permutation (page 261) · nth_element (page
262) · partial_sort (page 262) · partial_sort_copy (page 262) · partition (page 263) ·
pop_heap (page 263) · prev_permutation (page 263) · push_heap (page 264) ·
random_shuffle (page 264) · remove (page 264) · remove_copy (page 265) ·
remove_copy_if (page 265) · remove_if (page 265) · replace (page 266) ·
replace_copy (page 266) · replace_copy_if (page 266) · replace_if (page 266) ·
reverse (page 267) · reverse_copy (page 267) · rotate (page 267) · rotate_copy (page
267) · search (page 267) · search_n (page 268) · set_difference (page 268) ·
set_intersection (page 269) · set_symmetric_difference (page 269) · set_union
(page 270) · sort (page 270) · sort_heap (page 271) · stable_partition (page 271) ·
stable_sort (page 271) · swap (page 272) · swap_ranges (page 272) · transform
(page 272) · unique (page 272) · unique_copy (page 273) · upper_bound (page
namespace std {
template<class InIt, class Fun>
Fun for_each(InIt first, InIt last, Fun f);
template<class InIt, class T>
InIt find(InIt first, InIt last, const T& val);
template<class InIt, class Pred>
InIt find_if(InIt first, InIt last, Pred pr);
template<class FwdIt1, class FwdIt2>
FwdIt1 find_end(FwdIt1 first1, FwdIt1 last1,
FwdIt2 first2, FwdIt2 last2);
template<class FwdIt1, class FwdIt2, class Pred>
FwdIt1 find_end(FwdIt1 first1, FwdIt1 last1,
FwdIt2 first2, FwdIt2 last2, Pred pr);
template<class FwdIt1, class FwdIt2>
FwdIt1 find_first_of(FwdIt1 first1, FwdIt1 last1,
FwdIt2 first2, FwdIt2 last2);
template<class FwdIt1, class FwdIt2, class Pred>
FwdIt1 find_first_of(FwdIt1 first1, FwdIt1 last1,
FwdIt2 first2, FwdIt2 last2, Pred pr);
template<class FwdIt>
FwdIt adjacent_find(FwdIt first, FwdIt last);
template<class FwdIt, class Pred>
FwdIt adjacent_find(FwdIt first, FwdIt last, Pred pr);
template<class InIt, class T, class Dist>
typename iterator_traits<InIt>::difference_type
count(InIt first, InIt last,
const T& val);
template<class InIt, class Pred, class Dist>
typename iterator_traits<InIt>::difference_type
count_if(InIt first, InIt last,
Pred pr);
template<class InIt1, class InIt2>
pair<InIt1, InIt2> mismatch(InIt1 first, InIt1 last,
249
InIt2 x);
template<class InIt1, class InIt2, class Pred>
pair<InIt1, InIt2> mismatch(InIt1 first, InIt1 last,
InIt2 x, Pred pr);
template<class InIt1, class InIt2>
bool equal(InIt1 first, InIt1 last, InIt2 x);
template<class InIt1, class InIt2, class Pred>
bool equal(InIt1 first, InIt1 last, InIt2 x, Pred pr);
template<class FwdIt1, class FwdIt2>
FwdIt1 search(FwdIt1 first1, FwdIt1 last1,
FwdIt2 first2, FwdIt2 last2);
template<class FwdIt1, class FwdIt2, class Pred>
FwdIt1 search(FwdIt1 first1, FwdIt1 last1,
FwdIt2 first2, FwdIt2 last2, Pred pr);
template<class FwdIt, class Dist, class T>
FwdIt search_n(FwdIt first, FwdIt last,
Dist n, const T& val);
template<class FwdIt, class Dist, class T, class Pred>
FwdIt search_n(FwdIt first, FwdIt last,
Dist n, const T& val, Pred pr);
template<class InIt, class OutIt>
OutIt copy(InIt first, InIt last, OutIt x);
template<class BidIt1, class BidIt2>
BidIt2 copy_backward(BidIt1 first, BidIt1 last,
BidIt2 x);
template<class T>
void swap(T& x, T& y);
template<class FwdIt1, class FwdIt2>
FwdIt2 swap_ranges(FwdIt1 first, FwdIt1 last,
FwdIt2 x);
template<class FwdIt1, class FwdIt2>
void iter_swap(FwdIt1 x, FwdIt2 y);
template<class InIt, class OutIt, class Unop>
OutIt transform(InIt first, InIt last, OutIt x,
Unop uop);
template<class InIt1, class InIt2, class OutIt,
class Binop>
OutIt transform(InIt1 first1, InIt1 last1,
InIt2 first2, OutIt x, Binop bop);
template<class FwdIt, class T>
void replace(FwdIt first, FwdIt last,
const T& vold, const T& vnew);
template<class FwdIt, class Pred, class T>
void replace_if(FwdIt first, FwdIt last,
Pred pr, const T& val);
template<class InIt, class OutIt, class T>
OutIt replace_copy(InIt first, InIt last, OutIt x,
const T& vold, const T& vnew);
template<class InIt, class OutIt, class Pred, class T>
OutIt replace_copy_if(InIt first, InIt last, OutIt x,
Pred pr, const T& val);
template<class FwdIt, class T>
void fill(FwdIt first, FwdIt last, const T& x);
template<class OutIt, class Size, class T>
void fill_n(OutIt first, Size n, const T& x);
template<class FwdIt, class Gen>
void generate(FwdIt first, FwdIt last, Gen g);
template<class OutIt, class Pred, class Gen>
void generate_n(OutIt first, Dist n, Gen g);
template<class FwdIt, class T>
FwdIt remove(FwdIt first, FwdIt last, const T& val);
template<class FwdIt, class Pred>
FwdIt remove_if(FwdIt first, FwdIt last, Pred pr);
template<class InIt, class OutIt, class T>
OutIt remove_copy(InIt first, InIt last, OutIt x,
const T& val);
template<class InIt, class OutIt, class Pred>
250
Standard C++ Library
OutIt remove_copy_if(InIt first, InIt last, OutIt x,
Pred pr);
template<class FwdIt>
FwdIt unique(FwdIt first, FwdIt last);
template<class FwdIt, class Pred>
FwdIt unique(FwdIt first, FwdIt last, Pred pr);
template<class InIt, class OutIt>
OutIt unique_copy(InIt first, InIt last, OutIt x);
template<class InIt, class OutIt, class Pred>
OutIt unique_copy(InIt first, InIt last, OutIt x,
Pred pr);
template<class BidIt>
void reverse(BidIt first, BidIt last);
template<class BidIt, class OutIt>
OutIt reverse_copy(BidIt first, BidIt last, OutIt x);
template<class FwdIt>
void rotate(FwdIt first, FwdIt middle, FwdIt last);
template<class FwdIt, class OutIt>
OutIt rotate_copy(FwdIt first, FwdIt middle,
FwdIt last, OutIt x);
template<class RanIt>
void random_shuffle(RanIt first, RanIt last);
template<class RanIt, class Fun>
void random_shuffle(RanIt first, RanIt last, Fun& f);
template<class BidIt, class Pred>
BidIt partition(BidIt first, BidIt last, Pred pr);
template<class BidIt, class Pred>
BidIt stable_partition(BidIt first, BidIt last,
Pred pr);
template<class RanIt>
void sort(RanIt first, RanIt last);
template<class RanIt, class Pred>
void sort(RanIt first, RanIt last, Pred pr);
template<class BidIt>
void stable_sort(BidIt first, BidIt last);
template<class BidIt, class Pred>
void stable_sort(BidIt first, BidIt last, Pred pr);
template<class RanIt>
void partial_sort(RanIt first, RanIt middle,
RanIt last);
template<class RanIt, class Pred>
void partial_sort(RanIt first, RanIt middle,
RanIt last, Pred pr);
template<class InIt, class RanIt>
RanIt partial_sort_copy(InIt first1, InIt last1,
RanIt first2, RanIt last2);
template<class InIt, class RanIt, class Pred>
RanIt partial_sort_copy(InIt first1, InIt last1,
RanIt first2, RanIt last2, Pred pr);
template<class RanIt>
void nth_element(RanIt first, RanIt nth, RanIt last);
template<class RanIt, class Pred>
void nth_element(RanIt first, RanIt nth, RanIt last,
Pred pr);
template<class FwdIt, class T>
FwdIt lower_bound(FwdIt first, FwdIt last,
const T& val);
template<class FwdIt, class T, class Pred>
FwdIt lower_bound(FwdIt first, FwdIt last,
const T& val, Pred pr);
template<class FwdIt, class T>
FwdIt upper_bound(FwdIt first, FwdIt last,
const T& val);
template<class FwdIt, class T, class Pred>
FwdIt upper_bound(FwdIt first, FwdIt last,
const T& val, Pred pr);
template<class FwdIt, class T>
251
Chapter 13. Standard Template Library C++
pair<FwdIt, FwdIt> equal_range(FwdIt first,
FwdIt last, const T& val);
template<class FwdIt, class T, class Pred>
pair<FwdIt, FwdIt> equal_range(FwdIt first,
FwdIt last, const T& val, Pred pr);
template<class FwdIt, class T>
bool binary_search(FwdIt first, FwdIt last,
const T& val);
template<class FwdIt, class T, class Pred>
bool binary_search(FwdIt first, FwdIt last,
const T& val, Pred pr);
template<class InIt1, class InIt2, class OutIt>
OutIt merge(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2, OutIt x);
template<class InIt1, class InIt2, class OutIt,
class Pred>
OutIt merge(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2, OutIt x, Pred pr);
template<class BidIt>
void inplace_merge(BidIt first, BidIt middle,
BidIt last);
template<class BidIt, class Pred>
void inplace_merge(BidIt first, BidIt middle,
BidIt last, Pred pr);
template<class InIt1, class InIt2>
bool includes(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2);
template<class InIt1, class InIt2, class Pred>
bool includes(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2, Pred pr);
template<class InIt1, class InIt2, class OutIt>
OutIt set_union(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2, OutIt x);
template<class InIt1, class InIt2, class OutIt,
class Pred>
OutIt set_union(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2, OutIt x, Pred pr);
template<class InIt1, class InIt2, class OutIt>
OutIt set_intersection(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2, OutIt x);
template<class InIt1, class InIt2, class OutIt,
class Pred>
OutIt set_intersection(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2, OutIt x, Pred pr);
template<class InIt1, class InIt2, class OutIt>
OutIt set_difference(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2, OutIt x);
template<class InIt1, class InIt2, class OutIt,
class Pred>
OutIt set_difference(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2, OutIt x, Pred pr);
template<class InIt1, class InIt2, class OutIt>
OutIt set_symmetric_difference(InIt1 first1,
InIt1 last1, InIt2 first2, InIt2 last2, OutIt x);
template<class InIt1, class InIt2, class OutIt,
class Pred>
OutIt set_symmetric_difference(InIt1 first1,
InIt1 last1, InIt2 first2, InIt2 last2, OutIt x,
Pred pr);
template<class RanIt>
void push_heap(RanIt first, RanIt last);
template<class RanIt, class Pred>
void push_heap(RanIt first, RanIt last, Pred pr);
template<class RanIt>
void pop_heap(RanIt first, RanIt last);
template<class RanIt, class Pred>
void pop_heap(RanIt first, RanIt last, Pred pr);
252
Standard C++ Library
img
.......
template<class RanIt>
void make_heap(RanIt first, RanIt last);
template<class RanIt, class Pred>
void make_heap(RanIt first, RanIt last, Pred pr);
template<class RanIt>
void sort_heap(RanIt first, RanIt last);
template<class RanIt, class Pred>
void sort_heap(RanIt first, RanIt last, Pred pr);
template<class T>
const T& max(const T& x, const T& y);
template<class T, class Pred>
const T& max(const T& x, const T& y, Pred pr);
template<class T>
const T& min(const T& x, const T& y);
template<class T, class Pred>
const T& min(const T& x, const T& y, Pred pr);
template<class FwdIt>
FwdIt max_element(FwdIt first, FwdIt last);
template<class FwdIt, class Pred>
FwdIt max_element(FwdIt first, FwdIt last, Pred pr);
template<class FwdIt>
FwdIt min_element(FwdIt first, FwdIt last);
template<class FwdIt, class Pred>
FwdIt min_element(FwdIt first, FwdIt last, Pred pr);
template<class InIt1, class InIt2>
bool lexicographical_compare(InIt1 first1,
InIt1 last1, InIt2 first2, InIt2 last2);
template<class InIt1, class InIt2, class Pred>
bool lexicographical_compare(InIt1 first1,
InIt1 last1, InIt2 first2, InIt2 last2, Pred pr);
template<class BidIt>
bool next_permutation(BidIt first, BidIt last);
template<class BidIt, class Pred>
bool next_permutation(BidIt first, BidIt last,
Pred pr);
template<class BidIt>
bool prev_permutation(BidIt first, BidIt last);
template<class BidIt, class Pred>
bool prev_permutation(BidIt first, BidIt last,
Pred pr);
};
Include the STL (page 1) standard header <algorithm> to define numerous
template functions that perform useful algorithms. The descriptions that follow
make extensive use of common template parameter names (or prefixes) to indicate
the least powerful category of iterator permitted as an actual argument type:
v OutIt (page 37) -- to indicate an output iterator
v InIt (page 37) -- to indicate an input iterator
v FwdIt (page 37) -- to indicate a forward iterator
v BidIt (page 37) -- to indicate a bidirectional iterator
v RanIt (page 37) -- to indicate a random-access iterator
The descriptions of these templates employ a number of conventions (page 38)
common to all algorithms.
adjacent_find
template<class FwdIt>
FwdIt adjacent_find(FwdIt first, FwdIt last);
template<class FwdIt, class Pred>
FwdIt adjacent_find(FwdIt first, FwdIt last, Pred pr);
253
Chapter 13. Standard Template Library C++
img
...
The first template function determines the lowest N in the range [0, last - first)
for which N + 1 != last - first and the predicate *(first + N) == *(first + N
+ 1) is true. Here, operator== must impose an equivalence relationship (page 39)
between its operands. It then returns first + N. If no such value exists, the
function returns last. It evaluates the predicate exactly N + 1 times.
The second template function behaves the same, except that the predicate is
pr(*(first + N), *(first + N + 1)).
binary_search
template<class FwdIt, class T>
bool binary_search(FwdIt first, FwdIt last,
const T& val);
template<class FwdIt, class T, class Pred>
bool binary_search(FwdIt first, FwdIt last,
const T& val, Pred pr);
The first template function determines whether a value of N exists in the range [0,
last - first) for which *(first + N) has equivalent ordering (page 39) to val,
where the elements designated by iterators in the range [first, last) form a
sequence ordered by (page 39) operator<. If so, the function returns true. If no
such value exists, it returns false.
If FwdIt is a random-access iterator type, the function evaluates the ordering
predicate X < Y at most ceil(log(last - first)) + 2 times. Otherwise, the
function evaluates the predicate a number of times proportional to last - first.
The second template function behaves the same, except that it replaces
operator<(X, Y) with pr(X, Y).
copy
template<class InIt, class OutIt>
OutIt copy(InIt first, InIt last, OutIt x);
The template function evaluates *(x + N) = *(first + N)) once for each N in the
range [0, last - first), for strictly increasing values of N beginning with the
lowest value. It then returns x + N. If x and first designate regions of storage, x
must not be in the range [first, last).
copy_backward
template<class BidIt1, class BidIt2>
BidIt2 copy_backward(BidIt1 first, BidIt1 last,
BidIt2 x);
The template function evaluates *(x - N - 1) = *(last - N - 1)) once for each N
in the range [0, last - first), for strictly decreasing values of N beginning with
the highest value. It then returns x - (last - first). If x and first designate
regions of storage, x must not be in the range [first, last).
count
template<class InIt, class T>
typename iterator_traits<InIt>::difference_type
count(InIt first, InIt last, const T& val);
The template function sets a count n to zero. It then executes ++n for each N in the
range [0, last - first) for which the predicate *(first + N) == val is true.
254
Standard C++ Library
img
...
Here, operator== must impose an equivalence relationship (page 39) between its
operands. The function returns n. It evaluates the predicate exactly last - first
times.
count_if
template<class InIt, class Pred, class Dist>
typename iterator_traits<InIt>::difference_type
count_if(InIt first, InIt last,
Pred pr);
The template function sets a count n to zero. It then executes ++n for each N in the
range [0, last - first) for which the predicate pr(*(first + N)) is true. The
function returns n. It evaluates the predicate exactly last - first times.
equal
template<class InIt1, class
InIt2>
bool equal(InIt1 first,
InIt1 last, InIt2 x);
template<class InIt1, class
InIt2, class Pred>
bool equal(InIt1 first,
InIt1 last, InIt2 x, Pred pr);
The first template function returns true only if, for each N in the range [0, last1 -
first1), the predicate *(first1 + N) == *(first2 + N) is true. Here, operator==
must impose an equivalence relationship (page 39) between its operands. The
function evaluates the predicate at most once for each N.
The second template function behaves the same, except that the predicate is
pr(*(first1 + N), *(first2 + N)).
equal_range
template<class FwdIt, class T>
pair<FwdIt, FwdIt> equal_range(FwdIt first,
FwdIt last, const T& val);
template<class FwdIt, class T, class Pred>
pair<FwdIt, FwdIt> equal_range(FwdIt first,
FwdIt last, const T& val, Pred pr);
The first template function effectively returns pair( lower_bound(first, last,
val), upper_bound(first, last, val)), where the elements designated by
iterators in the range [first, last) form a sequence ordered by (page 39)
operator<. Thus, the function determines the largest range of positions over which
val can be inserted in the sequence and still preserve its ordering.
If FwdIt is a random-access iterator type, the function evaluates the ordering
predicate X < Y at most ceil(2 * log(last - first)) + 1. Otherwise, the function
evaluates the predicate a number of times proportional to last - first.
The second template function behaves the same, except that it replaces
operator<(X, Y) with pr(X, Y).
fill
template<class FwdIt, class T>
void fill(FwdIt first, FwdIt last, const T& x);
The template function evaluates *(first + N) = x once for each N in the range [0,
last - first).
255
Chapter 13. Standard Template Library C++
img
...
fill_n
template<class OutIt, class Size, class T>
void fill_n(OutIt first, Size n, const T& x);
The template function evaluates *(first + N) = x once for each N in the range [0,
n).
find
template<class InIt, class T>
InIt find(InIt first, InIt last, const T& val);
The template function determines the lowest value of N in the range [0, last -
first) for which the predicate *(first + N) == val is true. Here, operator== must
impose an equivalence relationship (page 39) between its operands. It then returns
first + N. If no such value exists, the function returns last. It evaluates the
predicate at most once for each N.
find_end
template<class FwdIt1, class FwdIt2>
FwdIt1 find_end(FwdIt1 first1, FwdIt1 last1,
FwdIt2 first2, FwdIt2 last2);
template<class FwdIt1, class FwdIt2, class Pred>
FwdIt1 find_end(FwdIt1 first1, FwdIt1 last1,
FwdIt2 first2, FwdIt2 last2, Pred pr);
The first template function determines the highest value of N in the range [0,
last1 - first1 - (last2 - first2)) such that for each M in the range [0, last2
- first2), the predicate *(first1 + N + M) == *(first2 + N + M) is true. Here,
operator== must impose an equivalence relationship (page 39) between its
operands. It then returns first1 + N. If no such value exists, the function returns
last1. It evaluates the predicate at most (last2 - first2) * (last1 - first1 -
(last2 - first2) + 1) times.
The second template function behaves the same, except that the predicate is
pr(*(first1 + N + M), *(first2 + N + M)).
find_first_of
template<class FwdIt1, class FwdIt2>
FwdIt1 find_first_of(FwdIt1 first1, FwdIt1 last1,
FwdIt2 first2, FwdIt2 last2);
template<class FwdIt1, class FwdIt2, class Pred>
FwdIt1 find_first_of(FwdIt1 first1, FwdIt1 last1,
FwdIt2 first2, FwdIt2 last2, Pred pr);
The first template function determines the lowest value of N in the range [0, last1
- first1) such that for some M in the range [0, last2 - first2), the predicate
*(first1 + N) == *(first2 + M) is true. Here, operator== must impose an
equivalence relationship (page 39) between its operands. It then returns first1 +
N. If no such value exists, the function returns last1. It evaluates the predicate at
most (last1 - first1) * (last2 - first2) times.
The second template function behaves the same, except that the predicate is
pr(*(first1 + N), *(first2 + M)).
256
Standard C++ Library
img
..
find_if
template<class InIt, class Pred>
InIt find_if(InIt first, InIt last, Pred pr);
The template function determines the lowest value of N in the range [0, last -
first) for which the predicate pred(*(first + N)) is true. It then returns first +
N. If no such value exists, the function returns last. It evaluates the predicate at
most once for each N.
for_each
template<class InIt, class Fun>
Fun for_each(InIt first, InIt last, Fun f);
The template function evaluates f(*(first + N)) once for each N in the range [0,
last - first). It then returns f.
generate
template<class FwdIt, class Gen>
void generate(FwdIt first, FwdIt last, Gen g);
The template function evaluates *(first + N) = g() once for each N in the range
[0, last - first).
generate_n
template<class OutIt, class Pred, class Gen>
void generate_n(OutIt first, Dist n, Gen g);
The template function evaluates *(first + N) = g() once for each N in the range
[0, n).
includes
template<class InIt1, class InIt2>
bool includes(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2);
template<class InIt1, class InIt2, class Pred>
bool includes(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2, Pred pr);
The first template function determines whether a value of N exists in the range [0,
last2 - first2) such that, for each M in the range [0, last1 - first1), *(first +
M) and *(first + N) do not have equivalent ordering (page 39), where the
elements designated by iterators in the ranges [first1, last1) and [first2,
last2) each form a sequence ordered by (page 39) operator<. If so, the function
returns false. If no such value exists, it returns true. Thus, the function determines
whether the ordered sequence designated by iterators in the range [first2,
last2) all have equivalent ordering with some element designated by iterators in
the range [first1, last1).
The function evaluates the predicate at most 2 * ((last1 - first1) + (last2 -
first2)) - 1 times.
The second template function behaves the same, except that it replaces
operator<(X, Y) with pr(X, Y).
257
Chapter 13. Standard Template Library C++
img
...
inplace_merge
template<class BidIt>
void inplace_merge(BidIt first, BidIt middle,
BidIt last);
template<class BidIt, class Pred>
void inplace_merge(BidIt first, BidIt middle,
BidIt last, Pred pr);
The first template function reorders the sequences designated by iterators in the
ranges [first, middle) and [middle, last), each ordered by (page 39) operator<,
to form a merged sequence of length last - first beginning at first also ordered
by operator<. The merge occurs without altering the relative order of elements
within either original sequence. Moreover, for any two elements from different
original sequences that have equivalent ordering (page 39), the element from the
ordered range [first, middle) precedes the other.
The function evaluates the ordering predicate X < Y at most ceil((last - first)
* log(last - first)) times. (Given enough temporary storage, it can evaluate the
predicate at most (last - first) - 1 times.)
The second template function behaves the same, except that it replaces
operator<(X, Y) with pr(X, Y).
iter_swap
template<class FwdIt1, class FwdIt2>
void iter_swap(FwdIt1 x, FwdIt2 y);
The template function leaves the value originally stored in *y subsequently stored
in *x, and the value originally stored in *x subsequently stored in *y.
lexicographical_compare
template<class InIt1, class InIt2>
bool lexicographical_compare(InIt1 first1,
InIt1 last1, InIt2 first2, InIt2 last2);
template<class InIt1, class InIt2, class Pred>
bool lexicographical_compare(InIt1 first1,
InIt1 last1, InIt2 first2, InIt2 last2, Pred pr);
The first template function determines K, the number of elements to compare as the
smaller of last1 - first1 and last2 - first2. It then determines the lowest value
of N in the range [0, K) for which *(first1 + N) and *(first2 + N) do not have
equivalent ordering (page 39). If no such value exists, the function returns true
only if K < (last2 - first2). Otherwise, it returns true only if *(first1 + N) <
*(first2 + N). Thus, the function returns true only if the sequence designated by
iterators in the range [first1, last1) is lexicographically less than the other
sequence.
The function evaluates the ordering predicate X < Y at most 2 * K times.
The second template function behaves the same, except that it replaces
operator<(X, Y) with pr(X, Y).
258
Standard C++ Library
img
..
lower_bound
template<class FwdIt, class T>
FwdIt lower_bound(FwdIt first, FwdIt last,
const T& val);
template<class FwdIt, class T, class Pred>
FwdIt lower_bound(FwdIt first, FwdIt last,
const T& val, Pred pr);
The first template function determines the highest value of N in the range (0, last
- first] such that, for each M in the range [0, N) the predicate *(first + M) <
val is true, where the elements designated by iterators in the range [first, last)
form a sequence ordered by (page 39) operator<. It then returns first + N. Thus,
the function determines the lowest position before which val can be inserted in the
sequence and still preserve its ordering.
If FwdIt is a random-access iterator type, the function evaluates the ordering
predicate X < Y at most ceil(log(last - first)) + 1 times. Otherwise, the
function evaluates the predicate a number of times proportional to last - first.
The second template function behaves the same, except that it replaces
operator<(X, Y) with pr(X, Y).
make_heap
template<class RanIt>
void make_heap(RanIt first, RanIt last);
template<class RanIt, class Pred>
void make_heap(RanIt first, RanIt last, Pred pr);
The first template function reorders the sequence designated by iterators in the
range [first, last) to form a heap ordered by (page 39) operator<.
The function evaluates the ordering predicate X < Y at most 3 * (last - first)
times.
The second template function behaves the same, except that it replaces
operator<(X, Y) with pr(X, Y).
max
template<class T>
const T& max(const T& x, const T& y);
template<class T, class Pred>
const T& max(const T& x, const T& y, Pred pr);
The first template function returns y if x < y. Otherwise it returns x. T need supply
only a single-argument constructor and a destructor.
The second template function behaves the same, except that it replaces
operator<(X, Y) with pr(X, Y).
max_element
template<class FwdIt>
FwdIt max_element(FwdIt first, FwdIt last);
template<class FwdIt, class Pred>
FwdIt max_element(FwdIt first, FwdIt last, Pred pr);
259
Chapter 13. Standard Template Library C++
img
..
The first template function determines the lowest value of N in the range [0, last
- first) such that, for each M in the range [0, last - first) the predicate
*(first + N) < *(first + M) is false. It then returns first + N. Thus, the function
determines the lowest position that contains the largest value in the sequence.
The function evaluates the ordering predicate X < Y exactly max((last - first) -
1, 0) times.
The second template function behaves the same, except that it replaces
operator<(X, Y) with pr(X, Y).
merge
template<class InIt1,
class InIt2, class OutIt>
OutIt merge(InIt1
first1, InIt1 last1,
InIt2 first2,
InIt2 last2, OutIt x);
template<class InIt1,
class InIt2, class OutIt,
class Pred>
OutIt merge(InIt1
first1, InIt1 last1,
InIt2 first2,
InIt2 last2, OutIt x, Pred pr);
The first template function determines K, the number of elements to copy as (last1
- first1) + (last2 - first2). It then alternately copies two sequences,
designated by iterators in the ranges [first1, last1) and [first2, last2) and
each ordered by (page 39) operator<, to form a merged sequence of length K
beginning at x, also ordered by operator<. The function then returns x + K.
The merge occurs without altering the relative order of elements within either
sequence. Moreover, for any two elements from different sequences that have
equivalent ordering (page 39), the element from the ordered range [first1,
last1) precedes the other. Thus, the function merges two ordered sequences to
form another ordered sequence.
If x and first1 designate regions of storage, the range [x, x + K) must not
overlap the range [first1, last1). If x and first2 designate regions of storage,
the range [x, x + K) must not overlap the range [first2, last2). The function
evaluates the ordering predicate X < Y at most K - 1 times.
The second template function behaves the same, except that it replaces
operator<(X, Y) with pr(X, Y).
min
template<class T>
const T& min(const T& x, const T& y);
template<class T, class Pred>
const T& min(const T& x, const T& y, Pred pr);
The first template function returns y if y < x. Otherwise it returns x. T need supply
only a single-argument constructor and a destructor.
The second template function behaves the same, except that it replaces
operator<(X, Y) with pr(X, Y).
260
Standard C++ Library
img
...
min_element
template<class FwdIt>
FwdIt min_element(FwdIt first, FwdIt last);
template<class FwdIt, class Pred>
FwdIt min_element(FwdIt first, FwdIt last, Pred pr);
The first template function determines the lowest value of N in the range [0, last
- first) such that, for each M in the range [0, last - first) the predicate
*(first + M) < *(first + N) is false. It then returns first + N. Thus, the function
determines the lowest position that contains the smallest value in the sequence.
The function evaluates the ordering predicate X < Y exactly max((last - first) -
1, 0) times.
The second template function behaves the same, except that it replaces
operator<(X, Y) with pr(X, Y).
mismatch
template<class InIt1, class InIt2>
pair<InIt1, InIt2> mismatch(InIt1 first, InIt1 last,
InIt2 x);
template<class InIt1, class InIt2, class Pred>
pair<InIt1, InIt2> mismatch(InIt1 first, InIt1 last,
InIt2 x, Pred pr);
The first template function determines the lowest value of N in the range [0, last1
- first1) for which the predicate !(*(first1 + N) == *(first2 + N)) is true.
Here, operator== must impose an equivalence relationship (page 39) between its
operands. It then returns pair(first1 + N, first2 + N). If no such value exists, N
has the value last1 - first1. The function evaluates the predicate at most once
for each N.
The second template function behaves the same, except that the predicate is
pr(*(first1 + N), *(first2 + N)).
next_permutation
template<class BidIt>
bool next_permutation(BidIt first, BidIt last);
template<class BidIt, class Pred>
bool next_permutation(BidIt first, BidIt last,
Pred pr);
The first template function determines a repeating sequence of permutations,
whose initial permutation occurs when the sequence designated by iterators in the
range [first, last) is ordered by (page 39) operator<. (The elements are sorted
in ascending order.) It then reorders the elements in the sequence, by evaluating
swap(X, Y) for the elements X and Y zero or more times, to form the next
permutation. The function returns true only if the resulting sequence is not the
initial permutation. Otherwise, the resultant sequence is the one next larger
lexicographically than the original sequence. No two elements may have equivalent
ordering (page 39).
The function evaluates swap(X, Y) at most (last - first) / 2.
The second template function behaves the same, except that it replaces
operator<(X, Y) with pr(X, Y).
261
Chapter 13. Standard Template Library C++
img
...
nth_element
template<class RanIt>
void nth_element(RanIt first, RanIt nth, RanIt last);
template<class RanIt, class Pred>
void nth_element(RanIt first, RanIt nth, RanIt last,
Pred pr);
The first template function reorders the sequence designated by iterators in the
range [first, last) such that for each N in the range [0, nth - first) and for
each M in the range [nth - first, last - first) the predicate !(*(first + M) <
*(first + N)) is true. Moreover, for N equal to nth - first and for each M in the
range (nth - first, last - first) the predicate !(*(first + M) < *(first +
N)) is true. Thus, if nth != last the element *nth is in its proper position if
elements of the entire sequence were sorted in ascending order, ordered by (page
39) operator<. Any elements before this one belong before it in the sort sequence,
and any elements after it belong after it.
The function evaluates the ordering predicate X < Y a number of times
proportional to last - first, on average.
The second template function behaves the same, except that it replaces
operator<(X, Y) with pr(X, Y).
partial_sort
template<class RanIt>
void partial_sort(RanIt first, RanIt middle,
RanIt last);
template<class RanIt, class Pred>
void partial_sort(RanIt first, RanIt middle,
RanIt last, Pred pr);
The first template function reorders the sequence designated by iterators in the
range [first, last) such that for each N in the range [0, middle - first) and
for each M in the range (N, last - first) the predicate !(*(first + M) < *(first
+ N)) is true. Thus, the smallest middle - first elements of the entire sequence
are sorted in ascending order, ordered by (page 39) operator<. The order of the
remaining elements is otherwise unspecified.
The function evaluates the ordering predicate X < Y at most ceil((last - first)
* log(middle - first)) times.
The second template function behaves the same, except that it replaces
operator<(X, Y) with pr(X, Y).
partial_sort_copy
template<class InIt, class RanIt>
RanIt partial_sort_copy(InIt first1, InIt last1,
RanIt first2, RanIt last2);
template<class InIt, class RanIt, class Pred>
RanIt partial_sort_copy(InIt first1, InIt last1,
RanIt first2, RanIt last2, Pred pr);
The first template function determines K, the number of elements to copy as the
smaller of last1 - first1 and last2 - first2. It then copies and reorders K of the
sequence designated by iterators in the range [first1, last1) such that the K
elements copied to first2 are ordered by (page 39) operator<. Moreover, for each
N in the range [0, K) and for each M in the range (0, last1 - first1)
262
Standard C++ Library
img
..
corresponding to an uncopied element, the predicate !(*(first2 + M) < *(first1
+ N)) is true. Thus, the smallest K elements of the entire sequence designated by
iterators in the range [first1, last1) are copied and sorted in ascending order to
the range [first2, first2 + K).
The function evaluates the ordering predicate X < Y at most ceil((last - first)
* log(K)) times.
The second template function behaves the same, except that it replaces
operator<(X, Y) with pr(X, Y).
partition
template<class BidIt, class Pred>
BidIt partition(BidIt first, BidIt last, Pred pr);
The template function reorders the sequence designated by iterators in the range
[first, last) and determines the value K such that for each N in the range [0, K)
the predicate pr(*(first + N)) is true, and for each N in the range [K, last -
first) the predicate pr(*(first + N)) is false. The function then returns first +
K.
The predicate must not alter its operand. The function evaluates pr(*(first + N))
exactly last - first times, and swaps at most (last - first) / 2 pairs of
elements.
pop_heap
template<class RanIt>
void pop_heap(RanIt first, RanIt last);
template<class RanIt, class Pred>
void pop_heap(RanIt first, RanIt last, Pred pr);
The first template function reorders the sequence designated by iterators in the
range [first, last) to form a new heap, ordered by (page 39) operator< and
designated by iterators in the range [first, last - 1), leaving the original
element at *first subsequently at *(last - 1). The original sequence must
designate an existing heap, also ordered by operator<. Thus, first != last must
be true and *(last - 1) is the element to remove from (pop off) the heap.
The function evaluates the ordering predicate X < Y at most ceil(2 * log(last -
first)) times.
The second template function behaves the same, except that it replaces
operator<(X, Y) with pr(X, Y).
prev_permutation
template<class BidIt>
bool prev_permutation(BidIt first, BidIt last);
template<class BidIt, class Pred>
bool prev_permutation(BidIt first, BidIt last,
Pred pr);
The first template function determines a repeating sequence of permutations,
whose initial permutation occurs when the sequence designated by iterators in the
range [first, last) is the reverse of one ordered by (page 39) operator<. (The
elements are sorted in descending order.) It then reorders the elements in the
sequence, by evaluating swap(X, Y) for the elements X and Y zero or more times, to
263
Chapter 13. Standard Template Library C++
img
.....
form the next permutation. The function returns true only if the resulting sequence
is not the initial permutation. Otherwise, the resultant sequence is the one next
smaller lexicographically than the original sequence. No two elements may have
equivalent ordering (page 39).
The function evaluates swap(X, Y) at most (last - first) / 2.
The second template function behaves the same, except that it replaces
operator<(X, Y) with pr(X, Y).
push_heap
template<class RanIt>
void push_heap(RanIt first, RanIt last);
template<class RanIt, class Pred>
void push_heap(RanIt first, RanIt last, Pred pr);
The first template function reorders the sequence designated by iterators in the
range [first, last) to form a new heap ordered by (page 39) operator<. Iterators
in the range [first, last - 1) must designate an existing heap, also ordered by
operator<. Thus, first != last must be true and *(last - 1) is the element to
add to (push on) the heap.
The function evaluates the ordering predicate X < Y at most ceil(log(last -
first)) times.
The second template function behaves the same, except that it replaces
operator<(X, Y) with pr(X, Y).
random_shuffle
template<class RanIt>
void random_shuffle(RanIt first, RanIt last);
template<class RanIt, class Fun>
void random_shuffle(RanIt first, RanIt last, Fun& f);
The first template function evaluates swap(*(first + N), *(first + M)) once for
each N in the range [1, last - first), where M is a value from some uniform
random distribution over the range [0, N). Thus, the function randomly shuffles
the order of elements in the sequence.
The second template function behaves the same, except that M is (Dist)f((Dist)N),
where Dist is a type convertible to iterator_traits (page 302):: difference_type (page
remove
template<class FwdIt, class T>
FwdIt remove(FwdIt first, FwdIt last, const T& val);
The template function effectively assigns first to X, then executes the statement:
if (!(*(first + N) == val))
*X++ = *(first + N);
once for each N in the range [0, last - first). Here, operator== must impose an
equivalence relationship (page 39) between its operands. It then returns X. Thus,
the function removes from the sequence all elements for which the predicate
264
Standard C++ Library
img
.
*(first + N) == val is true, without altering the relative order of remaining
elements, and returns the iterator value that designates the end of the revised
sequence.
remove_copy
template<class InIt, class OutIt, class T>
OutIt remove_copy(InIt first, InIt last, OutIt x,
const T& val);
The template function effectively executes the statement:
if (!(*(first + N) == val))
*x++ = *(first + N);
once for each N in the range [0, last - first). Here, operator== must impose an
equivalence relationship (page 39) between its operands. It then returns x. Thus,
the function removes from the sequence all elements for which the predicate
*(first + N) == val is true, without altering the relative order of remaining
elements, and returns the iterator value that designates the end of the revised
sequence.
If x and first designate regions of storage, the range [x, x + (last - first))
must not overlap the range [first, last).
remove_copy_if
template<class InIt, class OutIt, class Pred>
OutIt remove_copy_if(InIt first, InIt last, OutIt x,
Pred pr);
The template function effectively executes the statement:
if (!pr(*(first + N)))
*x++ = *(first + N);
once for each N in the range [0, last - first). It then returns x. Thus, the
function removes from the sequence all elements for which the predicate
pr(*(first + N)) is true, without altering the relative order of remaining elements,
and returns the iterator value that designates the end of the revised sequence.
If x and first designate regions of storage, the range [x, x + (last - first))
must not overlap the range [first, last).
remove_if
template<class FwdIt, class Pred>
FwdIt remove_if(FwdIt first, FwdIt last, Pred pr);
The template function effectively assigns first to X, then executes the statement:
if (!pr(*(first + N)))
*X++ = *(first + N);
once for each N in the range [0, last - first). It then returns X. Thus, the
function removes from the sequence all elements for which the predicate
pr(*(first + N)) is true, without altering the relative order of remaining elements,
and returns the iterator value that designates the end of the revised sequence.
265
Chapter 13. Standard Template Library C++
img
..
replace
template<caass FwdIt, class T>
void replace(FwdIt first, FwdIt last,
const T& vold, const T& vnew);
The template function executes the statement:
if (*(first + N) == vold)
*(first + N) = vnew;
once for each N in the range [0, last - first). Here, operator== must impose an
equivalence relationship (page 39) between its operands.
replace_copy
template<class InIt, class OutIt, class T>
OutIt replace_copy(InIt first, InIt last, OutIt x,
const T& vold, const T& vnew);
The template function executes the statement:
if (*(first + N) == vold)
*(x + N) = vnew;
else
*(x + N) = *(first + N)
once for each N in the range [0, last - first). Here, operator== must impose an
equivalence relationship (page 39) between its operands.
If x and first designate regions of storage, the range [x, x + (last - first))
must not overlap the range [first, last).
replace_copy_if
template<class InIt, class OutIt, class Pred, class T>
OutIt replace_copy_if(InIt first, InIt last, OutIt x,
Pred pr, const T& val);
The template function executes the statement:
if (pr(*(first + N)))
*(x + N) = val;
else
*(x + N) = *(first + N)
once for each N in the range [0, last - first).
If x and first designate regions of storage, the range [x, x + (last - first))
must not overlap the range [first, last).
replace_if
template<class FwdIt, class Pred, class T>
void replace_if(FwdIt first, FwdIt last,
Pred pr, const T& val);
The template function executes the statement:
if (pr(*(first + N)))
*(first + N) = val;
once for each N in the range [0, last - first).
266
Standard C++ Library
reverse
template<class BidIt>
void reverse(BidIt first, BidIt last);
The template function evaluates swap(*(first + N), *(last - 1 - N) once for
each N in the range [0, (last - first) / 2). Thus, the function reverses the order
of elements in the sequence.
reverse_copy
template<class BidIt, class OutIt>
OutIt reverse_copy(BidIt first, BidIt last, OutIt x);
The template function evaluates *(x + N) = *(last - 1 - N) once for each N in
the range [0, last - first). It then returns x + (last - first). Thus, the
function reverses the order of elements in the sequence that it copies.
If x and first designate regions of storage, the range [x, x + (last - first))
must not overlap the range [first, last).
rotate
template<class FwdIt>
void rotate(FwdIt first, FwdIt middle, FwdIt last);
The template function leaves the value originally stored in *(first + (N + (middle
- last)) % (last - first)) subsequently stored in *(first + N) for each N in the
range [0, last - first). Thus, if a ``left'' shift by one element leaves the element
originally stored in *(first + (N + 1) % (last - first)) subsequently stored in
*(first + N), then the function can be said to rotate the sequence either left by
middle - first elements or right by last - middle elements. Both [first,
middle) and [middle, last) must be valid ranges. The function swaps at most
last - first pairs of elements.
rotate_copy
template<class FwdIt, class OutIt>
OutIt rotate_copy(FwdIt first, FwdIt middle,
FwdIt last, OutIt x);
The template function evaluates *(x + N) = *(first + (N + (middle - first)) %
(last - first)) once for each N in the range [0, last - first). Thus, if a ``left''
shift by one element leaves the element originally stored in *(first + (N + 1) %
(last - first)) subsequently stored in *(first + N), then the function can be
said to rotate the sequence either left by middle - first elements or right by last
- middle elements as it copies. Both [first, middle) and [middle, last) must be
valid ranges.
If x and first designate regions of storage, the range [x, x + (last - first))
must not overlap the range [first, last).
search
template<class FwdIt1, class FwdIt2>
FwdIt1 search(FwdIt1 first1, FwdIt1 last1,
FwdIt2 first2, FwdIt2 last2);
template<class FwdIt1, class FwdIt2, class Pred>
FwdIt1 search(FwdIt1 first1, FwdIt1 last1,
FwdIt2 first2, FwdIt2 last2, Pred pr);
267
Chapter 13. Standard Template Library C++
img
....
The first template function determines the lowest value of N in the range [0,
(last1 - first1) - (last2 - first2)) such that for each M in the range [0,
last2 - first2), the predicate *(first1 + N + M) == *(first2 + M) is true. Here,
operator== must impose an equivalence relationship (page 39) between its
operands. It then returns first1 + N. If no such value exists, the function returns
last1. It evaluates the predicate at most (last2 - first2) * (last1 - first1)
times.
The second template function behaves the same, except that the predicate is
pr(*(first1 + N + M), *(first2 + M)).
search_n
template<class FwdIt, class Dist, class T>
FwdIt search_n(FwdIt first, FwdIt last,
Dist n, const T& val);
template<class FwdIt, class Dist, class T, class Pred>
FwdIt search_n(FwdIt first, FwdIt last,
Dist n, const T& val, Pred pr);
The first template function determines the lowest value of N in the range [0, (last
- first) - n) such that for each M in the range [0, n), the predicate *(first + N
+ M) == val is true. Here, operator== must impose an equivalence relationship
(page 39) between its operands. It then returns first + N. If no such value exists,
the function returns last. It evaluates the predicate at most n * (last - first)
times.
The second template function behaves the same, except that the predicate is
pr(*(first + N + M), val).
set_difference
template<class InIt1, class InIt2, class OutIt>
OutIt set_difference(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2, OutIt x);
template<class InIt1, class InIt2, class OutIt,
class Pred>
OutIt set_difference(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2, OutIt x, Pred pr);
The first template function alternately copies values from two sequences
designated by iterators in the ranges [first1, last1) and [first2, last2), both
ordered by (page 39) operator<, to form a merged sequence of length K beginning
at x, also ordered by operator<. The function then returns x + K.
The merge occurs without altering the relative order of elements within either
sequence. Moreover, for two elements from different sequences that have
equivalent ordering (page 39) that would otherwise be copied to adjacent elements,
the function copies only the element from the ordered range [first1, last1) and
skips the other. An element from one sequence that has equivalent ordering with
no element from the other sequence is copied from the ordered range [first1,
last1) and skipped from the other. Thus, the function merges two ordered
sequences to form another ordered sequence that is effectively the difference of
two sets.
If x and first1 designate regions of storage, the range [x, x + K) must not
overlap the range [first1, last1). If x and first2 designate regions of storage,
268
Standard C++ Library
img
....
the range [x, x + K) must not overlap the range [first2, last2). The function
evaluates the ordering predicate X < Y at most 2 * ((last1 - first1) + (last2 -
first2)) - 1 times.
The second template function behaves the same, except that it replaces
operator<(X, Y) with pr(X, Y).
set_intersection
template<class InIt1, class InIt2, class
OutIt>
OutIt set_intersection(InIt1 first1,
InIt1 last1,
InIt2 first2, InIt2 last2, OutIt
x);
template<class InIt1, class InIt2, class
OutIt,
class Pred>
OutIt set_intersection(InIt1 first1,
InIt1 last1,
InIt2 first2, InIt2 last2, OutIt
x, Pred pr);
The first template function alternately copies values from two sequences
designated by iterators in the ranges [first1, last1) and [first2, last2), both
ordered by (page 39) operator<, to form a merged sequence of length K beginning
at x, also ordered by operator<. The function then returns x + K.
The merge occurs without altering the relative order of elements within either
sequence. Moreover, for two elements from different sequences that have
equivalent ordering (page 39) that would otherwise be copied to adjacent elements,
the function copies only the element from the ordered range [first1, last1) and
skips the other. An element from one sequence that has equivalent ordering with
no element from the other sequence is also skipped. Thus, the function merges two
ordered sequences to form another ordered sequence that is effectively the
intersection of two sets.
If x and first1 designate regions of storage, the range [x, x + K) must not
overlap the range [first1, last1). If x and first2 designate regions of storage,
the range [x, x + K) must not overlap the range [first2, last2). The function
evaluates the ordering predicate X < Y at most 2 * ((last1 - first1) + (last2 -
first2)) - 1 times.
The second template function behaves the same, except that it replaces
operator<(X, Y) with pr(X, Y).
set_symmetric_difference
template<class InIt1, class InIt2, class
OutIt>
OutIt set_symmetric_difference(InIt1
first1,
InIt1 last1, InIt2 first2, InIt2
last2, OutIt x);
template<class InIt1, class InIt2, class
OutIt,
class Pred>
OutIt set_symmetric_difference(InIt1
first1,
InIt1 last1, InIt2 first2, InIt2
last2, OutIt x,
Pred pr);
The first template function alternately copies values from two sequences
designated by iterators in the ranges [first1, last1) and [first2, last2), both
ordered by (page 39) operator<, to form a merged sequence of length K beginning
at x, also ordered by operator<. The function then returns x + K.
The merge occurs without altering the relative order of elements within either
sequence. Moreover, for two elements from different sequences that have
equivalent ordering (page 39) that would otherwise be copied to adjacent elements,
269
Chapter 13. Standard Template Library C++
img
...
the function copies neither element. An element from one sequence that has
equivalent ordering with no element from the other sequence is copied. Thus, the
function merges two ordered sequences to form another ordered sequence that is
effectively the symmetric difference of two sets.
If x and first1 designate regions of storage, the range [x, x + K) must not
overlap the range [first1, last1). If x and first2 designate regions of storage,
the range [x, x + K) must not overlap the range [first2, last2). The function
evaluates the ordering predicate X < Y at most 2 * ((last1 - first1) + (last2 -
first2)) - 1 times.
The second template function behaves the same, except that it replaces
operator<(X, Y) with pr(X, Y).
set_union
template<class InIt1, class InIt2, class OutIt>
OutIt set_union(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2, OutIt x);
template<class InIt1, class InIt2, class OutIt,
class Pred>
OutIt set_union(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2, OutIt x, Pred pr);
The first template function alternately copies values from two sequences
designated by iterators in the ranges [first1, last1) and [first2, last2), both
ordered by (page 39) operator<, to form a merged sequence of length K beginning
at x, also ordered by operator<. The function then returns x + K.
The merge occurs without altering the relative order of elements within either
sequence. Moreover, for two elements from different sequences that have
equivalent ordering (page 39) that would otherwise be copied to adjacent elements,
the function copies only the element from the ordered range [first1, last1) and
skips the other. Thus, the function merges two ordered sequences to form another
ordered sequence that is effectively the union of two sets.
If x and first1 designate regions of storage, the range [x, x + K) must not
overlap the range [first1, last1). If x and first2 designate regions of storage,
the range [x, x + K) must not overlap the range [first2, last2). The function
evaluates the ordering predicate X < Y at most 2 * ((last1 - first1) + (last2 -
first2)) - 1 times.
The second template function behaves the same, except that it replaces
operator<(X, Y) with pr(X, Y).
sort
template<class RanIt>
void sort(RanIt first, RanIt last);
template<class RanIt, class Pred>
void sort(RanIt first, RanIt last, Pred pr);
The first template function reorders the sequence designated by iterators in the
range [first, last) to form a sequence ordered by (page 39) operator<. Thus, the
elements are sorted in ascending order.
The function evaluates the ordering predicate X < Y at most ceil((last - first)
* log(last - first)) times.
270
Standard C++ Library
img
....
The second template function behaves the same, except that it replaces
operator<(X, Y) with pr(X, Y).
sort_heap
template<class RanIt>
void sort_heap(RanIt first, RanIt last);
template<class RanIt, class Pred>
void sort_heap(RanIt first, RanIt last, Pred pr);
The first template function reorders the sequence designated by iterators in the
range [first, last) to form a sequence that is ordered by (page 39) operator<.
The original sequence must designate a heap, also ordered by (page 39) operator<.
Thus, the elements are sorted in ascending order.
The function evaluates the ordering predicate X < Y at most ceil((last - first)
* log(last - first)) times.
The second template function behaves the same, except that it replaces
operator<(X, Y) with pr(X, Y).
stable_partition
template<class BidIt, class Pred>
BidIt stable_partition(BidIt first, BidIt last,
Pred pr);
The template function reorders the sequence designated by iterators in the range
[first, last) and determines the value K such that for each N in the range [0, K)
the predicate pr(*(first + N)) is true, and for each N in the range [K, last -
first) the predicate pr(*(first + N)) is false. It does so without altering the
relative order of either the elements designated by indexes in the range [0, K) or
the elements designated by indexes in the range [K, last - first). The function
then returns first + K.
The predicate must not alter its operand. The function evaluates pr(*(first + N))
exactly last - first times, and swaps at most ceil((last - first) * log(last -
first)) pairs of elements. (Given enough temporary storage, it can replace the
swaps with at most 2 * (last - first) assignments.)
stable_sort
template<class BidIt>
void stable_sort(BidIt first, BidIt last);
template<class BidIt, class Pred>
void stable_sort(BidIt first, BidIt last, Pred pr);
The first template function reorders the sequence designated by iterators in the
range [first, last) to form a sequence ordered by (page 39) operator<. It does so
without altering the relative order of elements that have equivalent ordering (page
39). Thus, the elements are sorted in ascending order.
The function evaluates the ordering predicate X < Y at most ceil((last - first)
* (log(last - first))^2) times. (Given enough temporary storage, it can evaluate
the predicate at most ceil((last - first) * log(last - first)) times.)
The second template function behaves the same, except that it replaces
operator<(X, Y) with pr(X, Y).
271
Chapter 13. Standard Template Library C++
img
.
swap
template<class T>
void swap(T& x, T& y);
The template function leaves the value originally stored in y subsequently stored in
x, and the value originally stored in x subsequently stored in y.
swap_ranges
template<class FwdIt1, class FwdIt2>
FwdIt2 swap_ranges(FwdIt1 first, FwdIt1 last,
FwdIt2 x);
The template function evaluates swap(*(first + N), *(x + N)) once for each N in
the range [0, last - first). It then returns x + (last - first). If x and first
designate regions of storage, the range [x, x + (last - first)) must not overlap
the range [first, last).
transform
template<class InIt, class OutIt, class Unop>
OutIt transform(InIt first, InIt last, OutIt x,
Unop uop);
template<class InIt1, class InIt2, class OutIt,
class Binop>
OutIt transform(InIt1 first1, InIt1 last1,
InIt2 first2, OutIt x, Binop bop);
The first template function evaluates *(x + N) = uop(*(first + N)) once for each
N in the range [0, last - first). It then returns x + (last - first). The call
uop(*(first + N)) must not alter *(first + N).
The second template function evaluates *(x + N) = bop(*(first1 + N), *(first2
+ N)) once for each N in the range [0, last1 - first1). It then returns x + (last1
- first1). The call bop(*(first1 + N), *(first2 + N)) must not alter either
*(first1 + N) or *(first2 + N).
unique
template<class FwdIt>
FwdIt unique(FwdIt first, FwdIt last);
template<class FwdIt, class Pred>
FwdIt unique(FwdIt first, FwdIt last, Pred pr);
The first template function effectively assigns first to X, then executes the
statement:
if (N == 0 || !(*(first + N) == V))
V = *(first + N), *X++ = V;
once for each N in the range [0, last - first). It then returns X. Thus, the
function repeatedly removes from the sequence the second of a pair of elements for
which the predicate *(first + N) == *(first + N - 1) is true, until only the first
of a sequence of equal elements survives. Here, operator== must impose an
equivalence relationship (page 39) between its operands. It does so without
altering the relative order of remaining elements, and returns the iterator value
that designates the end of the revised sequence. The function evaluates the
predicate at most last - first times.
272
Standard C++ Library
img
..
The second template function behaves the same, except that it executes the
statement:
if (N == 0 || !pr(*(first + N), V))
V = *(first + N), *X++ = V;
unique_copy
template<class InIt, class
OutIt>
OutIt unique_copy(InIt
first, InIt last, OutIt x);
template<class InIt, class
OutIt, class Pred>
OutIt unique_copy(InIt
first, InIt last, OutIt x,
Pred pr);
The first template function effectively executes the statement:
if (N == 0 || !(*(first + N) == V))
V = *(first + N), *x++ = V;
once for each N in the range [0, last - first). It then returns x. Thus, the
function repeatedly removes from the sequence it copies the second of a pair of
elements for which the predicate *(first + N) == *(first + N - 1) is true, until
only the first of a sequence of equal elements survives. Here, operator== must
impose an equivalence relationship (page 39) between its operands. It does so
without altering the relative order of remaining elements, and returns the iterator
value that designates the end of the copied sequence.
If x and first designate regions of storage, the range [x, x + (last - first))
must not overlap the range [first, last).
The second template function behaves the same, except that it executes the
statement:
if (N == 0 || !pr(*(first + N), V))
V = *(first + N), *x++ = V;
upper_bound
template<class FwdIt, class T>
FwdIt upper_bound(FwdIt first, FwdIt last,
const T& val);
template<class FwdIt, class T, class Pred>
FwdIt upper_bound(FwdIt first, FwdIt last,
const T& val, Pred pr);
The first template function determines the highest value of N in the range (0, last
- first] such that, for each M in the range [0, N) the predicate !(val < *(first +
M)) is true, where the elements designated by iterators in the range [first, last)
form a sequence ordered by (page 39) operator<. It then returns first + N. Thus,
the function determines the highest position before which val can be inserted in
the sequence and still preserve its ordering.
If FwdIt is a random-access iterator type, the function evaluates the ordering
predicate X < Y at most ceil(log(last - first)) + 1 times. Otherwise, the
function evaluates the predicate a number of times proportional to last - first.
The second template function behaves the same, except that it replaces
operator<(X, Y) with pr(X, Y).
273
Chapter 13. Standard Template Library C++
img
.....................................
<deque>
namespace std {
template<class T, class A>
class deque;
// TEMPLATE FUNCTIONS
template<class T, class A>
bool operator==(
const deque<T, A>& lhs,
const deque<T, A>& rhs);
template<class T, class A>
bool operator!=(
const deque<T, A>& lhs,
const deque<T, A>& rhs);
template<class T, class A>
bool operator<(
const deque<T, A>& lhs,
const deque<T, A>& rhs);
template<class T, class A>
bool operator>(
const deque<T, A>& lhs,
const deque<T, A>& rhs);
template<class T, class A>
bool operator<=(
const deque<T, A>& lhs,
const deque<T, A>& rhs);
template<class T, class A>
bool operator>=(
const deque<T, A>& lhs,
const deque<T, A>& rhs);
template<class T, class A>
void swap(
deque<T, A>& lhs,
deque<T, A>& rhs);
};
Include the STL (page 1) standard header <deque> to define the container (page 41)
template class deque and several supporting templates.
deque
allocator_type (page 276) · assign (page 276) · at (page 276) · back (page 276) ·
begin (page 276) · clear (page 277) · const_iterator (page 277) · const_pointer (page
277) · const_reference (page 277) · const_reverse_iterator (page 277) · deque (page
277) · difference_type (page 277) · empty (page 278) · end (page 278) · erase (page
278) · front (page 278) · get_allocator (page 278) · insert (page 278) · iterator (page
279) · max_size (page 279) · operator[] (page 279) · pointer (page 279) · pop_back
(page 279) · pop_front (page 280) · push_back (page 280) · push_front (page 280) ·
rbegin (page 280) · reference (page 280) · rend (page 280) · resize (page 280) ·
reverse_iterator (page 281) · size (page 281) · size_type (page 281) · swap (page
281) · value_type (page 281)
template<class T, class A = allocator<T> >
class deque {
public:
typedef A allocator_type;
typedef typename A::pointer pointer;
typedef typename A::const_pointer const_pointer;
typedef typename A::reference reference;
typedef typename A::const_reference const_reference;
typedef typename A::value_type value_type;
typedef T0 iterator;
typedef T1 const_iterator;
typedef T2 size_type;
274
Standard C++ Library
img
..
typedef T3 difference_type;
typedef reverse_iterator<const_iterator>
const_reverse_iterator;
typedef reverse_iterator<iterator>
reverse_iterator;
deque();
explicit deque(const A& al);
explicit deque(size_type n);
deque(size_type n, const T& v);
deque(size_type n, const T& v,
const A& al);
deque(const deque& x);
template<class InIt>
deque(InIt first, InIt last);
template<class InIt>
deque(InIt first, InIt last, const A& al);
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
reverse_iterator rend();
const_reverse_iterator rend() const;
void resize(size_type n);
void resize(size_type n, T x);
size_type size() const;
size_type max_size() const;
bool empty() const;
A get_allocator() const;
reference at(size_type pos);
const_reference at(size_type pos) const;
reference operator[](size_type pos);
const_reference operator[](size_type pos);
reference front();
const_reference front() const;
reference back();
const_reference back() const;
void push_front(const T& x);
void pop_front();
void push_back(const T& x);
void pop_back();
template<class InIt>
void assign(InIt first, InIt last);
void assign(size_type n, const T& x);
iterator insert(iterator it, const T& x);
void insert(iterator it, size_type n, const T& x);
template<class InIt>
void insert(iterator it, InIt first, InIt last);
iterator erase(iterator it);
iterator erase(iterator first, iterator last);
void clear();
void swap(deque& x);
};
The template class describes an object that controls a varying-length sequence of
elements of type T. The sequence is represented in a way that permits insertion
and removal of an element at either end with a single element copy (constant
time). Such operations in the middle of the sequence require element copies and
assignments proportional to the number of elements in the sequence (linear time).
The object allocates and frees storage for the sequence it controls through a stored
allocator object (page 337) of class A. Such an allocator object must have the same
external interface as an object of template class allocator (page 337). Note that the
stored allocator object is not copied when the container object is assigned.
275
Chapter 13. Standard Template Library C++
Deque reallocation occurs when a member function must insert or erase elements
of the controlled sequence:
v If an element is inserted into an empty sequence, or if an element is erased to
leave an empty sequence, then iterators earlier returned by begin() and end()
become invalid.
v If an element is inserted at first(), then all iterators but no references, that
designate existing elements become invalid.
v If an element is inserted at end(), then end() and all iterators, but no references,
that designate existing elements become invalid.
v If an element is erased at first(), only that iterator and references to the erased
element become invalid.
v If an element is erased at last() - 1, only that iterator, last(), and references to
the erased element become invalid.
v Otherwise, inserting or erasing an element invalidates all iterators and
references.
deque::allocator_type
typedef A allocator_type;
The type is a synonym for the template parameter A.
deque::assign
template<class InIt>
void assign(InIt first, InIt last);
void assign(size_type n, const T& x);
If InIt is an integer type, the first member function behaves the same as
assign((size_type)first, (T)last). Otherwise, the first member function replaces
the sequence controlled by *this with the sequence [first, last), which must not
overlap the initial controlled sequence. The second member function replaces the
sequence controlled by *this with a repetition of n elements of value x.
deque::at
const_reference at(size_type pos) const;
reference at(size_type pos);
The member function returns a reference to the element of the controlled sequence
at position pos. If that position is invalid, the function throws an object of class
out_of_range.
deque::back
reference back();
const_reference back() const;
The member function returns a reference to the last element of the controlled
sequence, which must be non-empty.
deque::begin
const_iterator begin() const;
iterator begin();
The member function returns a random-access iterator that points at the first
element of the sequence (or just beyond the end of an empty sequence).
276
Standard C++ Library
img
.
deque::clear
void clear();
The member function calls erase( begin(), end()).
deque::const_iterator
typedef T1 const_iterator;
The type describes an object that can serve as a constant random-access iterator for
the controlled sequence. It is described here as a synonym for the
implementation-defined type T1.
deque::const_pointer
typedef typename A::const_pointer const_pointer;
The type describes an object that can serve as a constant pointer to an element of
the controlled sequence.
deque::const_reference
typedef typename A::const_reference const_reference;
The type describes an object that can serve as a constant reference to an element of
the controlled sequence.
deque::const_reverse_iterator
typedef reverse_iterator<const_iterator>
const_reverse_iterator;
The type describes an object that can serve as a constant reverse random-access
iterator for the controlled sequence.
deque::deque
deque();
explicit deque(const A& al);
explicit deque(size_type n);
deque(size_type n, const T& v);
deque(size_type n, const T& v,
const A& al);
deque(const deque& x);
template<class InIt>
deque(InIt first, InIt last);
template<class InIt>
deque(InIt first, InIt last, const A& al);
All constructors store an allocator object (page 337) and initialize the controlled
sequence. The allocator object is the argument al, if present. For the copy
constructor, it is x.get_allocator(). Otherwise, it is A().
The first two constructors specify an empty initial controlled sequence. The third
constructor specifies a repetition of n elements of value T(). The fourth and fifth
constructors specify a repetition of n elements of value x. The sixth constructor
specifies a copy of the sequence controlled by x. If InIt is an integer type, the last
two constructors specify a repetition of (size_type)first elements of value
(T)last. Otherwise, the last two constructors specify the sequence [first, last).
deque::difference_type
typedef T3 difference_type;
277
Chapter 13. Standard Template Library C++
img
..
The signed integer type describes an object that can represent the difference
between the addresses of any two elements in the controlled sequence. It is
described here as a synonym for the implementation-defined type T3.
deque::empty
bool empty() const;
The member function returns true for an empty controlled sequence.
deque::end
const_iterator end() const;
iterator end();
The member function returns a random-access iterator that points just beyond the
end of the sequence.
deque::erase
iterator erase(iterator it);
iterator erase(iterator first, iterator last);
The first member function removes the element of the controlled sequence pointed
to by it. The second member function removes the elements of the controlled
sequence in the range [first, last). Both return an iterator that designates the
first element remaining beyond any elements removed, or end() if no such element
exists.
Removing N elements causes N destructor calls and an assignment for each of the
elements between the insertion point and the nearer end of the sequence.
Removing an element at either end invalidates (page 279) only iterators and
references that designate the erased elements. Otherwise, erasing an element
invalidates all iterators and references.
The member functions never throw an exception.
deque::front
reference front();
const_reference front() const;
The member function returns a reference to the first element of the controlled
sequence, which must be non-empty.
deque::get_allocator
A get_allocator() const;
The member function returns the stored allocator object (page 337).
deque::insert
iterator insert(iterator it, const T& x);
void insert(iterator it, size_type n, const T& x);
template<class InIt>
void insert(iterator it, InIt first, InIt last);
Each of the member functions inserts, before the element pointed to by it in the
controlled sequence, a sequence specified by the remaining operands. The first
member function inserts a single element with value x and returns an iterator that
points to the newly inserted element. The second member function inserts a
repetition of n elements of value x.
278
Standard C++ Library
img
..
If InIt is an integer type, the last member function behaves the same as
insert(it, (size_type)first, (T)last). Otherwise, the last member function
inserts the sequence [first, last), which must not overlap the initial controlled
sequence.
When inserting a single element, the number of element copies is linear in the
number of elements between the insertion point and the nearer end of the
sequence. When inserting a single element at either end of the sequence, the
amortized number of element copies is constant. When inserting N elements, the
number of element copies is linear in N plus the number of elements between the
insertion point and the nearer end of the sequence -- except when the template
member is specialized for InIt an input or forward iterator, which behaves like N
single insertions. Inserting an element at either end invalidates (page 276) all
iterators, but no references, that designate existing elements. Otherwise, inserting
an element invalidates all iterators and references.
If an exception is thrown during the insertion of a single element, the container is
left unaltered and the exception is rethrown. If an exception is thrown during the
insertion of multiple elements, and the exception is not thrown while copying an
element, the container is left unaltered and the exception is rethrown.
deque::iterator
typedef T0 iterator;
The type describes an object that can serve as a random-access iterator for the
controlled sequence. It is described here as a synonym for the
implementation-defined type T0.
deque::max_size
size_type max_size() const;
The member function returns the length of the longest sequence that the object can
control.
deque::operator[]
const_reference operator[](size_type pos) const;
reference operator[](size_type pos);
The member function returns a reference to the element of the controlled sequence
at position pos. If that position is invalid, the behavior is undefined.
deque::pointer
typedef typename A::pointer pointer;
The type describes an object that can serve as a pointer to an element of the
controlled sequence.
deque::pop_back
void pop_back();
The member function removes the last element of the controlled sequence, which
must be non-empty. Removing the element invalidates (page 276) only iterators
and references that designate the erased element.
The member function never throws an exception.
279
Chapter 13. Standard Template Library C++
img
...
deque::pop_front
void pop_front();
The member function removes the first element of the controlled sequence, which
must be non-empty. Removing the element invalidates (page 276) only iterators
and references that designate the erased element.
The member function never throws an exception.
deque::push_back
void push_back(const T& x);
The member function inserts an element with value x at the end of the controlled
sequence. Inserting the element invalidates (page 276) all iterators, but no
references, to existing elements.
If an exception is thrown, the container is left unaltered and the exception is
rethrown.
deque::push_front
void push_front(const T& x);
The member function inserts an element with value x at the beginning of the
controlled sequence. Inserting the element invalidates (page 276) all iterators, but
no references, to existing elements.
If an exception is thrown, the container is left unaltered and the exception is
rethrown.
deque::rbegin
const_reverse_iterator rbegin() const;
reverse_iterator rbegin();
The member function returns a reverse iterator that points just beyond the end of
the controlled sequence. Hence, it designates the beginning of the reverse
sequence.
deque::reference
typedef typename A::reference reference;
The type describes an object that can serve as a reference to an element of the
controlled sequence.
deque::rend
const_reverse_iterator rend() const;
reverse_iterator rend();
The member function returns a reverse iterator that points at the first element of
the sequence (or just beyond the end of an empty sequence). Hence, it designates
the end of the reverse sequence.
deque::resize
void resize(size_type n);
void resize(size_type n, T x);
The member functions both ensure that size() henceforth returns n. If it must
make the controlled sequence longer, the first member function appends elements
280
Standard C++ Library
img
.
with value T(), while the second member function appends elements with value x.
To make the controlled sequence shorter, both member functions call
erase(begin() + n, end()).
deque::reverse_iterator
typedef reverse_iterator<iterator>
reverse_iterator;
The type describes an object that can serve as a reverse random-access iterator for
the controlled sequence.
deque::size
size_type size() const;
The member function returns the length of the controlled sequence.
deque::size_type
typedef T2 size_type;
The unsigned integer type describes an object that can represent the length of any
controlled sequence. It is described here as a synonym for the
implementation-defined type T2.
deque::swap
void swap(deque& x);
The member function swaps the controlled sequences between *this and x. If
get_allocator() == x.get_allocator(), it does so in constant time, it throws no
exceptions, and it invalidates no references, pointers, or iterators that designate
elements in the two controlled sequences. Otherwise, it performs a number of
element assignments and constructor calls proportional to the number of elements
in the two controlled sequences.
deque::value_type
typedef typename A::value_type value_type;
The type is a synonym for the template parameter T.
operator!=
template<class T, class A>
bool operator!=(
const deque <T, A>& lhs,
const deque <T, A>& rhs);
The template function returns !(lhs == rhs).
operator==
template<class T, class A>
bool operator==(
const deque <T, A>& lhs,
const deque <T, A>& rhs);
The template function overloads operator== to compare two objects of template
class deque (page 274). The function returns lhs.size() == rhs.size() &&
equal(lhs. begin(), lhs. end(), rhs.begin()).
281
Chapter 13. Standard Template Library C++
img
...........................
operator<
template<class T, class A>
bool operator<(
const deque <T, A>& lhs,
const deque <T, A>& rhs);
The template function overloads operator< to compare two objects of template
class deque. The function returns lexicographical_compare(lhs. begin(), lhs.
end(), rhs.begin(), rhs.end()).
operator<=
template<class T, class A>
bool operator<=(
const deque <T, A>& lhs,
const deque <T, A>& rhs);
The template function returns !(rhs < lhs).
operator>
template<class T, class A>
bool operator>(
const deque <T, A>& lhs,
const deque <T, A>& rhs);
The template function returns rhs < lhs.
operator>=
template<class T, class A>
bool operator>=(
const deque <T, A>& lhs,
const deque <T, A>& rhs);
The template function returns !(lhs < rhs).
swap
template<class T, class A>
void swap(
deque <T, A>& lhs,
deque <T, A>& rhs);
The template function executes lhs.swap (page 281)(rhs).
Portions derived from work copyright © 1994 by Hewlett-Packard Company. All rights
reserved.
<functional>
binary_function (page 285) · binary_negate (page 285) · binder1st (page 286) ·
binder2nd (page 286) · const_mem_fun_t (page 286) · const_mem_fun_ref_t (page
287) · const_mem_fun1_t (page 287) · const_mem_fun1_ref_t (page 287) · divides
(page 287) · equal_to (page 287) · greater (page 288) · greater_equal (page 288) ·
hash (page 288) · less (page 288) · less_equal (page 288) · logical_and (page 288) ·
logical_not (page 289) · logical_or (page 289) · mem_fun_t (page 289) ·
mem_fun_ref_t (page 290) · mem_fun1_t (page 290) · mem_fun1_ref_t (page 290) ·
minus (page 290) · modulus (page 290) · multiplies (page 290) · negate (page 291)
282
Standard C++ Library
img
.............
· not_equal_to (page 291) · plus (page 291) · pointer_to_binary_function (page
291) · pointer_to_unary_function (page 291) · unary_function (page 292) ·
unary_negate (page 292)
bind1st (page 285) · bind2nd (page 285) · mem_fun (page 289) · mem_fun_ref
(page 289) · not1 (page 291) · not2 (page 291) · ptr_fun (page 292)
namespace std {
template<class Arg, class Result>
struct unary_function;
template<class Arg1, class Arg2, class Result>
struct binary_function;
template<class T>
struct plus;
template<class T>
struct minus;
template<class T>
struct multiplies;
template<class T>
struct divides;
template<class T>
struct modulus;
template<class T>
struct negate;
template<class T>
struct equal_to;
template<class T>
struct not_equal_to;
template<class T>
struct greater;
template<class T>
struct less;
template<class T>
struct greater_equal;
template<class T>
struct less_equal;
template<class T>
struct logical_and;
template<class T>
struct logical_or;
template<class T>
struct logical_not;
template<class Pred>
struct unary_negate;
template<class Pred>
struct binary_negate;
template<class Pred>
class binder1st;
template<class Pred>
class binder2nd;
template<class Arg, class Result>
class pointer_to_unary_function;
template<class Arg1, class Arg2, class Result>
class pointer_to_binary_function;
template<class R, class T>
struct mem_fun_t;
template<class R, class T, class A>
struct mem_fun1_t;
template<class R, class T>
struct const_mem_fun_t;
template<class R, class T, class A>
struct const_mem_fun1_t;
template<class R, class T>
struct mem_fun_ref_t;
template<class R, class T, class A>
struct mem_fun1_ref_t;
template<class R, class T>
283
Chapter 13. Standard Template Library C++
struct const_mem_fun_ref_t;
template<class R, class T, class A>
struct const_mem_fun1_ref_t;
// TEMPLATE FUNCTIONS
template<class Pred>
unary_negate<Pred> not1(const Pred& pr);
template<class Pred>
binary_negate<Pred> not2(const Pred& pr);
template<class Pred, class T>
binder1st<Pred> bind1st(const Pred& pr, const T& x);
template<class Pred, class T>
binder2nd<Pred> bind2nd(const Pred& pr, const T& x);
template<class Arg, class Result>
pointer_to_unary_function<Arg, Result>
ptr_fun(Result (*)(Arg));
template<class Arg1, class Arg2, class Result>
pointer_to_binary_function<Arg1, Arg2, Result>
ptr_fun(Result (*)(Arg1, Arg2));
template<class R, class T>
mem_fun_t<R, T> mem_fun(R (T::*pm)());
template<class R, class T, class A>
mem_fun1_t<R, T, A> mem_fun(R (T::*pm)(A arg));
template<class R, class T>
const_mem_fun_t<R, T> mem_fun(R (T::*pm)() const);
template<class R, class T, class A>
const_mem_fun1_t<R, T, A> mem_fun(R (T::*pm)(A arg) const);
template<class R, class T>
mem_fun_ref_t<R, T> mem_fun_ref(R (T::*pm)());
template<class R, class T, class A>
mem_fun1_ref_t<R, T, A>
mem_fun_ref(R (T::*pm)(A arg));
template<class R, class T>
const_mem_fun_ref_t<R, T> mem_fun_ref(R (T::*pm)() const);
template<class R, class T, class A>
const_mem_fun1_ref_t<R, T, A>
mem_fun_ref(R (T::*pm)(A arg) const);
}
#ifdef _VACPP_TR1
namespace tr1 {
template <class _Ty>
struct hash;
template
<> struct hash<bool>;
template
<> struct hash<char>;
template
<> struct hash<signed char>;
template
<> struct hash<unsigned char>;
template
<> struct hash<wchar_t>;
template
<> struct hash<short>;
template
<> struct hash<unsigned short>;
template
<> struct hash<int>;
template
<> struct hash<unsigned int>;
template
<> struct hash<long>;
template
<> struct hash<unsigned long>;
template
<> struct hash<long long>;
template
<> struct hash<unsigned long long>;
template
<> struct hash<float>;
template
<> struct hash<double>;
template
<> struct hash<long double>;
template
<class _T> struct hash<_T *>;
template <class _CharT, class _Traits, class _Alloc>
struct hash<basic_string<_CharT, _Traits, _Alloc> >;
284
Standard C++ Library
img
..
}
#endif /* def _VACPP_TR1 */
Include the STL (page 1) standard header <functional> to define several templates
that help construct function objects, objects of a type that defines operator(). A
function object can thus be a function pointer, but in the more general case the
object can store additional information that can be used during a function call.
binary_function
template<class Arg1, class Arg2, class Result>
struct binary_function {
typedef Arg1 first_argument_type;
typedef Arg2 second_argument_type;
typedef Result result_type;
};
The template class serves as a base for classes that define a member function of the
form:
result_type operator()(const first_argument_type&,
const second_argument_type&) const
Hence, all such binary functions can refer to their first argument type as
first_argument_type, their second argument type as second_argument_type, and
their return type as result_type.
binary_negate
template<class Pred>
class binary_negate
: public binary_function<
typename Pred::first_argument_type,
typename Pred::second_argument_type, bool> {
public:
explicit binary_negate(const Pred& pr);
bool operator()(
const typename Pred::first_argument_type& x,
const typename Pred::second_argument_type& y) const;
};
The template class stores a copy of pr, which must be a binary function (page 285)
object. It defines its member function operator() as returning !pr(x, y).
bind1st
template<class Pred, class T>
binder1st<Pred> bind1st(const Pred& pr, const T& x);
The function returns binder1st<Pred>(pr, typename
Pred::first_argument_type(x)).
bind2nd
template<class Pred, class T>
binder2nd<Pred> bind2nd(const Pred& pr, const T& y);
The function returns binder2nd<Pred>(pr, typename
Pred::second_argument_type(y)).
285
Chapter 13. Standard Template Library C++
img
..
binder1st
template<class Pred>
class binder1st
: public unary_function<
typename Pred::second_argument_type,
typename Pred::result_type> {
public:
typedef typename Pred::second_argument_type argument_type;
typedef typename Pred::result_type result_type;
binder1st(const Pred& pr,
const typename Pred::first_argument_type& x);
result_type operator()(const argument_type& y) const;
protected:
Pred op;
typename Pred::first_argument_type value;
};
The template class stores a copy of pr, which must be a binary function (page 285)
object, in op, and a copy of x in value. It defines its member function operator()
as returning op(value, y).
binder2nd
template<class Pred>
class binder2nd
: public unary_function<
typename Pred::first_argument_type,
typename Pred::result_type> {
public:
typedef typename Pred::first_argument_type argument_type;
typedef typename Pred::result_type result_type;
binder2nd(const Pred& pr,
const typename Pred::second_argument_type& y);
result_type operator()(const argument_type& x) const;
protected:
Pred op;
typename Pred::second_argument_type value;
};
The template class stores a copy of pr, which must be a binary function (page 285)
object, in op, and a copy of y in value. It defines its member function operator()
as returning op(x, value).
const_mem_fun_t
template<class R, class T>
struct const_mem_fun_t
: public unary_function<T *, R> {
explicit const_mem_fun_t(R (T::*pm)() const);
R operator()(const T *p) const;
};
The template class stores a copy of pm, which must be a pointer to a member
function of class T, in a private member object. It defines its member function
operator() as returning (p->*pm)() const.
286
Standard C++ Library
const_mem_fun_ref_t
template<class R, class T>
struct const_mem_fun_ref_t
: public unary_function<T, R> {
explicit const_mem_fun_t(R (T::*pm)() const);
R operator()(const T& x) const;
};
The template class stores a copy of pm, which must be a pointer to a member
function of class T, in a private member object. It defines its member function
operator() as returning (x.*Pm)() const.
const_mem_fun1_t
template<class R, class T, class A>
struct const_mem_fun1_t
: public binary_function<T *, A, R> {
explicit const_mem_fun1_t(R (T::*pm)(A) const);
R operator()(const T *p, A arg) const;
};
The template class stores a copy of pm, which must be a pointer to a member
function of class T, in a private member object. It defines its member function
operator() as returning (p->*pm)(arg) const.
const_mem_fun1_ref_t
template<class R, class T, class A>
struct const_mem_fun1_ref_t
: public binary_function<T, A, R> {
explicit const_mem_fun1_ref_t(R (T::*pm)(A) const);
R operator()(const T& x, A arg) const;
};
The template class stores a copy of pm, which must be a pointer to a member
function of class T, in a private member object. It defines its member function
operator() as returning (x.*pm)(arg) const.
divides
template<class T>
struct divides : public binary_function<T, T, T> {
T operator()(const T& x, const T& y) const;
};
The template class defines its member function as returning x / y.
equal_to
template<class T>
struct equal_to
: public binary_function<T, T, bool> {
bool operator()(const T& x, const T& y) const;
};
The template class defines its member function as returning x == y.
287
Chapter 13. Standard Template Library C++
img
....
greater
template<class T>
struct greater : public binary_function<T, T, bool> {
bool operator()(const T& x, const T& y) const;
};
The template class defines its member function as returning x > y. The member
function defines a total ordering (page 401), even if T is an object pointer type.
greater_equal
template<class T>
struct greater_equal
: public binary_function<T, T, bool> {
bool operator()(const T& x, const T& y) const;
};
The template class defines its member function as returning x >= y. The member
function defines a total ordering (page 401), even if T is an object pointer type.
hash
namespace tr1 {
template <class T>
struct hash : public std::unary_function<T, std::size_t>
{
std::size_t operator()(T val) const;
};
}
The template class is used as the default hash function by the hashed associative
containers. Its member function operator() returns an unspecified value, but equal
arguments yield the same result.
less
template<class T>
struct less : public binary_function<T, T, bool> {
bool operator()(const T& x, const T& y) const;
};
The template class defines its member function as returning x < y. The member
function defines a total ordering (page 401), even if T is an object pointer type.
less_equal
template<class T>
struct less_equal
: public binary_function<T, T, bool> {
bool operator()(const T& x, const T& y) const;
};
The template class defines its member function as returning x <= y. The member
function defines a total ordering (page 401), even if T is an object pointer type.
logical_and
template<class T>
struct logical_and
: public binary_function<T, T, bool> {
bool operator()(const T& x, const T& y) const;
};
288
Standard C++ Library
The template class defines its member function as returning x && y.
logical_not
template<class T>
struct logical_not : public unary_function<T, bool> {
bool operator()(const T& x) const;
};
The template class defines its member function as returning !x.
logical_or
template<class T>
struct logical_or
: public binary_function<T, T, bool> {
bool operator()(const T& x, const T& y) const;
};
The template class defines its member function as returning x || y.
mem_fun
template<class R, class T>
mem_fun_t<R, T> mem_fun(R (T::*pm)());
template<class R, class T, class A>
mem_fun1_t<R, T, A> mem_fun(R (T::*pm)(A));
template<class R, class T>
const_mem_fun_t<R, T> mem_fun(R (T::*pm)() const);
template<class R, class T, class A>
const_mem_fun1_t<R, T, A> mem_fun(R (T::*pm)(A) const);
The template function returns pm cast to the return type.
mem_fun_ref
template<class R, class T>
mem_fun_ref_t<R, T> mem_fun_ref(R (T::*pm)());
template<class R, class T, class A>
mem_fun1_ref_t<R, T, A> mem_fun_ref(R (T::*pm)(A));
template<class R, class T>
const_mem_fun_ref_t<R, T> mem_fun_ref(R (T::*pm)() const);
template<class R, class T, class A>
const_mem_fun1_ref_t<R, T, A> mem_fun_ref(R (T::*pm)(A) const);
The template function returns pm cast to the return type.
mem_fun_t
template<class R, class T>
struct mem_fun_t : public unary_function<T *, R> {
explicit mem_fun_t(R (T::*pm)());
R operator()(T *p) const;
};
The template class stores a copy of pm, which must be a pointer to a member
function of class T, in a private member object. It defines its member function
operator() as returning (p->*pm)().
289
Chapter 13. Standard Template Library C++
mem_fun_ref_t
template<class R, class T>
struct mem_fun_ref_t
: public unary_function<T, R> {
explicit mem_fun_t(R (T::*pm)());
R operator()(T& x) const;
};
The template class stores a copy of pm, which must be a pointer to a member
function of class T, in a private member object. It defines its member function
operator() as returning (x.*Pm)().
mem_fun1_t
template<class R, class T, class A>
struct mem_fun1_t
: public binary_function<T *, A, R> {
explicit mem_fun1_t(R (T::*pm)(A));
R operator()(T *p, A arg) const;
};
The template class stores a copy of pm, which must be a pointer to a member
function of class T, in a private member object. It defines its member function
operator() as returning (p->*pm)(arg).
mem_fun1_ref_t
template<class R, class T, class A>
struct mem_fun1_ref_t
: public binary_function<T, A, R> {
explicit mem_fun1_ref_t(R (T::*pm)(A));
R operator()(T& x, A arg) const;
};
The template class stores a copy of pm, which must be a pointer to a member
function of class T, in a private member object. It defines its member function
operator() as returning (x.*pm)(arg).
minus
template<class T>
struct minus : public binary_function<T, T, T> {
T operator()(const T& x, const T& y) const;
};
The template class defines its member function as returning x - y.
modulus
template<class T>
struct modulus : public binary_function<T, T, T> {
T operator()(const T& x, const T& y) const;
};
The template class defines its member function as returning x % y.
multiplies
template<class T>
struct multiplies : public binary_function<T, T, T> {
T operator()(const T& x, const T& y) const;
};
290
Standard C++ Library
The template class defines its member function as returning x * y.
negate
template<class T>
struct negate : public unary_function<T, T> {
T operator()(const T& x) const;
};
The template class defines its member function as returning -x.
not1
template<class Pred>
unary_negate<Pred> not1(const Pred& pr);
The template function returns unary_negate<Pred>(pr).
not2
template<class Pred>
binary_negate<Pred> not2(const Pred& pr);
The template function returns binary_negate<Pred>(pr).
not_equal_to
template<class T>
struct not_equal_to
: public binary_function<T, T, bool> {
bool operator()(const T& x, const T& y) const;
};
The template class defines its member function as returning x != y.
plus
template<class T>
struct plus : public binary_function<T, T, T> {
T operator()(const T& x, const T& y) const;
};
The template class defines its member function as returning x + y.
pointer_to_binary_function
template<class Arg1, class Arg2, class Result>
class pointer_to_binary_function
: public binary_function<Arg1, Arg2, Result> {
public:
explicit pointer_to_binary_function(
Result (*pf)(Arg1, Arg2));
Result operator()(const Arg1 x, const Arg2 y) const;
};
The template class stores a copy of pf. It defines its member function operator()
as returning (*pf)(x, y).
pointer_to_unary_function
template<class Arg, class Result>
class pointer_to_unary_function
: public unary_function<Arg, Result> {
291
Chapter 13. Standard Template Library C++
img
.
public:
explicit pointer_to_unary_function(
Result (*pf)(Arg));
Result operator()(const Arg x) const;
};
The template class stores a copy of pf. It defines its member function operator()
as returning (*pf)(x).
ptr_fun
template<class Arg, class Result>
pointer_to_unary_function<Arg, Result>
ptr_fun(Result (*pf)(Arg));
template<class Arg1, class Arg2, class Result>
pointer_to_binary_function<Arg1, Arg2, Result>
ptr_fun(Result (*pf)(Arg1, Arg2));
The first template function returns pointer_to_unary_function<Arg, Result>(pf).
The second template function returns pointer_to_binary_function<Arg1, Arg2,
Result>(pf).
unary_function
template<class Arg, class Result>
struct unary_function {
typedef Arg argument_type;
typedef Result result_type;
};
The template class serves as a base for classes that define a member function of the
form:
result_type operator()(const argument_type&) const
Hence, all such unary functions can refer to their sole argument type as
argument_type and their return type as result_type.
unary_negate
template<class Pred>
class unary_negate
: public unary_function<
typename Pred::argument_type,
bool> {
public:
explicit unary_negate(const Pred& pr);
bool operator()(
const typename Pred::argument_type& x) const;
};
The template class stores a copy of pr, which must be a unary function (page 292)
object. It defines its member function operator() as returning !pr(x).
Portions derived from work copyright © 1994 by Hewlett-Packard Company. All rights
reserved.
292
Standard C++ Library
img
............................
<iterator>
advance (page 294) · back_insert_iterator (page 294) · back_inserter (page 296) ·
bidirectional_iterator_tag (page 296) · distance (page 296) · forward_iterator_tag
(page 296) · front_insert_iterator (page 296) · front_inserter (page 297) ·
input_iterator_tag (page 298) · insert_iterator (page 298) · inserter (page 299) ·
istream_iterator (page 299) · istreambuf_iterator (page 300) · iterator (page 302) ·
iterator_traits (page 302) · operator!= (page 303) · operator== (page 303) ·
operator< (page 304) · operator<= (page 304) · operator> (page 304) · operator>=
(page 304) · operator+ (page 304) · operator- (page 304) · ostream_iterator (page
304) · ostreambuf_iterator (page 306) · output_iterator_tag (page 307) ·
random_access_iterator_tag (page 307) · reverse_iterator (page 307)
namespace std {
struct input_iterator_tag;
struct output_iterator_tag;
struct forward_iterator_tag;
struct bidirectional_iterator_tag;
struct random_access_iterator_tag;
// TEMPLATE CLASSES
template<class C, class T, class Dist,
class Pt, class Rt>
struct iterator;
template<class It>
struct iterator_traits;
template<class T>
struct iterator_traits<T *>
template<class RanIt>
class reverse_iterator;
template<class Cont>
class back_insert_iterator;
template<class Cont>
class front_insert_iterator;
template<class Cont>
class insert_iterator;
template<class U, class E, class T, class Dist>
class istream_iterator;
template<class U, class E, class T>
class ostream_iterator;
template<class E, class T>
class istreambuf_iterator;
template<class E, class T>
class ostreambuf_iterator;
// TEMPLATE FUNCTIONS
template<class RanIt>
bool operator==(
const reverse_iterator<RanIt>& lhs,
const reverse_iterator<RanIt>& rhs);
template<class U, class E, class T, class Dist>
bool operator==(
const istream_iterator<U, E, T, Dist>& lhs,
const istream_iterator<U, E, T, Dist>& rhs);
template<class E, class T>
bool operator==(
const istreambuf_iterator<E, T>& lhs,
const istreambuf_iterator<E, T>& rhs);
template<class RanIt>
bool operator!=(
const reverse_iterator<RanIt>& lhs,
const reverse_iterator<RanIt>& rhs);
template<class U, class E, class T, class Dist>
bool operator!=(
const istream_iterator<U, E, T, Dist>& lhs,
293
Chapter 13. Standard Template Library C++
img
.
const istream_iterator<U, E, T, Dist>& rhs);
template<class E, class T>
bool operator!=(
const istreambuf_iterator<E, T>& lhs,
const istreambuf_iterator<E, T>& rhs);
template<class RanIt>
bool operator<(
const reverse_iterator<RanIt>& lhs,
const reverse_iterator<RanIt>& rhs);
template<class RanIt>
bool operator>(
const reverse_iterator<RanIt>& lhs,
const reverse_iterator<RanIt>& rhs);
template<class RanIt>
bool operator<=(
const reverse_iterator<RanIt>& lhs,
const reverse_iterator<RanIt>& rhs);
template<class RanIt>
bool operator>=(
const reverse_iterator<RanIt>& lhs,
const reverse_iterator<RanIt>& rhs);
template<class RanIt>
Dist operator-(
const reverse_iterator<RanIt>& lhs,
const reverse_iterator<RanIt>& rhs);
template<class RanIt>
reverse_iterator<RanIt> operator+(
Dist n,
const reverse_iterator<RanIt>& rhs);
template<class Cont>
back_insert_iterator<Cont> back_inserter(Cont& x);
template<class Cont>
front_insert_iterator<Cont> front_inserter(Cont& x);
template<class Cont, class Iter>
insert_iterator<Cont> inserter(Cont& x, Iter it);
template<class InIt, class Dist>
void advance(InIt& it, Dist n);
template<class Init, class Dist>
iterator_traits<InIt>::difference_type
distance(InIt first, InIt last);
};
Include the STL (page 1) standard header <iterator> to define a number of
classes, template classes, and template functions that aid in the declaration and
manipulation of iterators.
advance
template<class InIt, class Dist>
void advance(InIt& it, Dist n);
The template function effectively advances it by incrementing it n times. If InIt is
a random-access iterator type, the function evaluates the expression it += n.
Otherwise, it performs each increment by evaluating ++it. If InIt is an input or
forward iterator type, n must not be negative.
back_insert_iterator
template<class Cont>
class back_insert_iterator
: public iterator<output_iterator_tag,
void, void, void, void> {
public:
typedef Cont container_type;
typedef typename Cont::reference reference;
294
Standard C++ Library
img
.
typedef typename Cont::value_type value_type;
explicit back_insert_iterator(Cont& x);
back_insert_iterator&
operator=(typename Cont::const_reference val);
back_insert_iterator& operator*();
back_insert_iterator& operator++();
back_insert_iterator operator++(int);
protected:
Cont *container;
};
The template class describes an output iterator object. It inserts elements into a
container of type Cont, which it accesses via the protected pointer object it stores
called container. The container must define:
v the member type const_reference, which is the type of a constant reference to
an element of the sequence controlled by the container
v the member type reference, which is the type of a reference to an element of the
sequence controlled by the container
v the member type value_type, which is the type of an element of the sequence
controlled by the container
v the member function push_back(value_type c), which appends a new element
with value c to the end of the sequence
back_insert_iterator::back_insert_iterator
explicit back_insert_iterator(Cont& x);
The constructor initializes container (page 295) with &x.
back_insert_iterator::container_type
typedef Cont container_type;
The type is a synonym for the template parameter Cont.
back_insert_iterator::operator*
back_insert_iterator& operator*();
The member function returns *this.
back_insert_iterator::operator++
back_insert_iterator& operator++();
back_insert_iterator operator++(int);
The member functions both return *this.
back_insert_iterator::operator=
back_insert_iterator&
operator=(typename Cont::const_reference val);
The member function evaluates container. push_back(val), then returns *this.
back_insert_iterator::reference
typedef typename Cont::reference reference;
The type describes a reference to an element of the sequence controlled by the
associated container.
295
Chapter 13. Standard Template Library C++
back_insert_iterator::value_type
typedef typename Cont::value_type value_type;
The type describes the elements of the sequence controlled by the associated
container.
back_inserter
template<class Cont>
back_insert_iterator<Cont> back_inserter(Cont& x);
The template function returns back_insert_iterator<Cont>(x).
bidirectional_iterator_tag
struct bidirectional_iterator_tag
: public forward_iterator_tag {
};
The type is the same as iterator<It>::iterator_category when It describes an
object that can serve as a bidirectional iterator.
distance
template<class Init, class Dist>
typename iterator_traits<InIt>::difference_type
distance(InIt first, InIt last);
The template function sets a count n to zero. It then effectively advances first and
increments n until first == last. If InIt is a random-access iterator type, the
function evaluates the expression n += last - first. Otherwise, it performs each
iterator increment by evaluating ++first.
forward_iterator_tag
struct forward_iterator_tag
: public input_iterator_tag {
};
The type is the same as iterator<It>::iterator_category when It describes an
object that can serve as a forward iterator.
front_insert_iterator
template<class Cont>
class front_insert_iterator
: public iterator<output_iterator_tag,
void, void, void, void> {
public:
typedef Cont container_type;
typedef typename Cont::reference reference;
typedef typename Cont::value_type value_type;
explicit front_insert_iterator(Cont& x);
front_insert_iterator&
operator=(typename Cont::const_reference val);
front_insert_iterator& operator*();
front_insert_iterator& operator++();
front_insert_iterator operator++(int);
protected:
Cont *container;
};
296
Standard C++ Library
img
.
The template class describes an output iterator object. It inserts elements into a
container of type Cont, which it accesses via the protected pointer object it stores
called container. The container must define:
v the member type const_reference, which is the type of a constant reference to
an element of the sequence controlled by the container
v the member type reference, which is the type of a reference to an element of the
sequence controlled by the container
v the member type value_type, which is the type of an element of the sequence
controlled by the container
v the member function push_front(value_type c), which prepends a new element
with value c to the beginning of the sequence
front_insert_iterator::container_type
typedef Cont container_type;
The type is a synonym for the template parameter Cont.
front_insert_iterator::front_insert_iterator
explicit front_insert_iterator(Cont& x);
The constructor initializes container (page 297) with &x.
front_insert_iterator::operator*
front_insert_iterator& operator*();
The member function returns *this.
front_insert_iterator::operator++
front_insert_iterator& operator++();
front_insert_iterator operator++(int);
The member functions both return *this.
front_insert_iterator::operator=
front_insert_iterator&
operator=(typename Cont::const_reference val);
The member function evaluates container. push_front(val), then returns *this.
front_insert_iterator::reference
typedef typename Cont::reference reference;
The type describes a reference to an element of the sequence controlled by the
associated container.
front_insert_iterator::value_type
typedef typename Cont::value_type value_type;
The type describes the elements of the sequence controlled by the associated
container.
front_inserter
template<class Cont>
front_insert_iterator<Cont> front_inserter(Cont& x);
The template function returns front_insert_iterator<Cont>(x).
297
Chapter 13. Standard Template Library C++
img
..
input_iterator_tag
struct input_iterator_tag {
};
The type is the same as iterator<It>::iterator_category when It describes an
object that can serve as an input iterator.
insert_iterator
template<class Cont>
class insert_iterator
: public iterator<output_iterator_tag,
void, void, void, void> {
public:
typedef Cont container_type;
typedef typename Cont::reference reference;
typedef typename Cont::value_type value_type;
insert_iterator(Cont& x,
typename Cont::iterator it);
insert_iterator&
operator=(typename Cont::const_reference val);
insert_iterator& operator*();
insert_iterator& operator++();
insert_iterator& operator++(int);
protected:
Cont *container;
typename Cont::iterator iter;
};
The template class describes an output iterator object. It inserts elements into a
container of type Cont, which it accesses via the protected pointer object it stores
called container. It also stores the protected iterator object, of class Cont::iterator,
called iter. The container must define:
v the member type const_reference, which is the type of a constant reference to
an element of the sequence controlled by the container
v the member type iterator, which is the type of an iterator for the container
v the member type reference, which is the type of a reference to an element of the
sequence controlled by the container
v the member type value_type, which is the type of an element of the sequence
controlled by the container
v the member function insert(iterator it, value_type c), which inserts a new
element with value c immediately before the element designated by it in the
controlled sequence, then returns an iterator that designates the inserted element
insert_iterator::container_type
typedef Cont container_type;
The type is a synonym for the template parameter Cont.
insert_iterator::insert_iterator
insert_iterator(Cont& x,
typename Cont::iterator it);
The constructor initializes container (page 298) with &x, and iter (page 298) with it.
298
Standard C++ Library
insert_iterator::operator*
insert_iterator& operator*();
The member function returns *this.
insert_iterator::operator++
insert_iterator& operator++();
insert_iterator& operator++(int);
The member functions both return *this.
insert_iterator::operator=
insert_iterator&
operator=(typename Cont::const_reference val);
The member function evaluates iter = container. insert(iter, val), then
returns *this.
insert_iterator::reference
typedef typename Cont::reference reference;
The type describes a reference to an element of the sequence controlled by the
associated container.
insert_iterator::value_type
typedef typename Cont::value_type value_type;
The type describes the elements of the sequence controlled by the associated
container.
inserter
template<class Cont, class Iter>
insert_iterator<Cont> inserter(Cont& x, Iter it);
The template function returns insert_iterator<Cont>(x, it).
istream_iterator
template<class U, class E = char,
class T = char_traits>
class Dist = ptrdiff_t>
class istream_iterator
: public iterator<input_iterator_tag,
U, Dist, U *, U&> {
public:
typedef E char_type;
typedef T traits_type;
typedef basic_istream<E, T> istream_type;
istream_iterator();
istream_iterator(istream_type& is);
const U& operator*() const;
const U *operator->() const;
istream_iterator<U, E, T, Dist>& operator++();
istream_iterator<U, E, T, Dist> operator++(int);
};
The template class describes an input iterator object. It extracts objects of class U
from an input stream, which it accesses via an object it stores, of type pointer to
basic_istream<E, T>. After constructing or incrementing an object of class
299
Chapter 13. Standard Template Library C++
istream_iterator with a non-null stored pointer, the object attempts to extract and
store an object of type U from the associated input stream. If the extraction fails, the
object effectively replaces the stored pointer with a null pointer (thus making an
end-of-sequence indicator).
istream_iterator::char_type
typedef E char_type;
The type is a synonym for the template parameter E.
istream_iterator::istream_iterator
istream_iterator();
istream_iterator(istream_type& is);
The first constructor initializes the input stream pointer with a null pointer. The
second constructor initializes the input stream pointer with &is, then attempts to
extract and store an object of type U.
istream_iterator::istream_type
typedef basic_istream<E, T> istream_type;
The type is a synonym for basic_istream<E, T>.
istream_iterator::operator*
const U& operator*() const;
The operator returns the stored object of type U.
istream_iterator::operator->
const U *operator->() const;
The operator returns &**this.
istream_iterator::operator++
istream_iterator<U, E, T, Dist>& operator++();
istream_iterator<U, E, T, Dist> operator++(int);
The first operator attempts to extract and store an object of type U from the
associated input stream. The second operator makes a copy of the object,
increments the object, then returns the copy.
istream_iterator::traits_type
typedef T traits_type;
The type is a synonym for the template parameter T.
istreambuf_iterator
template<class E, class T = char_traits<E> >
class istreambuf_iterator
: public iterator<input_iterator_tag,
E, typename T::off_type, E *, E&> {
public:
typedef E char_type;
typedef T traits_type;
typedef typename T::int_type int_type;
typedef basic_streambuf<E, T> streambuf_type;
typedef basic_istream<E, T> istream_type;
istreambuf_iterator(streambuf_type *sb = 0) throw();
300
Standard C++ Library
istreambuf_iterator(istream_type& is) throw();
const E& operator*() const;
const E *operator->();
istreambuf_iterator& operator++();
istreambuf_iterator operator++(int);
bool equal(const istreambuf_iterator& rhs) const;
};
The template class describes an input iterator object. It extracts elements of class E
from an input stream buffer, which it accesses via an object it stores, of type
pointer to basic_streambuf<E, T>. After constructing or incrementing an object of
class istreambuf_iterator with a non-null stored pointer, the object effectively
attempts to extract and store an object of type E from the associated itput stream.
(The extraction may be delayed, however, until the object is actually dereferenced
or copied.) If the extraction fails, the object effectively replaces the stored pointer
with a null pointer (thus making an end-of-sequence indicator).
istreambuf_iterator::char_type
typedef E char_type;
The type is a synonym for the template parameter E.
istreambuf_iterator::equal
bool equal(const istreambuf_iterator& rhs) const;
The member function returns true only if the stored stream buffer pointers for the
object and rhs are both null pointers or are both non-null pointers.
istreambuf_iterator::int_type
typedef typename T::int_type int_type;
The type is a synonym for T::int_type.
istreambuf_iterator::istream_type
typedef basic_istream<E, T> istream_type;
The type is a synonym for basic_istream<E, T>.
istreambuf_iterator::istreambuf_iterator
istreambuf_iterator(streambuf_type *sb = 0) throw();
istreambuf_iterator(istream_type& is) throw();
The first constructor initializes the input stream-buffer pointer with sb. The second
constructor initializes the input stream-buffer pointer with is.rdbuf(), then
(eventually) attempts to extract and store an object of type E.
istreambuf_iterator::operator*
const E& operator*() const;
The operator returns the stored object of type E.
istreambuf_iterator::operator++
istreambuf_iterator& operator++();
istreambuf_iterator operator++(int);
The first operator (eventually) attempts to extract and store an object of type E
from the associated input stream. The second operator makes a copy of the object,
increments the object, then returns the copy.
301
Chapter 13. Standard Template Library C++
istreambuf_iterator::operator->
const E *operator->() const;
The operator returns &**this.
istreambuf_iterator::streambuf_type
typedef basic_streambuf<E, T> streambuf_type;
The type is a synonym for basic_streambuf<E, T>.
istreambuf_iterator::traits_type
typedef T traits_type;
The type is a synonym for the template parameter T.
iterator
template<class C, class T, class Dist = ptrdiff_t
class Pt = T *, class Rt = T&>
struct iterator {
typedef C iterator_category;
typedef T value_type;
typedef Dist difference_type;
typedef Pt pointer;
typedef Rt reference;
};
The template class serves as a base type for all iterators. It defines the member
types iterator_category, (a synonym for the template parameter C), value_type (a
synonym for the template parameter T), difference_type (a synonym for the
template parameter Dist), pointer (a synonym for the template parameter Pt), and
reference (a synonym for the template parameter T).
Note that value_type should not be a constant type even if pointer points at an
object of const type and reference designates an object of const type.
iterator_traits
template<class It>
struct iterator_traits {
typedef typename It::iterator_category iterator_category;
typedef typename It::value_type value_type;
typedef typename It::difference_type difference_type;
typedef typename It::pointer pointer;
typedef typename It::reference reference;
};
template<class T>
struct iterator_traits<T *> {
typedef random_access_iterator_tag iterator_category;
typedef T value_type;
typedef ptrdiff_t difference_type;
typedef T *pointer;
typedef T& reference;
};
template<class T>
struct iterator_traits<const T *> {
typedef random_access_iterator_tag iterator_category;
typedef T value_type;
typedef ptrdiff_t difference_type;
typedef const T *pointer;
typedef const T& reference;
};
302
Standard C++ Library
img
.
The template class determines several critical types associated with the iterator
type It. It defines the member types iterator_category (a synonym for
It::iterator_category), value_type (a synonym for It::value_type),
difference_type (a synonym for It::difference_type), pointer (a synonym for
It::pointer), and reference (a synonym for It::reference).
The partial specializations determine the critical types associated with an object
pointer type T *. In this implementation (page 3), you can also use several
template functions that do not make use of partial specialization:
template<class C, class T, class Dist>
C _Iter_cat(const iterator<C, T, Dist>&);
template<class T>
random_access_iterator_tag _Iter_cat(const T *);
template<class C, class T, class Dist>
T *_Val_type(const iterator<C, T, Dist>&);
template<class T>
T *_Val_type(const T *);
template<class C, class T, class Dist>
Dist *_Dist_type(const iterator<C, T, Dist>&);
template<class T>
ptrdiff_t *_Dist_type(const T *);
which determine several of the same types a bit more indirectly. You use these
functions as arguments on a function call. Their sole purpose is to supply a useful
template class parameter to the called function.
operator!=
template<class RanIt>
bool operator!=(
const reverse_iterator<RanIt>& lhs,
const reverse_iterator<RanIt>& rhs);
template<class U, class E, class T, class Dist>
bool operator!=(
const istream_iterator<U, E, T, Dist>& lhs,
const istream_iterator<U, E, T, Dist>& rhs);
template<class E, class T>
bool operator!=(
const istreambuf_iterator<E, T>& lhs,
const istreambuf_iterator<E, T>& rhs);
The template operator returns !(lhs == rhs).
operator==
template<class RanIt>
bool operator==(
const reverse_iterator<RanIt>& lhs,
const reverse_iterator<RanIt>& rhs);
template<class U, class E, class T, class Dist>
bool operator==(
const istream_iterator<U, E, T, Dist>& lhs,
const istream_iterator<U, E, T, Dist>& rhs);
template<class E, class T>
bool operator==(
const istreambuf_iterator<E, T>& lhs,
const istreambuf_iterator<E, T>& rhs);
The first template operator returns true only if lhs.current == rhs.current. The
second template operator returns true only if both lhs and rhs store the same
stream pointer. The third template operator returns lhs.equal(rhs).
303
Chapter 13. Standard Template Library C++
operator<
template<class RanIt>
bool operator<(
const reverse_iterator<RanIt>& lhs,
const reverse_iterator<RanIt>& rhs);
The template operator returns rhs.current < lhs.current [sic].
operator<=
template<class RanIt>
bool operator<=(
const reverse_iterator<RanIt>& lhs,
const reverse_iterator<RanIt>& rhs);
The template operator returns !(rhs < lhs).
operator>
template<class RanIt>
bool operator>(
const reverse_iterator<RanIt>& lhs,
const reverse_iterator<RanIt>& rhs);
The template operator returns rhs < lhs.
operator>=
template<class RanIt>
bool operator>=(
const reverse_iterator<RanIt>& lhs,
const reverse_iterator<RanIt>& rhs);
The template operator returns !(lhs < rhs).
operator+
template<class RanIt>
reverse_iterator<RanIt> operator+(Dist n,
const reverse_iterator<RanIt>& rhs);
The template operator returns rhs + n.
operator-
template<class RanIt>
Dist operator-(
const reverse_iterator<RanIt>& lhs,
const reverse_iterator<RanIt>& rhs);
The template operator returns rhs.current - lhs.current [sic].
ostream_iterator
template<class U, class E = char,
class T = char_traits<E>  >
class ostream_iterator
: public iterator<output_iterator_tag,
void, void, void, void> {
public:
typedef U value_type;
typedef E char_type;
typedef T traits_type;
304
Standard C++ Library
typedef basic_ostream<E, T> ostream_type;
ostream_iterator(ostream_type& os);
ostream_iterator(ostream_type& os, const E *delim);
ostream_iterator<U, E, T>& operator=(const U& val);
ostream_iterator<U, E, T>& operator*();
ostream_iterator<U, E, T>& operator++();
ostream_iterator<U, E, T> operator++(int);
};
The template class describes an output iterator object. It inserts objects of class U
into an output stream, which it accesses via an object it stores, of type pointer to
basic_ostream<E, T>. It also stores a pointer to a delimiter string, a
null-terminated string of elements of type E, which is appended after each
insertion. (Note that the string itself is not copied by the constructor.
ostream_iterator::char_type
typedef E char_type;
The type is a synonym for the template parameter E.
ostream_iterator::operator*
ostream_iterator<U, E, T>& operator*();
The operator returns *this.
ostream_iterator::operator++
ostream_iterator<U, E, T>& operator++();
ostream_iterator<U, E, T> operator++(int);
The operators both return *this.
ostream_iterator::operator=
ostream_iterator<U, E, T>& operator=(const U& val);
The operator inserts val into the output stream associated with the object, then
returns *this.
ostream_iterator::ostream_iterator
ostream_iterator(ostream_type& os);
ostream_iterator(ostream_type& os, const E *delim);
The first constructor initializes the output stream pointer with &os. The delimiter
string pointer designates an empty string. The second constructor initializes the
output stream pointer with &os and the delimiter string pointer with delim.
ostream_iterator::ostream_type
typedef basic_ostream<E, T> ostream_type;
The type is a synonym for basic_ostream<E, T>.
ostream_iterator::traits_type
typedef T traits_type;
The type is a synonym for the template parameter T.
305
Chapter 13. Standard Template Library C++
ostream_iterator::value_type
typedef U value_type;
The type is a synonym for the template parameter U.
ostreambuf_iterator
template<class E, class T = char_traits<E> >
class ostreambuf_iterator
: public iterator<output_iterator_tag,
void, void, void, void> {
public:
typedef E char_type;
typedef T traits_type;
typedef basic_streambuf<E, T> streambuf_type;
typedef basic_ostream<E, T> ostream_type;
ostreambuf_iterator(streambuf_type *sb) throw();
ostreambuf_iterator(ostream_type& os) throw();
ostreambuf_iterator& operator=(E x);
ostreambuf_iterator& operator*();
ostreambuf_iterator& operator++();
T1 operator++(int);
bool failed() const throw();
};
The template class describes an output iterator object. It inserts elements of class E
into an output stream buffer, which it accesses via an object it stores, of type
pointer to basic_streambuf<E, T>.
ostreambuf_iterator::char_type
typedef E char_type;
The type is a synonym for the template parameter E.
ostreambuf_iterator::failed
bool failed() const throw();
The member function returns true only if no insertion into the output stream
buffer has earlier failed.
ostreambuf_iterator::operator*
ostreambuf_iterator& operator*();
The operator returns *this.
ostreambuf_iterator::operator++
ostreambuf_iterator& operator++();
T1 operator++(int);
The first operator returns *this. The second operator returns an object of some
type T1 that can be converted to ostreambuf_iterator<E, T>.
ostreambuf_iterator::operator=
ostreambuf_iterator& operator=(E x);
The operator inserts x into the associated stream buffer, then returns *this.
306
Standard C++ Library
ostreambuf_iterator::ostream_type
typedef basic_ostream<E, T> ostream_type;
The type is a synonym for basic_ostream<E, T>.
ostreambuf_iterator::ostreambuf_iterator
ostreambuf_iterator(streambuf_type *sb) throw();
ostreambuf_iterator(ostream_type& os) throw();
The first conttructor initializes the output stream-buffer pointer with sb. The
second constructor initializes the output stream-buffer pointer with os.rdbuf().
(The stored pointer must not be a null pointer.)
ostreambuf_iterator::streambuf_type
typedef basic_streambuf<E, T> streambuf_type;
The type is a synonym for basic_streambuf<E, T>.
ostreambuf_iterator::traits_type
typedef T traits_type;
The type is a synonym for the template parameter T.
output_iterator_tag
struct output_iterator_tag {
};
The type is the same as iterator<It>::iterator_category when It describes an
object that can serve as a output iterator.
random_access_iterator_tag
struct random_access_iterator_tag
: public bidirectional_iterator_tag {
};
The type is the same as iterator<It>::iterator_category when It describes an
object that can serve as a random-access iterator.
reverse_iterator
template<class RanIt>
class reverse_iterator : public iterator<
typename iterator_traits<RanIt>::iterator_category,
typename iterator_traits<RanIt>::value_type,
typename iterator_traits<RanIt>::difference_type,
typename iterator_traits<RanIt>::pointer,
typename iterator_traits<RanIt>::reference> {
typedef typename iterator_traits<RanIt>::difference_type
Dist;
typedef typename iterator_traits<RanIt>::pointer
Ptr;
typedef typename iterator_traits<RanIt>::reference
Ref;
public:
typedef RanIt iterator_type;
reverse_iterator();
explicit reverse_iterator(RanIt x);
template<class U>
reverse_iterator(const reverse_iterator<U>& x);
307
Chapter 13. Standard Template Library C++
img
..
RanIt base() const;
Ref operator*() const;
Ptr operator->() const;
reverse_iterator& operator++();
reverse_iterator operator++(int);
reverse_iterator& operator--();
reverse_iterator operator--();
reverse_iterator& operator+=(Dist n);
reverse_iterator operator+(Dist n) const;
reverse_iterator& operator-=(Dist n);
reverse_iterator operator-(Dist n) const;
Ref operator[](Dist n) const;
protected:
RanIt current;
};
The template class describes an object that behaves like a random-access iterator,
only in reverse. It stores a random-access iterator of type RanIt in the protected
object current. Incrementing the object x of type reverse_iterator decrements
x.current, and decrementing x increments x.current. Moreover, the expression *x
evaluates to *(current - 1), of type Ref. Typically, Ref is type T&.
Thus, you can use an object of class reverse_iterator to access in reverse order a
sequence that is traversed in order by a random-access iterator.
Several STL containers (page 41) specialize reverse_iterator for RanIt a
bidirectional iterator. In these cases, you must not call any of the member functions
operator+=, operator+, operator-=, operator-, or operator[].
reverse_iterator::base
RanIt base() const;
The member function returns current (page 308).
reverse_iterator::iterator_type
typedef RanIt iterator_type;
The type is a synonym for the template parameter RanIt.
reverse_iterator::operator*
Ref operator*() const;
The operator returns *(current - 1).
reverse_iterator::operator+
reverse_iterator operator+(Dist n) const;
The operator returns reverse_iterator(*this) += n.
reverse_iterator::operator++
reverse_iterator& operator++();
reverse_iterator operator++(int);
The first (preincrement) operator evaluates --current. then returns *this.
The second (postincrement) operator makes a copy of *this, evaluates --current,
then returns the copy.
308
Standard C++ Library
img
...
reverse_iterator::operator+=
reverse_iterator& operator+=(Dist n);
The operator evaluates current - n. then returns *this.
reverse_iterator::operator-
reverse_iterator operator-(Dist n) const;
The operator returns reverse_iterator(*this) -= n.
reverse_iterator::operator--
reverse_iterator& operator--();
reverse_iterator operator--();
The first (predecrement) operator evaluates ++current. then returns *this.
The second (postdecrement) operator makes a copy of *this, evaluates ++current,
then returns the copy.
reverse_iterator::operator-=
reverse_iterator& operator-=(Dist n);
The operator evaluates current + n. then returns *this.
reverse_iterator::operator->
Ptr operator->() const;
The operator returns &**this.
reverse_iterator::operator[]
Ref operator[](Dist n) const;
The operator returns *(*this + n).
reverse_iterator::pointer
typedef Ptr pointer;
The type is a synonym for the template parameter Ref.
reverse_iterator::reference
typedef Ref reference;
The type is a synonym for the template parameter Ref.
reverse_iterator::reverse_iterator
reverse_iterator();
explicit reverse_iterator(RanIt x);
template<class U>
reverse_iterator (page 309)(const reverse_iterator<U>& x);
The first constructor initializes current (page 308) with its default constructor. The
second constructor initializes current with x.current.
The template constructor initializes current with x.base (page 308)().
309
Chapter 13. Standard Template Library C++
img
..........................................
<list>
namespace std {
template<class T, class A>
class list;
// TEMPLATE FUNCTIONS
template<class T, class A>
bool operator==(
const list<T, A>& lhs,
const list<T, A>& rhs);
template<class T, class A>
bool operator!=(
const list<T, A>& lhs,
const list<T, A>& rhs);
template<class T, class A>
bool operator<(
const list<T, A>& lhs,
const list<T, A>& rhs);
template<class T, class A>
bool operator>(
const list<T, A>& lhs,
const list<T, A>& rhs);
template<class T, class A>
bool operator<=(
const list<T, A>& lhs,
const list<T, A>& rhs);
template<class T, class A>
bool operator>=(
const list<T, A>& lhs,
const list<T, A>& rhs);
template<class T, class A>
void swap(
list<T, A>& lhs,
list<T, A>& rhs);
};
Include the STL (page 1) standard header <list> to define the container (page 41)
template class list and several supporting templates.
list
allocator_type (page 312) · assign (page 312) · back (page 312) · begin (page 312) ·
clear (page 312) · const_iterator (page 313) · const_pointer (page 313) ·
const_reference (page 313) · const_reverse_iterator (page 313) · difference_type
(page 313) · empty (page 313) · end (page 313) · erase (page 313) · front (page 314)
· get_allocator (page 314) · insert (page 314) · iterator (page 314) · list (page 314) ·
max_size (page 315) · merge (page 315) · pointer (page 315) · pop_back (page 315)
· pop_front (page 316) · push_back (page 316) · push_front (page 316) · rbegin
(page 316) · reference (page 316) · remove (page 316) · remove_if (page 316) · rend
(page 317) · resize (page 317) · reverse (page 317) · reverse_iterator (page 317) ·
size (page 317) · size_type (page 317) · sort (page 317) · splice (page 318) · swap
(page 318) · unique (page 318) · value_type (page 319)
template<class T, class A = allocator<T> >
class list {
public:
typedef A allocator_type;
typedef typename A::pointer pointer;
typedef typename A::const_pointer
const_pointer;
typedef typename A::reference reference;
typedef typename A::const_reference const_reference;
typedef typename A::value_type value_type;
typedef T0 iterator;
310
Standard C++ Library
typedef T1 const_iterator;
typedef T2 size_type;
typedef T3 difference_type;
typedef reverse_iterator<const_iterator>
const_reverse_iterator;
typedef reverse_iterator<iterator>
reverse_iterator;
list();
explicit list(const A& al);
explicit list(size_type n);
list(size_type n, const T& v);
list(size_type n, const T& v, const A& al);
list(const list& x);
template<class InIt>
list(InIt first, InIt last);
template<class InIt>
list(InIt first, InIt last, const A& al);
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
reverse_iterator rend();
const_reverse_iterator rend() const;
void resize(size_type n);
void resize(size_type n, T x);
size_type size() const;
size_type max_size() const;
bool empty() const;
A get_allocator() const;
reference front();
const_reference front() const;
reference back();
const_reference back() const;
void push_front(const T& x);
void pop_front();
void push_back(const T& x);
void pop_back();
template<class InIt>
void assign(InIt first, InIt last);
void assign(size_type n, const T& x);
iterator insert(iterator it, const T& x);
void insert(iterator it, size_type n, const T& x);
template<class InIt>
void insert(iterator it, InIt first, InIt last);
iterator erase(iterator it);
iterator erase(iterator first, iterator last);
void clear();
void swap(list& x);
void splice(iterator it, list& x);
void splice(iterator it, list& x, iterator first);
void splice(iterator it, list& x, iterator first,
iterator last);
void remove(const T& x);
templace<class Pred>
void remove_if(Pred pr);
void unique();
template<class Pred>
void unique(Pred pr);
void merge(list& x);
template<class Pred>
void merge(list& x, Pred pr);
void sort();
311
Chapter 13. Standard Template Library C++
img
...
template<class Pred>
void sort(Pred pr);
void reverse();
};
The template class describes an object that controls a varying-length sequence of
elements of type T. The sequence is stored as a bidirectional linked list of elements,
each containing a member of type T.
The object allocates and frees storage for the sequence it controls through a stored
allocator object (page 337) of class A. Such an allocator object must have the same
external interface as an object of template class allocator (page 337). Note that the
stored allocator object is not copied when the container object is assigned.
List reallocation occurs when a member function must insert or erase elements of
the controlled sequence. In all such cases, only iterators or references that point at
erased portions of the controlled sequence become invalid.
All additions to the controlled sequence occur as if by calls to insert (page 314),
which is the only member function that calls the constructor T(const T&). If such
an expression throws an exception, the container object inserts no new elements
and rethrows the exception. Thus, an object of template class list is left in a
known state when such exceptions occur.
list::allocator_type
typedef A allocator_type;
The type is a synonym for the template parameter A.
list::assign
template<class InIt>
void assign(InIt first, InIt last);
void assign(size_type n, const T& x);
If InIt is an integer type, the first member function behaves the same as
assign((size_type)first, (T)last). Otherwise, the first member function replaces
the sequence controlled by *this with the sequence [first, last), which must not
overlap the initial controlled sequence. The second member function replaces the
sequence controlled by *this with a repetition of n elements of value x.
list::back
reference back();
const_reference back() const;
The member function returns a reference to the last element of the controlled
sequence, which must be non-empty.
list::begin
const_iterator begin() const;
iterator begin();
The member function returns a bidirectional iterator that points at the first element
of the sequence (or just beyond the end of an empty sequence).
list::clear
void clear();
The member function calls erase( begin(), end()).
312
Standard C++ Library
list::const_iterator
typedef T1 const_iterator;
The type describes an object that can serve as a constant bidirectional iterator for
the controlled sequence. It is described here as a synonym for the
implementation-defined type T1.
list::const_pointer
typedef typename A::const_pointer
const_pointer;
The type describes an object that can serve as a constant pointer to an element of
the controlled sequence.
list::const_reference
typedef typename A::const_reference const_reference;
The type describes an object that can serve as a constant reference to an element of
the controlled sequence.
list::const_reverse_iterator
typedef reverse_iterator<const_iterator>
const_reverse_iterator;
The type describes an object that can serve as a constant reverse bidirectional
iterator for the controlled sequence.
list::difference_type
typedef T3 difference_type;
The signed integer type describes an object that can represent the difference
between the addresses of any two elements in the controlled sequence. It is
described here as a synonym for the implementation-defined type T3.
list::empty
bool empty() const;
The member function returns true for an empty controlled sequence.
list::end
const_iterator end() const;
iterator end();
The member function returns a bidirectional iterator that points just beyond the
end of the sequence.
list::erase
iterator erase(iterator it);
iterator erase(iterator first, iterator last);
The first member function removes the element of the controlled sequence pointed
to by it. The second member function removes the elements of the controlled
sequence in the range [first, last). Both return an iterator that designates the
first element remaining beyond any elements removed, or end() if no such element
exists.
313
Chapter 13. Standard Template Library C++
img
.....
Erasing N elements causes N destructor calls. No reallocation (page 312) occurs, so
iterators and references become invalid (page 312) only for the erased elements.
The member functions never throw an exception.
list::front
reference front();
const_reference front() const;
The member function returns a reference to the first element of the controlled
sequence, which must be non-empty.
list::get_allocator
A get_allocator() const;
The member function returns the stored allocator object (page 337).
list::insert
iterator insert(iterator it, const T& x);
void insert(iterator it, size_type n, const T& x);
template<class InIt>
void insert(iterator it, InIt first, InIt last);
Each of the member functions inserts, before the element pointed to by it in the
controlled sequence, a sequence specified by the remaining operands. The first
member function inserts a single element with value x and returns an iterator that
points to the newly inserted element. The second member function inserts a
repetition of n elements of value x.
If InIt is an integer type, the last member function behaves the same as
insert(it, (size_type)first, (T)last). Otherwise, the last member function
inserts the sequence [first, last), which must not overlap the initial controlled
sequence.
Inserting N elements causes N constructor calls. No reallocation (page 312) occurs,
so no iterators or references become invalid (page 312).
If an exception is thrown during the insertion of one or more elements, the
container is left unaltered and the exception is rethrown.
list::iterator
typedef T0 iterator;
The type describes an object that can serve as a bidirectional iterator for the
controlled sequence. It is described here as a synonym for the
implementation-defined type T0.
list::list
list();
explicit list(const A& al);
explicit list(size_type n);
list(size_type n, const T& v);
list(size_type n, const T& v,
const A& al);
list(const list& x);
template<class InIt>
list(InIt first, InIt last);
template<class InIt>
list(InIt first, InIt last, const A& al);
314
Standard C++ Library
img
...
All constructors store an allocator object (page 337) and initialize the controlled
sequence. The allocator object is the argument al, if present. For the copy
constructor, it is x.get_allocator(). Otherwise, it is A().
The first two constructors specify an empty initial controlled sequence. The third
constructor specifies a repetition of n elements of value T(). The fourth and fifth
constructors specify a repetition of n elements of value x. The sixth constructor
specifies a copy of the sequence controlled by x. If InIt is an integer type, the last
two constructors specify a repetition of (size_type)first elements of value
(T)last. Otherwise, the last two constructors specify the sequence [first, last).
None of the constructors perform any interim reallocations (page 312).
list::max_size
size_type max_size() const;
The member function returns the length of the longest sequence that the object can
control.
list::merge
void merge(list& x);
template<class Pred>
void merge(list& x, Pred pr);
Both member functions remove all elements from the sequence controlled by x and
insert them in the controlled sequence. Both sequences must be ordered by (page
39) the same predicate, described below. The resulting sequence is also ordered by
that predicate.
For the iterators Pi and Pj designating elements at positions i and j, the first
member function imposes the order !(*Pj < *Pi) whenever i < j. (The elements
are sorted in ascending order.) The second member function imposes the order
!pr(*Pj, *Pi) whenever i < j.
No pairs of elements in the original controlled sequence are reversed in the
resulting controlled sequence. If a pair of elements in the resulting controlled
sequence compares equal (!(*Pi < *Pj) && !(*Pj < *Pi)), an element from the
original controlled sequence appears before an element from the sequence
controlled by x.
An exception occurs only if pr throws an exception. In that case, the controlled
sequence is left in unspecified order and the exception is rethrown.
list::pointer
typedef typename A::pointer pointer;
The type describes an object that can serve as a pointer to an element of the
controlled sequence.
list::pop_back
void pop_back();
The member function removes the last element of the controlled sequence, which
must be non-empty.
The member function never throws an exception.
315
Chapter 13. Standard Template Library C++
list::pop_front
void pop_front();
The member function removes the first element of the controlled sequence, which
must be non-empty.
The member function never throws an exception.
list::push_back
void push_back(const T& x);
The member function inserts an element with value x at the end of the controlled
sequence.
If an exception is thrown, the container is left unaltered and the exception is
rethrown.
list::push_front
void push_front(const T& x);
The member function inserts an element with value x at the beginning of the
controlled sequence.
If an exception is thrown, the container is left unaltered and the exception is
rethrown.
list::rbegin
const_reverse_iterator rbegin() const;
reverse_iterator rbegin();
The member function returns a reverse bidirectional iterator that points just
beyond the end of the controlled sequence. Hence, it designates the beginning of
the reverse sequence.
list::reference
typedef typename A::reference reference;
The type describes an object that can serve as a reference to an element of the
controlled sequence.
list::remove
void remove(const T& x);
The member function removes from the controlled sequence all elements,
designated by the iterator P, for which *P == x.
The member function never throws an exception.
list::remove_if
templace<class Pred>
void remove_if(Pred pr);
The member function removes from the controlled sequence all elements,
designated by the iterator P, for which pr(*P) is true.
An exception occurs only if pr throws an exception. In that case, the controlled
sequence is left in an unspecified state and the exception is rethrown.
316
Standard C++ Library
list::rend
const_reverse_iterator rend() const;
reverse_iterator rend();
The member function returns a reverse bidirectional iterator that points at the first
element of the sequence (or just beyond the end of an empty sequence). Hence, it
designates the end of the reverse sequence.
list::resize
void resize(size_type n);
void resize(size_type n, T x);
The member functions both ensure that size() henceforth returns n. If it must
make the controlled sequence longer, the first member function appends elements
with value T(), while the second member function appends elements with value x.
To make the controlled sequence shorter, both member functions call
erase(begin() + n, end()).
list::reverse
void reverse();
The member function reverses the order in which elements appear in the
controlled sequence.
list::reverse_iterator
typedef reverse_iterator<iterator>
reverse_iterator;
The type describes an object that can serve as a reverse bidirectional iterator for the
controlled sequence.
list::size
size_type size() const;
The member function returns the length of the controlled sequence.
list::size_type
typedef T2 size_type;
The unsigned integer type describes an object that can represent the length of any
controlled sequence. It is described here as a synonym for the
implementation-defined type T2.
list::sort
void sort();
template<class Pred>
void sort(Pred pr);
Both member functions order the elements in the controlled sequence by a
predicate, described below.
For the iterators Pi and Pj designating elements at positions i and j, the first
member function imposes the order !(*Pj < *Pi) whenever i < j. (The elements
are sorted in ascending order.) The member template function imposes the order
!pr(*Pj, *Pi) whenever i < j. No pairs of elements in the original controlled
sequence are reversed in the resulting controlled sequence.
317
Chapter 13. Standard Template Library C++
img
.
An exception occurs only if pr throws an exception. In that case, the controlled
sequence is left in unspecified order and the exception is rethrown.
list::splice
void splice(iterator it, list& x);
void splice(iterator it, list& x, iterator first);
void splice(iterator it, list& x, iterator first,
iterator last);
The first member function inserts the sequence controlled by x before the element
in the controlled sequence pointed to by it. It also removes all elements from x.
(&x must not equal this.)
The second member function removes the element pointed to by first in the
sequence controlled by x and inserts it before the element in the controlled
sequence pointed to by it. (If it == first || it == ++first, no change occurs.)
The third member function inserts the subrange designated by [first, last) from
the sequence controlled by x before the element in the controlled sequence pointed
to by it. It also removes the original subrange from the sequence controlled by x.
(If &x == this, the range [first, last) must not include the element pointed to
by it.)
If the third member function inserts N elements, and &x != this, an object of class
iterator (page 314) is incremented N times. For all splice member functions, If
get_allocator() == str.get_allocator(), no exception occurs. Otherwise, a copy
and a destructor call also occur for each inserted element.
In all cases, only iterators or references that point at spliced elements become
invalid.
list::swap
void swap(list& x);
The member function swaps the controlled sequences between *this and x. If
get_allocator() == x.get_allocator(), it does so in constant time, it throws no
exceptions, and it invalidates no references, pointers, or iterators that designate
elements in the two controlled sequences. Otherwise, it performs a number of
element assignments and constructor calls proportional to the number of elements
in the two controlled sequences.
list::unique
void unique();
template<class Pred>
void unique(Pred pr);
The first member function removes from the controlled sequence every element
that compares equal to its preceding element. For the iterators Pi and Pj
designating elements at positions i and j, the second member function removes
every element for which i + 1 == j && pr(*Pi, *Pj).
For a controlled sequence of length N (> 0), the predicate pr(*Pi, *Pj) is evaluated
N - 1 times.
An exception occurs only if pr throws an exception. In that case, the controlled
sequence is left in an unspecified state and the exception is rethrown.
318
Standard C++ Library
img
.
list::value_type
typedef typename A::value_type value_type;
The type is a synonym for the template parameter T.
operator!=
template<class T, class A>
bool operator!=(
const list <T, A>& lhs,
const list <T, A>& rhs);
The template function returns !(lhs == rhs).
operator==
template<class T, class A>
bool operator==(
const list <T, A>& lhs,
const list <T, A>& rhs);
The template function overloads operator== to compare two objects of template
class list (page 310). The function returns lhs.size() == rhs.size() &&
equal(lhs. begin(), lhs. end(), rhs.begin()).
operator<
template<class T, class A>
bool operator<(
const list <T, A>& lhs,
const list <T, A>& rhs);
The template function overloads operator< to compare two objects of template
class list. The function returns lexicographical_compare(lhs. begin(), lhs.
end(), rhs.begin(), rhs.end()).
operator<=
template<class T, class A>
bool operator<=(
const list <T, A>& lhs,
const list <T, A>& rhs);
The template function returns !(rhs < lhs).
operator>
template<class T, class A>
bool operator>(
const list <T, A>& lhs,
const list <T, A>& rhs);
The template function returns rhs < lhs.
operator>=
template<class T, class A>
bool operator>=(
const list <T, A>& lhs,
const list <T, A>& rhs);
The template function returns !(lhs < rhs).
319
Chapter 13. Standard Template Library C++
img
.
swap
template<class T, class A>
void swap(
list <T, A>& lhs,
list <T, A>& rhs);
The template function executes lhs.swap (page 318)(rhs).
Portions derived from work copyright © 1994 by Hewlett-Packard Company. All rights
reserved.
<map>
namespace std {
template<class Key, class T, class Pred, class A>
class map;
template<class Key, class T, class Pred, class A>
class multimap;
// TEMPLATE FUNCTIONS
template<class Key, class T, class Pred, class
A>
bool operator==(
const map<Key, T, Pred, A>& lhs,
const map<Key, T, Pred, A>& rhs);
template<class Key, class T, class Pred, class
A>
bool operator==(
const multimap<Key, T, Pred, A>& lhs,
const multimap<Key, T, Pred, A>& rhs);
template<class Key, class T, class Pred, class
A>
bool operator!=(
const map<Key, T, Pred, A>& lhs,
const map<Key, T, Pred, A>& rhs);
template<class Key, class T, class Pred, class
A>
bool operator!=(
const multimap<Key, T, Pred, A>& lhs,
const multimap<Key, T, Pred, A>& rhs);
template<class Key, class T, class Pred, class
A>
bool operator<(
const map<Key, T, Pred, A>& lhs,
const map<Key, T, Pred, A>& rhs);
template<class Key, class T, class Pred, class
A>
bool operator<(
const multimap<Key, T, Pred, A>& lhs,
const multimap<Key, T, Pred, A>& rhs);
template<class Key, class T, class Pred, class
A>
bool operator>(
const map<Key, T, Pred, A>& lhs,
const map<Key, T, Pred, A>& rhs);
template<class Key, class T, class Pred, class
A>
bool operator>(
const multimap<Key, T, Pred, A>& lhs,
const multimap<Key, T, Pred, A>& rhs);
template<class Key, class T, class Pred, class
A>
bool operator<=(
const map<Key, T, Pred, A>& lhs,
const map<Key, T, Pred, A>& rhs);
template<class Key, class T, class Pred, class
A>
bool operator<=(
const multimap<Key, T, Pred, A>& lhs,
const multimap<Key, T, Pred, A>& rhs);
template<class Key, class T, class Pred, class
A>
bool operator>=(
const map<Key, T, Pred, A>& lhs,
const map<Key, T, Pred, A>& rhs);
template<class Key, class T, class Pred, class
A>
320
Standard C++ Library
img
.......................................
bool operator>=(
const multimap<Key, T, Pred, A>&
lhs,
const multimap<Key, T, Pred, A>&
rhs);
template<class Key, class T, class Pred,
class A>
void swap(
map<Key, T, Pred, A>& lhs,
map<Key, T, Pred, A>& rhs);
template<class Key, class T, class Pred,
class A>
void swap(
multimap<Key, T, Pred, A>& lhs,
multimap<Key, T, Pred, A>& rhs);
};
Include the STL (page 1) standard header <map> to define the container (page 41)
template classes map and multimap, and their supporting templates.
map
allocator_type (page 323) · begin (page 323) · clear (page 323) · const_iterator
(page 323) · const_pointer (page 323) · const_reference (page 323) ·
const_reverse_iterator (page 323) · count (page 323) · difference_type (page 323) ·
empty (page 324) · end (page 324) · equal_range (page 324) · erase (page 324) ·
find (page 324) · get_allocator (page 324) · insert (page 324) · iterator (page 325) ·
key_comp (page 325) · key_compare (page 325) · key_type (page 325) ·
lower_bound (page 325) · map (page 325) · mapped_type (page 326) · max_size
(page 326) · operator[] (page 326) · pointer (page 326) · rbegin (page 326) ·
reference (page 326) · rend (page 327) · reverse_iterator (page 327) · size (page
327) · size_type (page 327) · swap (page 327) · upper_bound (page 327) ·
value_comp (page 327) · value_compare (page 328) · value_type (page 328)
template<class Key, class T, class Pred = less<Key>,
class A = allocator<pair<const Key, T> > >
class map {
public:
typedef Key key_type;
typedef T mapped_type;
typedef Pred key_compare;
typedef A allocator_type;
typedef pair<const Key, T> value_type;
class value_compare;
typedef A::pointer pointer;
typedef A::const_pointer const_pointer;
typedef A::reference reference;
typedef A::const_reference const_reference;
typedef T0 iterator;
typedef T1 const_iterator;
typedef T2 size_type;
typedef T3 difference_type;
typedef reverse_iterator<const_iterator>
const_reverse_iterator;
typedef reverse_iterator<iterator> reverse_iterator;
map();
explicit map(const Pred& comp);
map(const Pred& comp, const A& al);
map(const map& x);
template<class InIt>
map(InIt first, InIt last);
template<class InIt>
map(InIt first, InIt last,
const Pred& comp);
template<class InIt>
map(InIt first, InIt last,
const Pred& comp, const A& al);
iterator begin();
const_iterator begin() const;
321
Chapter 13. Standard Template Library C++
img
.....
iterator end();
const_iterator end() const;
reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
reverse_iterator rend();
const_reverse_iterator rend() const;
size_type size() const;
size_type max_size() const;
bool empty() const;
A get_allocator() const;
mapped_type operator[](const Key& key);
pair<iterator, bool> insert(const value_type& x);
iterator insert(iterator it, const value_type& x);
template<class InIt>
void insert(InIt first, InIt last);
iterator erase(iterator it);
iterator erase(iterator first, iterator last);
size_type erase(const Key& key);
void clear();
void swap(map& x);
key_compare key_comp() const;
value_compare value_comp() const;
iterator find(const Key& key);
const_iterator find(const Key& key) const;
size_type count(const Key& key) const;
iterator lower_bound(const Key& key);
const_iterator lower_bound(const Key& key) const;
iterator upper_bound(const Key& key);
const_iterator upper_bound(const Key& key) const;
pair<iterator, iterator> equal_range(const Key& key);
pair<const_iterator, const_iterator>
equal_range(const Key& key) const;
};
The template class describes an object that controls a varying-length sequence of
elements of type pair<const Key, T>. The sequence is ordered by (page 39) the
predicate Pred. The first element of each pair is the sort key and the second is its
associated value. The sequence is represented in a way that permits lookup,
insertion, and removal of an arbitrary element with a number of operations
proportional to the logarithm of the number of elements in the sequence
(logarithmic time). Moreover, inserting an element invalidates no iterators, and
removing an element invalidates only those iterators which point at the removed
element.
The object orders the sequence it controls by calling a stored function object of
type Pred. You access this stored object by calling the member function key_comp().
Such a function object must impose a total ordering (page 401) on sort keys of type
Key. For any element x that precedes y in the sequence, key_comp()(y.first,
x.first) is false. (For the default function object less<Key>, sort keys never
decrease in value.) Unlike template class multimap (page 328), an object of
template class map ensures that key_comp()(x.first, y.first) is true. (Each key is
unique.)
The object allocates and frees storage for the sequence it controls through a stored
allocator object (page 337) of class A. Such an allocator object must have the same
external interface as an object of template class allocator (page 337). Note that the
stored allocator object is not copied when the container object is assigned.
322
Standard C++ Library
map::allocator_type
typedef A allocator_type;
The type is a synonym for the template parameter A.
map::begin
const_iterator begin() const;
iterator begin();
The member function returns a bidirectional iterator that points at the first element
of the sequence (or just beyond the end of an empty sequence).
map::clear
void clear();
The member function calls erase( begin(), end()).
map::const_iterator
typedef T1 const_iterator;
The type describes an object that can serve as a constant bidirectional iterator for
the controlled sequence. It is described here as a synonym for the
implementation-defined type T1.
map::const_pointer
typedef A::const_pointer const_pointer;
The type describes an object that can serve as a constant pointer to an element of
the controlled sequence.
map::const_reference
typedef A::const_reference const_reference;
The type describes an object that can serve as a constant reference to an element of
the controlled sequence.
map::const_reverse_iterator
typedef reverse_iterator<const_iterator>
const_reverse_iterator;
The type describes an object that can serve as a constant reverse bidirectional
iterator for the controlled sequence.
map::count
size_type count(const Key& key) const;
The member function returns the number of elements x in the range
[lower_bound(key), upper_bound(key)).
map::difference_type
typedef T3 difference_type;
The signed integer type describes an object that can represent the difference
between the addresses of any two elements in the controlled sequence. It is
described here as a synonym for the implementation-defined type T3.
323
Chapter 13. Standard Template Library C++
img
...
map::empty
bool empty() const;
The member function returns true for an empty controlled sequence.
map::end
const_iterator end() const;
iterator end();
The member function returns a bidirectional iterator that points just beyond the
end of the sequence.
map::equal_range
pair<iterator, iterator> equal_range(const Key& key);
pair<const_iterator, const_iterator>
equal_range(const Key& key) const;
The member function returns a pair of iterators x such that x.first ==
lower_bound(key) and x.second == upper_bound(key).
map::erase
iterator erase(iterator it);
iterator erase(iterator first, iterator last);
size_type erase(const Key& key);
The first member function removes the element of the controlled sequence pointed
to by it. The second member function removes the elements in the interval
[first, last). Both return an iterator that designates the first element remaining
beyond any elements removed, or end() if no such element exists.
The third member function removes the elements with sort keys in the range
[lower_bound(key), upper_bound(key)). It returns the number of elements it
removes.
The member functions never throw an exception.
map::find
iterator find(const Key& key);
const_iterator find(const Key& key) const;
The member function returns an iterator that designates the earliest element in the
controlled sequence whose sort key has equivalent ordering (page 39) to key. If no
such element exists, the function returns end().
map::get_allocator
A get_allocator() const;
The member function returns the stored allocator object (page 337).
map::insert
pair<iterator, bool> insert(const value_type& x);
iterator insert(iterator it, const value_type& x);
template<class InIt>
void insert(InIt first, InIt last);
The first member function determines whether an element y exists in the sequence
whose key has equivalent ordering (page 39) to that of x. If not, it creates such an
324
Standard C++ Library
element y and initializes it with x. The function then determines the iterator it that
designates y. If an insertion occurred, the function returns pair(it, true).
Otherwise, it returns pair(it, false).
The second member function returns insert(x), using it as a starting place within
the controlled sequence to search for the insertion point. (Insertion can occur in
amortized constant time, instead of logarithmic time, if the insertion point
immediately follows it.) The third member function inserts the sequence of
element values, for each it in the range [first, last), by calling insert(*it).
If an exception is thrown during the insertion of a single element, the container is
left unaltered and the exception is rethrown. If an exception is thrown during the
insertion of multiple elements, the container is left in a stable but unspecified state
and the exception is rethrown.
map::iterator
typedef T0 iterator;
The type describes an object that can serve as a bidirectional iterator for the
controlled sequence. It is described here as a synonym for the
implementation-defined type T0.
map::key_comp
key_compare key_comp() const;
The member function returns the stored function object that determines the order
of elements in the controlled sequence. The stored object defines the member
function:
bool operator()(const Key& x, const Key& y);
which returns true if x strictly precedes y in the sort order.
map::key_compare
typedef Pred key_compare;
The type describes a function object that can compare two sort keys to determine
the relative order of two elements in the controlled sequence.
map::key_type
typedef Key key_type;
The type describes the sort key object stored in each element of the controlled
sequence.
map::lower_bound
iterator lower_bound(const Key& key);
const_iterator lower_bound(const Key& key) const;
The member function returns an iterator that designates the earliest element x in
the controlled sequence for which key_comp()(x. first, key) is false.
If no such element exists, the function returns end().
map::map
map();
explicit map(const Pred& comp);
map(const Pred& comp, const A& al);
325
Chapter 13. Standard Template Library C++
img
.
map(const map& x);
template<class InIt>
map(InIt first, InIt last);
template<class InIt>
map(InIt first, InIt last,
const Pred& comp);
template<class InIt>
map(InIt first, InIt last,
const Pred& comp, const A& al);
All constructors store an allocator object (page 337) and initialize the controlled
sequence. The allocator object is the argument al, if present. For the copy
constructor, it is x.get_allocator(). Otherwise, it is A().
All constructors also store a function object that can later be returned by calling
key_comp(). The function object is the argument comp, if present. For the copy
constructor, it is x.key_comp()). Otherwise, it is Pred().
The first three constructors specify an empty initial controlled sequence. The fourth
constructor specifies a copy of the sequence controlled by x. The last three
constructors specify the sequence of element values [first, last).
map::mapped_type
typedef T mapped_type;
The type is a synonym for the template parameter T.
map::max_size
size_type max_size() const;
The member function returns the length of the longest sequence that the object can
control.
map::operator[]
T& operator[](const Key& key);
The member function determines the iterator it as the return value of insert(
value_type(key, T()). (It inserts an element with the specified key if no such
element exists.) It then returns a reference to (*it).second.
map::pointer
typedef A::pointer pointer;
The type describes an object that can serve as a pointer to an element of the
controlled sequence.
map::rbegin
const_reverse_iterator rbegin() const;
reverse_iterator rbegin();
The member function returns a reverse bidirectional iterator that points just
beyond the end of the controlled sequence. Hence, it designates the beginning of
the reverse sequence.
map::reference
typedef A::reference reference;
326
Standard C++ Library
The type describes an object that can serve as a reference to an element of the
controlled sequence.
map::rend
const_reverse_iterator rend() const;
reverse_iterator rend();
The member function returns a reverse bidirectional iterator that points at the first
element of the sequence (or just beyond the end of an empty sequence). Hence, it
designates the end of the reverse sequence.
map::reverse_iterator
typedef reverse_iterator<iterator> reverse_iterator;
The type describes an object that can serve as a reverse bidirectional iterator for the
controlled sequence.
map::size
size_type size() const;
The member function returns the length of the controlled sequence.
map::size_type
typedef T2 size_type;
The unsigned integer type describes an object that can represent the length of any
controlled sequence. It is described here as a synonym for the
implementation-defined type T2.
map::swap
void swap(map& x);
The member function swaps the controlled sequences between *this and x. If
get_allocator() == x.get_allocator(), it does so in constant time, it throws an
exception only as a result of copying the stored function object of type Pred, and it
invalidates no references, pointers, or iterators that designate elements in the two
controlled sequences. Otherwise, it performs a number of element assignments and
constructor calls proportional to the number of elements in the two controlled
sequences.
map::upper_bound
iterator upper_bound(const Key& key);
const_iterator upper_bound(const Key& key) const;
The member function returns an iterator that designates the earliest element x in
the controlled sequence for which key_comp()(key, x.first) is true.
If no such element exists, the function returns end().
map::value_comp
value_compare value_comp() const;
The member function returns a function object that determines the order of
elements in the controlled sequence.
327
Chapter 13. Standard Template Library C++
img
....................................
map::value_compare
class value_compare
: public binary_function<value_type, value_type,
bool> {
public:
bool operator()(const value_type& x,
const value_type& y) const
{return (comp(x.first, y.first)); }
protected:
value_compare(key_compare pr)
: comp(pr) {}
key_compare comp;
};
The type describes a function object that can compare the sort keys in two
elements to determine their relative order in the controlled sequence. The function
object stores an object comp of type key_compare. The member function operator()
uses this object to compare the sort-key components of two element.
map::value_type
typedef pair (page 402)<const Key, T> value_type;
The type describes an element of the controlled sequence.
multimap
allocator_type (page 330) · begin (page 330) · clear (page 330) · const_iterator
(page 330) · const_pointer (page 330) · const_reference (page 330) ·
const_reverse_iterator (page 330) · count (page 330) · difference_type (page 330) ·
empty (page 331) · end (page 331) · equal_range (page 331) · erase (page 331) ·
find (page 331) · get_allocator (page 331) · insert (page 331) · iterator (page 332) ·
key_comp (page 332) · key_compare (page 332) · key_type (page 332) ·
lower_bound (page 332) · mapped_type (page 332) · max_size (page 333) ·
multimap (page 333) · rbegin (page 333) · reference (page 333) · rend (page 333) ·
reverse_iterator (page 334) · size (page 334) · size_type (page 334) · swap (page
334) · upper_bound (page 334) · value_comp (page 334) · value_compare (page
334) · value_type (page 335)
template<class Key, class T, class Pred = less<Key>,
class A = allocator<pair<const Key, T> > >
class multimap {
public:
typedef Key key_type;
typedef T mapped_type;
typedef Pred key_compare;
typedef A allocator_type;
typedef pair<const Key, T> value_type;
class value_compare;
typedef A::reference reference;
typedef A::const_reference const_reference;
typedef T0 iterator;
typedef T1 const_iterator;
typedef T2 size_type;
typedef T3 difference_type;
typedef reverse_iterator<const_iterator>
const_reverse_iterator;
typedef reverse_iterator<iterator> reverse_iterator;
multimap();
explicit multimap(const Pred& comp);
multimap(const Pred& comp, const A& al);
multimap(const multimap& x);
template<class InIt>
multimap(InIt first, InIt last);
328
Standard C++ Library
img
....
template<class InIt>
multimap(InIt first, InIt last,
const Pred& comp);
template<class InIt>
multimap(InIt first, InIt last,
const Pred& comp, const A& al);
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
reverse_iterator rend();
const_reverse_iterator rend() const;
size_type size() const;
size_type max_size() const;
bool empty() const;
A get_allocator() const;
iterator insert(const value_type& x);
iterator insert(iterator it, const value_type& x);
template<class InIt>
void insert(InIt first, InIt last);
iterator erase(iterator it);
iterator erase(iterator first, iterator last);
size_type erase(const Key& key);
void clear();
void swap(multimap& x);
key_compare key_comp() const;
value_compare value_comp() const;
iterator find(const Key& key);
const_iterator find(const Key& key) const;
size_type count(const Key& key) const;
iterator lower_bound(const Key& key);
const_iterator lower_bound(const Key& key) const;
iterator upper_bound(const Key& key);
const_iterator upper_bound(const Key& key) const;
pair<iterator, iterator> equal_range(const Key& key);
pair<const_iterator, const_iterator>
equal_range(const Key& key) const;
};
The template class describes an object that controls a varying-length sequence of
elements of type pair<const Key, T>. The sequence is ordered by (page 39) the
predicate Pred. The first element of each pair is the sort key and the second is its
associated value. The sequence is represented in a way that permits lookup,
insertion, and removal of an arbitrary element with a number of operations
proportional to the logarithm of the number of elements in the sequence
(logarithmic time). Moreover, inserting an element invalidates no iterators, and
removing an element invalidates only those iterators which point at the removed
element.
The object orders the sequence it controls by calling a stored function object of
type Pred. You access this stored object by calling the member function key_comp().
Such a function object must impose a total ordering (page 401) on sort keys of type
Key. For any element x that precedes y in the sequence, key_comp()(y.first,
x.first) is false. (For the default function object less<Key>, sort keys never
decrease in value.) Unlike template class map (page 321), an object of template
class multimap does not ensure that key_comp()(x.first, y.first) is true. (Keys
need not be unique.)
The object allocates and frees storage for the sequence it controls through a stored
allocator object (page 337) of class A. Such an allocator object must have the same
329
Chapter 13. Standard Template Library C++
img
.
external interface as an object of template class allocator (page 337). Note that the
stored allocator object is not copied when the container object is assigned.
multimap::allocator_type
typedef A allocator_type;
The type is a synonym for the template parameter A.
multimap::begin
const_iterator begin() const;
iterator begin();
The member function returns a bidirectional iterator that points at the first element
of the sequence (or just beyond the end of an empty sequence).
multimap::clear
void clear();
The member function calls erase( begin(), end()).
multimap::const_iterator
typedef T1 const_iterator;
The type describes an object that can serve as a constant bidirectional iterator for
the controlled sequence. It is described here as a synonym for the
implementation-defined type T1.
multimap::const_pointer
typedef A::const_pointer const_pointer;
The type describes an object that can serve as a constant pointer to an element of
the controlled sequence.
multimap::const_reference
typedef A::const_reference const_reference;
The type describes an object that can serve as a constant reference to an element of
the controlled sequence.
multimap::const_reverse_iterator
typedef reverse_iterator<const_iterator>
const_reverse_iterator;
The type describes an object that can serve as a constant reverse bidirectional
iterator for the controlled sequence.
multimap::count
size_type count(const Key& key) const;
The member function returns the number of elements x in the range
[lower_bound(key), upper_bound(key)).
multimap::difference_type
typedef T3 difference_type;
330
Standard C++ Library
img
..
The signed integer type describes an object that can represent the difference
between the addresses of any two elements in the controlled sequence. It is
described here as a synonym for the implementation-defined type T3.
multimap::empty
bool empty() const;
The member function returns true for an empty controlled sequence.
multimap::end
const_iterator end() const;
iterator end();
The member function returns a bidirectional iterator that points just beyond the
end of the sequence.
multimap::equal_range
pair<iterator, iterator> equal_range(const Key& key);
pair<const_iterator, const_iterator>
equal_range(const Key& key) const;
The member function returns a pair of iterators x such that x.first ==
lower_bound(key) and x.second == upper_bound(key).
multimap::erase
iterator erase(iterator it);
iterator erase(iterator first, iterator last);
size_type erase(const Key& key);
The first member function removes the element of the controlled sequence pointed
to by it. The second member function removes the elements in the range [first,
last). Both return an iterator that designates the first element remaining beyond
any elements removed, or end() if no such element exists.
The third member removes the elements with sort keys in the range
[lower_bound(key), upper_bound(key)). It returns the number of elements it
removes.
The member functions never throw an exception.
multimap::find
iterator find(const Key& key);
const_iterator find(const Key& key) const;
The member function returns an iterator that designates the earliest element in the
controlled sequence whose sort key has equivalent ordering (page 39) to key. If no
such element exists, the function returns end().
multimap::get_allocator
A get_allocator() const;
The member function returns the stored allocator object (page 337).
multimap::insert
iterator insert(const value_type& x);
iterator insert(iterator it, const value_type& x);
template<class InIt>
void insert(InIt first, InIt last);
331
Chapter 13. Standard Template Library C++
The first member function inserts the element x in the controlled sequence, then
returns the iterator that designates the inserted element. The second member
function returns insert(x), using it as a starting place within the controlled
sequence to search for the insertion point. (Insertion can occur in amortized
constant time, instead of logarithmic time, if the insertion point immediately
follows it.) The third member function inserts the sequence of element values, for
each it in the range [first, last), by calling insert(*it).
If an exception is thrown during the insertion of a single element, the container is
left unaltered and the exception is rethrown. If an exception is thrown during the
insertion of multiple elements, the container is left in a stable but unspecified state
and the exception is rethrown.
multimap::iterator
typedef T0 iterator;
The type describes an object that can serve as a bidirectional iterator for the
controlled sequence. It is described here as a synonym for the
implementation-defined type T0.
multimap::key_comp
key_compare key_comp() const;
The member function returns the stored function object that determines the order
of elements in the controlled sequence. The stored object defines the member
function:
bool operator()(const Key& x, const Key& y);
which returns true if x strictly precedes y in the sort order.
multimap::key_compare
typedef Pred key_compare;
The type describes a function object that can compare two sort keys to determine
the relative order of two elements in the controlled sequence.
multimap::key_type
typedef Key key_type;
The type describes the sort key object stored in each element of the controlled
sequence.
multimap::lower_bound
iterator lower_bound(const Key& key);
const_iterator lower_bound(const Key& key) const;
The member function returns an iterator that designates the earliest element x in
the controlled sequence for which key_comp()(x. first, key) is false.
If no such element exists, the function returns end().
multimap::mapped_type
typedef T mapped_type;
The type is a synonym for the template parameter T.
332
Standard C++ Library
img
...
multimap::max_size
size_type max_size() const;
The member function returns the length of the longest sequence that the object can
control.
multimap::multimap
multimap();
explicit multimap(const Pred& comp);
multimap(const Pred& comp, const A& al);
multimap(const multimap& x);
template<class InIt>
multimap(InIt first, InIt last);
template<class InIt>
multimap(InIt first, InIt last,
const Pred& comp);
template<class InIt>
multimap(InIt first, InIt last,
const Pred& comp, const A& al);
All constructors store an allocator object (page 337) and initialize the controlled
sequence. The allocator object is the argument al, if present. For the copy
constructor, it is x.get_allocator (page 331)(). Otherwise, it is A().
All constructors also store a function object that can later be returned by calling
key_comp(). The function object is the argument comp, if present. For the copy
constructor, it is x.key_comp (page 332)()). Otherwise, it is Pred().
The first three constructors specify an empty initial controlled sequence. The fourth
constructor specifies a copy of the sequence controlled by x. The last three
constructors specify the sequence of element values [first, last).
multimap::pointer
typedef A::pointer pointer;
The type describes an object that can serve as a pointer to an element of the
controlled sequence.
multimap::rbegin
const_reverse_iterator rbegin() const;
reverse_iterator rbegin();
The member function returns a reverse bidirectional iterator that points just
beyond the end of the controlled sequence. Hence, it designates the beginning of
the reverse sequence.
multimap::reference
typedef A::reference reference;
The type describes an object that can serve as a reference to an element of the
controlled sequence.
multimap::rend
const_reverse_iterator rend() const;
reverse_iterator rend();
333
Chapter 13. Standard Template Library C++
img
.
The member function returns a reverse bidirectional iterator that points at the first
element of the sequence (or just beyond the end of an empty sequence). Hence, it
designates the end of the reverse sequence.
multimap::reverse_iterator
typedef reverse_iterator<iterator> reverse_iterator;
The type describes an object that can serve as a reverse bidirectional iterator for the
controlled sequence.
multimap::size
size_type size() const;
The member function returns the length of the controlled sequence.
multimap::size_type
typedef T2 size_type;
The unsigned integer type describes an object that can represent the length of any
controlled sequence. It is described here as a synonym for the
implementation-defined type T2.
multimap::swap
void swap(multimap& x);
The member function swaps the controlled sequences between *this and x. If
get_allocator() == x.get_allocator(), it does so in constant time, it throws an
exception only as a result of copying the stored function object of type Pred, and it
invalidates no references, pointers, or iterators that designate elements in the two
controlled sequences. Otherwise, it performs a number of element assignments and
constructor calls proportional to the number of elements in the two controlled
sequences.
multimap::upper_bound
iterator upper_bound(const Key& key);
const_iterator upper_bound(const Key& key) const;
The member function returns an iterator that designates the earliest element x in
the controlled sequence for which key_comp()(key, x.first) is true.
If no such element exists, the function returns end().
multimap::value_comp
value_compare value_comp() const;
The member function returns a function object that determines the order of
elements in the controlled sequence.
multimap::value_compare
class value_compare
: public binary_function (page 285)<value_type, value_type,
bool> {
public:
bool operator()(const value_type& x,
const value_type& y) const
{return (comp(x.first, x.second)); }
protected:
334
Standard C++ Library
img
.........
value_compare(key_compare pr)
: comp(pr) {}
key_compare comp;
};
The type describes a function object that can compare the sort keys in two
elements to determine their relative order in the controlled sequence. The function
object stores an object comp of type key_compare. The member function operator()
uses this object to compare the sort-key components of two element.
multimap::value_type
typedef pair (page 402)<const Key, T> value_type;
The type describes an element of the controlled sequence.
operator!=
template<class Key, class T, class Pred, class A>
bool operator!=(
const map <Key, T, Pred, A>& lhs,
const map <Key, T, Pred, A>& rhs);
template<class Key, class T, class Pred, class A>
bool operator!=(
const multimap <Key, T, Pred, A>& lhs,
const multimap <Key, T, Pred, A>& rhs);
The template function returns !(lhs == rhs).
operator==
template<class Key, class T, class Pred, class A>
bool operator==(
const map <Key, T, Pred, A>& lhs,
const map <Key, T, Pred, A>& rhs);
template<class Key, class T, class Pred, class A>
bool operator==(
const multimap <Key, T, Pred, A>& lhs,
const multimap <Key, T, Pred, A>& rhs);
The first template function overloads operator== to compare two objects of
template class multimap (page 328). The second template function overloads
operator== to compare two objects of template class multimap (page 328). Both
functions return lhs.size (page 334)() == rhs.size() && equal (page 255)(lhs.
begin (page 330)(), lhs. end (page 331)(), rhs.begin()).
operator<
template<class Key, class T, class Pred, class A>
bool operator<(
const map <Key, T, Pred, A>& lhs,
const map <Key, T, Pred, A>& rhs);
template<class Key, class T, class Pred, class A>
bool operator<(
const multimap <Key, T, Pred, A>& lhs,
const multimap <Key, T, Pred, A>& rhs);
The first template function overloads operator< to compare two objects of template
class multimap (page 328). The second template function overloads operator< to
compare two objects of template class multimap (page 328). Both functions return
lexicographical_compare(lhs. begin(), lhs. end(), rhs.begin(), rhs.end()).
335
Chapter 13. Standard Template Library C++
img
.
operator<=
template<class Key, class T, class Pred, class A>
bool operator<=(
const map <Key, T, Pred, A>& lhs,
const map <Key, T, Pred, A>& rhs);
template<class Key, class T, class Pred, class A>
bool operator<=(
const multimap <Key, T, Pred, A>& lhs,
const multimap <Key, T, Pred, A>& rhs);
The template function returns !(rhs < lhs).
operator>
template<class Key, class T, class Pred, class A>
bool operator>(
const map <Key, T, Pred, A>& lhs,
const map <Key, T, Pred, A>& rhs);
template<class Key, class T, class Pred, class A>
bool operator>(
const multimap <Key, T, Pred, A>& lhs,
const multimap <Key, T, Pred, A>& rhs);
The template function returns rhs < lhs.
operator>=
template<class Key, class T, class Pred, class A>
bool operator>=(
const map <Key, T, Pred, A>& lhs,
const map <Key, T, Pred, A>& rhs);
template<class Key, class T, class Pred, class A>
bool operator!=(
const multimap <Key, T, Pred, A>& lhs,
const multimap <Key, T, Pred, A>& rhs);
The template function returns !(lhs < rhs).
swap
template<class Key, class T, class Pred, class A>
void swap(
map <Key, T, Pred, A>& lhs,
map <Key, T, Pred, A>& rhs);
template<class Key, class T, class Pred, class A>
void swap(
multimap <Key, T, Pred, A>& lhs,
multimap <Key, T, Pred, A>& rhs);
The template function executes lhs.swap (page 327)(rhs).
Portions derived from work copyright © 1994 by Hewlett-Packard Company. All
rights reserved.
<memory>
namespace std {
template<class T>
class allocator;
template<>
class allocator<void>;
template<class FwdIt, class T>
class raw_storage_iterator;
336
Standard C++ Library
img
.
template<class T>
class auto_ptr;
// TEMPLATE OPERATORS
template<class T>
bool operator==(allocator<T>& lhs,
allocator<T>& rhs);
template<class T>
bool operator!=(allocator<T>& lhs,
allocator<T>& rhs);
// TEMPLATE FUNCTIONS
template<class T>
pair<T *, ptrdiff_t>
get_temporary_buffer(ptrdiff_t n);
template<class T>
void return_temporary_buffer(T *p);
template<class InIt, class FwdIt>
FwdIt uninitialized_copy(InIt first, InIt last,
FwdIt result);
template<class FwdIt, class T>
void uninitialized_fill(FwdIt first, FwdIt last,
const T& x);
template<class FwdIt, class Size, class T>
void uninitialized_fill_n(FwdIt first, Size n,
const T& x);
};
Include the STL (page 1) standard header <memory> to define a class, an operator,
and several templates that help allocate and free objects.
allocator
template<class T>
class allocator {
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef T *pointer;
typedef const T *const_pointer;
typedef T& reference;
typedef const T& const_reference;
typedef T value_type;
pointer address(reference x) const;
const_pointer address(const_reference x) const;
template<class U>
struct rebind;
allocator();
template<class U>
allocator(const allocator<U>& x);
template<class U>
allocator& operator=(const allocator<U>& x);
template<class U>
pointer allocate(size_type n, const U *hint = 0);
void deallocate(pointer p, size_type n);
void construct(pointer p, const T& val);
void destroy(pointer p);
size_type max_size() const;
};
The template class describes an object that manages storage allocation and freeing
for arrays of objects of type T. An object of class allocator is the default allocator
object specified in the constructors for several container template classes in the
Standard C++ library.
337
Chapter 13. Standard Template Library C++
img
....
Template class allocator supplies several type definitions that are rather
pedestrian. They hardly seem worth defining. But another class with the same
members might choose more interesting alternatives. Constructing a container with
an allocator object of such a class gives individual control over allocation and
freeing of elements controlled by that container.
For example, an allocator object might allocate storage on a private heap. Or it
might allocate storage on a far heap, requiring nonstandard pointers to access the
allocated objects. Or it might specify, through the type definitions it supplies, that
elements be accessed through special accessor objects that manage shared
memory, or perform automatic garbage collection. Hence, a class that allocates
storage using an allocator object should use these types religiously for declaring
pointer and reference objects (as do the containers in the Standard C++ library).
Thus, an allocator defines the types (among others):
pointer (page 339) -- behaves like a pointer to T
v
const_pointer (page 338) -- behaves like a const pointer to T
v
reference (page 340) -- behaves like a reference to T
v
const_reference (page 339) -- behaves like a const reference to T
v
These types specify the form that pointers and references must take for allocated
elements. (allocator::pointer is not necessarily the same as T * for all allocator
objects, even though it has this obvious definition for class allocator.)
allocator::address
pointer address(reference x) const;
const_pointer address(const_reference x) const;
The member functions return the address of x, in the form that pointers must take
for allocated elements.
allocator::allocate
template<class U>
pointer allocate(size_type n, const U *hint = 0);
The member function allocates storage for an array of n elements of type T, by
calling operator new(n). It returns a pointer to the allocated object. The hint
argument helps some allocators in improving locality of reference -- a valid choice
is the address of an object earlier allocated by the same allocator object, and not
yet deallocated. To supply no hint, use a null pointer argument instead.
allocator::allocator
allocator();
template<class U>
allocator(const allocator<U>& x);
The constructor does nothing. In general, however, an allocator object constructed
from another allocator object should compare equal to it (and hence permit
intermixing of object allocation and freeing between the two allocator objects).
allocator::const_pointer
typedef const T *pointer;
The pointer type describes an object p that can designate, via the expression *p,
any const object that an object of template class allocator can allocate.
338
Standard C++ Library
img
.
allocator::const_reference
typedef const T& const_reference;
The reference type describes an object x that can designate any const object that an
object of template class allocator can allocate.
allocator::construct
void construct(pointer p, const T& val);
The member function constructs an object of type T at p by evaluating the
placement new expression new ((void *)p) T(val).
allocator::deallocate
void deallocate(pointer p, size_type n);
The member function frees storage for the array of n objects of type T beginning at
p, by calling operator delete(p). The pointer p must have been earlier returned by
a call to allocate (page 338) for an allocator object that compares equal to *this,
allocating an array object of the same size and type. deallocate never throws an
exception.
allocator::destroy
void destroy(pointer p);
The member function destroys the object designated by p, by calling the destructor
p->T::~T().
allocator::difference_type
typedef ptrdiff_t difference_type;
The signed integer type describes an object that can represent the difference
between the addresses of any two elements in a sequence that an object of
template class allocator can allocate.
allocator::max_size
size_type max_size() const;
The member function returns the length of the longest sequence of elements of
type T that an object of class allocator might be able to allocate.
allocator::operator=
template<class U>
allocator& operator=(const allocator<U>& x);
The template assignment operator does nothing. In general, however, an allocator
object assigned to another allocator object should compare equal to it (and hence
permit intermixing of object allocation and freeing between the two allocator
objects).
allocator::pointer
typedef T *pointer;
The pointer type describes an object p that can designate, via the expression *p,
any object that an object of template class allocator can allocate.
339
Chapter 13. Standard Template Library C++
img
.....
allocator::rebind
template<class U>
struct rebind {
typedef allocator<U> other;
};
The member template class defines the type other. Its sole purpose is to provide
the type name allocator<U> given the type name allocator<T>.
For example, given an allocator object al of type A, you can allocate an object of
type U with the expression:
A::rebind<U>::other(al).allocate(1, (U *)0)
Or, you can simply name its pointer type by writing the type:
A::rebind<U>::other::pointer
allocator::reference
typedef T& reference;
The reference type describes an object x that can designate any object that an object
of template class allocator can allocate.
allocator::size_type
typedef size_t size_type;
The unsigned integer type describes an object that can represent the length of any
sequence that an object of template class allocator can allocate.
allocator::value_type
typedef T value_type;
The type is a synonym for the template parameter T.
allocator<void>
template<>
class allocator<void> {
typedef void *pointer;
typedef const void *const_pointer;
typedef void value_type;
template<class U>
struct rebind;
allocator();
template<class U>
allocator(const allocator<U>);
template<class U>
allocator<void>& operator=(const allocator<U>);
};
The class explicitly specializes template class allocator (page 337) for type void. Its
constructors and assignment operator behave the same as for the template class,
but it defines only the types const_pointer (page 338), pointer (page 339),
value_type (page 340), and the nested template class rebind (page 340).
auto_ptr
template<U>
struct auto_ptr_ref;
template<class T>
340
Standard C++ Library
img
.
class auto_ptr {
public:
typedef T element_type;
explicit auto_ptr(T *p = 0) throw();
auto_ptr(auto_ptr<T>& rhs) throw();
template<class U>
auto_ptr(auto_ptr<U>& rhs) throw();
auto_ptr(auto_ptr_ref<T> rhs) throw();
~auto_ptr();
template<class U>
operator auto_ptr<U>() throw();
template<class U>
operator auto_ptr_ref<U>() throw();
template<class U>
auto_ptr<T>& operator=(auto_ptr<U>& rhs) throw();
auto_ptr<T>& operator=(auto_ptr<T>& rhs) throw();
auto_ptr<T>& operator=(auto_ptr_ref<T>& rhs) throw();
T& operator*() const throw();
T *operator->() const throw();
T *get() const throw();
T *release() const throw();
void reset(T *p = 0);
};
The class describes an object that stores a pointer to an allocated object of type T.
The stored pointer must either be null or designate an object allocated by a new
expression. An object constructed with a non-null pointer owns the pointer. It
transfers ownership if its stored value is assigned to another object. (It replaces the
stored value after a transfer with a null pointer.) The destructor for auto_ptr<T>
deletes the allocated object if it owns it. Hence, an object of class auto_ptr<T>
ensures that an allocated object is automatically deleted when control leaves a
block, even via a thrown exception. You should not construct two auto_ptr<T>
objects that own the same object.
You can pass an auto_ptr<T> object by value as an argument to a function call. You
can return such an object by value as well. (Both operations depend on the implicit
construction of intermediate objects of class auto_ptr_ref<U>, by various subtle
conversion rules.) You cannot, however, reliably manage a sequence of auto_ptr<T>
objects with an STL container (page 41).
auto_ptr::auto_ptr
explicit auto_ptr(T *p = 0) throw();
auto_ptr(auto_ptr<T>& rhs) throw();
auto_ptr(auto_ptr_ref<T> rhs) throw();
template<class U>
auto_ptr(auto_ptr<U>& rhs) throw();
The first constructor stores p as the pointer to the allocated object. The second
constructor transfers ownership of the pointer stored in rhs, by storing
rhs.release(). in the constructed object. The third constructor behaves the same as
the second, except that it stores rhs.ref.release(), where ref is the reference
stored in rhs.
The template constructor behaves the same as the second constructor, provided
that a pointer to U can be implicitly converted to a pointer to T.
auto_ptr_ref
template<U>
struct auto_ptr_ref {
auto_ptr_ref(auto_ptr<U>& rhs);
};
341
Chapter 13. Standard Template Library C++
A helper class that describes an object that stores a reference to an object of class
auto_ptr<T>.
auto_ptr::~auto_ptr
~auto_ptr();
The destructor evaluates the expression delete q.
auto_ptr::element_type
typedef T element_type;
The type is a synonym for the template parameter T.
auto_ptr::get
T *get() const throw();
The member function returns the stored pointer.
auto_ptr::operator=
template<class U>
auto_ptr<T>& operator=(auto_ptr<U>& rhs) throw();
auto_ptr<T>& operator=(auto_ptr<>& rhs) throw();
auto_ptr<T>& operator=(auto_ptr_ref<>& rhs) throw();
The assignment evaluates the expression delete q, but only if the stored pointer
value q changes as a result of the assignment. It then transfers ownership of the
pointer stored in rhs, by storing rhs.release() in *this. The function returns
*this.
auto_ptr::operator*
T& operator*() const throw();
The indirection operator returns *get(). Hence, the stored pointer must not be
null.
auto_ptr::operator->
T *operator->() const throw();
The selection operator returns get(), so that the expression al->m behaves the
same as (al.get())->m, where al is an object of class auto_ptr<T>. Hence, the
stored pointer must not be null, and T must be a class, structure, or union type
with a member m.
auto_ptr::operator auto_ptr<U>
template<class U>
operator auto_ptr<U>() throw();
The type cast operator returns auto_ptr<U>(*this).
auto_ptr::operator auto_ptr_ref<U>
template<class U>
operator auto_ptr_ref<U>() throw();
The type cast operator returns auto_ptr_ref<U>(*this).
auto_ptr::release
T *release() throw();
342
Standard C++ Library
img
.
The member replaces the stored pointer with a null pointer and returns the
previously stored pointer.
auto_ptr::reset
void reset(T *p = 0);
The member function evaluates the expression delete q, but only if the stored
pointer value q changes as a result of function call. It then replaces the stored
pointer with p.
get_temporary_buffer
template<class T>
pair<T *, ptrdiff_t>
get_temporary_buffer(ptrdiff_t n);
The template function allocates storage for a sequence of at most n elements of
type T, from an unspecified source (which may well be the standard heap used by
operator new). It returns a value pr, of type pair<T *, ptrdiff_t>. If the function
allocates storage, pr.first designates the allocated storage and pr.second is the
number of elements in the longest sequence the storage can hold. Otherwise,
pr.first is a null pointer.
In this implementation (page 3), if a translator does not support member template
functions, the template:
template<class T>
pair<T *, ptrdiff_t>
get_temporary_buffer(ptrdiff_t n);
is replaced by:
template<class T>
pair<T *, ptrdiff_t>
get_temporary_buffer(ptrdiff_t n, T *);
operator!=
template<class T>
bool operator!=(allocator<T>& lhs,
allocator<T>& rhs);
The template operator returns false.
operator==
template<class T>
bool operator==(allocator<T>& lhs,
allocator<T>& rhs);
The template operator returns true. (Two allocator objects should compare equal
only if an object allocated through one can be deallocated through the other. If the
value of one object is determined from another by assignment or by construction,
the two object should compare equal.)
raw_storage_iterator
template<class FwdIt, class T>
class raw_storage_iterator
: public iterator<output_iterator_tag,
void, void, void, void> {
public:
343
Chapter 13. Standard Template Library C++
typedef FwdIt iter_type;
typedef T element_type;
explicit raw_storage_iterator(FwdIt it);
raw_storage_iterator<FwdIt, T>& operator*();
raw_storage_iterator<FwdIt, T>&
operator=(const T& val);
raw_storage_iterator<FwdIt, T>& operator++();
raw_storage_iterator<FwdIt, T> operator++(int);
};
The class describes an output iterator that constructs objects of type T in the
sequence it generates. An object of class raw_storage_iterator<FwdIt, T> accesses
storage through a forward iterator object, of class FwdIt, that you specify when you
construct the object. For an object it of class FwdIt, the expression &*it must
designate unconstructed storage for the next object (of type T) in the generated
sequence.
raw_storage_iterator::element_type
typedef T element_type;
The type is a synonym for the template parameter T.
raw_storage_iterator::iter_type
typedef FwdIt iter_type;
The type is a synonym for the template parameter FwdIt.
raw_storage_iterator::operator*
raw_storage_iterator<FwdIt, T>& operator*();
The indirection operator returns *this (so that operator=(const T&) can perform
the actual store in an expression such as *x = val).
raw_storage_iterator::operator=
raw_storage_iterator<FwdIt, T>& operator=(const T& val);
The assignment operator constructs the next object in the output sequence using
the stored iterator value it, by evaluating the placement new expression new ((void
*)&*it) T(val). The function returns *this.
raw_storage_iterator::operator++
raw_storage_iterator<FwdIt, T>& operator++();
raw_storage_iterator<FwdIt, T> operator++(int);
The first (preincrement) operator increments the stored output iterator object, then
returns *this.
The second (postincrement) operator makes a copy of *this, increments the stored
output iterator object, then returns the copy.
raw_storage_iterator::raw_storage_iterator
explicit raw_storage_iterator(FwdIt it);
The constructor stores it as the output iterator object.
return_temporary_buffer
template<class T>
void return_temporary_buffer(T *p);
344
Standard C++ Library
img
.
The template function frees the storage designated by p, which must be earlier
allocated by a call to get_temporary_buffer (page 343).
uninitialized_copy
template<class InIt, class FwdIt>
FwdIt uninitialized_copy(InIt first, InIt last,
FwdIt result);
The template function effectively executes:
while (first != last)
new ((void *)&*result++) U(*first++);
return first;
where U is iterator_traits<InIt>::value_type, unless the code throws an
exception. In that case, all constructed objects are destroyed and the exception is
rethrown.
uninitialized_fill
template<class FwdIt, class T>
void uninitialized_fill(FwdIt first, FwdIt last,
const T& x);
The template function effectively executes:
while (first != last)
new ((void *)&*first++) U(x);
where U is iterator_traits<FwdIt>::value_type, unless the code throws an
exception. In that case, all constructed objects are destroyed and the exception is
rethrown.
uninitialized_fill_n
template<class FwdIt, class Size, class T>
void uninitialized_fill_n(FwdIt first, Size n,
const T& x);
The template function effectively executes:
while (0 < n--)
new ((void *)&*first++) U(x);
where U is iterator_traits<FwdIt>::value_type, unless the code throws an
exception. In that case, all constructed objects are destroyed and the exception is
rethrown.
Portions derived from work copyright © 1994 by Hewlett-Packard Company. All rights
reserved.
<numeric>
namespace std {
template<class InIt, class T>
T accumulate(InIt first, InIt last, T val);
template<class InIt, class T, class Pred>
T accumulate(InIt first, InIt last, T val, Pred pr);
template<class InIt1, class InIt2, class T>
T inner_product(InIt1 first1, InIt1 last1,
Init2 first2, T val);
template<class InIt1, class InIt2, class T,
345
Chapter 13. Standard Template Library C++
img
..
class Pred1, class Pred2>
T inner_product(InIt1 first1, InIt1 last1,
Init2 first2, T val, Pred1 pr1, Pred2 pr2);
template<class InIt, class OutIt>
OutIt partial_sum(InIt first, InIt last,
OutIt result);
template<class InIt, class OutIt, class Pred>
OutIt partial_sum(InIt first, InIt last,
OutIt result, Pred pr);
template<class InIt, class OutIt>
OutIt adjacent_difference(InIt first, InIt last,
OutIt result);
template<class InIt, class OutIt, class Pred>
OutIt adjacent_difference(InIt first, InIt last,
OutIt result, Pred pr);
};
Include the STL (page 1) standard header <numeric> to define several template
functions useful for computing numeric values. The descriptions of these templates
employ a number of conventions (page 38) common to all algorithms.
accumulate
template<class InIt, class T>
T accumulate(InIt first, InIt last, T val);
template<class InIt, class T, class Pred>
T accumulate(InIt first, InIt last, T val, Pred pr);
The first template function repeatedly replaces val with val + *I, for each value of
the InIt iterator I in the interval [first, last). It then returns val.
The second template function repeatedly replaces val with pr(val, *I), for each
value of the InIt iterator I in the interval [first, last). It then returns val.
adjacent_difference
template<class InIt, class OutIt>
OutIt adjacent_difference(InIt first, InIt last,
OutIt result);
template<class InIt, class OutIt, class Pred>
OutIt adjacent_difference(InIt first, InIt last,
OutIt result, Pred pr);
The first template function stores successive values beginning at result, for each
value of the InIt iterator I in the interval [first, last). The first value val stored
(if any) is *I. Each subsequent value stored is *I - val, and val is replaced by *I.
The function returns result incremented last - first times.
The second template function stores successive values beginning at result, for
each value of the InIt iterator I in the interval [first, last). The first value val
stored (if any) is *I. Each subsequent value stored is pr(*I, val), and val is
replaced by *I. The function returns result incremented last - first times.
inner_product
template<class InIt1, class InIt2, class T>
T inner_product(InIt1 first1, InIt1 last1,
Init2 first2, T val);
template<class InIt1, class InIt2, class T,
class Pred1, class Pred2>
T inner_product(InIt1 first1, InIt1 last1,
Init2 first2, T val, Pred1 pr1, Pred2 pr2);
346
Standard C++ Library
img
.
The first template function repeatedly replaces val with val + (*I1 * *I2), for
each value of the InIt1 iterator I1 in the interval [first1, last2). In each case,
the InIt2 iterator I2 equals first2 + (I1 - first1). The function returns val.
The first template function repeatedly replaces val with pr1(val, pr2(*I1, *I2)),
for each value of the InIt1 iterator I1 in the interval [first1, last2). In each
case, the InIt2 iterator I2 equals first2 + (I1 - first1). The function returns
val.
partial_sum
template<class InIt, class
OutIt>
OutIt partial_sum(InIt
first, InIt last,
OutIt result);
template<class InIt, class
OutIt, class Pred>
OutIt partial_sum(InIt
first, InIt last,
OutIt result, Pred
pr);
The first template function stores successive values beginning at result, for each
value of the InIt iterator I in the interval [first, last). The first value val stored
(if any) is *I. Each subsequent value val stored is val + *I. The function returns
result incremented last - first times.
The second template function stores successive values beginning at result, for
each value of the InIt iterator I in the interval [first, last). The first value val
stored (if any) is *I. Each subsequent value val stored is pr(val, *I). The function
returns result incremented last - first times.
Portions derived from work copyright © 1994 by Hewlett-Packard Company. All rights
reserved.
<queue>
namespace std {
template<class T, class Cont>
class queue;
template<class T, class Cont, class Pred>
class priority_queue;
// TEMPLATE FUNCTIONS
template<class T, class Cont>
bool operator==(const queue<T, Cont>& lhs,
const queue<T, Cont>&);
template<class T, class Cont>
bool operator!=(const queue<T, Cont>& lhs,
const queue<T, Cont>&);
template<class T, class Cont>
bool operator<(const queue<T, Cont>& lhs,
const queue<T, Cont>&);
template<class T, class Cont>
bool operator>(const queue<T, Cont>& lhs,
const queue<T, Cont>&);
template<class T, class Cont>
bool operator<=(const queue<T, Cont>& lhs,
const queue<T, Cont>&);
template<class T, class Cont>
bool operator>=(const queue<T, Cont>& lhs,
const queue<T, Cont>&);
};
Include the STL (page 1) standard header <queue> to define the template classes
priority_queue and queue, and several supporting templates.
347
Chapter 13. Standard Template Library C++
img
....
operator!=
template<class T, class Cont>
bool operator!=(const queue <T, Cont>& lhs,
const queue <T, Cont>& rhs);
The template function returns !(lhs == rhs).
operator==
template<class T, class Cont>
bool operator==(const queue <T, Cont>& lhs,
const queue <T, Cont>& rhs);
The template function overloads operator== to compare two objects of template
class queue (page 351). The function returns lhs.c (page 351) == rhs.c.
operator<
template<class T, class Cont>
bool operator<(const queue <T, Cont>& lhs,
const queue <T, Cont>& rhs);
The template function overloads operator< to compare two objects of template
class queue (page 351). The function returns lhs.c (page 351) < rhs.c.
operator<=
template<class T, class Cont>
bool operator<=(const queue <T, Cont>& lhs,
const queue <T, Cont>& rhs);
The template function returns !(rhs < lhs).
operator>
template<class T, class Cont>
bool operator>(const queue <T, Cont>& lhs,
const queue <T, Cont>& rhs);
The template function returns rhs < lhs.
operator>=
template<class T, class Cont>
bool operator>=(const queue <T, Cont>& lhs,
const queue <T, Cont>& rhs);
The template function returns !(lhs < rhs).
priority_queue
template<class T,
class Cont = vector<T>,
class Pred = less<typename Cont::value_type> >
class priority_queue {
public:
typedef Cont container_type;
typedef typename Cont::value_type value_type;
typedef typename Cont::size_type size_type;
priority_queue();
explicit priority_queue(const Pred& pr);
priority_queue(const Pred& pr,
348
Standard C++ Library
img
...
const container_type& cont);
priority_queue(const priority_queue& x);
template<class InIt>
priority_queue(InIt first, InIt last);
template<class InIt>
priority_queue(InIt first, InIt last,
const Pred& pr);
template<class InIt>
priority_queue(InIt first, InIt last,
const Pred& pr, const container_type& cont);
bool empty() const;
size_type size() const;
const value_type& top() const;
void push(const value_type& x);
void pop();
protected:
Cont c;
Pred comp;
};
The template class describes an object that controls a varying-length sequence of
elements. The object allocates and frees storage for the sequence it controls through
a protected object named c, of class Cont. The type T of elements in the controlled
sequence must match value_type (page 351).
The sequence is ordered using a protected object named comp. After each insertion
or removal of the top element (at position zero), for the iterators P0 and Pi
designating elements at positions 0 and i, comp(*P0, *Pi) is false. (For the default
template parameter less<typename Cont::value_type> the top element of the
sequence compares largest, or highest priority.)
An object of class Cont must supply random-access iterators and several public
members defined the same as for deque (page 274) and vector (page 404) (both of
which are suitable candidates for class Cont). The required members are:
typedef T value_type;
typedef T0 size_type;
typedef T1 iterator;
Cont();
template<class InIt>
Cont(InIt first, InIt last);
template<class InIt>
void insert(iterator it, InIt first, InIt last);
iterator begin();
iterator end();
bool empty() const;
size_type size() const;
const value_type& front() const;
void push_back(const value_type& x);
void pop_back();
Here, T0 and T1 are unspecified types that meet the stated requirements.
priority_queue::container_type
typedef typename Cont::container_type container_type;
The type is a synonym for the template parameter Cont.
priority_queue::empty
bool empty() const;
The member function returns true for an empty controlled sequence.
349
Chapter 13. Standard Template Library C++
img
.
priority_queue::pop
void pop();
The member function removes the first element of the controlled sequence, which
must be non-empty, then reorders it.
priority_queue::priority_queue
priority_queue();
explicit priority_queue(const Pred& pr);
priority_queue(const Pred& pr,
const container_type& cont);
priority_queue(const priority_queue& x);
template<class InIt>
priority_queue(InIt first, InIt last);
template<class InIt>
priority_queue(InIt first, InIt last,
const Pred& pr);
template<class InIt>
priority_queue(InIt first, InIt last,
const Pred& pr, const container_type& cont);
All constructors with an argument cont initialize the stored object with c(cont).
The remaining constructors initialize the stored object with c, to specify an empty
initial controlled sequence. The last three constructors then call c.insert(c.end(),
first, last).
All constructors also store a function object in comp (page 349). The function object
pr is the argument pr, if present. For the copy constructor, it is x.comp. Otherwise,
it is Pred().
A non-empty initial controlled sequence is then ordered by calling
make_heap(c.begin(), c.end(), comp).
priority_queue::push
void push(const T& x);
The member function inserts an element with value x at the end of the controlled
sequence, then reorders it.
priority_queue::size
size_type size() const;
The member function returns the length of the controlled sequence.
priority_queue::size_type
typedef typename Cont::size_type size_type;
The type is a synonym for Cont::size_type.
priority_queue::top
const value_type& top() const;
The member function returns a reference to the first (highest priority) element of
the controlled sequence, which must be non-empty.
350
Standard C++ Library
img
...
priority_queue::value_type
typedef typename Cont::value_type value_type;
The type is a synonym for Cont::value_type.
queue
template<class T,
class Cont = deque<T> >
class queue {
public:
typedef Cont container_type;
typedef typename Cont::value_type value_type;
typedef typename Cont::size_type size_type;
queue();
explicit queue(const container_type& cont);
bool empty() const;
size_type size() const;
value_type& back();
const value_type& back() const;
value_type& front();
const value_type& front() const;
void push(const value_type& x);
void pop();
protected:
Cont c;
};
The template class describes an object that controls a varying-length sequence of
elements. The object allocates and frees storage for the sequence it controls through
a protected object named c, of class Cont. The type T of elements in the controlled
sequence must match value_type (page 352).
An object of class Cont must supply several public members defined the same as
for deque (page 274) and list (page 310) (both of which are suitable candidates for
class Cont). The required members are:
typedef T value_type;
typedef T0 size_type;
Cont();
bool empty() const;
size_type size() const;
value_type& front();
const value_type& front() const;
value_type& back();
const value_type& back() const;
void push_back(const value_type& x);
void pop_front();
bool operator==(const Cont& X) const;
bool operator!=(const Cont& X) const;
bool operator<(const Cont& X) const;
bool operator>(const Cont& X) const;
bool operator<=(const Cont& X) const;
bool operator>=(const Cont& X) const;
Here, T0 is an unspecified type that meets the stated requirements.
queue::back
value_type& back();
const value_type& back() const;
The member function returns a reference to the last element of the controlled
sequence, which must be non-empty.
351
Chapter 13. Standard Template Library C++
queue::container_type
typedef Cont container_type;
The type is a synonym for the template parameter Cont.
queue::empty
bool empty() const;
The member function returns true for an empty controlled sequence.
queue::front
value_type& front();
const value_type& front() const;
The member function returns a reference to the first element of the controlled
sequence, which must be non-empty.
queue::pop
void pop();
The member function removes the last element of the controlled sequence, which
must be non-empty.
queue::push
void push(const T& x);
The member function inserts an element with value x at the end of the controlled
sequence.
queue::queue
queue();
explicit queue(const container_type& cont);
The first constructor initializes the stored object with c(), to specify an empty
initial controlled sequence. The second constructor initializes the stored object with
c(cont), to specify an initial controlled sequence that is a copy of the sequence
controlled by cont.
queue::size
size_type size() const;
The member function returns the length of the controlled sequence.
queue::size_type
typedef typename Cont::size_type size_type;
The type is a synonym for Cont::size_type.
queue::value_type
typedef typename Cont::value_type value_type;
The type is a synonym for Cont::value_type.
Portions derived from work copyright © 1994 by Hewlett-Packard Company. All rights
reserved.
352
Standard C++ Library
img
<set>
namespace std {
template<class Key, class Pred, class A>
class set;
template<class Key, class Pred, class A>
class multiset;
// TEMPLATE FUNCTIONS
template<class Key, class Pred, class A>
bool operator==(
const set<Key, Pred, A>& lhs,
const set<Key, Pred, A>& rhs);
template<class Key, class Pred, class A>
bool operator==(
const multiset<Key, Pred, A>& lhs,
const multiset<Key, Pred, A>& rhs);
template<class Key, class Pred, class A>
bool operator!=(
const set<Key, Pred, A>& lhs,
const set<Key, Pred, A>& rhs);
template<class Key, class Pred, class A>
bool operator!=(
const multiset<Key, Pred, A>& lhs,
const multiset<Key, Pred, A>& rhs);
template<class Key, class Pred, class A>
bool operator<(
const set<Key, Pred, A>& lhs,
const set<Key, Pred, A>& rhs);
template<class Key, class Pred, class A>
bool operator<(
const multiset<Key, Pred, A>& lhs,
const multiset<Key, Pred, A>& rhs);
template<class Key, class Pred, class A>
bool operator>(
const set<Key, Pred, A>& lhs,
const set<Key, Pred, A>& rhs);
template<class Key, class Pred, class A>
bool operator>(
const multiset<Key, Pred, A>& lhs,
const multiset<Key, Pred, A>& rhs);
template<class Key, class Pred, class A>
bool operator<=(
const set<Key, Pred, A>& lhs,
const set<Key, Pred, A>& rhs);
template<class Key, class Pred, class A>
bool operator<=(
const multiset<Key, Pred, A>& lhs,
const multiset<Key, Pred, A>& rhs);
template<class Key, class Pred, class A>
bool operator>=(
const set<Key, Pred, A>& lhs,
const set<Key, Pred, A>& rhs);
template<class Key, class Pred, class A>
bool operator>=(
const multiset<Key, Pred, A>& lhs,
const multiset<Key, Pred, A>& rhs);
template<class Key, class Pred, class A>
void swap(
set<Key, Pred, A>& lhs,
set<Key, Pred, A>& rhs);
template<class Key, class Pred, class A>
void swap(
multiset<Key, Pred, A>& lhs,
multiset<Key, Pred, A>& rhs);
};
353
Chapter 13. Standard Template Library C++
img
.....................................
Include the STL (page 1) standard header <set> to define the container (page 41)
template classes set and multiset, and their supporting templates.
multiset
allocator_type (page 355) · begin (page 355) · clear (page 355) · const_iterator
(page 355) · const_pointer (page 355) · const_reference (page 356) ·
const_reverse_iterator (page 356) · count (page 356) · difference_type (page 356) ·
empty (page 356) · end (page 356) · equal_range (page 356) · erase (page 356) ·
find (page 357) · get_allocator (page 357) · insert (page 357) · iterator (page 357) ·
key_comp (page 357) · key_compare (page 357) · key_type (page 358) ·
lower_bound (page 358) · max_size (page 358) · multiset (page 358) · pointer
(page 358) · rbegin (page 358) · reference (page 359) · rend (page 359) ·
reverse_iterator (page 359) · size (page 359) · size_type (page 359) · swap (page
359) · upper_bound (page 359) · value_comp (page 359) · value_compare (page
360) · value_type (page 360)
template<class Key, class Pred = less<Key>,
class A = allocator<Key> >
class multiset {
public:
typedef Key key_type;
typedef Pred key_compare;
typedef Key value_type;
typedef Pred value_compare;
typedef A allocator_type;
typedef A::pointer pointer;
typedef A::const_pointer const_pointer;
typedef A::reference reference;
typedef A::const_reference const_reference;
typedef T0 iterator;
typedef T1 const_iterator;
typedef T2 size_type;
typedef T3 difference_type;
typedef reverse_iterator<const_iterator>
const_reverse_iterator;
typedef reverse_iterator<iterator> reverse_iterator;
multiset();
explicit multiset(const Pred& comp);
multiset(const Pred& comp, const A& al);
multiset(const multiset& x);
template<class InIt>
multiset(InIt first, InIt last);
template<class InIt>
multiset(InIt first, InIt last,
const Pred& comp);
template<class InIt>
multiset(InIt first, InIt last,
const Pred& comp, const A& al);
const_iterator begin() const;
const_iterator end() const;
const_reverse_iterator rbegin() const;
const_reverse_iterator rend() const;
size_type size() const;
size_type max_size() const;
bool empty() const;
A get_allocator() const;
iterator insert(const value_type& x);
iterator insert(iterator it, const value_type& x);
template<class InIt>
void insert(InIt first, InIt last);
iterator erase(iterator it);
iterator erase(iterator first, iterator last);
size_type erase(const Key& key);
void clear();
354
Standard C++ Library
img
.....
void swap(multiset& x);
key_compare key_comp() const;
value_compare value_comp() const;
const_iterator find(const Key& key) const;
size_type count(const Key& key) const;
const_iterator lower_bound(const Key& key) const;
const_iterator upper_bound(const Key& key) const;
pair<const_iterator, const_iterator>
equal_range(const Key& key) const;
};
The template class describes an object that controls a varying-length sequence of
elements of type const Key. The sequence is ordered by (page 39) the predicate
Pred. Each element serves as both a sort key and a value. The sequence is
represented in a way that permits lookup, insertion, and removal of an arbitrary
element with a number of operations proportional to the logarithm of the number
of elements in the sequence (logarithmic time). Moreover, inserting an element
invalidates no iterators, and removing an element invalidates only those iterators
which point at the removed element.
The object orders the sequence it controls by calling a stored function object of
type Pred. You access this stored object by calling the member function key_comp().
Such a function object must impose a total ordering (page 401) on sort keys of type
Key. For any element x that precedes y in the sequence, key_comp()(y, x) is false.
(For the default function object less<Key>, sort keys never decrease in value.)
Unlike template class set (page 361), an object of template class multiset does not
ensure that key_comp()(x, y) is true. (Keys need not be unique.)
The object allocates and frees storage for the sequence it controls through a stored
allocator object (page 337) of class A. Such an allocator object must have the same
external interface as an object of template class allocator (page 337). Note that the
stored allocator object is not copied when the container object is assigned.
multiset::allocator_type
typedef A allocator_type;
The type is a synonym for the template parameter A.
multiset::begin
const_iterator begin() const;
The member function returns a bidirectional iterator that points at the first element
of the sequence (or just beyond the end of an empty sequence).
multiset::clear
void clear();
The member function calls erase( begin(), iset::end()).
multiset::const_iterator
typedef T1 const_iterator;
The type describes an object that can serve as a constant bidirectional iterator for
the controlled sequence. It is described here as a synonym for the
implementation-defined type T1.
multiset::const_pointer
typedef A::const_pointer const_pointer;
355
Chapter 13. Standard Template Library C++
The type describes an object that can serve as a constant pointer to an element of
the controlled sequence.
multiset::const_reference
typedef A::const_reference const_reference;
The type describes an object that can serve as a constant reference to an element of
the controlled sequence.
multiset::const_reverse_iterator
typedef reverse_iterator<const_iterator>
const_reverse_iterator;
The type describes an object that can serve as a constant reverse bidirectional
iterator for the controlled sequence.
multiset::count
size_type count(const Key& key) const;
The member function returns the number of elements x in the range
[lower_bound(key), upper_bound(key)).
multiset::difference_type
typedef T3 difference_type;
The signed integer type describes an object that can represent the difference
between the addresses of any two elements in the controlled sequence. It is
described here as a synonym for the implementation-defined type T3.
multiset::empty
bool empty() const;
The member function returns true for an empty controlled sequence.
multiset::end
const_iterator end() const;
The member function returns a bidirectional iterator that points just beyond the
end of the sequence.
multiset::equal_range
pair<const_iterator, const_iterator>
equal_range(const Key& key) const;
The member function returns a pair of iterators x such that x.first ==
lower_bound(key) and x.second == upper_bound(key).
multiset::erase
iterator erase(iterator it);
iterator erase(iterator first, iterator last);
size_type erase(const Key& key);
The first member function removes the element of the controlled sequence pointed
to by it. The second member function removes the elements in the range [first,
last). Both return an iterator that designates the first element remaining beyond
any elements removed, or end() if no such element exists.
356
Standard C++ Library
img
..
The third member removes the elements with sort keys in the range
[lower_bound(key), upper_bound(key)). It returns the number of elements it
removes.
The member functions never throw an exception.
multiset::find
const_iterator find(const Key& key) const;
The member function returns an iterator that designates the earliest element in the
controlled sequence whose sort key has equivalent ordering (page 39) to key. If no
such element exists, the function returns end().
multiset::get_allocator
A get_allocator() const;
The member function returns the stored allocator object (page 337).
multiset::insert
iterator insert(const value_type& x);
iterator insert(iterator it, const value_type& x);
template<class InIt>
void insert(InIt first, InIt last);
The first member function inserts the element x in the controlled sequence, then
returns the iterator that designates the inserted element. The second member
function returns insert(x), using it as a starting place within the controlled
sequence to search for the insertion point. (Insertion can occur in amortized
constant time, instead of logarithmic time, if the insertion point immediately
follows it.) The third member function inserts the sequence of element values, for
each it in the range [first, last), by calling insert(*it).
If an exception is thrown during the insertion of a single element, the container is
left unaltered and the exception is rethrown. If an exception is thrown during the
insertion of multiple elements, the container is left in a stable but unspecified state
and the exception is rethrown.
multiset::iterator
typedef T0 iterator;
The type describes an object that can serve as a bidirectional iterator for the
controlled sequence. It is described here as a synonym for the
implementation-defined type T0.
multiset::key_comp
key_compare key_comp() const;
The member function returns the stored function object that determines the order
of elements in the controlled sequence. The stored object defines the member
function:
bool operator(const Key& x, const Key& y);
which returns true if x strictly precedes y in the sort order.
multiset::key_compare
typedef Pred key_compare;
357
Chapter 13. Standard Template Library C++
img
.
The type describes a function object that can compare two sort keys to determine
the relative order of two elements in the controlled sequence.
multiset::key_type
typedef Key key_type;
The type describes the sort key object which constitutes each element of the
controlled sequence.
multiset::lower_bound
const_iterator lower_bound(const Key& key) const;
The member function returns an iterator that designates the earliest element x in
the controlled sequence for which key_comp()(x, key) is false.
If no such element exists, the function returns end().
multiset::max_size
size_type max_size() const;
The member function returns the length of the longest sequence that the object can
control.
multiset::multiset
multiset();
explicit multiset(const Pred& comp);
multiset(const Pred& comp, const A& al);
multiset(const multiset& x);
template<class InIt>
multiset(InIt first, InIt last);
template<class InIt>
multiset(InIt first, InIt last,
const Pred& comp);
template<class InIt>
multiset(InIt first, InIt last,
const Pred& comp, const A& al);
All constructors store an allocator object (page 337) and initialize the controlled
sequence. The allocator object is the argument al, if present. For the copy
constructor, it is x.get_allocator(). Otherwise, it is A().
All constructors also store a function object that can later be returned by calling
key_comp(). The function object is the argument comp, if present. For the copy
constructor, it is x.key_comp()). Otherwise, it is Pred().
The first three constructors specify an empty initial controlled sequence. The fourth
constructor specifies a copy of the sequence controlled by x. The last three
constructors specify the sequence of element values [first, last).
multiset::pointer
typedef A::pointer pointer;
The type describes an object that can serve as a pointer to an element of the
controlled sequence.
multiset::rbegin
const_reverse_iterator rbegin() const;
358
Standard C++ Library
The member function returns a reverse bidirectional iterator that points just
beyond the end of the controlled sequence. Hence, it designates the beginning of
the reverse sequence.
multiset::reference
typedef A::reference reference;
The type describes an object that can serve as a reference to an element of the
controlled sequence.
multiset::rend
const_reverse_iterator rend() const;
The member function returns a reverse bidirectional iterator that points at the first
element of the sequence (or just beyond the end of an empty sequence). Hence, it
designates the end of the reverse sequence.
multiset::reverse_iterator
typedef reverse_iterator<iterator> reverse_iterator;
The type describes an object that can serve as a reverse bidirectional iterator for the
controlled sequence.
multiset::size
size_type size() const;
The member function returns the length of the controlled sequence.
multiset::size_type
typedef T2 size_type;
The unsigned integer type describes an object that can represent the length of any
controlled sequence. It is described here as a synonym for the
implementation-defined type T2.
multiset::swap
void swap(multiset& x);
The member function swaps the controlled sequences between *this and x. If
get_allocator() == x.get_allocator(), it does so in constant time, it throws an
exception only as a result of copying the stored function object of type Pred, and it
invalidates no references, pointers, or iterators that designate elements in the two
controlled sequences. Otherwise, it performs a number of element assignments and
constructor calls proportional to the number of elements in the two controlled
sequences.
multiset::upper_bound
const_iterator upper_bound(const Key& key) const;
The member function returns an iterator that designates the earliest element x in
the controlled sequence for which key_comp()(key, x) is true.
If no such element exists, the function returns end().
multiset::value_comp
value_compare value_comp() const;
359
Chapter 13. Standard Template Library C++
img
........
The member function returns a function object that determines the order of
elements in the controlled sequence.
multiset::value_compare
typedef Pred value_compare;
The type describes a function object that can compare two elements as sort keys to
determine their relative order in the controlled sequence.
multiset::value_type
typedef Key value_type;
The type describes an element of the controlled sequence.
operator!=
template<class Key, class Pred, class A>
bool operator!=(
const set <Key, Pred, A>& lhs,
const set <Key, Pred, A>& rhs);
template<class Key, class Pred, class A>
bool operator!=(
const multiset <Key, Pred, A>& lhs,
const multiset <Key, Pred, A>& rhs);
The template function returns !(lhs == rhs).
operator==
template<class Key, class Pred, class A>
bool operator==(
const set <Key, Pred, A>& lhs,
const set <Key, Pred, A>& rhs);
template<class Key, class Pred, class A>
bool operator==(
const multiset <Key, Pred, A>& lhs,
const multiset <Key, Pred, A>& rhs);
The first template function overloads operator== to compare two objects of
template class multiset (page 354). The second template function overloads
operator== to compare two objects of template class multiset (page 354). Both
functions return lhs.size (page 359)() == rhs.size() && equal (page 255)(lhs.
begin (page 355)(), lhs. end (page 356)(), rhs.begin()).
operator<
template<class Key, class Pred, class A>
bool operator<(
const set <Key, Pred, A>& lhs,
const set <Key, Pred, A>& rhs);
template<class Key, class Pred, class A>
bool operator<(
const multiset <Key, Pred, A>& lhs,
const multiset <Key, Pred, A>& rhs);
The first template function overloads operator< to compare two objects of template
class multiset (page 354). The second template function overloads operator< to
compare two objects of template class multiset (page 354). Both functions return
lexicographical_compare(lhs. begin(), lhs. end(), rhs.begin(), rhs.end()).
360
Standard C++ Library
img
...................................
operator<=
template<class Key, class Pred, class A>
bool operator<=(
const set <Key, Pred, A>& lhs,
const set <Key, Pred, A>& rhs);
template<class Key, class Pred, class A>
bool operator<=(
const multiset <Key, Pred, A>& lhs,
const multiset <Key, Pred, A>& rhs);
The template function returns !(rhs < lhs).
operator>
template<class Key, class Pred, class A>
bool operator>(
const set <Key, Pred, A>& lhs,
const set <Key, Pred, A>& rhs);
template<class Key, class Pred, class A>
bool operator>(
const multiset <Key, Pred, A>& lhs,
const multiset <Key, Pred, A>& rhs);
The template function returns rhs < lhs.
operator>=
template<class Key, class Pred, class A>
bool operator>=(
const set <Key, Pred, A>& lhs,
const set <Key, Pred, A>& rhs);
template<class Key, class Pred, class A>
bool operator>=(
const multiset <Key, Pred, A>& lhs,
const multiset <Key, Pred, A>& rhs);
The template function returns !(lhs < rhs).
set
allocator_type (page 363) · begin (page 363) · clear (page 363) · const_iterator
(page 363) · const_pointer (page 363) · const_reference (page 363) ·
const_reverse_iterator (page 363) · count (page 363) · difference_type (page 363) ·
empty (page 364) · end (page 364) · equal_range (page 364) · erase (page 364) ·
find (page 364) · get_allocator (page 364) · insert (page 364) · iterator (page 365) ·
key_comp (page 365) · key_compare (page 365) · key_type (page 365) ·
lower_bound (page 365) · max_size (page 365) · pointer (page 366) · rbegin (page
366) · reference (page 366) · rend (page 366) · reverse_iterator (page 366) · set
(page 366) · size (page 367) · size_type (page 367) · swap (page 367) ·
upper_bound (page 367) · value_comp (page 367) · value_compare (page 367) ·
value_type (page 367)
template<class Key, class Pred = less<Key>,
class A = allocator<Key> >
class set {
public:
typedef Key key_type;
typedef Pred key_compare;
typedef Key value_type;
typedef Pred value_compare;
typedef A allocator_type;
typedef A::pointer pointer;
typedef A::const_pointer const_pointer;
361
Chapter 13. Standard Template Library C++
img
...
typedef A::reference reference;
typedef A::const_reference const_reference;
typedef T0 iterator;
typedef T1 const_iterator;
typedef T2 size_type;
typedef T3 difference_type;
typedef reverse_iterator<const_iterator>
const_reverse_iterator;
typedef reverse_iterator<iterator> reverse_iterator;
set();
explicit set(const Pred& comp);
set(const Pred& comp, const A& al);
set(const set& x);
template<class InIt>
set(InIt first, InIt last);
template<class InIt>
set(InIt first, InIt last,
const Pred& comp);
template<class InIt>
set(InIt first, InIt last,
const Pred& comp, const A& al);
const_iterator begin() const;
const_iterator end() const;
const_reverse_iterator rbegin() const;
const_reverse_iterator rend() const;
size_type size() const;
size_type max_size() const;
bool empty() const;
A get_allocator() const;
pair<iterator, bool> insert(const value_type& x);
iterator insert(iterator it, const value_type& x);
template<class InIt>
void insert(InIt first, InIt last);
iterator erase(iterator it);
iterator erase(iterator first, iterator last);
size_type erase(const Key& key);
void clear();
void swap(set& x);
key_compare key_comp() const;
value_compare value_comp() const;
const_iterator find(const Key& key) const;
size_type count(const Key& key) const;
const_iterator lower_bound(const Key& key) const;
const_iterator upper_bound(const Key& key) const;
pair<const_iterator, const_iterator>
equal_range(const Key& key) const;
};
The template class describes an object that controls a varying-length sequence of
elements of type const Key. The sequence is ordered by (page 39) the predicate
Pred. Each element serves as both a sort key and a value. The sequence is
represented in a way that permits lookup, insertion, and removal of an arbitrary
element with a number of operations proportional to the logarithm of the number
of elements in the sequence (logarithmic time). Moreover, inserting an element
invalidates no iterators, and removing an element invalidates only those iterators
which point at the removed element.
The object orders the sequence it controls by calling a stored function object of
type Pred. You access this stored object by calling the member function key_comp().
Such a function object must impose a total ordering (page 401) on sort keys of type
Key. For any element x that precedes y in the sequence, key_comp()(y, x) is false.
(For the default function object less<Key>, sort keys never decrease in value.)
Unlike template class multiset (page 354), an object of template class set ensures
that key_comp()(x, y) is true. (Each key is unique.)
362
Standard C++ Library
img
..
The object allocates and frees storage for the sequence it controls through a stored
allocator object (page 337) of class A. Such an allocator object must have the same
external interface as an object of template class allocator (page 337). Note that the
stored allocator object is not copied when the container object is assigned.
set::allocator_type
typedef A allocator_type;
The type is a synonym for the template parameter A.
set::begin
const_iterator begin() const;
The member function returns a bidirectional iterator that points at the first element
of the sequence (or just beyond the end of an empty sequence).
set::clear
void clear();
The member function calls erase( begin(), end()).
set::const_iterator
typedef T1 const_iterator;
The type describes an object that can serve as a constant bidirectional iterator for
the controlled sequence. It is desciibed here as a synonym for the
implementation-defined type T1.
set::const_pointer
typedef A::const_pointer const_pointer;
The type describes an object that can serve as a constant pointer to an element of
the controlled sequence.
set::const_reference
typedef A::const_reference const_reference;
The type describes an object that can serve as a constant reference to an element of
the controlled sequence.
set::const_reverse_iterator
typedef reverse_iterator<const_iterator>
const_reverse_iterator;
The type describes an object that can serve as a constant reverse bidirectional
iterator for the controlled sequence.
set::count
size_type count(const Key& key) const;
The member function returns the number of elements x in the range
[lower_bound(key), upper_bound(key)).
set::difference_type
typedef T3 difference_type;
363
Chapter 13. Standard Template Library C++
img
..
The signed integer type describes an object that can represent the difference
between the addresses of any two elements in the controlled sequence. It is
desciibed here as a synonym for the implementation-defined type T3.
set::empty
bool empty() const;
The member function returns true for an empty controlled sequence.
set::end
const_iterator end() const;
The member function returns a bidirectional iterator that points just beyond the
end of the sequence.
set::equal_range
pair<const_iterator, const_iterator>
equal_range(const Key& key) const;
The member function returns a pair of iterators x such that x.first ==
lower_bound(key) and x.second == upper_bound(key).
set::erase
iterator erase(iterator it);
iterator erase(iterator first, iterator last);
size_type erase(const Key& key);
The first member function removes the element of the controlled sequence pointed
to by it. The second member function removes the elements in the range [first,
last). Both return an iterator that designates the first element remaining beyond
any elements removed, or end() if no such element exists.
The third member removes the elements with sort keys in the range
[lower_bound(key), upper_bound(key)). It returns the number of elements it
removes.
The member functions never throw an exception.
set::find
const_iterator find(const Key& key) const;
The member function returns an iterator that designates the earliest element in the
controlled sequence whose sort key has equivalent ordering (page 39) to key. If no
such element exists, the function returns end().
set::get_allocator
A get_allocator() const;
The member function returns the stored allocator object.
set::insert
pair<iterator, bool> insert(const value_type& x);
iterator insert(iterator it, const value_type& x);
template<class InIt>
void insert(InIt first, InIt last);
The first member function determines whether an element y exists in the sequence
whose key has equivalent ordering (page 39) to that of x. If not, it creates such an
364
Standard C++ Library
element y and initializes it with x. The function then determines the iterator it that
designates y. If an insertion occurred, the function returns pair(it, true).
Otherwise, it returns pair(it, false).
The second member function returns insert(x), using it as a starting place within
the controlled sequence to search for the insertion point. (Insertion can occur in
amortized constant time, instead of logarithmic time, if the insertion point
immediately follows it.) The third member function inserts the sequence of
element values, for each it in the range [first, last), by calling insert(*it).
If an exception is thrown during the insertion of a single element, the container is
left unaltered and the exception is rethrown. If an exception is thrown during the
insertion of multiple elements, the container is left in a stable but unspecified state
and the exception is rethrown.
set::iterator
typedef T0 iterator;
The type describes an object that can serve as a bidirectional iterator for the
controlled sequence. It is described here as a synonym for the
implementation-defined type T0.
set::key_comp
key_compare key_comp() const;
The member function returns the stored function object that determines the order
of elements in the controlled sequence. The stored object defines the member
function:
bool operator(const Key& x, const Key& y);
which returns true if x strictly precedes y in the sort order.
set::key_compare
typedef Pred key_compare;
The type describes a function object that can compare two sort keys to determine
the relative order of two elements in the controlled sequence.
set::key_type
typedef Key key_type;
The type describes the sort key object which constitutes each element of the
controlled sequence.
set::lower_bound
const_iterator lower_bound(const Key& key) const;
The member function returns an iterator that designates the earliest element x in
the controlled sequence for which key_comp()(x, key) is false.
If no such element exists, the function returns end().
set::max_size
size_type max_size() const;
365
Chapter 13. Standard Template Library C++
img
.
The member function returns the length of the longest sequence that the object can
control.
set::pointer
typedef A::const_pointer pointer;
The type describes an object that can serve as a pointer to an element of the
controlled sequence.
set::rbegin
const_reverse_iterator rbegin() const;
The member function returns a reverse bidirectional iterator that points just
beyond the end of the controlled sequence. Hence, it designates the beginning of
the reverse sequence.
set::reference
typedef A::const_reference reference;
The type describes an object that can serve as a reference to an element of the
controlled sequence.
set::rend
const_reverse_iterator rend() const;
The member function returns a reverse bidirectional iterator that points at the first
element of the sequence (or just beyond the end of an empty sequence). Hence, it
designates the end of the reverse sequence.
set::reverse_iterator
typedef reverse_iterator<iterator> reverse_iterator;
The type describes an object that can serve as a reverse bidirectional iterator for the
controlled sequence.
set::set
set();
explicit set(const Pred& comp);
set(const Pred& comp, const A& al);
set(const set& x);
template<class InIt>
set(InIt first, InIt last);
template<class InIt>
set(InIt first, InIt last,
const Pred& comp);
template<class InIt>
set(InIt first, InIt last,
const Pred& comp, const A& al);
All constructors store an allocator object (page 337) and initialize the controlled
sequence. The allocator object is the argument al, if present. For the copy
constructor, it is x.get_allocator(). Otherwise, it is A().
All constructors also store a function object that can later be returned by calling
key_comp(). The function object is the argument comp, if present. For the copy
constructor, it is x.key_comp()). Otherwise, it is Pred().
366
Standard C++ Library
The first three constructors specify an empty initial controlled sequence. The fourth
constructor specifies a copy of the sequence controlled by x. The last three
constructors specify the sequence of element values [first, last).
set::size
size_type size() const;
The member function returns the length of the controlled sequence.
set::size_type
typedef T2 size_type;
The unsigned integer type describes an object that can represent the length of any
controlled sequence. It is desciibed here as a synonym for the implementation-
defined type T2.
set::swap
void swap(set& x);
The member function swaps the controlled sequences between *this and x. If
get_allocator() == x.get_allocator(), it does so in constant time, it throws an
exception only as a result of copying the stored function object of type Pred, and it
invalidates no references, pointers, or iterators that designate elements in the two
controlled sequences. Otherwise, it performs a number of element assignments and
constructor calls proportional to the number of elements in the two controlled
sequences.
set::upper_bound
const_iterator upper_bound(const Key& key) const;
The member function returns an iterator that designates the earliest element x in
the controlled sequence for which key_comp()(key, x) is true.
If no such element exists, the function returns end().
set::value_comp
value_compare value_comp() const;
The member function returns a function object that determines the order of
elements in the controlled sequence.
set::value_compare
typedef Pred value_compare;
The type describes a function object that can compare two elements as sort keys to
determine their relative order in the controlled sequence.
set::value_type
typedef Key value_type;
The type describes an element of the controlled sequence.
swap
template<class Key, class Pred, class A>
void swap(
multiset <Key, Pred, A>& lhs,
multiset <Key, Pred, A>& rhs);
367
Chapter 13. Standard Template Library C++
img
..
template<class Key, class Pred, class A>
void swap(
set <Key, Pred, A>& lhs,
set <Key, Pred, A>& rhs);
The template function executes lhs.swap(rhs).
Portions derived from work copyright © 1994 by Hewlett-Packard Company. All rights
reserved.
<stack>
namespace std {
template<class T, class Cont>
class stack;
// TEMPLATE FUNCTIONS
template<class T, class Cont>
bool operator==(const stack<T, Cont>& lhs,
const stack<T, Cont>&);
template<class T, class Cont>
bool operator!=(const stack<T, Cont>& lhs,
const stack<T, Cont>&);
template<class T, class Cont>
bool operator<(const stack<T, Cont>& lhs,
const stack<T, Cont>&);
template<class T, class Cont>
bool operator>(const stack<T, Cont>& lhs,
const stack<T, Cont>&);
template<class T, class Cont>
bool operator<=(const stack<T, Cont>& lhs,
const stack<T, Cont>&);
template<class T, class Cont>
bool operator>=(const stack<T, Cont>& lhs,
const stack<T, Cont>&);
};
Include the STL (page 1) standard header <stack> to define the template class
stack and two supporting templates.
operator!=
template<class T, class Cont>
bool operator!=(const stack <T, Cont>& lhs,
const stack <T, Cont>& rhs);
The template function returns !(lhs == rhs).
operator==
template<class T, class Cont>
bool operator==(const stack <T, Cont>& lhs,
const stack <T, Cont>& rhs);
The template function overloads operator== to compare two objects of template
class stack (page 369). The function returns lhs.c == rhs.c.
operator<
template<class T, class Cont>
bool operator<(const stack <T, Cont>& lhs,
const stack <T, Cont>& rhs);
368
Standard C++ Library
img
.....
The template function overloads operator< to compare two objects of template
class stack (page 369). The function returns lhs.c < rhs.c.
operator<=
template<class T, class Cont>
bool operator<=(const stack <T, Cont>& lhs,
const stack <T, Cont>& rhs);
The template function returns !(rhs < lhs).
operator>
template<class T, class Cont>
bool operator>(const stack <T, Cont>& lhs,
const stack <T, Cont>& rhs);
The template function returns rhs < lhs.
operator>=
template<class T, class Cont>
bool operator>=(const stack <T, Cont>& lhs,
const stack <T, Cont>& rhs);
The template function returns !(lhs < rhs).
stack
template<class T,
class Cont = deque<T> >
class stack {
public:
typedef Cont container_type;
typedef typename Cont::value_type value_type;
typedef typename Cont::size_type size_type;
stack();
explicit stack(const container_type& cont);
bool empty() const;
size_type size() const;
value_type& top();
const value_type& top() const;
void push(const value_type& x);
void pop();
protected:
Cont c;
};
The template class describes an object that controls a varying-length sequence of
elements. The object allocates and frees storage for the sequence it controls through
a protected object named c, of class Cont. The type T of elements in the controlled
sequence must match value_type (page 371).
An object of class Cont must supply several public members defined the same as
for deque (page 274), list (page 310), and vector (page 404) (all of which are
suitable candidates for class Cont). The required members are:
typedef T value_type;
typedef T0 size_type;
Cont();
bool empty() const;
size_type size() const;
value_type& back();
const value_type& back() const;
369
Chapter 13. Standard Template Library C++
void push_back(const value_type& x);
void pop_back();
bool operator==(const Cont& X) const;
bool operator!=(const Cont& X) const;
bool operator<(const Cont& X) const;
bool operator>(const Cont& X) const;
bool operator<=(const Cont& X) const;
bool operator>=(const Cont& X) const;
Here, T0 is an unspecified type that meets the stated requirements.
stack::container_type
typedef Cont container_type;
The type is a synonym for the template parameter Cont.
stack::empty
bool empty() const;
The member function returns true for an empty controlled sequence.
stack::pop
void pop();
The member function removes the last element of the controlled sequence, which
must be non-empty.
stack::push
void push(const T& x);
The member function inserts an element with value x at the end of the controlled
sequence.
stack::size
size_type size() const;
The member function returns the length of the controlled sequence.
stack::size_type
typedef typename Cont::size_type size_type;
The type is a synonym for Cont::size_type.
stack::stack
stack();
explicit stack(const container_type& cont);
The first constructor initializes the stored object with c(), to specify an empty
initial controlled sequence. The second constructor initializes the stored object with
c(cont), to specify an initial controlled sequence that is a copy of the sequence
controlled by cont.
stack::top
value_type& top();
const value_type& top() const;
The member function returns a reference to the last element of the controlled
sequence, which must be non-empty.
370
Standard C++ Library
img
..........................................
stack::value_type
typedef typename Cont::value_type value_type;
The type is a synonym for Cont::value_type.
Portions derived from work copyright © 1994 by Hewlett-Packard Company. All
rights reserved.
<unordered_map>
Note: To enable this header file, you must define the macro _VACPP_TR1.
namespace std {
namespace tr1 {
template <class Key,
class T,
class Hash = hash<Key>,
class Pred = std::equal_to<Key>,
class Alloc = std::allocator<std::pair<const Key, T> > >
class unordered_map;
template <class Key,
class T,
class Hash = hash<Key>,
class Pred = std::equal_to<Key>,
class Alloc = std::allocator<std::pair<const Key, T> > >
class unordered_multimap;
}
}
Include the STL (page 1) standard header <unordered_map> to define the container
(page 41) template classes unordered_map and unordered_multimap, and their
supporting templates.
unordered_map
allocator_type (page 373) · begin (page 373) · bucket (page 373) · bucket_count
(page 374) · bucket_size (page 374) · clear (page 374) · const_iterator (page 374) ·
const_local_iterator (page 374) · const_pointer (page 374) · const_reference (page
374) · count (page 374) · difference_type (page 374) · empty (page 375) · end (page
375) · equal_range (page 375) · erase (page 375) · find (page 375) · get_allocator
(page 375) · hash_function (page 375) · hasher (page 375) · insert (page 376) ·
iterator (page 376) · key_eq (page 376) · key_equal (page 376) · key_type (page
376) · load_factor (page 376) · local_iterator (page 376) · mapped_type (page 377) ·
max_bucket_count (page 377) · max_load_factor (page 377) · max_size (page 377) ·
operator[] (page 377) · pointer (page 377) · reference (page 377) · rehash (page
377) · size (page 378) · size_type (page 378) · swap (page 378) · unordered_map
(page 378) · value_type (page 378)
namespace std {
namespace tr1 {
template <class Key,
class T,
class Hash  = hash<Key>,
class Pred  = std::equal_to<Key>,
class A= std::allocator<std::pair<const Key, T> > >
class unordered_map
{
public:
// types
typedef Key
key_type;
typedef std::pair<const Key, T>
value_type;
371
Chapter 13. Standard Template Library C++
typedef
T
mapped_type;
typedef
Hash
hasher;
typedef
Pred
key_equal;
typedef
A
allocator_type;
typedef
typename
A::pointer
pointer;
typedef
typename
A::const_pointer
const_pointer;
typedef
typename
A::reference
reference;
typedef
typename
A::const_reference const_reference;
typedef
T0
size_type;
typedef
T1
difference_type;
typedef
T2
iterator;
typedef
T3
const_iterator;
typedef
T4
local_iterator;
typedef
T5
const_local_iterator;
// construct/destroy/copy
explicit unordered_map(size_type n = 3,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
template <class InputIterator>
unordered_map(InputIterator f, InputIterator l,
size_type n = 3,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
unordered_map(const unordered_map&);
~unordered_map();
unordered_map& operator=(const unordered_map&);
A get_allocator() const;
// size and capacity
bool empty() const;
size_type size() const;
size_type max_size() const;
// iterators
iterator
begin();
const_iterator
begin() const;
iterator
end();
const_iterator
end() const;
// modifiers
std::pair<iterator, bool> insert(const value_type& obj);
iterator insert(const_iterator hint, const value_type& obj);
template <class InputIterator>
void insert(InputIterator first, InputIterator last);
void erase(const_iterator position);
size_type erase(const key_type& k);
void erase(const_iterator first, const_iterator last);
void clear();
void swap(unordered_map&);
// observers
hasher hash_function() const;
key_equal key_eq() const;
// lookup
iterator
find(const key_type& k);
const_iterator find(const key_type& k) const;
size_type count(const key_type& k) const;
std::pair<iterator, iterator>
equal_range(const key_type& k);
std::pair<const_iterator, const_iterator>
372
Standard C++ Library
img
..
equal_range(const key_type& k) const;
mapped_type& operator[](const key_type& k);
// bucket interface
size_type bucket_count() const;
size_type max_bucket_count() const;
size_type bucket_size(size_type n) const;
size_type bucket(const key_type& k) const;
local_iterator begin(size_type n);
const_local_iterator begin(size_type n) const;
local_iterator end(size_type n);
const_local_iterator end(size_type n) const;
// hash policy
float load_factor() const;
float max_load_factor() const;
void max_load_factor(float z);
void rehash(size_type n);
};
template <class Key, class T, class Hash, class Pred, class Alloc>
void swap(const unordered_map<Key, T, Hash, Pred, Alloc>& x,
const unordered_map<Key, T, Hash, Pred, Alloc>& y);
}
}
The template class describes an object that controls a varying-length sequence of
elements of type pair<const Key, T>. The sequence is unordered. The first element
of each pair is the sort key and the second is its associated value. If you have an
optimal hash function, the number of operations performed during lookup,
insertion, and removal of an arbitrary element does not depend on the number of
elements in the sequence. Moreover, inserting an element invalidates no iterators,
and removing an element invalidates only those iterators which point at the
removed element.
The object allocates and frees storage for the sequence it controls through a stored
allocator object (page 337) of class A. Such an allocator object must have the same
external interface as an object of template class allocator (page 337). Note that the
stored allocator object is not copied when the container object is assigned.
unordered_map::allocator_type
typedef A allocator_type;
The type is a synonym for the template parameter A.
unordered_map::begin
iterator begin();
const_iterator begin() const;
local_iterator begin(size_type n);
const_local_iterator begin(size_type n) const;
The member function returns a bidirectional iterator that points at the first element
of the sequence (or just beyond the end of an empty sequence).
unordered_map::bucket
size_type bucket(const key_type& k) const;
The member function returns the index of the bucket that contains the specified
key.
373
Chapter 13. Standard Template Library C++
unordered_map::bucket_count
size_type bucket_count() const;
The member function returns the number of buckets that the unordered map
contains.
unordered_map::bucket_size
size_type bucket_size(size_type n) const;
The member function returns the number of elements in the nth bucket.
unordered_map::clear
void clear();
The member function calls erase( begin(), end()).
unordered_map::const_iterator
typedef T3 const_iterator;
The type describes an object that can serve as a constant bidirectional iterator for
the controlled sequence. It is described here as a synonym for the
implementation-defined type T3.
unordered_map::const_local_iterator
typedef T5 const_local_iterator;
The type describes an object that can serve as a constant bidirectional iterator for
the controlled sequence. It is described here as a synonym for the
implementation-defined type T5.
unordered_map::const_pointer
typedef typename A::const_pointer const_pointer;
The type describes an object that can serve as a constant pointer to an element of
the controlled sequence.
unordered_map::const_reference
typedef typename A::const_reference const_reference;
The type describes an object that can serve as a constant reference to an element of
the controlled sequence.
unordered_map::count
size_type count(const key_type& k) const;
The member function returns the number of elements in the map that have a key
equivalent to k, based on the key_eq function.
unordered_map::difference_type
typedef T1 difference_type;
The signed integer type describes an object that can represent the difference
between the addresses of any two elements in the controlled sequence. It is
described here as a synonym for the implementation-defined type T1.
374
Standard C++ Library
img
..
unordered_map::empty
bool empty() const;
The member function returns true for an empty controlled sequence.
unordered_map::end
const_iterator end() const;
iterator end();
local_iterator end(size_type n);
const_local_iterator end(size_type n) const;
The member function returns a bidirectional iterator that points just beyond the
end of the sequence.
unordered_map::equal_range
std::pair<iterator, iterator>
equal_range(const key_type& k);
std::pair<const_iterator, const_iterator>
equal_range(const key_type& k) const;
The member function returns a range that contains all of the elements with the
specified key. It returns make_pair(end(), end()) if no such elements exist.
unordered_map::erase
void erase(const_iterator position);
size_type erase(const key_type& k);
void erase(const_iterator first, const_iterator last);
The first member function removes the element of the controlled sequence pointed
to by it. The second member function removes the elements in the interval
[first, last). Both return an iterator that designates the first element remaining
beyond any elements removed, or end() if no such element exists.
The third member function removes all the elements in the map. It returns the
number of elements it removes.
The member functions never throw an exception.
unordered_map::find
iterator
find(const key_type& k);
const_iterator find(const key_type& k) const;
The member function returns an iterator that designates the earliest element in the
controlled sequence whose sort key has equivalent ordering (page 39) to key. If no
such element exists, the function returns end().
unordered_map::get_allocator
A get_allocator() const;
The member function returns the stored allocator object (page 337).
unordered_map::hasher
typedef Hash hasher;
The type returns a value of type std::size_t.
unordered_map::hash_function
hasher hash_function() const;
375
Chapter 13. Standard Template Library C++
img
.
The member function returns the hash function that was used to construct the
map.
unordered_map::insert
std::pair<iterator, bool> insert(const value_type& obj);
iterator insert(const_iterator hint, const value_type& obj);
template <class InputIterator>
void insert(InputIterator first, InputIterator last);
The first member function determines whether an element y exists in the sequence
whose key has equivalent ordering (page 39) to that of obj. If not, it creates such
an element y and initializes it with obj. The function then determines the iterator
it that designates y. If an insertion occurred, the function returns pair(it, true).
Otherwise, it returns pair(it, false).
The second member function returns insert(obj), using it as a starting place
within the controlled sequence to search for the insertion point. The third member
function inserts the sequence of element values, for each it in the range [first,
last), by calling insert(*it).
If an exception is thrown during the insertion of a single element, the container is
left unaltered and the exception is rethrown. If an exception is thrown during the
insertion of multiple elements, the container is left in a stable but unspecified state
and the exception is rethrown.
unordered_map::iterator
typedef T2 iterator;
The type describes an object that can serve as a bidirectional iterator for the
controlled sequence. It is described here as a synonym for the
implementation-defined type T2.
unordered_map::key_eq
key_equal key_eq() const;
The member function returns the key equality function that was used to create the
map.
unordered_map::key_equal
typedef Pred key_equal;
The type returns an equivalence relation.
unordered_map::key_type
typedef Key key_type;
The type describes the sort key object stored in each element of the controlled
sequence.
unordered_map::load_factor
float load_factor() const;
The member function returns the average number of elements per bucket.
unordered_map::local_iterator
typedef T4 local_iterator;
376
Standard C++ Library
The type describes an object that can serve as a constant bidirectional iterator for
the controlled sequence. It is described here as a synonym for the
implementation-defined type T4.
unordered_map::mapped_type
typedef T mapped_type;
The type is a synonym for the template parameter T.
unordered_map::max_bucket_count
size_type max_bucket_count() const;
The member function returns the maximum number of buckets that the unordered
map can contain.
unordered_map::max_load_factor
float max_load_factor() const;
void max_load_factor(float z);
The first member function returns the maximum value that the container attempts
to maintain for the load factor (the average number of elements per bucket). If the
load factor increases beyond this value, the container creates more buckets.
The second member function sets the maximum load factor. If this value is less
than the current load factor, the unordered map is rehashed.
unordered_map::max_size
size_type max_size() const;
The member function returns the length of the longest sequence that the object can
control.
unordered_map::operator[]
mapped_type& operator[](const key_type& k);
The member function determines the iterator it as the return value of insert(
value_type(k, T()). (It inserts an element with the specified key if no such
element exists.) It then returns a reference to (*it).second.
unordered_map::pointer
typedef typename A::pointer pointer;
The type describes an object that can serve as a pointer to an element of the
controlled sequence.
unordered_map::reference
typedef typename A::reference reference;
The type describes an object that can serve as a reference to an element of the
controlled sequence.
unordered_map::rehash
void rehash(size_type n);
The member function rehashes the unordered map, ensuring that it contains at
least n buckets.
377
Chapter 13. Standard Template Library C++
img
......................
unordered_map::size
size_type size() const;
The member function returns the length of the controlled sequence.
unordered_map::size_type
typedef T0 size_type;
The unsigned integer type describes an object that can represent the length of any
controlled sequence. It is described here as a synonym for the
implementation-defined type T0.
unordered_map::swap
void swap(unordered_map& x);
The member function swaps the controlled sequences between *this and x. If
get_allocator() == x.get_allocator(), it does so in constant time, it throws an
exception only as a result of copying the stored function object of type Pred, and it
invalidates no references, pointers, or iterators that designate elements in the two
controlled sequences. Otherwise, it performs a number of element assignments and
constructor calls proportional to the number of elements in the two controlled
sequences.
unordered_map::unordered_map
explicit unordered_map(size_type n = 3,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
template <class InputIterator>
unordered_map(InputIterator f, InputIterator l,
size_type n = 3,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
unordered_map(const unordered_map&);
~unordered_map();
unordered_map& operator=(const unordered_map&);
All constructors store an allocator object (page 337) and initialize the controlled
sequence. The allocator object is the argument al, if present. For the copy
constructor, it is x.get_allocator(). Otherwise, it is A().
The first three constructors specify an empty initial controlled sequence. The fourth
constructor specifies a copy of the sequence controlled by x. The last three
constructors specify the sequence of element values [first, last).
unordered_map::value_type
typedef std::pair<const Key, T> value_type;
The type describes an element of the controlled sequence.
unordered_multimap
allocator_type (page 380) · begin (page 381) · bucket (page 381) · bucket_count
(page 381) · bucket_size (page 381) · clear (page 381) · const_iterator (page 381) ·
const_local_iterator (page 381) · const_pointer (page 381) · const_reference (page
381) · count (page 382) · difference_type (page 382) · empty (page 382) · end (page
382) · equal_range (page 382) · erase (page 382) · find (page 382) · get_allocator
(page 383) · hash_function (page 383) · hasher (page 383) · insert (page 383) ·
378
Standard C++ Library
img
.................
iterator (page 383) · key_eq (page 383) · key_equal (page 383) · key_type (page
384) · load_factor (page 384) · local_iterator (page 384) · mapped_type (page 384) ·
max_bucket_count (page 384) · max_load_factor (page 384) · max_size (page 384) ·
reference (page 384) · rehash (page 385) · size (page 385) · size_type (page 385) ·
swap (page 385) · unordered_multimap (page 385) · value_type (page 385)
namespace std {
namespace tr1 {
template <class Key,
class T,
class Hash  = hash<Key>,
class Pred  = std::equal_to<Key>,
class A= std::allocator<std::pair<const Key, T> > >
class unordered_multimap
{
public:
// types
typedef Key
key_type;
typedef std::pair<const Key, T>
value_type;
typedef T
mapped_type;
typedef Hash
hasher;
typedef Pred
key_equal;
typedef A
allocator_type;
typedef typename A::pointer
pointer;
typedef typename A::const_pointer
const_pointer;
typedef typename A::reference
reference;
typedef typename A::const_reference const_reference;
typedef T0
size_type;
typedef T1
difference_type;
typedef
T2
iterator;
typedef
T3
const_iterator;
typedef
T4
local_iterator;
typedef
T5
const_local_iterator;
// construct/destroy/copy
explicit unordered_multimap(size_type n = 3,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
template <class InputIterator>
unordered_multimap(InputIterator f, InputIterator l,
size_type n = 3,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
unordered_multimap(const unordered_multimap&);
~unordered_multimap();
unordered_multimap& operator=(const unordered_multimap&);
A get_allocator() const;
// size and capacity
bool empty() const;
size_type size() const;
size_type max_size() const;
// iterators
iterator
begin();
const_iterator
begin() const;
iterator
end();
const_iterator
end() const;
// modifiers
iterator insert(const value_type& obj);
iterator insert(const_iterator hint, const value_type& obj);
template <class InputIterator>
void insert(InputIterator first, InputIterator last);
379
Chapter 13. Standard Template Library C++
img
..
void erase(const_iterator position);
size_type erase(const key_type& k);
void erase(const_iterator first, const_iterator last);
void clear();
void swap(unordered_multimap&);
// observers
hasher hash_function() const;
key_equal key_eq() const;
// lookup
iterator
find(const key_type& k);
const_iterator find(const key_type& k) const;
size_type count(const key_type& k) const;
std::pair<iterator, iterator>
equal_range(const key_type& k);
std::pair<const_iterator, const_iterator>
equal_range(const key_type& k) const;
// bucket interface
size_type bucket_count() const;
size_type max_bucket_count() const;
size_type bucket_size(size_type n) const;
size_type bucket(const key_type& k) const;
local_iterator begin(size_type n);
const_local_iterator begin(size_type n) const;
local_iterator end(size_type n);
const_local_iterator end(size_type n) const;
// hash policy
float load_factor() const;
float max_load_factor() const;
void max_load_factor(float z);
void rehash(size_type n);
};
template <class Key, class T, class Hash, class Pred, class Alloc>
void swap(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
}
}
The template class describes an object that controls a varying-length sequence of
elements of type pair<const Key, T>. The sequence is unordered. The first element
of each pair is the sort key and the second is its associated value. If you have an
optimal hash function, the number of operations performed during lookup,
insertion, and removal of an arbitrary element does not depend on the number of
elements in the sequence. Moreover, inserting an element invalidates no iterators,
and removing an element invalidates only those iterators which point at the
removed element.
The object allocates and frees storage for the sequence it controls through a stored
allocator object (page 337) of class A. Such an allocator object must have the same
external interface as an object of template class allocator (page 337). Note that the
stored allocator object is not copied when the container object is assigned.
unordered_multimap::allocator_type
typedef A allocator_type;
The type is a synonym for the template parameter A.
380
Standard C++ Library
unordered_multimap::begin
iterator begin();
const_iterator begin() const;
local_iterator begin(size_type n);
const_local_iterator begin(size_type n) const;
The member function returns a bidirectional iterator that points at the first element
of the sequence (or just beyond the end of an empty sequence).
unordered_multimap::bucket
size_type bucket(const key_type& k) const;
The member function returns the index of the bucket that contains the specified
key.
unordered_multimap::bucket_count
size_type bucket_count() const;
The member function returns the number of buckets that the unordered multimap
contains.
unordered_multimap::bucket_size
size_type bucket_size(size_type n) const;
The member function returns the number of elements in the nth bucket.
unordered_multimap::clear
void clear();
The member function calls erase( begin(), end()).
unordered_multimap::const_iterator
typedef T3 const_iterator;
The type describes an object that can serve as a constant bidirectional iterator for
the controlled sequence. It is described here as a synonym for the
implementation-defined type T3.
unordered_multimap::const_local_iterator
typedef T5 const_local_iterator;
The type describes an object that can serve as a constant bidirectional iterator for
the controlled sequence. It is described here as a synonym for the
implementation-defined type T5.
unordered_multimap::const_pointer
typedef typename A::const_pointer const_pointer;
The type describes an object that can serve as a constant pointer to an element of
the controlled sequence.
unordered_multimap::const_reference
typedef typename A::const_reference const_reference;
The type describes an object that can serve as a constant reference to an element of
the controlled sequence.
381
Chapter 13. Standard Template Library C++
unordered_multimap::count
size_type count(const key_type& k) const;
The member function returns the number of elements in the multimap that have a
key equivalent to k, based on the key_eq function.
unordered_multimap::difference_type
typedef T1 difference_type;
The signed integer type describes an object that can represent the difference
between the addresses of any two elements in the controlled sequence. It is
described here as a synonym for the implementation-defined type T1.
unordered_multimap::empty
bool empty() const;
The member function returns true for an empty controlled sequence.
unordered_multimap::end
const_iterator end() const;
iterator end();
local_iterator end(size_type n);
const_local_iterator end(size_type n) const;
The member function returns a bidirectional iterator that points just beyond the
end of the sequence.
unordered_multimap::equal_range
std::pair<iterator, iterator>
equal_range(const key_type& k);
std::pair<const_iterator, const_iterator>
equal_range(const key_type& k) const;
The member function returns a range that contains all of the elements with the
specified key. It returns make_pair(end(), end()) if no such elements exist.
unordered_multimap::erase
void erase(const_iterator position);
size_type erase(const key_type& k);
void erase(const_iterator first, const_iterator last);
The first member function removes the element of the controlled sequence pointed
to by it. The second member function removes the elements in the range [first,
last). Both return an iterator that designates the first element remaining beyond
any elements removed, or end() if no such element exists.
The third member removes all the elements in the multimap. It returns the number
of elements it removes.
The member functions never throw an exception.
unordered_multimap::find
iterator
find(const key_type& k);
const_iterator find(const key_type& k) const;
382
Standard C++ Library
img
..
The member function returns an iterator that designates the earliest element in the
controlled sequence whose sort key has equivalent ordering (page 39) to key. If no
such element exists, the function returns end().
unordered_multimap::get_allocator
A get_allocator() const;
The member function returns the stored allocator object (page 337).
unordered_multimap::hasher
typedef Hash hasher;
The type returns a value of type std::size_t.
unordered_multimap::hash_function
hasher hash_function() const;
The member function returns the hash function that was used to construct the
multimap.
unordered_multimap::insert
iterator insert(const value_type& obj);
iterator insert(const_iterator hint, const value_type& obj);
template <class InputIterator>
void insert(InputIterator first, InputIterator last);
The first member function inserts the element obj in the controlled sequence, then
returns the iterator that designates the inserted element. The second member
function returns insert(obj), using it as a starting place within the controlled
sequence to search for the insertion point. The third member function inserts the
sequence of element values, for each it in the range [first, last), by calling
insert(*it).
If an exception is thrown during the insertion of a single element, the container is
left unaltered and the exception is rethrown. If an exception is thrown during the
insertion of multiple elements, the container is left in a stable but unspecified state
and the exception is rethrown.
unordered_multimap::iterator
typedef T2 iterator;
The type describes an object that can serve as a bidirectional iterator for the
controlled sequence. It is described here as a synonym for the
implementation-defined type T2.
unordered_multimap::key_eq
key_equal key_eq() const;
The member function returns the key equality function that was used to create the
multimap.
unordered_multimap::key_equal
typedef Pred key_equal;
The type returns an equivalence relation.
383
Chapter 13. Standard Template Library C++
unordered_multimap::key_type
typedef Key key_type;
The type describes the sort key object stored in each element of the controlled
sequence.
unordered_multimap::load_factor
float load_factor() const;
The member function returns the average number of elements per bucket.
unordered_multimap::local_iterator
typedef T4 local_iterator;
The type describes an object that can serve as a constant bidirectional iterator for
the controlled sequence. It is described here as a synonym for the
implementation-defined type T4.
unordered_multimap::mapped_type
typedef T mapped_type;
The type is a synonym for the template parameter T.
unordered_multimap::max_bucket_count
size_type max_bucket_count() const;
The member function returns the maximum number of buckets that the unordered
multimap can contain.
unordered_multimap::max_load_factor
float max_load_factor() const;
void max_load_factor(float z);
The first member function returns the maximum value that the container attempts
to maintain for the load factor (the average number of elements per bucket). If the
load factor increases beyond this value, the container creates more buckets.
The second member function sets the maximum load factor. If this value is less
than the current load factor, the unordered multimap is rehashed.
unordered_multimap::max_size
size_type max_size() const;
The member function returns the length of the longest sequence that the object can
control.
unordered_multimap::pointer
typedef typename A::pointer pointer;
The type describes an object that can serve as a pointer to an element of the
controlled sequence.
unordered_multimap::reference
typedef typename A::reference reference;
The type describes an object that can serve as a reference to an element of the
controlled sequence.
384
Standard C++ Library
img
..
unordered_multimap::rehash
void rehash(size_type n);
The member function rehashes the unordered multimap, ensuring that it contains
at least n buckets.
unordered_multimap::size
size_type size() const;
The member function returns the length of the controlled sequence.
unordered_multimap::size_type
typedef T0 size_type;
The unsigned integer type describes an object that can represent the length of any
controlled sequence. It is described here as a synonym for the
implementation-defined type T0.
unordered_multimap::swap
void swap(unordered_multimap& x);
The member function swaps the controlled sequences between *this and x. If
get_allocator() == x.get_allocator(), it does so in constant time, it throws an
exception only as a result of copying the stored function object of type Pred, and it
invalidates no references, pointers, or iterators that designate elements in the two
controlled sequences. Otherwise, it performs a number of element assignments and
constructor calls proportional to the number of elements in the two controlled
sequences.
unordered_multimap::unordered_multimap
explicit unordered_multimap(size_type n = 3,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
template <class InputIterator>
unordered_multimap(InputIterator f, InputIterator l,
size_type n = 3,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
unordered_multimap(const unordered_multimap&);
~unordered_multimap();
unordered_multimap& operator=(const unordered_multimap&);
All constructors store an allocator object (page 337) and initialize the controlled
sequence. The allocator object is the argument al, if present. For the copy
constructor, it is x.get_allocator (page 383)(). Otherwise, it is A().
The first three constructors specify an empty initial controlled sequence. The fourth
constructor specifies a copy of the sequence controlled by x. The last three
constructors specify the sequence of element values [first, last).
unordered_multimap::value_type
typedef std::pair<const Key, T> value_type;
The type describes an element of the controlled sequence.
385
Chapter 13. Standard Template Library C++
img
........................................
<unordered_set>
Note: To enable this header file, you must define the macro _VACPP_TR1.
namespace std {
namespace tr1 {
template <class Value,
class Hash = hash<Value>,
class Pred = std::equal_to<Value>,
class Alloc = std::allocator<Value> >
class unordered_set;
template <class Value,
class Hash = hash<Value>,
class Pred = std::equal_to<Value>,
class Alloc = std::allocator<Value> >
class unordered_multiset;
}
}
Include the STL (page 1) standard header <unordered_set> to define the container
(page 41) template classes unordered_set and unordered_multiset, and their
supporting templates.
unordered_multiset
allocator_type (page 388) · begin (page 388) · bucket (page 388) · bucket_count
(page 388) · bucket_size (page 388) · clear (page 389) · const_iterator (page 389) ·
const_local_iterator (page 389) · const_pointer (page 389) · const_reference (page
389) · count (page 389) · difference_type (page 389) · empty (page 389) · end (page
389) · equal_range (page 390) · erase (page 390) · find (page 390) · get_allocator
(page 390) · hash_function (page 390) · hasher (page 390) · insert (page 390) ·
iterator (page 391) · key_eq (page 391) · key_equal (page 391) · key_type (page
391) · load_factor (page 391) · local_iterator (page 391) · max_bucket_count (page
391) · max_load_factor (page 391) · max_size (page 392) · pointer (page 392) ·
reference (page 392) · rehash (page 392) · size (page 392) · size_type (page 392) ·
swap (page 392) · unordered_multiset (page 393) · value_type (page 393)
namespace std {
namespace tr1 {
template <class Value,
class Hash  = hash<Value>,
class Pred  = std::equal_to<Value>,
class A= std::allocator<Value> >
class unordered_multiset
{
public:
// types
typedef Value
key_type;
typedef Value
value_type;
typedef Hash
hasher;
typedef Pred
key_equal;
typedef A
allocator_type;
typedef typename A::pointer
pointer;
typedef typename A::const_pointer
const_pointer;
typedef typename A::reference
reference;
typedef typename A::const_reference const_reference;
typedef T0
size_type;
typedef T1
difference_type;
typedef
T2
iterator;
typedef
T3
const_iterator;
typedef
T4
local_iterator;
typedef
T5
const_local_iterator;
386
Standard C++ Library
// construct/destroy/copy
explicit unordered_multiset(size_type n = 3,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
template <class InputIterator>
unordered_multiset(InputIterator f, InputIterator l,
size_type n = 3,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
unordered_multiset(const unordered_multiset&);
~unordered_multiset();
unordered_multiset& operator=(const unordered_multiset&);
A get_allocator() const;
// size and capacity
bool empty() const;
size_type size() const;
size_type max_size() const;
// iterators
iterator
begin();
const_iterator
begin() const;
iterator
end();
const_iterator
end() const;
// modifiers
iterator insert(const value_type& obj);
iterator insert(const_iterator hint, const value_type& obj);
template <class InputIterator>
void insert(InputIterator first, InputIterator last);
void erase(const_iterator position);
size_type erase(const key_type& k);
void erase(const_iterator first, const_iterator last);
void clear();
void swap(unordered_multiset&);
// observers
hasher hash_function() const;
key_equal key_eq() const;
// lookup
iterator
find(const key_type& k);
const_iterator find(const key_type& k) const;
size_type count(const key_type& k) const;
std::pair<iterator, iterator>
equal_range(const key_type& k);
std::pair<const_iterator, const_iterator>
equal_range(const key_type& k) const;
// bucket interface
size_type bucket_count() const;
size_type max_bucket_count() const;
size_type bucket_size(size_type n) const;
size_type bucket(const key_type& k) const;
local_iterator begin(size_type n);
const_local_iterator begin(size_type n) const;
local_iterator end(size_type n);
const_local_iterator end(size_type n) const;
// hash policy
float load_factor() const;
387
Chapter 13. Standard Template Library C++
img
..
float max_load_factor() const;
void max_load_factor(float z);
void rehash(size_type n);
};
template <class Value, class Hash, class Pred, class Alloc>
void swap(const unordered_multiset<Value, Hash, Pred, Alloc>& x,
const unordered_multiset<Value, Hash, Pred, Alloc>& y);
}
}
The template class describes an object that controls a varying-length sequence of
elements of type const Key. The sequence is unordered. Each element serves as
both a sort key and a value. If you have an optimal hash function, the number of
operations performed during lookup, insertion, and removal of an arbitrary
element does not depend on the number of elements in the sequence. Moreover,
inserting an element invalidates no iterators, and removing an element invalidates
only those iterators which point at the removed element.
The object allocates and frees storage for the sequence it controls through a stored
allocator object (page 337) of class A. Such an allocator object must have the same
external interface as an object of template class allocator (page 337). Note that the
stored allocator object is not copied when the container object is assigned.
unordered_multiset::allocator_type
typedef A allocator_type;
The type is a synonym for the template parameter A.
unordered_multiset::begin
iterator
begin();
const_iterator begin() const;
local_iterator begin(size_type n);
const_local_iterator begin(size_type n) const;
The member function returns a bidirectional iterator that points at the first element
of the sequence (or just beyond the end of an empty sequence).
unordered_multiset::bucket
size_type bucket(const key_type& k) const;
The member function returns the index of the bucket that contains the specified
key.
unordered_multiset::bucket_count
size_type bucket_count() const;
The member function returns the number of buckets that the unordered multiset
contains.
unordered_multiset::bucket_size
size_type bucket_size(size_type n) const;
The member function returns the number of elements in the nth bucket.
388
Standard C++ Library
unordered_multiset::clear
void clear();
The member function calls erase( begin(), end()).
unordered_multiset::const_iterator
typedef T3 const_iterator;
The type describes an object that can serve as a constant bidirectional iterator for
the controlled sequence. It is described here as a synonym for the
implementation-defined type T3.
unordered_multiset::const_local_iterator
typedef T5 const_local_iterator;
The type describes an object that can serve as a constant bidirectional iterator for
the controlled sequence. It is described here as a synonym for the
implementation-defined type T5.
unordered_multiset::const_pointer
typedef typename A::const_pointer const_pointer;
The type describes an object that can serve as a constant pointer to an element of
the controlled sequence.
unordered_multiset::const_reference
typedef typename A::const_reference const_reference;
The type describes an object that can serve as a constant reference to an element of
the controlled sequence.
unordered_multiset::count
size_type count(const key_type& k) const;
The member function returns the number of elements in the multiset that have a
key equivalent to k, based on the key_eq function.
unordered_multiset::difference_type
typedef T1 difference_type;
The signed integer type describes an object that can represent the difference
between the addresses of any two elements in the controlled sequence. It is
described here as a synonym for the implementation-defined type T1.
unordered_multiset::empty
bool empty() const;
The member function returns true for an empty controlled sequence.
unordered_multiset::end
iterator
end();
const_iterator end() const;
local_iterator end(size_type n);
const_local_iterator end(size_type n) const;
The member function returns a bidirectional iterator that points just beyond the
end of the sequence.
389
Chapter 13. Standard Template Library C++
img
..
unordered_multiset::equal_range
std::pair<iterator, iterator>
equal_range(const key_type& k);
std::pair<const_iterator, const_iterator>
equal_range(const key_type& k) const;
The member function returns a range that contains all of the elements with the
specified key. It returns make_pair(end(), end()) if no such elements exist.
unordered_multiset::erase
void erase(const_iterator position);
size_type erase(const key_type& k);
void erase(const_iterator first, const_iterator last);
The first member function removes the element of the controlled sequence pointed
to by it. The second member function removes the elements in the range [first,
last). Both return an iterator that designates the first element remaining beyond
any elements removed, or end() if no such element exists.
The third member removes all the elements in the multiset. It returns the number
of elements it removes.
The member functions never throw an exception.
unordered_multiset::find
iterator
find(const key_type& k);
const_iterator find(const key_type& k) const;
The member function returns an iterator that designates the earliest element in the
controlled sequence whose sort key has equivalent ordering (page 39) to key. If no
such element exists, the function returns end().
unordered_multiset::get_allocator
A get_allocator() const;
The member function returns the stored allocator object (page 337).
unordered_multiset::hasher
typedef Hash hasher;
The type returns a value of type std::size_t.
unordered_multiset::hash_function
hasher hash_function() const;
The member function returns the hash function that was used to construct the
multiset.
unordered_multiset::insert
iterator insert(const value_type& obj);
iterator insert(const_iterator hint, const value_type& obj);
template <class InputIterator>
void insert(InputIterator first, InputIterator last);
The first member function inserts the element obj in the controlled sequence, then
returns the iterator that designates the inserted element. The second member
function returns insert(obj), using it as a starting place within the controlled
390
Standard C++ Library
sequence to search for the insertion point. The third member function inserts the
sequence of element values, for each it in the range [first, last), by calling
insert(*it).
If an exception is thrown during the insertion of a single element, the container is
left unaltered and the exception is rethrown. If an exception is thrown during the
insertion of multiple elements, the container is left in a stable but unspecified state
and the exception is rethrown.
unordered_multiset::iterator
typedef T2 iterator;
The type describes an object that can serve as a bidirectional iterator for the
controlled sequence. It is described here as a synonym for the
implementation-defined type T2.
unordered_multiset::key_eq
key_equal key_eq() const;
The member function returns the key equality function that was used to create the
multiset.
unordered_multiset::key_equal
typedef Pred key_equal;
The type returns an equivalence relation.
unordered_multiset::key_type
typedef Value key_type;
The type describes the sort key object which constitutes each element of the
controlled sequence.
unordered_multiset::load_factor
float load_factor() const;
The member function returns the average number of elements per bucket.
unordered_multiset::local_iterator
typedef T4 local_iterator;
The type describes an object that can serve as a constant bidirectional iterator for
the controlled sequence. It is described here as a synonym for the
implementation-defined type T4.
unordered_multiset::max_bucket_count
size_type max_bucket_count() const;
The member function returns the maximum number of buckets that the unordered
multiset can contain.
unordered_multiset::max_load_factor
float max_load_factor() const;
void max_load_factor(float z);
391
Chapter 13. Standard Template Library C++
The first member function returns the maximum value that the container attempts
to maintain for the load factor (the average number of elements per bucket). If the
load factor increases beyond this value, the container creates more buckets.
The second member function sets the maximum load factor. If this value is less
than the current load factor, the unordered multiset is rehashed.
unordered_multiset::max_size
size_type max_size() const;
The member function returns the length of the longest sequence that the object can
control.
unordered_multiset::pointer
typedef typename A::pointer pointer;
The type describes an object that can serve as a pointer to an element of the
controlled sequence.
unordered_multiset::reference
typedef typename A::reference reference;
The type describes an object that can serve as a reference to an element of the
controlled sequence.
unordered_multiset::rehash
void rehash(size_type n);
The member function rehashes the unordered multiset, ensuring that it contains at
least n buckets.
unordered_multiset::size
size_type size() const;
The member function returns the length of the controlled sequence.
unordered_multiset::size_type
typedef T0 size_type;
The unsigned integer type describes an object that can represent the length of any
controlled sequence. It is described here as a synonym for the
implementation-defined type T0.
unordered_multiset::swap
void swap(unordered_multiset& x);
The member function swaps the controlled sequences between *this and x. If
get_allocator() == x.get_allocator(), it does so in constant time, it throws an
exception only as a result of copying the stored function object of type Pred, and it
invalidates no references, pointers, or iterators that designate elements in the two
controlled sequences. Otherwise, it performs a number of element assignments and
constructor calls proportional to the number of elements in the two controlled
sequences.
392
Standard C++ Library
img
.......................................
unordered_multiset::unordered_multiset
explicit unordered_multiset(size_type n = 3,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
template <class InputIterator>
unordered_multiset(InputIterator f, InputIterator l,
size_type n = 3,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
unordered_multiset(const unordered_multiset&);
~unordered_multiset();
unordered_multiset& operator=(const unordered_multiset&);
All constructors store an allocator object (page 337) and initialize the controlled
sequence. The allocator object is the argument al, if present. For the copy
constructor, it is x.get_allocator(). Otherwise, it is A().
The first three constructors specify an empty initial controlled sequence. The fourth
constructor specifies a copy of the sequence controlled by x. The last three
constructors specify the sequence of element values [first, last).
unordered_multiset::value_type
typedef Value value_type;
The type describes an element of the controlled sequence.
unordered_set
allocator_type (page 395) · begin (page 395) · bucket (page 395) · bucket_count
(page 395) · bucket_size (page 396) · clear (page 396) · const_iterator (page 396) ·
const_local_iterator (page 396) · const_pointer (page 396) · const_reference (page
396) · count (page 396) · difference_type (page 396) · empty (page 396) · end (page
396) · equal_range (page 397) · erase (page 397) · find (page 397) · get_allocator
(page 397) · hash_function (page 397) · hasher (page 397) · insert (page 397) ·
iterator (page 398) · key_eq (page 398) · key_equal (page 398) · key_type (page
398) · load_factor (page 398) · local_iterator (page 398) · max_bucket_count (page
398) · max_load_factor (page 399) · max_size (page 399) · pointer (page 399) ·
reference (page 399) · rehash (page 399) · size (page 399) · size_type (page 399) ·
swap (page 399) · unordered_set (page 400) · value_type (page 400)
namespace std {
namespace tr1 {
template <class Value,
class Hash  = hash<Value>,
class Pred  = std::equal_to<Value>,
class A= std::allocator<Value> >
class unordered_set
{
public:
// types
typedef Value
key_type;
typedef Value
value_type;
typedef Hash
hasher;
typedef Pred
key_equal;
typedef A
allocator_type;
typedef typename A::pointer
pointer;
typedef typename A::const_pointer
const_pointer;
typedef typename A::reference
reference;
typedef typename A::const_reference const_reference;
typedef T0
size_type;
typedef T1
difference_type;
393
Chapter 13. Standard Template Library C++
typedef
T2
iterator;
typedef
T3
const_iterator;
typedef
T4
local_iterator;
typedef
T5
const_local_iterator;
// construct/destroy/copy
explicit unordered_set(size_type n = 3,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
template <class InputIterator>
unordered_set(InputIterator f, InputIterator l,
size_type n = 3,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
unordered_set(const unordered_set&);
~unordered_set();
unordered_set& operator=(const unordered_set&);
A get_allocator() const;
// size and capacity
bool empty() const;
size_type size() const;
size_type max_size() const;
// iterators
iterator
begin();
const_iterator
begin() const;
iterator
end();
const_iterator
end() const;
// modifiers
std::pair<iterator, bool> insert(const value_type& obj);
iterator insert(const_iterator hint, const value_type& obj);
template <class InputIterator>
void insert(InputIterator first, InputIterator last);
void erase(const_iterator position);
size_type erase(const key_type& k);
void erase(const_iterator first, const_iterator last);
void clear();
void swap(unordered_set&);
// observers
hasher hash_function() const;
key_equal key_eq() const;
// lookup
iterator
find(const key_type& k);
const_iterator find(const key_type& k) const;
size_type count(const key_type& k) const;
std::pair<iterator, iterator>
equal_range(const key_type& k);
std::pair<const_iterator, const_iterator>
equal_range(const key_type& k) const;
// bucket interface
size_type bucket_count() const;
size_type max_bucket_count() const;
size_type bucket_size(size_type n) const;
size_type bucket(const key_type& k) const;
local_iterator begin(size_type n);
const_local_iterator begin(size_type n) const;
394
Standard C++ Library
img
..
local_iterator end(size_type n);
const_local_iterator end(size_type n) const;
// hash policy
float load_factor() const;
float max_load_factor() const;
void max_load_factor(float z);
void rehash(size_type n);
};
template <class Value, class Hash, class Pred, class Alloc>
void swap(const unordered_set<Value, Hash, Pred, Alloc>& x,
const unordered_set<Value, Hash, Pred, Alloc>& y);
}
}
The template class describes an object that controls a varying-length sequence of
elements of type const Key. The sequence is unordered. Each element serves as
both a sort key and a value. If you have an optimal hash function, the number of
operations performed during lookup, insertion, and removal of an arbitrary
element does not depend on the number of elements in the sequence. Moreover,
inserting an element invalidates no iterators, and removing an element invalidates
only those iterators which point at the removed element.
The object allocates and frees storage for the sequence it controls through a stored
allocator object (page 337) of class A. Such an allocator object must have the same
external interface as an object of template class allocator (page 337). Note that the
stored allocator object is not copied when the container object is assigned.
unordered_set::allocator_type
typedef A allocator_type;
The type is a synonym for the template parameter A.
unordered_set::begin
iterator
begin();
const_iterator begin() const;
local_iterator begin(size_type n);
const_local_iterator begin(size_type n) const;
The member function returns a bidirectional iterator that points at the first element
of the sequence (or just beyond the end of an empty sequence).
unordered_set::bucket
size_type bucket(const key_type& k) const;
The member function returns the index of the bucket that contains the specified
key.
unordered_set::bucket_count
size_type bucket_count() const;
The member function returns the number of buckets that the unordered set
contains.
395
Chapter 13. Standard Template Library C++
unordered_set::bucket_size
size_type bucket_size(size_type n) const;
The member function returns the number of elements in the nth bucket.
unordered_set::clear
void clear();
The member function calls erase( begin(), end()).
unordered_set::const_iterator
typedef T3 const_iterator;
The type describes an object that can serve as a constant bidirectional iterator for
the controlled sequence. It is desciibed here as a synonym for the
implementation-defined type T3.
unordered_set::const_local_iterator
typedef T5 const_local_iterator;
The type describes an object that can serve as a constant bidirectional iterator for
the controlled sequence. It is described here as a synonym for the
implementation-defined type T5.
unordered_set::const_pointer
typedef typename A::const_pointer const_pointer;
The type describes an object that can serve as a constant pointer to an element of
the controlled sequence.
unordered_set::const_reference
typedef typename A::const_reference const_reference;
The type describes an object that can serve as a constant reference to an element of
the controlled sequence.
unordered_set::count
size_type count(const key_type& k) const;
The member function returns the number of elements in the set that have a key
equivalent to k, based on the key_eq function.
unordered_set::difference_type
typedef T1 difference_type;
The signed integer type describes an object that can represent the difference
between the addresses of any two elements in the controlled sequence. It is
desciibed here as a synonym for the implementation-defined type T1.
unordered_set::empty
bool empty() const;
The member function returns true for an empty controlled sequence.
unordered_set::end
iterator
end();
const_iterator end() const;
396
Standard C++ Library
img
.
local_iterator end(size_type n);
const_local_iterator end(size_type n) const;
The member function returns a bidirectional iterator that points just beyond the
end of the sequence.
unordered_set::equal_range
std::pair<iterator, iterator>
equal_range(const key_type& k);
std::pair<const_iterator, const_iterator>
equal_range(const key_type& k) const;
The member function returns a range that contains all of the elements with the
specified key. It returns make_pair(end(), end()) if no such elements exist.
unordered_set::erase
void erase(const_iterator position);
size_type erase(const key_type& k);
void erase(const_iterator first, const_iterator last);
The first member function removes the element of the controlled sequence pointed
to by it. The second member function removes the elements in the range [first,
last). Both return an iterator that designates the first element remaining beyond
any elements removed, or end() if no such element exists.
The third member removes all the elements in the set. It returns the number of
elements it removes.
The member functions never throw an exception.
unordered_set::find
iterator
find(const key_type& k);
const_iterator find(const key_type& k) const;
The member function returns an iterator that designates the earliest element in the
controlled sequence whose sort key has equivalent ordering (page 39) to key. If no
such element exists, the function returns end().
unordered_set::get_allocator
A get_allocator() const;
The member function returns the stored allocator object.
unordered_set::hasher
typedef Hash hasher;
The type returns a value of type std::size_t.
unordered_set::hash_function
hasher hash_function() const;
The member function returns the hash function that was used to construct the set.
unordered_set::insert
std::pair<iterator, bool> insert(const value_type& obj);
iterator insert(const_iterator hint, const value_type& obj);
template <class InputIterator>
void insert(InputIterator first, InputIterator last);
397
Chapter 13. Standard Template Library C++
img
.
The first member function determines whether an element y exists in the sequence
whose key has equivalent ordering (page 39) to that of obj. If not, it creates such
an element y and initializes it with obj. The function then determines the iterator
it that designates y. If an insertion occurred, the function returns pair(it, true).
Otherwise, it returns pair(it, false).
The second member function returns insert(obj), using it as a starting place
within the controlled sequence to search for the insertion point. The third member
function inserts the sequence of element values, for each it in the range [first,
last), by calling insert(*it).
If an exception is thrown during the insertion of a single element, the container is
left unaltered and the exception is rethrown. If an exception is thrown during the
insertion of multiple elements, the container is left in a stable but unspecified state
and the exception is rethrown.
unordered_set::iterator
typedef T2 iterator;
The type describes an object that can serve as a bidirectional iterator for the
controlled sequence. It is described here as a synonym for the
implementation-defined type T2.
unordered_set::key_eq
key_equal key_eq() const;
The member function returns the key equality function that was used to create the
map.
unordered_set::key_equal
typedef Pred key_equal;
The type returns an equivalence relation.
unordered_set::key_type
typedef Value key_type;
The type describes the sort key object which constitutes each element of the
controlled sequence.
unordered_set::load_factor
float load_factor() const;
The member function returns the average number of elements per bucket.
unordered_set::local_iterator
typedef T4 local_iterator;
The type describes an object that can serve as a constant bidirectional iterator for
the controlled sequence. It is described here as a synonym for the
implementation-defined type T4.
unordered_set::max_bucket_count
size_type max_bucket_count() const;
The member function returns the maximum number of buckets that the unordered
set can contain.
398
Standard C++ Library
unordered_set::max_load_factor
float max_load_factor() const;
void max_load_factor(float z);
The first member function returns the maximum value that the container attempts
to maintain for the load factor (the average number of elements per bucket). If the
load factor increases beyond this value, the container creates more buckets.
The second member function sets the maximum load factor. If this value is less
than the current load factor, the unordered set is rehashed.
unordered_set::max_size
size_type max_size() const;
The member function returns the length of the longest sequence that the object can
control.
unordered_set::pointer
typedef typename A::const_pointer pointer;
The type describes an object that can serve as a pointer to an element of the
controlled sequence.
unordered_set::reference
typedef typename A::const_reference reference;
The type describes an object that can serve as a reference to an element of the
controlled sequence.
unordered_set::rehash
void rehash(size_type n);
The member function rehashes the unordered set, ensuring that it contains at least
n buckets.
unordered_set::size
size_type size() const;
The member function returns the length of the controlled sequence.
unordered_set::size_type
typedef T0 size_type;
The unsigned integer type describes an object that can represent the length of any
controlled sequence. It is desciibed here as a synonym for the implementation-
defined type T0.
unordered_set::swap
void swap(unordered_set& x);
The member function swaps the controlled sequences between *this and x. If
get_allocator() == x.get_allocator(), it does so in constant time, it throws an
exception only as a result of copying the stored function object of type Pred, and it
invalidates no references, pointers, or iterators that designate elements in the two
controlled sequences. Otherwise, it performs a number of element assignments and
constructor calls proportional to the number of elements in the two controlled
sequences.
399
Chapter 13. Standard Template Library C++
img
..
unordered_set::unordered_set
explicit unordered_set(size_type n = 3,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
template <class InputIterator>
unordered_set(InputIterator f, InputIterator l,
size_type n = 3,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
unordered_set(const unordered_set&);
~unordered_set();
unordered_set& operator=(const unordered_set&);
All constructors store an allocator object (page 337) and initialize the controlled
sequence. The allocator object is the argument al, if present. For the copy
constructor, it is x.get_allocator(). Otherwise, it is A().
The first three constructors specify an empty initial controlled sequence. The fourth
constructor specifies a copy of the sequence controlled by x. The last three
constructors specify the sequence of element values [first, last).
unordered_set::value_type
typedef Value value_type;
The type describes an element of the controlled sequence.
<utility>
namespace std {
template<class T, class U>
struct pair (page 402);
// TEMPLATE FUNCTIONS
template<class T, class U>
pair<T, U> make_pair(T x, U y);
template<class T, class U>
bool operator==(const pair<T, U>& x,
const pair<T, U>& y);
template<class T, class U>
bool operator!=(const pair<T, U>& x,
const pair<T, U>& y);
template<class T, class U>
bool operator<(const pair<T, U>& x,
const pair<T, U>& y);
template<class T, class U>
bool operator>(const pair<T, U>& x,
const pair<T, U>& y);
template<class T, class U>
bool operator<=(const pair<T, U>& x,
const pair<T, U>& y);
template<class T, class U>
bool operator>=(const pair<T, U>& x,
const pair<T, U>& y);
namespace rel_ops {
template<class T>
400
Standard C++ Library
img
..
bool operator!=(const T& x, const T& y);
template<class T>
bool operator<=(const T& x, const T& y);
template<class T>
bool operator>(const T& x, const T& y);
template<class T>
bool operator>=(const T& x, const T& y);
};
};
Include the STL (page 1) standard header <utility> to define several templates of
general use throughout the Standard Template Library.
Four template operators -- operator!=, operator<=, operator>, and operator>= --
define a total ordering on pairs of operands of the same type, given definitions of
operator== and operator<.
If an implementation (page 3) supports namespaces, these template operators are
defined in the rel_ops namespace, nested within the std namespace. If you wish
to make use of these template operators, write the declaration:
using namespace std::rel_ops;
which promotes the template operators into the current namespace.
make_pair
template<class T, class U>
pair<T, U> make_pair(T x, U y);
The template function returns pair<T, U>(x, y).
operator!=
template<class T>
bool operator!=(const T& x, const T& y);
template<class T, class U>
bool operator!=(const pair<T, U>& x,
const pair<T, U>& y);
The template function returns !(x == y).
operator==
template<class T, class U>
bool operator==(const pair<T, U>& x,
const pair<T, U>& y);
The template function returns x.first == y.first && x.second == y.second.
operator<
template<class T, class U>
bool operator<(const pair<T, U>& x,
const pair<T, U>& y);
The template function returns x.first < y.first || !(y.first < x.first &&
x.second < y.second).
401
Chapter 13. Standard Template Library C++
operator<=
template<class T>
bool operator<=(const T& x, const T& y);
template<class T, class U>
bool operator<=(const pair<T, U>& x,
const pair<T, U>& y);
The template function returns !(y < x).
operator>
template<class T>
bool operator>(const T& x, const T& y);
template<class T, class U>
bool operator>(const pair<T, U>& x,
const pair<T, U>& y);
The template function returns y < x.
operator>=
template<class T>
bool operator>=(const T& x, const T& y);
template<class T, class U>
bool operator>=(const pair<T, U>& x,
const pair<T, U>& y);
The template function returns !(x < y).
pair
template<class T, class U>
struct pair {
typedef T first_type;
typedef U second_type
T first;
U second;
pair();
pair(const T& x, const U& y);
template<class V, class W>
pair(const pair<V, W>& pr);
};
The template class stores a pair of objects, first, of type T, and second, of type U.
The type definition first_type, is the same as the template parameter T, while
second_type, is the same as the template parameter U.
The first (default) constructor initializes first to T() and second to U(). The
second constructor initializes first to x and second to y. The third (template)
constructor initializes first to pr.first and second to pr.second. T and U each
need supply only a default constructor, single-argument constructor, and a
destructor.
Portions derived from work copyright © 1994 by Hewlett-Packard Company. All rights
reserved.
402
Standard C++ Library
img
.......
<vector>
namespace std {
template<class T, class A>
class vector;
template<class A>
class vector<bool>;
// TEMPLATE FUNCTIONS
template<class T, class A>
bool operator==(
const vector<T, A>& lhs,
const vector<T, A>& rhs);
template<class T, class A>
bool operator!=(
const vector<T, A>& lhs,
const vector<T, A>& rhs);
template<class T, class A>
bool operator<(
const vector<T, A>& lhs,
const vector<T, A>& rhs);
template<class T, class A>
bool operator>(
const vector<T, A>& lhs,
const vector<T, A>& rhs);
template<class T, class A>
bool operator<=(
const vector<T, A>& lhs,
const vector<T, A>& rhs);
template<class T, class A>
bool operator>=(
const vector<T, A>& lhs,
const vector<T, A>& rhs);
template<class T, class A>
void swap(
vector<T, A>& lhs,
vector<T, A>& rhs);
};
Include the STL (page 1) standard header <vector> to define the container (page
41) template class vector and several supporting templates.
operator!=
template<class T, class A>
bool operator!=(
const vector <T, A>& lhs,
const vector <T, A>& rhs);
The template function returns !(lhs == rhs).
operator==
template<class T, class A>
bool operator==(
const vector <T, A>& lhs,
const vector <T, A>& rhs);
The template function overloads operator== to compare two objects of template
class vector (page 404). The function returns lhs.size (page 410)() == rhs.size()
&& equal (page 255)(lhs. begin (page 406)(), lhs. end (page 407)(),
rhs.begin()).
403
Chapter 13. Standard Template Library C++
img
...................................
operator<
template<class T, class A>
bool operator<(
const vector <T, A>& lhs,
const vector <T, A>& rhs);
The template function overloads operator< to compare two objects of template
class vector. The function returns lexicographical_compare(lhs. begin(), lhs.
end(), rhs.begin(), rhs.end()).
operator<=
template<class T, class A>
bool operator<=(
const vector <T, A>& lhs,
const vector <T, A>& rhs);
The template function returns !(rhs < lhs).
operator>
template<class T, class A>
bool operator>(
const vector <T, A>& lhs,
const vector <T, A>& rhs);
The template function returns rhs < lhs.
operator>=
template<class T, class A>
bool operator>=(
const vector <T, A>& lhs,
const vector <T, A>& rhs);
The template function returns !(lhs < rhs).
swap
template<class T, class A>
void swap(
vector <T, A>& lhs,
vector <T, A>& rhs);
The template function executes lhs.swap(rhs).
vector
allocator_type (page 406) · assign (page 406) · at (page 406) · back (page 406) ·
begin (page 406) · capacity (page 406) · clear (page 407) · const_iterator (page 407)
· const_pointer (page 407) · const_reference (page 407) · const_reverse_iterator
(page 407) · difference_type (page 407) · empty (page 407) · end (page 407) · erase
(page 407) · front (page 408) · get_allocator (page 408) · insert (page 408) · iterator
(page 409) · max_size (page 409) · operator[] (page 409) · pointer (page 409) ·
pop_back (page 409) · push_back (page 409) · rbegin (page 409) · reference (page
409) · rend (page 410) · reserve (page 410) · resize (page 410) · reverse_iterator
(page 410) · size (page 410) · size_type (page 410) · swap (page 410) · value_type
(page 411) · vector (page 411)
template<class T, class A = allocator<T> >
class vector {
public:
404
Standard C++ Library
typedef A allocator_type;
typedef typename A::pointer pointer;
typedef typename A::const_pointer
const_pointer;
typedef typename A::reference reference;
typedef typename A::const_reference
const_reference;
typedef typename A::value_type value_type;
typedef T0 iterator;
typedef T1 const_iterator;
typedef T2 size_type;
typedef T3 difference_type;
typedef reverse_iterator<const_iterator>
const_reverse_iterator;
typedef reverse_iterator<iterator>
reverse_iterator;
vector();
explicit vector(const A& al);
explicit vector(size_type n);
vector(size_type n, const T& x);
vector(size_type n, const T& x,
const A& al);
vector(const vector& x);
template<class InIt>
vector(InIt first, InIt last);
template<class InIt>
vector(InIt first, InIt last,
const A& al);
void reserve(size_type n);
size_type capacity() const;
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
reverse_iterator rend();
const_reverse_iterator rend() const;
void resize(size_type n);
void resize(size_type n, T x);
size_type size() const;
size_type max_size() const;
bool empty() const;
A get_allocator() const;
reference at(size_type pos);
const_reference at(size_type pos) const;
reference operator[](size_type pos);
const_reference operator[](size_type pos);
reference front();
const_reference front() const;
reference back();
const_reference back() const;
void push_back(const T& x);
void pop_back();
template<class InIt>
void assign(InIt first, InIt last);
void assign(size_type n, const T& x);
iterator insert(iterator it, const T& x);
void insert(iterator it, size_type n, const T& x);
template<class InIt>
void insert(iterator it, InIt first, InIt last);
iterator erase(iterator it);
iterator erase(iterator first, iterator last);
void clear();
void swap>(vector& x);
};
405
Chapter 13. Standard Template Library C++
img
...
The template class describes an object that controls a varying-length sequence of
elements of type T. The sequence is stored as an array of T.
The object allocates and frees storage for the sequence it controls through a stored
allocator object (page 337) of class A. Such an allocator object must have the same
external interface as an object of template class allocator (page 337). Note that the
stored allocator object is not copied when the container object is assigned.
Vector reallocation occurs when a member function must grow the controlled
sequence beyond its current storage capacity (page 406). Other insertions and
erasures may alter various storage addresses within the sequence. In all such cases,
iterators or references that point at altered portions of the controlled sequence
become invalid.
vector::allocator_type
typedef A allocator_type;
The type is a synonym for the template parameter A.
vector::assign
template<class InIt>
void assign(InIt first, InIt last);
void assign(size_type n, const T& x);
If InIt is an integer type, the first member function behaves the same as
assign((size_type)first, (T)last). Otherwise, the first member function replaces
the sequence controlled by *this with the sequence [first, last), which must not
overlap the initial controlled sequence. The second member function replaces the
sequence controlled by *this with a repetition of n elements of value x.
vector::at
const_reference at(size_type pos) const;
reference at(size_type pos);
The member function returns a reference to the element of the controlled sequence
at position pos. If that position is invalid, the function throws an object of class
out_of_range.
vector::back
reference back();
const_reference back() const;
The member function returns a reference to the last element of the controlled
sequence, which must be non-empty.
vector::begin
const_iterator begin() const;
iterator begin();
The member function returns a random-access iterator that points at the first
element of the sequence (or just beyond the end of an empty sequence).
vector::capacity
size_type capacity() const;
The member function returns the storage currently allocated to hold the controlled
sequence, a value at least as large as size().
406
Standard C++ Library
vector::clear
void clear();
The member function calls erase( begin(), end()).
vector::const_iterator
typedef T1 const_iterator;
The type describes an object that can serve as a constant random-access iterator for
the controlled sequence. It is described here as a synonym for the
implementation-defined type T1.
vector::const_pointer
typedef typename A::const_pointer
const_pointer;
The type describes an object that can serve as a constant pointer to an element of
the controlled sequence.
vector::const_reference
typedef typename A::const_reference
const_reference;
The type describes an object that can serve as a constant reference to an element of
the controlled sequence.
vector::const_reverse_iterator
typedef reverse_iterator<const_iterator>
const_reverse_iterator;
The type describes an object that can serve as a constant reverse iterator for the
controlled sequence.
vector::difference_type
typedef T3 difference_type;
The signed integer type describes an object that can represent the difference
between the addresses of any two elements in the controlled sequence. It is
described here as a synonym for the implementation-defined type T3.
vector::empty
bool empty() const;
The member function returns true for an empty controlled sequence.
vector::end
const_iterator end() const;
iterator end();
The member function returns a random-access iterator that points just beyond the
end of the sequence.
vector::erase
iterator erase(iterator it);
iterator erase(iterator first, iterator last);
407
Chapter 13. Standard Template Library C++
img
.....
The first member function removes the element of the controlled sequence pointed
to by it. The second member function removes the elements of the controlled
sequence in the range [first, last). Both return an iterator that designates the
first element remaining beyond any elements removed, or end() if no such element
exists.
Erasing N elements causes N destructor calls and an assignment for each of the
elements between the insertion point and the end of the sequence. No reallocation
(page 406) occurs, so iterators and references become invalid (page 406) only from
the first element erased through the end of the sequence.
The member functions never throw an exception.
vector::front
reference front();
const_reference front() const;
The member function returns a reference to the first element of the controlled
sequence, which must be non-empty.
vector::get_allocator
A get_allocator() const;
The member function returns the stored allocator object (page 337).
vector::insert
iterator insert(iterator it, const T& x);
void insert(iterator it, size_type n, const T& x);
template<class InIt>
void insert(iterator it, InIt first, InIt last);
Each of the member functions inserts, before the element pointed to by it in the
controlled sequence, a sequence specified by the remaining operands. The first
member function inserts a single element with value x and returns an iterator that
points to the newly inserted element. The second member function inserts a
repetition of n elements of value x.
If InIt is an integer type, the last member function behaves the same as
insert(it, (size_type)first, (T)last). Otherwise, the last member function
inserts the sequence [first, last), which must not overlap the initial controlled
sequence.
When inserting a single element, the number of element copies is linear in the
number of elements between the insertion point and the end of the sequence.
When inserting a single element at the end of the sequence, the amortized number
of element copies is constant. When inserting N elements, the number of element
copies is linear in N plus the number of elements between the insertion point and
the end of the sequence -- except when the template member is specialized for
InIt an input iterator, which behaves like N single insertions.
If reallocation (page 406) occurs, the size of the controlled sequence at least
doubles, and all iterators and references become invalid (page 406). If no
reallocation occurs, iterators become invalid only from the point of insertion
through the end of the sequence.
If an exception is thrown during the insertion of a single element, the container is
left unaltered and the exception is rethrown. If an exception is thrown during the
408
Standard C++ Library
insertion of multiple elements, and the exception is not thrown while copying an
element, the container is left unaltered and the exception is rethrown.
vector::iterator
typedef T0 iterator;
The type describes an object that can serve as a random-access iterator for the
controlled sequence. It is described here as a synonym for the
implementation-defined type T0.
vector::max_size
size_type max_size() const;
The member function returns the length of the longest sequence that the object can
control.
vector::operator[]
const_reference operator[](size_type pos) const;
reference operator[](size_type pos);
The member function returns a reference to the element of the controlled sequence
at position pos. If that position is invalid, the behavior is undefined.
vector::pointer
typedef typename A::pointer pointer;
The type describes an object that can serve as a pointer to an element of the
controlled sequence.
vector::pop_back
void pop_back();
The member function removes the last element of the controlled sequence, which
must be non-empty.
The member function never throws an exception.
vector::push_back
void push_back(const T& x);
The member function inserts an element with value x at the end of the controlled
sequence.
If an exception is thrown, the container is left unaltered and the exception is
rethrown.
vector::rbegin
const_reverse_iterator rbegin() const;
reverse_iterator rbegin();
The member function returns a reverse iterator that points just beyond the end of
the controlled sequence. Hence, it designates the beginning of the reverse
sequence.
vector::reference
typedef typename A::reference reference;
409
Chapter 13. Standard Template Library C++
The type describes an object that can serve as a reference to an element of the
controlled sequence.
vector::rend
const_reverse_iterator rend() const;
reverse_iterator rend();
The member function returns a reverse iterator that points at the first element of
the sequence (or just beyond the end of an empty sequence). Hence, it designates
the end of the reverse sequence.
vector::reserve
void reserve(size_type n);
If n is greater than max_size(), the member function reports a length error by
throwing an object of class length_error. Otherwise, it ensures that capacity()
henceforth returns at least n.
vector::resize
void resize(size_type n);
void resize(size_type n, T x);
The member functions both ensure that size() henceforth returns n. If it must
make the controlled sequence longer, the first member function appends elements
with value T(), while the second member function appends elements with value x.
To make the controlled sequence shorter, both member functions call
erase(begin() + n, end()).
vector::reverse_iterator
typedef reverse_iterator<iterator>
reverse_iterator;
The type describes an object that can serve as a reverse iterator for the controlled
sequence.
vector::size
size_type size() const;
The member function returns the length of the controlled sequence.
vector::size_type
typedef T2 size_type;
The unsigned integer type describes an object that can represent the length of any
controlled sequence. It is described here as a synonym for the
implementation-defined type T2.
vector::swap
void swap(vector& x);
The member function swaps the controlled sequences between *this and x. If
get_allocator() == x.get_allocator(), it does so in constant time, it throws no
exceptions, and it invalidates no references, pointers, or iterators that designate
elements in the two controlled sequences. Otherwise, it performs a number of
element assignments and constructor calls proportional to the number of elements
in the two controlled sequences.
410
Standard C++ Library
img
...
vector::value_type
typedef typename A::value_type value_type;
The type is a synonym for the template parameter T.
vector::vector
vector();
explicit vector(const A& al);
explicit vector(size_type n);
vector(size_type n, const T& x);
vector(size_type n, const T& x, const A& al);
vector(const vector& x);
template<class InIt>
vector(InIt first, InIt last);
template<class InIt>
vector(InIt first, InIt last, const A& al);
All constructors store an allocator object (page 337) and initialize the controlled
sequence. The allocator object is the argument al, if present. For the copy
constructor, it is x.get_allocator(). Otherwise, it is A().
The first two constructors specify an empty initial controlled sequence. The third
constructor specifies a repetition of n elements of value T(). The fourth and fifth
constructors specify a repetition of n elements of value x. The sixth constructor
specifies a copy of the sequence controlled by x. If InIt is an integer type, the last
two constructors specify a repetition of (size_type)first elements of value
(T)last. Otherwise, the last two constructors specify the sequence [first, last).
All constructors copy N elements and perform no interim reallocation (page 406).
vector<bool, A>
template<class A>
class vector<bool, A> {
public:
class reference;
typedef bool const_reference;
typedef T0 iterator;
typedef T1 const_iterator;
typedef T4 pointer;
typedef T5 const_pointer;
void flip();
static void swap(reference x, reference y);
// rest same as template class vector
};
The class is a partial specialization of template class vector (page 404) for elements
of type bool. It alters the definition of four member types (to optimize the packing
and unpacking of elements) and adds two member functions. Its behavior is
otherwise the same as for template class vector.
vector<bool, A>::const_iterator
typedef T1 const_iterator;
The type describes an object that can serve as a constant random-access iterator for
the controlled sequence. It is described here as a synonym for the unspecified type
T1.
vector<bool, A>::const_pointer
typedef T5 const_pointer;
411
Chapter 13. Standard Template Library C++
The type describes an object that can serve as a pointer to a constant element of
the controlled sequence. It is described here as a synonym for the unspecified type
T5.
vector<bool, A>::const_reference
typedef bool const_reference;
The type describes an object that can serve as a constant reference to an element of
the controlled sequence, in this case bool.
vector<bool, A>::flip
void flip();
The member function inverts the values of all the members of the controlled
sequence.
vector<bool, A>::iterator
typedef T0 iterator;
The type describes an object that can serve as a random-access iterator for the
controlled sequence. It is described here as a synonym for the unspecified type T0.
vector<bool, A>::pointer
typedef T4 pointer;
The type describes an object that can serve as a pointer to an element of the
controlled sequence. It is described here as a synonym for the unspecified type T4.
vector<bool, A>::reference
class reference {
public:
reference& operator=(const reference& x);
reference& operator=(bool x);
void flip();
bool operator~() const;
operator bool() const;
};
The type describes an object that can serve as a reference to an element of the
controlled sequence. Specifically, for two objects x and y of class reference:
v bool(x) yields the value of the element designated by x
v ~x yields the inverted value of the element designated by x
v x.flip() inverts the value stored in x
v y = bool(x) and y = x both assign the value of the element designated by x to
the element designated by y
It is unspecified how member functions of class vector<bool> construct objects of
class reference that designate elements of a controlled sequence. The default
constructor for class reference generates an object that refers to no such element.
vector<bool, A>::swap
void swap(reference x, reference y);
The static member function swaps the members of the controlled sequences
designated by x and y.
412
Standard C++ Library
Portions derived from work copyright © 1994 by Hewlett-Packard Company. All rights
reserved.
413
Chapter 13. Standard Template Library C++
414
Standard C++ Library
Table of Contents:
  1. C++ Library
  2. C++ Library Overview:Using C++ Library Headers, Iostreams Conventions
  3. Characters:Escape Sequences, Multibyte Characters, Wide-Character Encoding
  4. Expressions
  5. Files and Streams:Text and Binary Streams, Controlling Streams, Stream States
  6. Indefinite Integrals of Logarithmic Functions:Combinations of Logarithms and Polynomials, The Logarithm
  7. Formatted Input:Scan Formats, Scan Functions, Scan Conversion Specifiers
  8. Formatted Output:Print Formats, Print Functions, Print Conversion Specifiers
  9. STL Conventions:Iterator Conventions, Algorithm Conventions
  10. Containers:Cont::const_reference, difference_type, reverse_iterator
  11. Preprocessing
  12. Standard C++ Library Header Files:bitset, conj, cos, showpoint, streampos
  13. Standard Template Library C++:adjacent_find, copy_backward, lexicographical_compare
  14. Appendix. Type Traits:Helper Class, Primary Type Categories, Binary Type Traits
  15. Notices:References, Bug Reports