|
|
|
28.7.1
Sorting
[alg.sort]
28.7.1.1
sort
[sort]
template<class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);
template<class ExecutionPolicy, class RandomAccessIterator>
void sort(ExecutionPolicy&& exec,
RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void sort(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
void sort(ExecutionPolicy&& exec,
RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
1
Requires: RandomAccessIterator shall satisfy the requirements of ValueSwappable (20.5.3.2). The
type of *first shall satisfy the requirements of MoveConstructible (Table 23) and of MoveAssignable
(Table 25).
2
Effects: Sorts the elements in the range [first, last).
3
Complexity: O(N log N ) comparisons, where N = last - first.
28.7.1.2
stable_sort
[stable.sort]
template<class RandomAccessIterator>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
template<class ExecutionPolicy, class RandomAccessIterator>
void stable_sort(ExecutionPolicy&& exec,
RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
void stable_sort(ExecutionPolicy&& exec,
RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
1
Requires: RandomAccessIterator shall satisfy the requirements of ValueSwappable (20.5.3.2). The
type of *first shall satisfy the requirements of MoveConstructible (Table 23) and of MoveAssignable
(Table 25).
2
Effects: Sorts the elements in the range [first, last).
3
Complexity: At most N log2(N ) comparisons, where N = last - first, but only N log N comparisons
if there is enough extra memory.
4
Remarks: Stable (20.5.5.7).
28.7.1.3
partial_sort
[partial.sort]
template<class RandomAccessIterator>
void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last);
template<class ExecutionPolicy, class RandomAccessIterator>
void partial_sort(ExecutionPolicy&& exec,
RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last);
§ 28.7.1.3
922
template<class RandomAccessIterator, class Compare>
void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last,
Compare comp);
template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
void partial_sort(ExecutionPolicy&& exec,
RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last,
Compare comp);
1
Requires: RandomAccessIterator shall satisfy the requirements of ValueSwappable (20.5.3.2). The
type of *first shall satisfy the requirements of MoveConstructible (Table 23) and of MoveAssignable
(Table 25).
2
Effects: Places the first middle - first sorted elements from the range [first, last) into the range
[first, middle). The rest of the elements in the range [middle, last) are placed in an unspecified
order.
3
Complexity: Approximately (last - first) * log(middle - first) comparisons.
28.7.1.4
partial_sort_copy
[partial.sort.copy]
template<class InputIterator, class RandomAccessIterator>
RandomAccessIterator
partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last);
template<class ExecutionPolicy, class ForwardIterator, class RandomAccessIterator>
RandomAccessIterator
partial_sort_copy(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last);
template<class InputIterator, class RandomAccessIterator,
class Compare>
RandomAccessIterator
partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last,
Compare comp);
template<class ExecutionPolicy, class ForwardIterator, class RandomAccessIterator,
class Compare>
RandomAccessIterator
partial_sort_copy(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last,
Compare comp);
1
Requires: RandomAccessIterator shall satisfy the requirements of ValueSwappable (20.5.3.2). The
type of *result_first shall satisfy the requirements of MoveConstructible (Table 23) and of Move-
Assignable (Table 25).
2
Effects: Places the first min(last - first, result_last - result_first) sorted elements into the
range [result_first, result_first + min(last - first, result_last - result_first)).
3
Returns: The smaller of: result_last or result_first + (last - first).
4
Complexity: Approximately (last - first) * log(min(last - first, result_last - result_-
first)) comparisons.
§ 28.7.1.4
923
28.7.1.5
is_sorted
[is.sorted]
template<class ForwardIterator>
constexpr bool is_sorted(ForwardIterator first, ForwardIterator last);
1
Returns: is_sorted_until(first, last) == last
template<class ExecutionPolicy, class ForwardIterator>
bool is_sorted(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last);
2
Returns: is_sorted_until(std::forward<ExecutionPolicy>(exec),
first, last)
==
last
template<class ForwardIterator, class Compare>
constexpr bool is_sorted(ForwardIterator first, ForwardIterator last,
Compare comp);
3
Returns: is_sorted_until(first, last, comp) == last
template<class ExecutionPolicy, class ForwardIterator, class Compare>
bool is_sorted(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last,
Compare comp);
4
Returns:
is_sorted_until(std::forward<ExecutionPolicy>(exec), first, last,
comp)
== last
template<class ForwardIterator>
constexpr ForwardIterator
is_sorted_until(ForwardIterator first, ForwardIterator last);
template<class ExecutionPolicy, class ForwardIterator>
ForwardIterator
is_sorted_until(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class Compare>
constexpr ForwardIterator
is_sorted_until(ForwardIterator first, ForwardIterator last,
Compare comp);
template<class ExecutionPolicy, class ForwardIterator, class Compare>
ForwardIterator
is_sorted_until(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last,
Compare comp);
5
Returns: If (last - first) < 2, returns last. Otherwise, returns the last iterator i in [first,
last] for which the range [first, i) is sorted.
6
Complexity: Linear.
28.7.2
Nth element
[alg.nth.element]
template<class RandomAccessIterator>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last);
template<class ExecutionPolicy, class RandomAccessIterator>
void nth_element(ExecutionPolicy&& exec,
RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last, Compare comp);
template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
void nth_element(ExecutionPolicy&& exec,
RandomAccessIterator first, RandomAccessIterator nth,
§ 28.7.2
924
RandomAccessIterator last, Compare comp);
1
Requires: RandomAccessIterator shall satisfy the requirements of ValueSwappable (20.5.3.2). The
type of *first shall satisfy the requirements of MoveConstructible (Table 23) and of MoveAssignable
(Table 25).
2
Effects: After nth_element the element in the position pointed to by nth is the element that would
be in that position if the whole range were sorted, unless nth == last. Also for every iterator i in
the range [first, nth) and every iterator j in the range [nth, last) it holds that: !(*j < *i) or
comp(*j, *i) == false.
3
Complexity: For the overloads with no ExecutionPolicy, linear on average. For the overloads
with an ExecutionPolicy, O(N) applications of the predicate, and O(N log N) swaps, where N =
last - first.
28.7.3
Binary search
[alg.binary.search]
1
All of the algorithms in this subclause are versions of binary search and assume that the sequence being
searched is partitioned with respect to an expression formed by binding the search key to an argument of the
implied or explicit comparison function. They work on non-random access iterators minimizing the number of
comparisons, which will be logarithmic for all types of iterators. They are especially appropriate for random
access iterators, because these algorithms do a logarithmic number of steps through the data structure. For
non-random access iterators they execute a linear number of steps.
28.7.3.1
lower_bound
[lower.bound]
template<class ForwardIterator, class T>
constexpr ForwardIterator
lower_bound(ForwardIterator first, ForwardIterator last,
const T& value);
template<class ForwardIterator, class T, class Compare>
constexpr ForwardIterator
lower_bound(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);
1
Requires: The elements e of [first, last) shall be partitioned with respect to the expression e <
value or comp(e, value).
2
Returns: The furthermost iterator i in the range [first, last] such that for every iterator j in the
range [first, i) the following corresponding conditions hold: *j < value or comp(*j, value) !=
false.
3
Complexity: At most log2(last - first) + O(1) comparisons.
28.7.3.2
upper_bound
[upper.bound]
template<class ForwardIterator, class T>
constexpr ForwardIterator
upper_bound(ForwardIterator first, ForwardIterator last,
const T& value);
template<class ForwardIterator, class T, class Compare>
constexpr ForwardIterator
upper_bound(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);
1
Requires: The elements e of [first, last) shall be partitioned with respect to the expression !(value
< e) or !comp(value, e).
2
Returns: The furthermost iterator i in the range [first, last] such that for every iterator j in the
range [first, i) the following corresponding conditions hold: !(value < *j) or comp(value, *j)
== false.
3
Complexity: At most log2(last - first) + O(1) comparisons.
§ 28.7.3.2
925
28.7.3.3
equal_range
[equal.range]
template<class ForwardIterator, class T>
constexpr pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first,
ForwardIterator last, const T& value);
template<class ForwardIterator, class T, class Compare>
constexpr pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first,
ForwardIterator last, const T& value,
Compare comp);
1
Requires: The elements e of [first, last) shall be partitioned with respect to the expressions e
< value and !(value < e) or comp(e, value) and !comp(value, e). Also, for all elements e of
[first, last), e < value shall imply !(value < e) or comp(e, value) shall imply !comp(value,
e).
2
Returns:
make_pair(lower_bound(first, last, value),
upper_bound(first, last, value))
or
make_pair(lower_bound(first, last, value, comp),
upper_bound(first, last, value, comp))
3
Complexity: At most 2 ∗ log2(last - first) + O(1) comparisons.
28.7.3.4
binary_search
[binary.search]
template<class ForwardIterator, class T>
constexpr bool
binary_search(ForwardIterator first, ForwardIterator last,
const T& value);
template<class ForwardIterator, class T, class Compare>
constexpr bool
binary_search(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);
1
Requires: The elements e of [first, last) shall be partitioned with respect to the expressions e
< value and !(value < e) or comp(e, value) and !comp(value, e). Also, for all elements e of
[first, last), e < value shall imply !(value < e) or comp(e, value) shall imply !comp(value,
e).
2
Returns: true if there is an iterator i in the range [first, last) that satisfies the correspond-
ing conditions: !(*i < value) && !(value < *i) or comp(*i, value) == false && comp(value,
*i) == false.
3
Complexity: At most log2(last - first) + O(1) comparisons.
28.7.4
Partitions
[alg.partitions]
template<class InputIterator, class Predicate>
constexpr bool is_partitioned(InputIterator first, InputIterator last, Predicate pred);
template<class ExecutionPolicy, class ForwardIterator, class Predicate>
bool is_partitioned(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last, Predicate pred);
1
Requires: For the overload with no ExecutionPolicy, InputIterator’s value type shall be convertible
to Predicate’s argument type. For the overload with an ExecutionPolicy, ForwardIterator’s value
type shall be convertible to Predicate’s argument type.
2
Returns: true if [first, last) is empty or if the elements e of [first, last) are partitioned with
respect to the expression pred(e).
3
Complexity: Linear. At most last - first applications of pred.
§ 28.7.4
926
template<class ForwardIterator, class Predicate>
ForwardIterator
partition(ForwardIterator first, ForwardIterator last, Predicate pred);
template<class ExecutionPolicy, class ForwardIterator, class Predicate>
ForwardIterator
partition(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last, Predicate pred);
4
Requires: ForwardIterator shall satisfy the requirements of ValueSwappable (20.5.3.2).
5
Effects: Places all the elements in the range [first, last) that satisfy pred before all the elements
that do not satisfy it.
6
Returns: An iterator i such that for every iterator j in the range [first, i) pred(*j) != false,
and for every iterator k in the range [i, last), pred(*k) == false.
7
Complexity: Let N = last - first:
(7.1)
—
For the overload with no ExecutionPolicy, exactly N applications of the predicate. At most
N/2 swaps if ForwardIterator meets the BidirectionalIterator requirements and at most N
swaps otherwise.
(7.2)
—
For the overload with an ExecutionPolicy, O(N log N ) swaps and O(N ) applications of the
predicate.
template<class BidirectionalIterator, class Predicate>
BidirectionalIterator
stable_partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred);
template<class ExecutionPolicy, class BidirectionalIterator, class Predicate>
BidirectionalIterator
stable_partition(ExecutionPolicy&& exec,
BidirectionalIterator first, BidirectionalIterator last, Predicate pred);
8
Requires: BidirectionalIterator shall satisfy the requirements of ValueSwappable (20.5.3.2). The
type of *first shall satisfy the requirements of MoveConstructible (Table 23) and of MoveAssignable
(Table 25).
9
Effects: Places all the elements in the range [first, last) that satisfy pred before all the elements
that do not satisfy it.
10
Returns: An iterator i such that for every iterator j in the range [first, i), pred(*j) != false, and
for every iterator k in the range [i, last), pred(*k) == false. The relative order of the elements
in both groups is preserved.
11
Complexity: Let N = last - first:
(11.1)
—
For the overload with no ExecutionPolicy, at most N log N swaps, but only O(N ) swaps if there
is enough extra memory. Exactly N applications of the predicate.
(11.2)
—
For the overload with an ExecutionPolicy, O(N log N ) swaps and O(N ) applications of the
predicate.
template<class InputIterator, class OutputIterator1,
class OutputIterator2, class Predicate>
constexpr pair<OutputIterator1, OutputIterator2>
partition_copy(InputIterator first, InputIterator last,
OutputIterator1 out_true, OutputIterator2 out_false, Predicate pred);
template<class ExecutionPolicy, class ForwardIterator, class ForwardIterator1,
class ForwardIterator2, class Predicate>
pair<ForwardIterator1, ForwardIterator2>
partition_copy(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last,
ForwardIterator1 out_true, ForwardIterator2 out_false, Predicate pred);
12
Requires:
(12.1)
—
For the overload with no ExecutionPolicy, InputIterator’s value type shall be CopyAssignable
(Table 26), and shall be writable (27.2.1) to the out_true and out_false OutputIterators, and
shall be convertible to Predicate’s argument type.
§ 28.7.4
927
(12.2)
—
For the overload with an ExecutionPolicy, ForwardIterator’s value type shall be CopyAssign-
able, and shall be writable to the out_true and out_false ForwardIterators, and shall
be convertible to Predicate’s argument type.
[Note: There may be a performance cost if
ForwardIterator’s value type is not CopyConstructible.
— end note ]
(12.3)
—
For both overloads, the input range shall not overlap with either of the output ranges.
13
Effects: For each iterator i in [first, last), copies *i to the output range beginning with out_true
if pred(*i) is true, or to the output range beginning with out_false otherwise.
14
Returns: A pair p such that p.first is the end of the output range beginning at out_true and
p.second is the end of the output range beginning at out_false.
15
Complexity: Exactly last - first applications of pred.
template<class ForwardIterator, class Predicate>
constexpr ForwardIterator
partition_point(ForwardIterator first, ForwardIterator last, Predicate pred);
16
Requires: ForwardIterator’s value type shall be convertible to Predicate’s argument type. The
elements e of [first, last) shall be partitioned with respect to the expression pred(e).
17
Returns: An iterator mid such that all_of(first, mid, pred) and none_of(mid,
last, pred) are
both true.
18
Complexity: O(log(last - first)) applications of pred.
28.7.5
Merge
[alg.merge]
template<class InputIterator1, class InputIterator2,
class OutputIterator>
constexpr OutputIterator
merge(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
template<class ExecutionPolicy, class ForwardIterator1, class
ForwardIterator2,
class ForwardIterator>
ForwardIterator
merge(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator result);
template<class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
constexpr OutputIterator
merge(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
template<class ExecutionPolicy, class ForwardIterator1, class
ForwardIterator2,
class ForwardIterator, class Compare>
ForwardIterator
merge(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator result, Compare comp);
1
Requires: The ranges [first1, last1) and [first2, last2) shall be sorted with respect to oper-
ator< or comp. The resulting range shall not overlap with either of the original ranges.
2
Effects: Copies all the elements of the two ranges [first1, last1) and [first2, last2) into
the range [result, result_last), where result_last is result + (last1 - first1) + (last2 -
first2), such that the resulting range satisfies is_sorted(result, result_last) or is_sorted(re-
sult, result_last, comp), respectively.
3
Returns: result + (last1 - first1) + (last2 - first2).
4
Complexity: Let N = (last1 - first1) + (last2 - first2):
(4.1)
—
For the overloads with no ExecutionPolicy, at most N − 1 comparisons.
§ 28.7.5
928
(4.2)
—
For the overloads with an ExecutionPolicy, O(N ) comparisons.
5
Remarks: Stable (20.5.5.7).
template<class BidirectionalIterator>
void inplace_merge(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last);
template<class ExecutionPolicy, class BidirectionalIterator>
void inplace_merge(ExecutionPolicy&& exec,
BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last);
template<class BidirectionalIterator, class Compare>
void inplace_merge(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last, Compare comp);
template<class ExecutionPolicy, class BidirectionalIterator, class Compare>
void inplace_merge(ExecutionPolicy&& exec,
BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last, Compare comp);
6
Requires: The ranges [first, middle) and [middle, last) shall be sorted with respect to operator<
or comp. BidirectionalIterator shall satisfy the requirements of ValueSwappable (20.5.3.2). The
type of *first shall satisfy the requirements of MoveConstructible (Table 23) and of MoveAssignable
(Table 25).
7
Effects: Merges two sorted consecutive ranges [first, middle) and [middle, last), putting the
result of the merge into the range [first, last). The resulting range will be in non-decreasing order;
that is, for every iterator i in [first, last) other than first, the condition *i < *(i - 1) or,
respectively, comp(*i, *(i - 1)) will be false.
8
Complexity: Let N = last - first:
(8.1)
—
For the overloads with no ExecutionPolicy, if enough additional memory is available, exactly
N − 1 comparisons.
(8.2)
—
For the overloads with no ExecutionPolicy if no additional memory is available, O(N log N )
comparisons.
(8.3)
—
For the overloads with an ExecutionPolicy, O(N log N ) comparisons.
9
Remarks: Stable (20.5.5.7).
28.7.6
Set operations on sorted structures
[alg.set.operations]
1
This subclause defines all the basic set operations on sorted structures. They also work with multisets (26.4.7)
containing multiple copies of equivalent elements. The semantics of the set operations are generalized to
multisets in a standard way by defining set_union() to contain the maximum number of occurrences of
every element, set_intersection() to contain the minimum, and so on.
28.7.6.1
includes
[includes]
template<class InputIterator1, class InputIterator2>
constexpr bool includes(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
bool includes(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);
template<class InputIterator1, class InputIterator2, class Compare>
constexpr bool includes(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
Compare comp);
§ 28.7.6.1
929
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class Compare>
bool includes(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
Compare comp);
1
Returns: true if [first2, last2) is empty or if every element in the range [first2, last2) is
contained in the range [first1, last1). Returns false otherwise.
2
Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 comparisons.
28.7.6.2
set_union
[set.union]
template<class InputIterator1, class InputIterator2,
class OutputIterator>
constexpr OutputIterator
set_union(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class ForwardIterator>
ForwardIterator
set_union(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator result);
template<class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
constexpr OutputIterator
set_union(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class ForwardIterator, class Compare>
ForwardIterator
set_union(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator result, Compare comp);
1
Requires: The resulting range shall not overlap with either of the original ranges.
2
Effects: Constructs a sorted union of the elements from the two ranges; that is, the set of elements that
are present in one or both of the ranges.
3
Returns: The end of the constructed range.
4
Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 comparisons.
5
Remarks: If [first1, last1) contains m elements that are equivalent to each other and [first2,
last2) contains n elements that are equivalent to them, then all m elements from the first range shall
be copied to the output range, in order, and then max(n − m,0) elements from the second range shall
be copied to the output range, in order.
28.7.6.3
set_intersection
[set.intersection]
template<class InputIterator1, class InputIterator2,
class OutputIterator>
constexpr OutputIterator
set_intersection(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class ForwardIterator>
ForwardIterator
set_intersection(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
§ 28.7.6.3
930
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator result);
template<class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
constexpr OutputIterator
set_intersection(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class ForwardIterator, class Compare>
ForwardIterator
set_intersection(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator result, Compare comp);
1
Requires: The resulting range shall not overlap with either of the original ranges.
2
Effects: Constructs a sorted intersection of the elements from the two ranges; that is, the set of elements
that are present in both of the ranges.
3
Returns: The end of the constructed range.
4
Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 comparisons.
5
Remarks: If [first1, last1) contains m elements that are equivalent to each other and [first2,
last2) contains n elements that are equivalent to them, the first min(m, n) elements shall be copied
from the first range to the output range, in order.
28.7.6.4
set_difference
[set.difference]
template<class InputIterator1, class InputIterator2,
class OutputIterator>
constexpr OutputIterator
set_difference(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class ForwardIterator>
ForwardIterator
set_difference(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator result);
template<class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
constexpr OutputIterator
set_difference(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class ForwardIterator, class Compare>
ForwardIterator
set_difference(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator result, Compare comp);
1
Requires: The resulting range shall not overlap with either of the original ranges.
2
Effects: Copies the elements of the range [first1, last1) which are not present in
the
range
[first2, last2) to the range beginning at result. The elements in the constructed range are sorted.
3
Returns: The end of the constructed range.
4
Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 comparisons.
§ 28.7.6.4
931
5
Remarks: If [first1, last1) contains m elements that are equivalent to each other and [first2,
last2) contains n elements that are equivalent to them, the last max(m − n, 0) elements from
[first1, last1) shall be copied to the output range.
28.7.6.5
set_symmetric_difference
[set.symmetric.difference]
template<class InputIterator1, class InputIterator2,
class OutputIterator>
constexpr OutputIterator
set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class ForwardIterator>
ForwardIterator
set_symmetric_difference(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator result);
template<class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
constexpr OutputIterator
set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class ForwardIterator, class Compare>
ForwardIterator
set_symmetric_difference(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator result, Compare comp);
1
Requires: The resulting range shall not overlap with either of the original ranges.
2
Effects: Copies the elements of the range [first1, last1) that are not present in the range [first2,
last2), and the elements of the range [first2, last2) that are not present in the range [first1,
last1) to the range beginning at result. The elements in the constructed range are sorted.
3
Returns: The end of the constructed range.
4
Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 comparisons.
5
Remarks: If [first1, last1) contains m elements that are equivalent to each other and [first2,
last2) contains n elements that are equivalent to them, then |m − n| of those elements shall be copied
to the output range: the last m − n of these elements from [first1, last1) if m > n, and the last
n − m of these elements from [first2, last2) if m < n.
28.7.7
Heap operations
[alg.heap.operations]
1
A heap is a particular organization of elements in a range between two random access iterators [a, b) such
that:
⌊i−1⌋
(1.1)
—
With N = b - a, for all i, 0 < i < N , comp(a[
], a[i]) is false.
2
(1.2)
—
*a may be removed by pop_heap(), or a new element added by push_heap(), in O(log N ) time.
2
These properties make heaps useful as priority queues.
3
make_heap() converts a range into a heap and sort_heap() turns a heap into a sorted sequence.
28.7.7.1
push_heap
[push.heap]
template<class RandomAccessIterator>
void push_heap(RandomAccessIterator first, RandomAccessIterator last);
§ 28.7.7.1
932
template<class RandomAccessIterator, class Compare>
void push_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
1
Requires: The range [first, last - 1) shall be a valid heap. The type of *first shall satisfy the
MoveConstructible requirements (Table 23) and the MoveAssignable requirements (Table 25).
2
Effects: Places the value in the location last - 1 into the resulting heap [first, last).
3
Complexity: At most log(last - first) comparisons.
28.7.7.2
pop_heap
[pop.heap]
template<class RandomAccessIterator>
void pop_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void pop_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
1
Requires: The range [first, last) shall be a valid non-empty heap. RandomAccessIterator shall
satisfy the requirements of ValueSwappable (20.5.3.2). The type of *first shall satisfy the requirements
of MoveConstructible (Table 23) and of MoveAssignable (Table 25).
2
Effects: Swaps the value in the location first with the value in the location last - 1 and makes
[first, last - 1) into a heap.
3
Complexity: At most 2 log(last - first) comparisons.
28.7.7.3
make_heap
[make.heap]
template<class RandomAccessIterator>
void make_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void make_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
1
Requires: The type of *first shall satisfy the MoveConstructible requirements (Table 23) and the
MoveAssignable requirements (Table 25).
2
Effects: Constructs a heap out of the range [first, last).
3
Complexity: At most 3(last - first) comparisons.
28.7.7.4
sort_heap
[sort.heap]
template<class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
1
Requires: The range [first, last) shall be a valid heap. RandomAccessIterator shall satisfy the
requirements of ValueSwappable (20.5.3.2). The type of *first shall satisfy the requirements of
MoveConstructible (Table 23) and of MoveAssignable (Table 25).
2
Effects: Sorts elements in the heap [first, last).
3
Complexity: At most 2N log N comparisons, where N = last - first.
28.7.7.5
is_heap
[is.heap]
template<class RandomAccessIterator>
constexpr bool is_heap(RandomAccessIterator first, RandomAccessIterator last);
1
Returns: is_heap_until(first, last) == last
§ 28.7.7.5
933
template<class ExecutionPolicy, class RandomAccessIterator>
bool is_heap(ExecutionPolicy&& exec,
RandomAccessIterator first, RandomAccessIterator last);
2
Returns: is_heap_until(std::forward<ExecutionPolicy>(exec), first, last)
==
last
template<class RandomAccessIterator, class Compare>
constexpr bool is_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
3
Returns: is_heap_until(first, last, comp) == last
template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
bool is_heap(ExecutionPolicy&& exec,
RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
4
Returns:
is_heap_until(std::forward<ExecutionPolicy>(exec), first, last, comp) == last
template<class RandomAccessIterator>
constexpr RandomAccessIterator
is_heap_until(RandomAccessIterator first, RandomAccessIterator last);
template<class ExecutionPolicy, class RandomAccessIterator>
RandomAccessIterator
is_heap_until(ExecutionPolicy&& exec,
RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
constexpr RandomAccessIterator
is_heap_until(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
RandomAccessIterator
is_heap_until(ExecutionPolicy&& exec,
RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
5
Returns: If (last - first) < 2, returns last. Otherwise, returns the last iterator i in [first,
last] for which the range [first, i) is a heap.
6
Complexity: Linear.
28.7.8
Minimum and maximum
[alg.min.max]
template<class T> constexpr const T& min(const T& a, const T& b);
template<class T, class Compare>
constexpr const T& min(const T& a, const T& b, Compare comp);
1
Requires: For the first form, type T shall be LessThanComparable (Table 21).
2
Returns: The smaller value.
3
Remarks: Returns the first argument when the arguments are equivalent.
4
Complexity: Exactly one comparison.
template<class T>
constexpr T min(initializer_list<T> t);
template<class T, class Compare>
constexpr T min(initializer_list<T> t, Compare comp);
5
Requires: T shall be CopyConstructible and t.size() > 0. For the first form, type T shall be
LessThanComparable.
6
Returns: The smallest value in the initializer_list.
7
Remarks: Returns a copy of the leftmost argument when several arguments are equivalent to the
smallest.
8
Complexity: Exactly t.size() - 1 comparisons.
§ 28.7.8
934
template<class T> constexpr const T& max(const T& a, const T& b);
template<class T, class Compare>
constexpr const T& max(const T& a, const T& b, Compare comp);
9
Requires: For the first form, type T shall be LessThanComparable (Table 21).
10
Returns: The larger value.
11
Remarks: Returns the first argument when the arguments are equivalent.
12
Complexity: Exactly one comparison.
template<class T>
constexpr T max(initializer_list<T> t);
template<class T, class Compare>
constexpr T max(initializer_list<T> t, Compare comp);
13
Requires: T shall be CopyConstructible and t.size() > 0. For the first form, type T shall be
LessThanComparable.
14
Returns: The largest value in the initializer_list.
15
Remarks: Returns a copy of the leftmost argument when several arguments are equivalent to the largest.
16
Complexity: Exactly t.size() - 1 comparisons.
template<class T> constexpr pair<const T&, const T&> minmax(const T& a, const T& b);
template<class T, class Compare>
constexpr pair<const T&, const T&> minmax(const T& a, const T& b, Compare comp);
17
Requires: For the first form, type T shall be LessThanComparable (Table 21).
18
Returns: pair<const T&, const T&>(b, a) if b is smaller than a, and pair<const T&, const
T&>(a, b) otherwise.
19
Remarks: Returns pair<const T&, const T&>(a, b) when the arguments are equivalent.
20
Complexity: Exactly one comparison.
template<class T>
constexpr pair<T, T> minmax(initializer_list<T> t);
template<class T, class Compare>
constexpr pair<T, T> minmax(initializer_list<T> t, Compare comp);
21
Requires: T shall be CopyConstructible and t.size() > 0. For the first form, type T shall be
LessThanComparable.
22
Returns: pair<T, T>(x, y), where x has the smallest and y has the largest value in the initializer list.
23
Remarks: x is a copy of the leftmost argument when several arguments are equivalent to the smallest.
y is a copy of the rightmost argument when several arguments are equivalent to the largest.
24
Complexity: At most (3/2)t.size() applications of the corresponding predicate.
template<class ForwardIterator>
constexpr ForwardIterator min_element(ForwardIterator first, ForwardIterator last);
template<class ExecutionPolicy, class ForwardIterator>
ForwardIterator min_element(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class Compare>
constexpr ForwardIterator min_element(ForwardIterator first, ForwardIterator last,
Compare comp);
template<class ExecutionPolicy, class ForwardIterator, class Compare>
ForwardIterator min_element(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last,
Compare comp);
25
Returns: The first iterator i in the range [first, last) such that for every iterator j in the range
[first, last) the following corresponding conditions hold: !(*j < *i) or comp(*j, *i) == false.
Returns last if first == last.
§ 28.7.8
935
26
Complexity: Exactly max(last - first - 1, 0) applications of the corresponding comparisons.
template<class ForwardIterator>
constexpr ForwardIterator max_element(ForwardIterator first, ForwardIterator last);
template<class ExecutionPolicy, class ForwardIterator>
ForwardIterator max_element(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class Compare>
constexpr ForwardIterator max_element(ForwardIterator first, ForwardIterator last,
Compare comp);
template<class ExecutionPolicy, class ForwardIterator, class Compare>
ForwardIterator max_element(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last,
Compare comp);
27
Returns: The first iterator i in the range [first, last) such that for every iterator j in the range
[first, last) the following corresponding conditions hold: !(*i < *j) or comp(*i, *j) == false.
Returns last if first == last.
28
Complexity: Exactly max(last - first - 1, 0) applications of the corresponding comparisons.
template<class ForwardIterator>
constexpr pair<ForwardIterator, ForwardIterator>
minmax_element(ForwardIterator first, ForwardIterator last);
template<class ExecutionPolicy, class ForwardIterator>
pair<ForwardIterator, ForwardIterator>
minmax_element(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class Compare>
constexpr pair<ForwardIterator, ForwardIterator>
minmax_element(ForwardIterator first, ForwardIterator last, Compare comp);
template<class ExecutionPolicy, class ForwardIterator, class Compare>
pair<ForwardIterator, ForwardIterator>
minmax_element(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last, Compare comp);
29
Returns: make_pair(first, first) if [first, last) is empty, otherwise make_pair(m, M), where
m is the first iterator in [first, last) such that no iterator in the range refers to a smaller element,
and where M is the last iterator269 in [first, last) such that no iterator in the range refers to a
larger element.
⌊3
⌋
30
Complexity: At most max(
(N − 1)
, 0) applications of the corresponding predicate, where N is last
2
- first.
28.7.9
Bounded value
[alg.clamp]
template<class T>
constexpr const T& clamp(const T& v, const T& lo, const T& hi);
template<class T, class Compare>
constexpr const T& clamp(const T& v, const T& lo, const T& hi, Compare comp);
1
Requires: The value of lo shall be no greater than hi. For the first form, type T shall be LessThan-
Comparable (Table 21).
2
Returns: lo if v is less than lo, hi if hi is less than v, otherwise v.
3
[ Note: If NaN is avoided, T can be a floating-point type.
— end note ]
4
Complexity: At most two comparisons.
28.7.10
Lexicographical comparison
[alg.lex.comparison]
template<class InputIterator1, class InputIterator2>
constexpr bool
269) This behavior intentionally differs from max_element().
§ 28.7.10
936
lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
bool
lexicographical_compare(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);
template<class InputIterator1, class InputIterator2, class Compare>
constexpr bool
lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
Compare comp);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class Compare>
bool
lexicographical_compare(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
Compare comp);
1
Returns: true if the sequence of elements defined by the range [first1, last1) is lexicographically
less than the sequence of elements defined by the range [first2, last2) and false otherwise.
2
Complexity: At most 2 min(last1 - first1, last2 - first2) applications of the corresponding
comparison.
3
Remarks: If two sequences have the same number of elements and their corresponding elements (if any)
are equivalent, then neither sequence is lexicographically less than the other. If one sequence is a prefix
of the other, then the shorter sequence is lexicographically less than the longer sequence. Otherwise,
the lexicographical comparison of the sequences yields the same result as the comparison of the first
corresponding pair of elements that are not equivalent.
4
[ Example: The following sample implementation satisfies these requirements:
for ( ; first1 != last1 && first2 != last2 ; ++first1, (void) ++first2) {
if (*first1 < *first2) return true;
if (*first2 < *first1) return false;
}
return first1 == last1 && first2 != last2;
— end example ]
5
[Note: An empty sequence is lexicographically less than any non-empty sequence, but not less than
any empty sequence. — end note ]
28.7.11
Three-way comparison algorithms
[alg.3way]
template<class T, class U> constexpr auto compare_3way(const T& a, const U& b);
1
Effects: Compares two values and produces a result of the strongest applicable comparison category
type:
(1.1)
—
Returns a <=> b if that expression is well-formed.
(1.2)
—
Otherwise, if the expressions a == b and a < b are each well-formed and convertible to bool, re-
turns strong_ordering::equal when a == b is true, otherwise returns strong_ordering::less
when a < b is true, and otherwise returns strong_ordering::greater.
(1.3)
—
Otherwise, if the expression a == b is well-formed and convertible to bool, returns strong_-
equality::equal when a == b is true, and otherwise returns strong_equality::nonequal.
(1.4)
—
Otherwise, the function is defined as deleted.
template<class InputIterator1, class InputIterator2, class Cmp>
constexpr auto
lexicographical_compare_3way(InputIterator1 b1, InputIterator1 e1,
InputIterator2 b2, InputIterator2 e2,
Cmp comp)
§ 28.7.11
937
-> common_comparison_category_t<decltype(comp(*b1, *b2)), strong_ordering>;
2
Requires: Cmp shall be a function object type whose return type is a comparison category type.
3
Effects: Lexicographically compares two ranges and produces a result of the strongest applicable
comparison category type. Equivalent to:
for ( ; b1 != e1 && b2 != e2; void(++b1), void(++b2) )
if (auto cmp = comp(*b1,*b2); cmp != 0)
return cmp;
return b1 != e1 ? strong_ordering::greater :
b2 != e2 ? strong_ordering::less :
strong_ordering::equal;
template<class InputIterator1, class InputIterator2>
constexpr auto
lexicographical_compare_3way(InputIterator1 b1, InputIterator1 e1,
InputIterator2 b2, InputIterator2 e2);
4
Effects: Equivalent to:
return lexicographical_compare_3way(b1, e1, b2, e2,
[](const auto& t, const auto& u) {
return compare_3way(t, u);
});
28.7.12
Permutation generators
[alg.permutation.generators]
template<class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first,
BidirectionalIterator last);
template<class BidirectionalIterator, class Compare>
bool next_permutation(BidirectionalIterator first,
BidirectionalIterator last, Compare comp);
1
Requires: BidirectionalIterator shall satisfy the requirements of ValueSwappable (20.5.3.2).
2
Effects: Takes a sequence defined by the range [first, last) and transforms it into the next permu-
tation. The next permutation is found by assuming that the set of all permutations is lexicographically
sorted with respect to operator< or comp.
3
Returns: true if such a permutation exists. Otherwise, it transforms the sequence into the smallest
permutation, that is, the ascendingly sorted one, and returns false.
4
Complexity: At most (last - first) / 2 swaps.
template<class BidirectionalIterator>
bool prev_permutation(BidirectionalIterator first,
BidirectionalIterator last);
template<class BidirectionalIterator, class Compare>
bool prev_permutation(BidirectionalIterator first,
BidirectionalIterator last, Compare comp);
5
Requires: BidirectionalIterator shall satisfy the requirements of ValueSwappable (20.5.3.2).
6
Effects: Takes a sequence defined by the range [first, last) and transforms it into the previous
permutation. The previous permutation is found by assuming that the set of all permutations is
lexicographically sorted with respect to operator< or comp.
7
Returns: true if such a permutation exists. Otherwise, it transforms the sequence into the largest
permutation, that is, the descendingly sorted one, and returns false.
8
Complexity: At most (last - first) / 2 swaps.
28.8
C library algorithms
[alg.c.library]
1
[ Note: The header <cstdlib> (21.2.2) declares the functions described in this subclause.
— end note ]
void* bsearch(const void* key, const void* base, size_t nmemb, size_t size,
c-compare-pred * compar);
§ 28.8
938
void* bsearch(const void* key, const void* base, size_t nmemb, size_t size,
compare-pred * compar);
void qsort(void* base, size_t nmemb, size_t size, c-compare-pred * compar);
void qsort(void* base, size_t nmemb, size_t size, compare-pred * compar);
2
Effects: These functions have the semantics specified in the C standard library.
3
Remarks: The behavior is undefined unless the objects in the array pointed to by base are of trivial
type.
4
Throws: Any exception thrown by compar() (20.5.5.12).
See also: ISO C 7.22.5.
§ 28.8
939
29
Numerics library
[numerics]
29.1
General
[numerics.general]
1
This Clause describes components that C++ programs may use to perform seminumerical operations.
2
The following subclauses describe components for complex number types, random number generation, numeric
(n-at-a-time) arrays, generalized numeric algorithms, and mathematical functions for floating-point types, as
summarized in Table 101.
Table 101 — Numerics library summary
Subclause
Header(s)
29.2
Definitions
29.3
Requirements
29.4
Floating-point environment
<cfenv>
29.5
Complex numbers
<complex>
29.6
Random number generation
<random>
29.7
Numeric arrays
<valarray>
29.8
Generalized numeric operations
<numeric>
29.9
Mathematical functions for
<cmath>
floating-point types
<cstdlib>
29.2
Definitions
[numerics.defns]
1
Define GENERALIZED_NONCOMMUTATIVE_SUM(op, a1, ..., aN) as follows:
(1.1)
—
a1 when N is 1, otherwise
(1.2)
—
op(GENERALIZED_NONCOMMUTATIVE_SUM(op, a1, ..., aK),
GENERALIZED_NONCOMMUTATIVE_SUM(op, aM, ..., aN)) for any K where 1 < K + 1 = M ≤ N.
2
Define GENERALIZED_SUM(op, a1, ..., aN) as GENERALIZED_NONCOMMUTATIVE_SUM(op, b1, ..., bN),
where b1, ..., bN may be any permutation of a1, ..., aN.
29.3
Numeric type requirements
[numeric.requirements]
1
The complex and valarray components are parameterized by the type of information they contain and
manipulate. A C++ program shall instantiate these components only with a type T that satisfies the following
requirements:270
(1.1)
—
T is not an abstract class (it has no pure virtual member functions);
(1.2)
—
T is not a reference type;
(1.3)
—
T is not cv-qualified;
(1.4)
—
If T is a class, it has a public default constructor;
(1.5)
—
If T is a class, it has a public copy constructor with the signature T::T(const T&)
(1.6)
—
If T is a class, it has a public destructor;
(1.7)
—
If T is a class, it has a public assignment operator whose signature is either T& T::operator=(const
T&) or T& T::operator=(T)
(1.8)
—
If T is a class, its assignment operator, copy and default constructors, and destructor shall correspond
to each other in the following sense:
(1.8.1)
—
Initialization of raw storage using the copy constructor on the value of T(), however obtained, is
semantically equivalent to value-initialization of the same raw storage.
270) In other words, value types. These include arithmetic types, pointers, the library class complex, and instantiations of
valarray for value types.
§ 29.3
940
(1.8.2)
—
Initialization of raw storage using the default constructor, followed by assignment, is semantically
equivalent to initialization of raw storage using the copy constructor.
(1.8.3)
—
Destruction of an object, followed by initialization of its raw storage using the copy constructor, is
semantically equivalent to assignment to the original object.
[Note: This rule states, in part, that there shall not be any subtle differences in the semantics of
initialization versus assignment. This gives an implementation considerable flexibility in how arrays are
initialized.
[Example: An implementation is allowed to initialize a valarray by allocating storage using the new
operator (which implies a call to the default constructor for each element) and then assigning each
element its value. Or the implementation can allocate raw storage and use the copy constructor to
initialize each element.
— end example ]
If the distinction between initialization and assignment is important for a class, or if it fails to satisfy any
of the other conditions listed above, the programmer should use vector (26.3.11) instead of valarray
for that class.
— end note ]
(1.9)
—
If T is a class, it does not overload unary operator&.
2
If any operation on T throws an exception the effects are undefined.
3
In addition, many member and related functions of valarray<T> can be successfully instantiated and will
exhibit well-defined behavior if and only if T satisfies additional requirements specified for each such member
or related function.
4
[ Example: It is valid to instantiate valarray<complex>, but operator>() will not be successfully instantiated
for valarray<complex> operands, since complex does not have any ordering operators.
— end example ]
29.4
The floating-point environment
[cfenv]
29.4.1
Header <cfenv> synopsis
[cfenv.syn]
#define FE_ALL_EXCEPT see below
#define FE_DIVBYZERO see below
#define FE_INEXACT see below
#define FE_INVALID see below
#define FE_OVERFLOW see below
#define FE_UNDERFLOW see below
#define FE_DOWNWARD see below
#define FE_TONEAREST see below
#define FE_TOWARDZERO see below
#define FE_UPWARD see below
#define FE_DFL_ENV see below
namespace std {
// types
using fenv_t
= object type ;
using fexcept_t = integer type ;
// functions
int feclearexcept(int except);
int fegetexceptflag(fexcept_t* pflag, int except);
int feraiseexcept(int except);
int fesetexceptflag(const fexcept_t* pflag, int except);
int fetestexcept(int except);
int fegetround();
int fesetround(int mode);
int fegetenv(fenv_t* penv);
int feholdexcept(fenv_t* penv);
int fesetenv(const fenv_t* penv);
int feupdateenv(const fenv_t* penv);
}
§
29.4.1
941
1
The contents and meaning of the header <cfenv> are the same as the C standard library header <fenv.h>.
[Note: This document does not require an implementation to support the FENV_ACCESS pragma; it is
implementation-defined (19.6) whether the pragma is supported. As a consequence, it is implementation-
defined whether these functions can be used to test floating-point status flags, set floating-point control
modes, or run under non-default mode settings. If the pragma is used to enable control over the floating-point
environment, this document does not specify the effect on floating-point evaluation in constant expressions.
— end note ]
2
The floating-point environment has thread storage duration (6.6.4.2). The initial state for a thread’s
floating-point environment is the state of the floating-point environment of the thread that constructs the
corresponding thread object (33.3.2) at the time it constructed the object. [ Note: That is, the child thread
gets the floating-point state of the parent thread at the time of the child’s creation.
— end note ]
3
A separate floating-point environment shall be maintained for each thread. Each function accesses the
environment corresponding to its calling thread.
See also: ISO C 7.6
29.5
Complex numbers
[complex.numbers]
1
The header <complex> defines a class template, and numerous functions for representing and manipulating
complex numbers.
2
The effect of instantiating the template complex for any type other than float, double, or long double is
unspecified. The specializations complex<float>, complex<double>, and complex<long double> are literal
types (6.7).
3
If the result of a function is not mathematically defined or not in the range of representable values for its
type, the behavior is undefined.
4
If z is an lvalue expression of type cv complex<T> then:
(4.1)
—
the expression reinterpret_cast<cv T(&)[2]>(z) shall be well-formed,
(4.2)
—
reinterpret_cast<cv T(&)[2]>(z)[0] shall designate the real part of z, and
(4.3)
—
reinterpret_cast<cv T(&)[2]>(z)[1] shall designate the imaginary part of z.
Moreover, if a is an expression of type cv complex<T>* and the expression a[i] is well-defined for an integer
expression i, then:
(4.4)
—
reinterpret_cast<cv T*>(a)[2*i] shall designate the real part of a[i], and
(4.5)
—
reinterpret_cast<cv T*>(a)[2*i + 1] shall designate the imaginary part of a[i].
29.5.1
Header <complex> synopsis
[complex.syn]
namespace std {
// 29.5.2, class template complex
template<class T> class complex;
// 29.5.3, complex specializations
template<> class complex<float>;
template<> class complex<double>;
template<> class complex<long double>;
// 29.5.6, operators
template<class T> constexpr complex<T> operator+(const complex<T>&, const complex<T>&);
template<class T> constexpr complex<T> operator+(const complex<T>&, const T&);
template<class T> constexpr complex<T> operator+(const T&, const complex<T>&);
template<class T> constexpr complex<T> operator-(const complex<T>&, const complex<T>&);
template<class T> constexpr complex<T> operator-(const complex<T>&, const T&);
template<class T> constexpr complex<T> operator-(const T&, const complex<T>&);
template<class T> constexpr complex<T> operator*(const complex<T>&, const complex<T>&);
template<class T> constexpr complex<T> operator*(const complex<T>&, const T&);
template<class T> constexpr complex<T> operator*(const T&, const complex<T>&);
§ 29.5.1
942
template<class T> constexpr complex<T> operator/(const complex<T>&, const complex<T>&);
template<class T> constexpr complex<T> operator/(const complex<T>&, const T&);
template<class T> constexpr complex<T> operator/(const T&, const complex<T>&);
template<class T> constexpr complex<T> operator+(const complex<T>&);
template<class T> constexpr complex<T> operator-(const complex<T>&);
template<class T> constexpr bool operator==(const complex<T>&, const complex<T>&);
template<class T> constexpr bool operator==(const complex<T>&, const T&);
template<class T> constexpr bool operator==(const T&, const complex<T>&);
template<class T> constexpr bool operator!=(const complex<T>&, const complex<T>&);
template<class T> constexpr bool operator!=(const complex<T>&, const T&);
template<class T> constexpr bool operator!=(const T&, const complex<T>&);
template<class T, class charT, class traits>
basic_istream<charT, traits>& operator>>(basic_istream<charT,
traits>&,
complex<T>&);
template<class T, class charT, class traits>
basic_ostream<charT, traits>& operator<<(basic_ostream<charT,
traits>&,
const
complex<T>&);
// 29.5.7, values
template<class T> constexpr T real(const complex<T>&);
template<class T> constexpr T imag(const complex<T>&);
template<class T> T abs(const complex<T>&);
template<class T> T arg(const complex<T>&);
template<class T> constexpr T norm(const complex<T>&);
template<class T> constexpr complex<T> conj(const complex<T>&);
template<class T> complex<T> proj(const complex<T>&);
template<class T> complex<T> polar(const T&, const T& = T());
// 29.5.8, transcendentals
template<class T> complex<T> acos(const complex<T>&);
template<class T> complex<T> asin(const complex<T>&);
template<class T> complex<T> atan(const complex<T>&);
template<class T> complex<T> acosh(const complex<T>&);
template<class T> complex<T> asinh(const complex<T>&);
template<class T> complex<T> atanh(const complex<T>&);
template<class T> complex<T> cos
(const complex<T>&);
template<class T> complex<T> cosh (const complex<T>&);
template<class T> complex<T> exp
(const complex<T>&);
template<class T> complex<T> log
(const complex<T>&);
template<class T> complex<T> log10(const complex<T>&);
template<class T> complex<T> pow
(const complex<T>&, const T&);
template<class T> complex<T> pow
(const complex<T>&, const complex<T>&);
template<class T> complex<T> pow
(const T&, const complex<T>&);
template<class T> complex<T> sin
(const complex<T>&);
template<class T> complex<T> sinh (const complex<T>&);
template<class T> complex<T> sqrt (const complex<T>&);
template<class T> complex<T> tan
(const complex<T>&);
template<class T> complex<T> tanh (const complex<T>&);
// 29.5.10, complex literals
inline namespace literals {
inline namespace complex_literals {
constexpr complex<long double> operator""il(long double);
constexpr complex<long double> operator""il(unsigned long long);
constexpr complex<double> operator""i(long double);
§
29.5.1
943
constexpr complex<double> operator""i(unsigned long long);
constexpr complex<float> operator""if(long double);
constexpr complex<float> operator""if(unsigned long long);
}
}
}
29.5.2
Class template complex
[complex]
namespace std {
template<class T> class complex {
public:
using value_type = T;
constexpr complex(const T& re = T(), const T& im = T());
constexpr complex(const complex&);
template<class X> constexpr complex(const complex<X>&);
constexpr T real() const;
constexpr void real(T);
constexpr T imag() const;
constexpr void imag(T);
constexpr complex& operator= (const T&);
constexpr complex& operator+=(const T&);
constexpr complex& operator-=(const T&);
constexpr complex& operator*=(const T&);
constexpr complex& operator/=(const T&);
constexpr complex& operator=(const complex&);
template<class X> constexpr complex& operator= (const complex<X>&);
template<class X> constexpr complex& operator+=(const complex<X>&);
template<class X> constexpr complex& operator-=(const complex<X>&);
template<class X> constexpr complex& operator*=(const complex<X>&);
template<class X> constexpr complex& operator/=(const complex<X>&);
};
}
1
The class complex describes an object that can store the Cartesian components, real() and imag(), of a
complex number.
29.5.3
complex specializations
[complex.special]
namespace std {
template<> class complex<float> {
public:
using value_type = float;
constexpr complex(float re = 0.0f, float im = 0.0f);
constexpr explicit complex(const complex<double>&);
constexpr explicit complex(const complex<long double>&);
constexpr float real() const;
constexpr void real(float);
constexpr float imag() const;
constexpr void imag(float);
constexpr complex& operator= (float);
constexpr complex& operator+=(float);
constexpr complex& operator-=(float);
constexpr complex& operator*=(float);
constexpr complex& operator/=(float);
constexpr complex& operator=(const complex&);
template<class X> constexpr complex& operator= (const complex<X>&);
template<class X> constexpr complex& operator+=(const complex<X>&);
§ 29.5.3
944
template<class X> constexpr complex& operator-=(const complex<X>&);
template<class X> constexpr complex& operator*=(const complex<X>&);
template<class X> constexpr complex& operator/=(const complex<X>&);
};
template<> class complex<double> {
public:
using value_type = double;
constexpr complex(double re = 0.0, double im = 0.0);
constexpr complex(const complex<float>&);
constexpr explicit complex(const complex<long double>&);
constexpr double real() const;
constexpr void real(double);
constexpr double imag() const;
constexpr void imag(double);
constexpr complex& operator= (double);
constexpr complex& operator+=(double);
constexpr complex& operator-=(double);
constexpr complex& operator*=(double);
constexpr complex& operator/=(double);
constexpr complex& operator=(const complex&);
template<class X> constexpr complex& operator= (const complex<X>&);
template<class X> constexpr complex& operator+=(const complex<X>&);
template<class X> constexpr complex& operator-=(const complex<X>&);
template<class X> constexpr complex& operator*=(const complex<X>&);
template<class X> constexpr complex& operator/=(const complex<X>&);
};
template<> class complex<long double> {
public:
using value_type = long double;
constexpr complex(long double re = 0.0L, long double im = 0.0L);
constexpr complex(const complex<float>&);
constexpr complex(const complex<double>&);
constexpr long double real() const;
constexpr void real(long double);
constexpr long double imag() const;
constexpr void imag(long double);
constexpr complex& operator= (long double);
constexpr complex& operator+=(long double);
constexpr complex& operator-=(long double);
constexpr complex& operator*=(long double);
constexpr complex& operator/=(long double);
constexpr complex& operator=(const complex&);
template<class X> constexpr complex& operator= (const complex<X>&);
template<class X> constexpr complex& operator+=(const complex<X>&);
template<class X> constexpr complex& operator-=(const complex<X>&);
template<class X> constexpr complex& operator*=(const complex<X>&);
template<class X> constexpr complex& operator/=(const complex<X>&);
};
}
29.5.4
complex member functions
[complex.members]
template<class T> constexpr complex(const T& re = T(), const T& im = T());
1
Effects: Constructs an object of class complex.
§ 29.5.4
945
2
Postconditions: real() == re && imag() == im.
constexpr T real() const;
3
Returns: The value of the real component.
constexpr void real(T val);
4
Effects: Assigns val to the real component.
constexpr T imag() const;
5
Returns: The value of the imaginary component.
constexpr void imag(T val);
6
Effects: Assigns val to the imaginary component.
29.5.5
complex member operators
[complex.member.ops]
constexpr complex& operator+=(const T& rhs);
1
Effects: Adds the scalar value rhs to the real part of the complex value *this and stores the result in
the real part of *this, leaving the imaginary part unchanged.
2
Returns: *this.
constexpr complex& operator-=(const T& rhs);
3
Effects: Subtracts the scalar value rhs from the real part of the complex value *this and stores the
result in the real part of *this, leaving the imaginary part unchanged.
4
Returns: *this.
constexpr complex& operator*=(const T& rhs);
5
Effects: Multiplies the scalar value rhs by the complex value *this and stores the result in *this.
6
Returns: *this.
constexpr complex& operator/=(const T& rhs);
7
Effects: Divides the scalar value rhs into the complex value *this and stores the result in *this.
8
Returns: *this.
template<class X> constexpr complex& operator+=(const complex<X>& rhs);
9
Effects: Adds the complex value rhs to the complex value *this and stores the sum in *this.
10
Returns: *this.
template<class X> constexpr complex& operator-=(const complex<X>& rhs);
11
Effects: Subtracts the complex value rhs from the complex value *this and stores the difference in
*this.
12
Returns: *this.
template<class X> constexpr complex& operator*=(const complex<X>& rhs);
13
Effects: Multiplies the complex value rhs by the complex value *this and stores the product in *this.
14
Returns: *this.
template<class X> constexpr complex& operator/=(const complex<X>& rhs);
15
Effects: Divides the complex value rhs into the complex value *this and stores the quotient in *this.
16
Returns: *this.
29.5.6
complex non-member operations
[complex.ops]
template<class T> constexpr complex<T> operator+(const complex<T>& lhs);
1
Returns: complex<T>(lhs).
2
Remarks: unary operator.
§ 29.5.6
946
template<class T> constexpr complex<T> operator+(const complex<T>& lhs, const complex<T>& rhs);
template<class T> constexpr complex<T> operator+(const complex<T>& lhs, const T& rhs);
template<class T> constexpr complex<T> operator+(const T& lhs, const complex<T>& rhs);
3
Returns: complex<T>(lhs) += rhs.
template<class T> constexpr complex<T> operator-(const complex<T>& lhs);
4
Returns: complex<T>(-lhs.real(),-lhs.imag()).
5
Remarks: unary operator.
template<class T> constexpr complex<T> operator-(const complex<T>& lhs, const complex<T>& rhs);
template<class T> constexpr complex<T> operator-(const complex<T>& lhs, const T& rhs);
template<class T> constexpr complex<T> operator-(const T& lhs, const complex<T>& rhs);
6
Returns: complex<T>(lhs) -= rhs.
template<class T> constexpr complex<T> operator*(const complex<T>& lhs, const complex<T>& rhs);
template<class T> constexpr complex<T> operator*(const complex<T>& lhs, const T& rhs);
template<class T> constexpr complex<T> operator*(const T& lhs, const complex<T>& rhs);
7
Returns: complex<T>(lhs) *= rhs.
template<class T> constexpr complex<T> operator/(const complex<T>& lhs, const complex<T>& rhs);
template<class T> constexpr complex<T> operator/(const complex<T>& lhs, const T& rhs);
template<class T> constexpr complex<T> operator/(const T& lhs, const complex<T>& rhs);
8
Returns: complex<T>(lhs) /= rhs.
template<class T> constexpr bool operator==(const complex<T>& lhs, const complex<T>& rhs);
template<class T> constexpr bool operator==(const complex<T>& lhs, const T& rhs);
template<class T> constexpr bool operator==(const T& lhs, const complex<T>& rhs);
9
Returns: lhs.real() == rhs.real() && lhs.imag() == rhs.imag().
10
Remarks: The imaginary part is assumed to be T(), or 0.0, for the T arguments.
template<class T> constexpr bool operator!=(const complex<T>& lhs, const complex<T>& rhs);
template<class T> constexpr bool operator!=(const complex<T>& lhs, const T& rhs);
template<class T> constexpr bool operator!=(const T& lhs, const complex<T>& rhs);
11
Returns: rhs.real() != lhs.real() || rhs.imag() != lhs.imag().
template<class T, class charT, class traits>
basic_istream<charT, traits>& operator>>(basic_istream<charT, traits>& is, complex<T>& x);
12
Requires: The input values shall be convertible to T.
13
Effects: Extracts a complex number x of the form: u, (u), or (u,v), where u is the real part and v is
the imaginary part (30.7.4.2).
14
If bad input is encountered, calls is.setstate(ios_base::failbit) (which may throw ios::failure
(30.5.5.4)).
15
Returns: is.
16
Remarks: This extraction is performed as a series of simpler extractions. Therefore, the skipping of
whitespace is specified to be the same for each of the simpler extractions.
template<class T, class charT, class traits>
basic_ostream<charT, traits>& operator<<(basic_ostream<charT, traits>& o, const complex<T>& x);
17
Effects: Inserts the complex number x onto the stream o as if it were implemented as follows:
basic_ostringstream<charT, traits> s;
s.flags(o.flags());
s.imbue(o.getloc());
s.precision(o.precision());
s << ’(’ << x.real() << "," << x.imag() << ’)’;
return o << s.str();
18
[Note: In a locale in which comma is used as a decimal point character, the use of comma as a field
separator can be ambiguous. Inserting showpoint into the output stream forces all outputs to show an
§ 29.5.6
947
explicit decimal point character; as a result, all inserted sequences of complex numbers can be extracted
unambiguously.
— end note ]
29.5.7
complex value operations
[complex.value.ops]
template<class T> constexpr T real(const complex<T>& x);
1
Returns: x.real().
template<class T> constexpr T imag(const complex<T>& x);
2
Returns: x.imag().
template<class T> T abs(const complex<T>& x);
3
Returns: The magnitude of x.
template<class T> T arg(const complex<T>& x);
4
Returns: The phase angle of x, or atan2(imag(x), real(x)).
template<class T> constexpr T norm(const complex<T>& x);
5
Returns: The squared magnitude of x.
template<class T> constexpr complex<T> conj(const complex<T>& x);
6
Returns: The complex conjugate of x.
template<class T> complex<T> proj(const complex<T>& x);
7
Returns: The projection of x onto the Riemann sphere.
8
Remarks: Behaves the same as the C function cproj. See also: ISO C
7.3.9.5
template<class T> complex<T> polar(const T& rho, const T& theta = T());
9
Requires: rho shall be non-negative and non-NaN. theta shall be finite.
10
Returns: The complex value corresponding to a complex number whose magnitude is rho and whose
phase angle is theta.
29.5.8
complex transcendentals
[complex.transcendentals]
template<class T> complex<T> acos(const complex<T>& x);
1
Returns: The complex arc cosine of x.
2
Remarks: Behaves the same as the C function cacos. See also: ISO C 7.3.5.1
template<class T> complex<T> asin(const complex<T>& x);
3
Returns: The complex arc sine of x.
4
Remarks: Behaves the same as the C function casin. See also: ISO C 7.3.5.2
template<class T> complex<T> atan(const complex<T>& x);
5
Returns: The complex arc tangent of x.
6
Remarks: Behaves the same as the C function catan. See also: ISO C 7.3.5.3
template<class T> complex<T> acosh(const complex<T>& x);
7
Returns: The complex arc hyperbolic cosine of x.
8
Remarks: Behaves the same as the C function cacosh. See also: ISO C 7.3.6.1
template<class T> complex<T> asinh(const complex<T>& x);
9
Returns: The complex arc hyperbolic sine of x.
10
Remarks: Behaves the same as the C function casinh. See also: ISO C 7.3.6.2
template<class T> complex<T> atanh(const complex<T>& x);
11
Returns: The complex arc hyperbolic tangent of x.
§ 29.5.8
948
12
Remarks: Behaves the same as the C function catanh. See also: ISO C 7.3.6.3
template<class T> complex<T> cos(const complex<T>& x);
13
Returns: The complex cosine of x.
template<class T> complex<T> cosh(const complex<T>& x);
14
Returns: The complex hyperbolic cosine of x.
template<class T> complex<T> exp(const complex<T>& x);
15
Returns: The complex base-e exponential of x.
template<class T> complex<T> log(const complex<T>& x);
16
Returns: The complex natural (base-e) logarithm of x. For all x, imag(log(x)) lies in the interval
[−π, π]. [ Note: The semantics of this function are intended to be the same in C++ as they are for
clog in C. — end note ]
17
Remarks: The branch cuts are along the negative real axis.
template<class T> complex<T> log10(const complex<T>& x);
18
Returns: The complex common (base-10) logarithm of x, defined as log(x) / log(10).
19
Remarks: The branch cuts are along the negative real axis.
template<class T> complex<T> pow(const complex<T>& x, const complex<T>& y);
template<class T> complex<T> pow(const complex<T>& x, const T& y);
template<class T> complex<T> pow(const T& x, const complex<T>& y);
20
Returns: The complex power of base x raised to the yth power, defined as exp(y * log(x)). The
value returned for pow(0, 0) is implementation-defined.
21
Remarks: The branch cuts are along the negative real axis.
template<class T> complex<T> sin(const complex<T>& x);
22
Returns: The complex sine of x.
template<class T> complex<T> sinh(const complex<T>& x);
23
Returns: The complex hyperbolic sine of x.
template<class T> complex<T> sqrt(const complex<T>& x);
24
Returns: The complex square root of x, in the range of the right half-plane. [ Note: The semantics of
this function are intended to be the same in C++ as they are for csqrt in C. — end note ]
25
Remarks: The branch cuts are along the negative real axis.
template<class T> complex<T> tan(const complex<T>& x);
26
Returns: The complex tangent of x.
template<class T> complex<T> tanh(const complex<T>& x);
27
Returns: The complex hyperbolic tangent of x.
29.5.9
Additional overloads
[cmplx.over]
1
The following function templates shall have additional overloads:
arg
norm
conj
proj
imag
real
where norm, conj, imag, and real are constexpr overloads.
2
The additional overloads shall be sufficient to ensure:
(2.1)
—
If the argument has type long double, then it is effectively cast to complex<long double>.
(2.2)
—
Otherwise, if the argument has type double or an integer type, then it is effectively cast to complex<
double>.
§ 29.5.9
949
(2.3)
—
Otherwise, if the argument has type float, then it is effectively cast to complex<float>.
3
Function template pow shall have additional overloads sufficient to ensure, for a call with at least one argument
of type complex<T>:
(3.1)
—
If either argument has type complex<long double> or type long double, then both arguments are
effectively cast to complex<long double>.
(3.2)
—
Otherwise, if either argument has type complex<double>, double, or an integer type, then both
arguments are effectively cast to complex<double>.
(3.3)
—
Otherwise, if either argument has type complex<float> or float, then both arguments are effectively
cast to complex<float>.
29.5.10
Suffixes for complex number literals
[complex.literals]
1
This subclause describes literal suffixes for constructing complex number literals. The suffixes i, il, and
if create complex numbers of the types complex<double>, complex<long double>, and complex<float>
respectively, with their imaginary part denoted by the given literal number and the real part being zero.
constexpr complex<long double> operator""il(long double d);
constexpr complex<long double> operator""il(unsigned long long d);
2
Returns: complex<long double>{0.0L, static_cast<long double>(d)}.
constexpr complex<double> operator""i(long double d);
constexpr complex<double> operator""i(unsigned long long d);
3
Returns: complex<double>{0.0, static_cast<double>(d)}.
constexpr complex<float> operator""if(long double d);
constexpr complex<float> operator""if(unsigned long long d);
4
Returns: complex<float>{0.0f, static_cast<float>(d)}.
29.6
Random number generation
[rand]
1
This subclause defines a facility for generating (pseudo-)random numbers.
2
In addition to a few utilities, four categories of entities are described: uniform random bit generators, random
number engines, random number engine adaptors, and random number distributions. These categorizations
are applicable to types that satisfy the corresponding requirements, to objects instantiated from such types,
and to templates producing such types when instantiated. [ Note: These entities are specified in such a way
as to permit the binding of any uniform random bit generator object e as the argument to any random
number distribution object d, thus producing a zero-argument function object such as given by bind(d,e).
— end note ]
3
Each of the entities specified via this subclause has an associated arithmetic type (6.7.1) identified as
result_type. With T as the result_type thus associated with such an entity, that entity is characterized:
a) as boolean or equivalently as boolean-valued, if T is bool;
b) otherwise as integral or equivalently as integer-valued, if numeric_limits<T>::is_integer is true;
c) otherwise as floating or equivalently as real-valued.
If integer-valued, an entity may optionally be further characterized as signed or unsigned, according to
numeric_limits<T>::is_signed.
4
Unless otherwise specified, all descriptions of calculations in this subclause use mathematical real numbers.
5
Throughout this subclause, the operators bitand , bitor , and xor denote the respective conventional bitwise
operations. Further:
a) the operator rshift denotes a bitwise right shift with zero-valued bits appearing in the high bits of the
result, and
b) the operator lshiftw denotes a bitwise left shift with zero-valued bits appearing in the low bits of the
result, and whose result is always taken modulo 2w .
§ 29.6
950
29.6.1
Requirements
[rand.req]
29.6.1.1
General requirements
[rand.req.genl]
1
Throughout this subclause 29.6, the effect of instantiating a template:
a) that has a template type parameter named Sseq is undefined unless the corresponding template
argument is cv-unqualified and satisfies the requirements of seed sequence (29.6.1.2).
b) that has a template type parameter named URBG is undefined unless the corresponding template
argument is cv-unqualified and satisfies the requirements of uniform random bit generator (29.6.1.3).
c) that has a template type parameter named Engine is undefined unless the corresponding template
argument is cv-unqualified and satisfies the requirements of random number engine (29.6.1.4).
d) that has a template type parameter named RealType is undefined unless the corresponding template
argument is cv-unqualified and is one of float, double, or long double.
e) that has a template type parameter named IntType is undefined unless the corresponding template
argument is cv-unqualified and is one of short, int, long, long long, unsigned short, unsigned
int, unsigned long, or unsigned long long.
f) that has a template type parameter named UIntType is undefined unless the corresponding template
argument is cv-unqualified and is one of unsigned short, unsigned int, unsigned long, or unsigned
long long.
2
Throughout this subclause 29.6, phrases of the form “x is an iterator of a specific kind” shall be interpreted
as equivalent to the more formal requirement that “x is a value of a type satisfying the requirements of the
specified iterator type”.
3
Throughout this subclause 29.6, any constructor that can be called with a single argument and that satisfies
a requirement specified in this subclause shall be declared explicit.
29.6.1.2
Seed sequence requirements
[rand.req.seedseq]
1
A seed sequence is an object that consumes a sequence of integer-valued data and produces a requested
number of unsigned integer values i, 0 ≤ i < 232, based on the consumed data.
[Note: Such an object
provides a mechanism to avoid replication of streams of random variates. This can be useful, for example, in
applications requiring large numbers of random number engines.
— end note ]
2
A class S satisfies the requirements of a seed sequence if the expressions shown in Table 102 are valid and
have the indicated semantics, and if S also satisfies all other requirements of this subclause 29.6.1.2. In that
Table and throughout this subclause:
a) T is the type named by S’s associated result_type;
b) q is a value of S and r is a possibly const value of S;
c) ib and ie are input iterators with an unsigned integer value_type of at least 32 bits;
d) rb and re are mutable random access iterators with an unsigned integer value_type of at least 32 bits;
e) ob is an output iterator; and
f) il is a value of initializer_list<T>.
Table 102 — Seed sequence requirements
Expression
Return type
Pre/post-condition
Complexity
S::result_type
T
T is an unsigned integer
compile-time
type (6.7.1) of at least 32 bits.
S()
Creates a seed sequence with
constant
the same initial state as all
other default-constructed seed
sequences of type S.
S(ib,ie)
Creates a seed sequence having
O(ie − ib)
internal state that depends on
some or all of the bits of the
supplied sequence [ib, ie).
§ 29.6.1.2
951
|
|