Category: algorithms
Component type: function
template <class InputIterator, class UnaryFunction>
UnaryFunction for_each(InputIterator first, InputIterator last, UnaryFunction f);
For_each applies the function object f to each element in the range [first, last); f's return value, if any, is ignored. Applications are performed in forward order, i.e. from first to last. For_each returns the function object after it has been applied to each element. [1]
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
• InputIterator is a model of Input Iterator
• UnaryFunction is a model of Unary Function
• UnaryFunction does not apply any non-constant operation through its argument.
• InputIterator's value type is convertible to UnaryFunction 's argument type.
• [first, last) is a valid range.
Linear. Exactly last – first applications of UnaryFunction.
template<class T> struct print : public unary_function<T, void> {
print(ostream& out) : os(out), count(0) {}
void operator() (T x) { os << x << ' '; ++count; }
ostream& os;
int count;
};
int main() {
int A[] = {1, 4, 2, 8, 5, 7};
const int N = sizeof(A) / sizeof(int);
print<int> P = for_each(A, A + N, print<int>(cout));
cout << endl << P.count << " objects printed." << endl;
}
[1] This return value is sometimes useful, since a function object may have local state. It might, for example, count the number of times that it is called, or it might have a status flag to indicate whether or not a call succeeded.
The function object overview, count, copy
Category: algorithms
Component type: function
template<class InputIterator, class EqualityComparable>
InputIterator find(InputIterator first, InputIterator last, const EqualityComparable& value);
Returns the first iterator i in the range [first, last) such that *i == value. Returns last if no such iterator exists.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
• EqualityComparable is a model of EqualityComparable.
• InputIterator is a model of InputIterator.
• Equality is defined between objects of type EqualityComparable and objects of InputIterator's value type.
• [first, last) is a valid range.
Linear: at most last – first comparisons for equality.
list <int>L;
L.push_back(3);
L.push_back(1);
L.push_back(7);
list<int>::iterator result = find(L.begin(), L.end(), 7);
assert(result == L.end() || *result == 7);
find_if.
Category: algorithms
Component type: function
template<class InputIterator, class Predicate>
InputIterator find_if(InputIterator first, InputIterator last, Predicate pred);
Returns the first iterator i in the range [first, last) such that pred(*i) is true. Returns last if no such iterator exists.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
• Predicate is a model of Predicate.
• InputIterator is a model of InputIterator.
• The value type of InputIterator is convertible to the argument type of Predicate.
• [first, last) is a valid range.
• For each iterator i in the range [first, last), *i is in the domain of Predicate.
Linear: at most last – first applications of Pred.
list<int> L;
L.push_back(-3);
L.push_back(0);
L.push_back(3); L.push_back(-2);
list<int>::iterator result = find_if(L.begin(), L.end(), bind2nd(greater<int>(), 0));
assert(result == L.end() || *result > 0);
find.
Category: algorithms
Component type: function
Adjacent_find is an overloaded name; there are actually two adjacent_find functions.
template <class ForwardIterator>
ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last);
template <class ForwardIterator, class BinaryPredicate>
ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred);
The first version of adjacent_find returns the first iterator i such that i and i+1 are both valid iterators in [first, last), and such that *i == *(i+1). It returns last if no such iterator exists.
The second version of adjacent_find returns the first iterator i such that i and i+1 are both valid iterators in [first, last), and such that binary_pred(*i, *(i+1)) is true. It returns last if no such iterator exists.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
For the first version:
• ForwardIterator is a model of Forward Iterator.
• ForwardIterator 's value type is Equality Comparable.
For the second version:
• ForwardIterator is a model of Forward Iterator.
• ForwardIterator's value type is convertible to BinaryPredicate's first argument type and to its second argument type.
• [first, last) is a valid range.
Linear. If first == last then no comparison are performed; otherwise, at most (last – first) – 1 comparisons.
Find the first element that is greater than its successor.
int A[] = {1, 2, 3, 4, 6, 5, 7, 8};
const int N = sizeof(A) / sizeof(int);
const int* p = adjacent_find(A, A + N, greater <int>());
cout << "Element " << p – A << " is out of order: " << *p << " > " << *(p + 1) << "." << endl;
find, mismatch, equal, search
Category: algorithms
Component type: function
find_first_of is an overloaded name; there are actually two find_first_of functions.
template <class InputIterator, class ForwardIterator>
InputIterator find_first_of(InputIterator first1, InputIterator last1, ForwardIterator first2, ForwardIterator last2);
template <class InputIterator, class ForwardIterator, class BinaryPredicate>
InputIterator find_first_of(InputIterator first1, InputIterator last1, ForwardIterator first2, ForwardIterator last2, BinaryPredicate comp);
Find_first_of is similar to find, in that it performs linear seach through a range of Input Iterators. The difference is that while find searches for one particular value, find_first_of searches for any of several values. Specifically, find_first_of searches for the first occurrance in the range [first1, last1) of any of the elements in [first2, last2). (Note that this behavior is reminiscent of the function strpbrk from the standard C library.)
The two versions of find_first_of differ in how they compare elements for equality. The first uses operator==, and the second uses and arbitrary user-supplied function object comp. The first version returns the first iterator i in [first1, last1) such that, for some iterator j in [first2, last2), *i == *j. The second returns the first iterator i in [first1, last1) such that, for some iterator j in [first2, last2), comp(*i, *j) is true. As usual, both versions return last1 if no such iterator i exists.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
For the first version:
• InputIterator is a model of Input Iterator.
• ForwardIterator is a model of Forward Iterator.
• InputIterator 's value type is EqualityComparable , and can be compared for equality with ForwardIterator's value type.
For the second version:
• InputIterator is a model of Input Iterator.
• ForwardIterator is a model of Forward Iterator.
• BinaryPredicate is a model of Binary Predicate.
• InputIterator's value type is convertible to BinaryPredicate's first argument type.
• ForwardIterator's value type is convertible to BinaryPredicate's second argument type.
• [first1, last1) is a valid range.
• [first2, last2) is a valid range.
At most (last1 – first1) * (last2 – first2) comparisons.
Like strpbrk, one use for find_first_of is finding whitespace in a string; space, tab, and newline are all whitespace characters.
int main() {
const char* WS = "\t\n ";
const int n_WS = strlen(WS);
char* s1 = "This sentence contains five words.";
char* s2 = "OneWord";
char* end1 = find_first_of(s1, s1 + strlen(s1), WS, WS + n_WS);
char* end2 = find_first_of(s2, s2 + strlen(s2), WS, WS + n_WS);
printf("First word of s1: %.*s\n", end1 – s1, s1);
printf("First word of s2: %.*s\n", end2 – s2, s2);
}
find, find_if, search
Category: algorithms
Component type: function
Count is an overloaded name: there are two count functions.
template <class InputIterator, class EqualityComparable>
iterator_traits<InputIterator>::difference_type count(InputIterator first, InputIterator last, const EqualityComparable& value);
template <class InputIterator, class EqualityComparable, class Size>
void count(InputIterator first, InputIterator last, const EqualityComparable& value, Size& n);
Count finds the number of elements in [first, last) that are equal to value. More precisely, the first version of count returns the number of iterators i in [first, last) such that *i == value. The second version of count adds to n the number of iterators i in [first, last) such that *i == value.
The second version of count was the one defined in the original STL, and the first version is the one defined in the draft C++ standard; the definition was changed because the older interface was clumsy and error-prone. The older interface required the use of a temporary variable, which had to be initialized to 0 before the call to count.
Both interfaces are currently supported [1], for reasons of backward compatibility, but eventually the older version will be removed.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
For the first version, which takes three arguments:
• InputIterator is a model of Input Iterator.
• EqualityComparable is a model of Equality Comparable.
• InputIterator's value type is a model of Equality Comparable.
• An object of InputIterator's value type can be compared for equality with an object of type EqualityComparable.
For the second version, which takes four arguments:
• InputIterator is a model of Input Iterator.
• EqualityComparable is a model of Equality Comparable.
• Size is an integral type that can hold values of InputIterator's distance type.
• InputIterator's value type is a model of Equality Comparable.
• An object of InputIterator's value type can be compared for equality with an object of type EqualityComparable.
• [first, last) is a valid range.
For the second version:
• [first, last) is a valid range.
• n plus the number of elements equal to value does not exceed the maximum value of type Size.
Linear. Exactly last – first comparisons.
int main() {
int A[] = { 2, 0, 4, 6, 0, 3, 1, –7 };
const int N = sizeof(A) / sizeof(int);
cout << "Number of zeros: " << count(A, A + N, 0) << endl;
}
[1] The new count interface uses the iterator_traits class, which relies on a C++ feature known as partial specialization. Many of today's compilers don't implement the complete standard; in particular, many compilers do not support partial specialization. If your compiler does not support partial specialization, then you will not be able to use the newer version of count, or any other STL components that involve iterator_traits.
count_if, find, find_if
Category: algorithms
Component type: function
Count_if is an overloaded name: there are two count_if functions.
template <class InputIterator, class Predicate> iterator_traits<InputIterator>::difference_type count_if(InputIterator first, InputIterator last, Predicate pred);
template <class InputIterator, class Predicate, class Size>
void count_if(InputIterator first, InputIterator last, Predicate pred, Size& n);
Count_if finds the number of elements in [first, last) that satisfy the predicate pred. More precisely, the first version of count_if returns the number of iterators i in [first, last) such that pred(*i) is true . The second version of count adds to n the number of iterators i in [first, last) such that pred(*i) is true.
The second version of count_if was the one defined in the original STL, and the first version is the one defined in the draft C++ standard; the definition was changed because the older interface was clumsy and error-prone. The older interface required the use of a temporary variable, which had to be initialized to 0 before the call to count_if.
Both interfaces are currently supported [1], for reasons of backward compatibility, but eventually the older version will be removed.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
For the first version, which takes three arguments:
• InputIterator is a model of Input Iterator.
• Predicate is a model of Predicate.
• InputIterator's value type is convertible to Predicate's argument type.
For the second version, which takes four arguments:
• InputIterator is a model of Input Iterator.
• Predicate is a model of Predicate.
• Size is an integral type that can hold values of InputIterator's distance type.
• InputIterator's value type is convertible to Predicate's argument type.
For the first version:
• [first, last) is a valid range.
For the second version:
• [first, last) is a valid range.
• n plus the number of elements that satisfy pred does not exceed the maximum value of type Size.
Linear. Exactly last – first applications of pred.
int main() {
int A[] = { 2, 0, 4, 6, 0, 3, 1, –7 };
const int N = sizeof(A) / sizeof(int);
cout << "Number of even elements: " << count_if(A, A + N, compose1(bind2nd(equal_to<int>(), 0), bind2nd(modulus<int>(), 2))) << endl;
}
[1] The new count interface uses the iterator_traits class, which relies on a C++ feature known as partial specialization . Many of today's compilers don't implement the complete standard; in particular, many compilers do not support partial specialization. If your compiler does not support partial specialization, then you will not be able to use the newer version of count, or any other STL components that involve iterator_traits.
count, find, find_if
Category: algorithms
Component type: function
Mismatch is an overloaded name; there are actually two mismatch functions.
template <class InputIterator1, class InputIterator2>
pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
template <class InputIterator1, class InputIterator2, class BinaryPredicate>
pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate binary_pred);
Mismatch finds the first position where the two ranges [first1, last1) and [first2, first2 + (last1 – first1)) differ. The two versions of mismatch use different tests for whether elements differ.
The first version of mismatch finds the first iterator i in [first1, last1) such that *i != *(first2 + (i – first1)). The return value is a pair whose first element is i and whose second element is *(first2 + (i – first1)). If no such iterator i exists, the return value is a pair whose first element is last1 and whose second element is *(first2 + (last1 – first1)).
The second version of mismatch finds the first iterator i in [first1, last1) such that binary_pred(*i, *(first2 + (i – first1)) is false. The return value is a pair whose first element is i and whose second element is *(first2 + (i – first1)). If no such iterator i exists, the return value is a pair whose first element is last1 and whose second element is *(first2 + (last1 – first1)).
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
For the first version:
• InputIterator1 is a model of Input Iterator.
• InputIterator2 is a model of Input Iterator.
• InputIterator1's value type is a model of Equality Comparable.
• InputIterator2's value type is a model of Equality Comparable.
• InputIterator1's value type can be compared for equality with InputIterator2's value type.
For the second version:
• InputIterator1 is a model of Input Iterator.
• InputIterator2 is a model of Input Iterator.
• BinaryPredicate is a model of Binary Predicate.
• InputIterator1's value type is convertible to BinaryPredicate's first argument type.
• InputIterator2's value type is convertible to BinaryPredicate's second argument type.
• [first1, last1) is a valid range.
• [first2, first2 + (last2 – last1)) is a valid range.
Linear. At most last1 – first1 comparisons.
int A1[] = { 3, 1, 4, 1, 5, 9, 3 };
int A2[] = { 3, 1, 4, 2, 8, 5, 7 };
const int N = sizeof(A1) / sizeof(int);
pair<int*, int*> result = mismatch(A1, A1 + N, A2);
cout << "The first mismatch is in position " << result.first – A1 << endl;
cout << "Values are: " << *(result.first) << ", " << *(result.second) << endl;
equal, search, find, find_if
Category: algorithms
Component type: function
Equal is an overloaded name; there are actually two equal functions.
template <class InputIterator 1, class InputIterator 2>
bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
template <class InputIterator 1, class InputIterator 2, class BinaryPredicate>
bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate binary_pred);
Equal returns true if the two ranges [first1, last1) and [first2, first2 + (last1 – first1)) are identical when compared element-by-element, and otherwise returns false. [1]
The first version of equal returns true if and only if for every iterator i in [first1, last1), *i == *(first2 + (i – first1)). The second version of equal returns true if and only if for every iterator i in [first1, last1), binary_pred(*i, *(first2 + (i – first1)) is true.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
For the first version:
• InputIterator1 is a model of Input Iterator.
• InputIterator2 is a model of Input Iterator.
• InputIterator1's value type is a model of Equality Comparable.
• InputIterator2's value type is a model of Equality Comparable.
• InputIterator1's value type can be compared for equality with InputIterator2's value type.
For the second version:
• InputIterator1 is a model of Input Iterator.
• InputIterator2 is a model of Input Iterator.
• BinaryPredicate is a model of Binary Predicate.
• InputIterator1's value type is convertible to BinaryPredicate 's first argument type.
• InputIterator2's value type is convertible to BinaryPredicate 's second argument type.
• [first1, last1) is a valid range.
• [first2, first2 + (last2 – last1)) is a valid range.
Linear. At most last1 – first1 comparisons.
int A1[] = { 3, 1, 4, 1, 5, 9, 3 };
int A2[] = { 3, 1, 4, 2, 8, 5, 7 };
const int N = sizeof(A1) / sizeof(int);
cout << "Result of comparison: " << equal(A1, A1 + N, A2) << endl;
[1] Note that this is very similar to the behavior of mismatch: The only real difference is that while equal will simply return false if the two ranges differ, mismatch returns the first location where they do differ. The expression equal(f1, l1, f2) is precisely equivalent to the expression mismatch(f1, l1, f2).first == l1, and this is in fact how equal could be implemented.
mismatch, search, find, find_if
Category: algorithms
Component type: function
Search is an overloaded name; there are actually two search functions.
template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2);
template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate binary_pred);
Search finds a subsequence within the range [first1, last1) that is identical to [first2, last2) when compared element-by-element. It returns an iterator pointing to the beginning of that subsequence, or else last1 if no such subsequence exists. The two versions of search differ in how they determine whether two elements are the same: the first uses operator==, and the second uses the user-supplied function object binary_pred.
The first version of search returns the first iterator i in the range [first1, last1 – (last2 – first2)) [1] such that, for every iterator j in the range [first2, last2), *(i + (j – first2)) == *j. The second version returns the first iterator i in [first1, last1 – (last2 – first2)) such that, for every iterator j in [first2, last2), binary_pred(*(i + (j – first2)), *j) is true. These conditions simply mean that every element in the subrange beginning with i must be the same as the corresponding element in [first2, last2).
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
For the first version:
• ForwardIterator1 is a model of Forward Iterator.
• ForwardIterator2 is a model of Forward Iterator.
• ForwardIterator1's value type is a model of EqualityComparable.
• ForwardIterator2's value type is a model of EqualityComparable.
• Objects of ForwardIterator1's value type can be compared for equality with Objects of ForwardIterator2's value type.
For the second version:
• ForwardIterator1 is a model of Forward Iterator.
• ForwardIterator2 is a model of Forward Iterator.
• BinaryPredicate is a model of Binary Predicate.
• ForwardIterator1's value type is convertible to BinaryPredicate's first argument type.
• ForwardIterator2's value type is convertible to BinaryPredicate's second argument type.
• [first1, last1) is a valid range.
• [first2, last2) is a valid range.
Worst case behavior is quadratic: at most (last1 – first1) * (last2 – first2) comparisons. This worst case, however, is rare. Average complexity is linear.
const char S1[] = "Hello, world!";
const char S2[] = "world";
const int N1 = sizeof(S1) – 1;
const int N2 = sizeof(S2) – 1;
const char* p = search(S1, S1 + N1, S2, S2 + N2);
printf("Found subsequence \"%s\" at character %d of sequence \"%s\".\n", S2, p – S1, S1);
[1] The reason that this range is [first1, last1 – (last2 – first2)), instead of simply [first1, last1), is that we are looking for a subsequence that is equal to the complete sequence [first2, last2). An iterator i can't be the beginning of such a subsequence unless last1 – i is greater than or equal to last2 – first2. Note the implication of this: you may call search with arguments such that last1 – first1 is less than last2 – first2, but such a search will always fail.
find, find_if, find_end, search_n, mismatch, equal
Category: algorithms
Component type: function
Search_n is an overloaded name; there are actually two search_n functions.
template<class ForwardIterator, class Integer, class T>
ForwardIterator search_n(ForwardIterator first, ForwardIterator last, Integer count, const T& value);
template<class ForwardIterator, class Integer, class T, class BinaryPredicate>
ForwardIterator search_n(ForwardIterator first, ForwardIterator last, Integer count, const T& value, BinaryPredicate binary_pred);
Search_n searches for a subsequence of count consecutive elements in the range [first, last), all of which are equal to value. [1] It returns an iterator pointing to the beginning of that subsequence, or else last if no such subsequence exists. The two versions of search_n differ in how they determine whether two elements are the same: the first uses operator==, and the second uses the user-supplied function object binary_pred.
The first version of search returns the first iterator i in the range [first, last – count) [2] such that, for every iterator j in the range [i, i + count), *j == value. The second version returns the first iterator i in the range [first, last – count) such that, for every iterator j in the range [i, i + count), binary_pred(*j, value) is true.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
For the first version:
• ForwardIterator is a model of Forward Iterator.
• Integer is an integral type.
• T is a model of EqualityComparable.
• ForwardIterator's value type is a model of EqualityComparable.
• Objects of ForwardIterator's value type can be compared for equality with Objects of type T.
For the second version:
• ForwardIterator is a model of Forward Iterator.
• Integer is an integral type.
• T is a model of EqualityComparable.
• BinaryPredicate is a model of Binary Predicate.
• ForwardIterator's value type is convertible to BinaryPredicate's first argument type.
• T is convertible to BinaryPredicate's second argument type.
• [first, last) is a valid range.
• count is non-negative [1].
Linear. Search_n performs at most last – first comparisons.
(The C++ standard permits the complexity to be O(n(last – first )), but this is unnecessarily lax. There is no reason for search_n to examine any element more than once.)
bool eq_nosign(int x, int y) { return abs(x) == abs(y); }
void lookup(int* first, int* last, size_t count, int val) {
cout << "Searching for a sequence of " << count << " '" << val << "'" << (count != 1 ? "s: " : ": ");
int* result = search_n(first, last, count, val);
if (result == last) cout << "Not found" << endl;
else cout << "Index = " << result – first << endl;
}
void lookup_nosign(int* first, int* last, size_t count, int val) {
cout << "Searching for a (sign-insensitive) sequence of " << count << " '" << val << "'" << (count != 1 ? "s: " : ": ");
int* result = search_n(first, last, count, val, eq_nosign);
if (result == last) cout << "Not found" << endl;
else cout << "Index = " << result – first << endl;
}
int main() {
const int N = 10;
int A[N] = {1, 2, 1, 1, 3, –3, 1, 1, 1, 1};
lookup(A, A+N, 1, 4);
lookup(A, A+N, 0, 4);
lookup(A, A+N, 1, 1);
lookup(A, A+N, 2, 1);
lookup(A, A+N, 3, 1);
lookup(A, A+N, 4, 1);
lookup(A, A+N, 1, 3);
lookup(A, A+N, 2, 3);
lookup_nosign(A, A+N, 1, 3);
lookup_nosign(A, A+N, 2, 3);
}
The output is
Searching for a sequence of 1 '4': Not found
Searching for a sequence of 0 '4's: Index = 0
Searching for a sequence of 1 '1': Index = 0
Searching for a sequence of 2 '1's: Index = 2
Searching for a sequence of 3 '1's: Index = 6
Searching for a sequence of 4 '1's: Index = 6
Searching for a sequence of 1 '3': Index = 4
Searching for a sequence of 2 '3's: Not found
Searching for a (sign-insensitive) sequence of 1 '3': Index = 4
Searching for a (sign-insensitive) sequence of 2 '3's: Index = 4
[1] Note that count is permitted to be zero: a subsequence of zero elements is well defined. If you call search_n with count equal to zero, then the search will always succeed: no matter what value is, every range contains a subrange of zero consecutive elements that are equal to value. When search_n is called with count equal to zero, the return value is always first.
[2] The reason that this range is [first, last – count), rather than just [first, last), is that we are looking for a subsequence whose length is count; an iterator i can't be the beginning of such a subsequence unless last – count is greater than or equal to count. Note the implication of this: you may call search_n with arguments such that last – first is less than count, but such a search will always fail.
search, find_end, find, find_if
Category: algorithms
Component type: function
find_end is an overloaded name; there are actually two find_end functions.
template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2);
template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate comp);
Find_end is misnamed: it is much more similar to search than to find, and a more accurate name would have been search_end.
Like search, find_end attempts to find a subsequence within the range [first1, last1) that is identical to [first2, last2). The difference is that while search finds the first such subsequence, find_end finds the last such subsequence. Find_end returns an iterator pointing to the beginning of that subsequence; if no such subsequence exists, it returns last1.
The two versions of find_end differ in how they determine whether two elements are the same: the first uses operator==, and the second uses the user-supplied function object comp.
The first version of find_end returns the last iterator i in the range [first1, last1 – (last2 – first2)) such that, for every iterator j in the range [first2, last2), *(i + (j – first2)) == *j. The second version of find_end returns the last iterator i in [first1, last1 – (last2 – first2)) such that, for every iterator j in [first2, last2), binary_pred(*(i + (j – first2)), *j) is true. These conditions simply mean that every element in the subrange beginning with i must be the same as the corresponding element in [first2, last2).
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
For the first version:
• ForwardIterator1 is a model of Forward Iterator.
• ForwardIterator2 is a model of Forward Iterator.
• ForwardIterator1's value type is a model of EqualityComparable.
• ForwardIterator2's value type is a model of EqualityComparable.
• Objects of ForwardIterator1's value type can be compared for equality with Objects of ForwardIterator2's value type.
For the second version:
• ForwardIterator1 is a model of Forward Iterator.
• ForwardIterator2 is a model of Forward Iterator.
• BinaryPredicate is a model of Binary Predicate.
• ForwardIterator1's value type is convertible to BinaryPredicate's first argument type.
• ForwardIterator2's value type is convertible to BinaryPredicate's second argument type.
• [first1, last1) is a valid range.
• [first2, last2) is a valid range.
The number of comparisons is proportional to (last1 – first1) * (last2 – first2). If both ForwardIterator1 and ForwardIterator2 are models of Bidirectional Iterator, then the average complexity is linear and the worst case is at most (last1 – first1) * (last2 – first2) comparisons.
int main() {
char* s = "executable.exe";
char* suffix = "exe";
const int N = strlen(s);
const int N_suf = strlen(suffix);
char* location = find_end(s, s + N, suffix, suffix + N_suf);
if (location != s + N) {
cout << "Found a match for " << suffix << " within " << s << endl;
cout << s << endl;
int i;
for (i = 0; i < (location – s); ++i) cout << ' ';
for (i = 0; i < N_suf; ++i) cout << '^';
cout << endl;
} else cout << "No match for " << suffix << " within " << s << endl;
}
[1] The reason that this range is [first1, last1 – (last2 – first2)), instead of simply [first1, last1), is that we are looking for a subsequence that is equal to the complete sequence [first2, last2). An iterator i can't be the beginning of such a subsequence unless last1 – i is greater than or equal to last2 – first2. Note the implication of this: you may call find_end with arguments such that last1 – first1 is less than last2 – first2, but such a search will always fail.
search
Category: algorithms
Component type: function
template <class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result);
Copy copies elements from the range [first, last) to the range [result, result + (last – first)). That is, it performs the assignments *result = *first, *(result + 1) = *(first + 1), and so on. [1] Generally, for every integer n from 0 to last – first, copy performs the assignment *(result + n) = *(first + n). Assignments are performed in forward order, i.e. in order of increasing n. [2]
The return value is result + (last – first)
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
• InputIterator is a model of Input Iterator.
• OutputIterator is a model of Output Iterator.
• InputIterator's value type is convertible to a type in OutputIterator's set of value types.
• [first, last) is a valid range.
• result is not an iterator within the range [first, last).
• There is enough space to hold all of the elements being copied. More formally, the requirement is that [result, result + (last – first)) is a valid range. [1]
Linear. Exactly last – first assignments are performed.
vector<int> V(5);
iota(V.begin(), V.end(), 1);
list<int> L(V.size());
copy(V.begin(), V.end(), L.begin());
assert(equal(V.begin(), V.end(), L.begin()));
[1] Note the implications of this. Copy cannot be used to insert elements into an empty Container: it overwrites elements, rather than inserting elements. If you want to insert elements into a Sequence, you can either use its insert member function explicitly, or else you can use copy along with an insert_iterator adaptor.
[2] The order of assignments matters in the case where the input and output ranges overlap: copy may not be used if result is in the range [first, last). That is, it may not be used if the beginning of the output range overlaps with the input range, but it may be used if the end of the output range overlaps with the input range; copy_backward has opposite restrictions. If the two ranges are completely nonoverlapping, of course, then either algorithm may be used. The order of assignments also matters if result is an ostream_iterator, or some other iterator whose semantics depends on the order or assignments.
copy_backward, copy_n
Category: algorithms
Component type: function
template <class InputIterator, class Size, class OutputIterator>
OutputIterator copy_n(InputIterator first, Size count, OutputIterator result);
Copy_n copies elements from the range [first, first + n) to the range [result, result + n). That is, it performs the assignments *result = *first, *(result + 1) = *(first + 1), and so on. Generally, for every integer i from 0 up to (but not including) n, copy_n performs the assignment *(result + i) = *(first + i). Assignments are performed in forward order, i.e. in order of increasing n. [1]
The return value is result + n.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h. This function is an SGI extension; it is not part of the C++ standard.
• InputIterator is a model of Input Iterator.
• OutputIterator is a model of Output Iterator.
• Size is an integral type.
• InputIterator's value type is convertible to a type in OutputIterator's set of value types.
• n >= 0.
• [first, first + n) is a valid range.
• result is not an iterator within the range [first, first + n).
• [result, result + n) is a valid range.
Linear. Exactly n assignments are performed.
vector<int> V(5);
iota(V.begin(), V.end(), 1);
list<int> L(V.size());
copy_n(V.begin(), V.size(), L.begin());
assert(equal(V.begin(), V.end(), L.begin()));
[1] Copy_n is almost, but not quite, redundant. If first is an input iterator, as opposed to a forward iterator, then the copy_n operation can't be expressed in terms of copy.
copy, copy_backward
Category: algorithms
Component type: function
template <class BidirectionalIterator1, class BidirectionalIterator2>
BidirectionalIterator2 copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 result);
Copy_backward copies elements from the range [first, last) to the range [result – (last – first), result) [1]. That is, it performs the assignments *(result – 1) = *(last – 1), *(result – 2) = *(last – 2), and so on. Generally, for every integer n from 0 to last – first, copy_backward performs the assignment *(result – n – 1) = *(last – n – 1). Assignments are performed from the end of the input sequence to the beginning, i.e. in order of increasing n. [2]
The return value is result – (last – first)
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
• BidirectionalIterator1 and BidirectionalIterator2 are models of BidirectionalIterator.
• BidirectionalIterator1's value type is convertible to BidirectionalIterator2's value type.
• [first, last) is a valid range.
• result is not an iterator within the range [first, last).
• There is enough space to hold all of the elements being copied. More formally, the requirement is that [result – (last – first), result) is a valid range.
Linear. Exactly last – first assignments are performed.
vector<int> V(15);
iota(V.begin(), V.end(), 1);
copy_backward(V.begin(), V.begin() + 10, V.begin() + 15);
[1] Result is an iterator that points to the end of the output range. This is highly unusual: in all other STL algorithms that denote an output range by a single iterator, that iterator points to the beginning of the range.
[2] The order of assignments matters in the case where the input and output ranges overlap: copy_backward may not be used if result is in the range [first, last). That is, it may not be used if the end of the output range overlaps with the input range, but it may be used if the beginning of the output range overlaps with the input range; copy has opposite restrictions. If the two ranges are completely nonoverlapping, of course, then either algorithm may be used.
copy, copy_n
Category: algorithms
Component type: function
template <class Assignable>
void swap(Assignable& a, Assignable& b);
Assigns the contents of a to b and the contents of b to a. This is used as a primitive operation by many other algorithms.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
• Assignable is a model of Assignable.
None.
Amortized constant time. [1] [2]
int x = 1;
int y = 2;
assert(x == 1 && y == 2);
swap(x, y);
assert(x == 2 && y == 1);
[1] The time required to swap two objects of type T will obviously depend on the type; "constant time" does not mean that performance will be the same for an 8-bit char as for a 128-bit complex<double>.
[2] This implementation of swap makes one call to a copy constructor and two calls to an assignment operator; roughly, then, it should be expected to take about the same amount of time as three assignments. In many cases, however, it is possible to write a specialized version of swap that is far more efficient. Consider, for example, swapping two vector<double>s each of which has N elements. The unspecialized version requires 3*N assignments of double, but a specialized version requires only nine pointer assignments. This is important because swap is used as a primitive operation in many other STL algorithms, and because containers of containers (list<vector<char> >, for example) are very common. The STL includes specialized versions of swap for all container classes. User-defined types should also provide specialized versions of swap whenever it is possible to write one that is more efficient than the general version.
iter_swap, swap_ranges
Category: algorithms
Component type: function
template <class ForwardIterator1, class ForwardIterator 2>
inline void iter_swap(ForwardIterator1 a, ForwardIterator2 b);
Equivalent to swap(*a, *b). [1]
Declared in algo.h. The implementation is in algobase.h.
• ForwardIterator1 and ForwardIterator2 are models of Forward Iterator.
• ForwardIterator1 and ForwardIterator2 are mutable.
• ForwardIterator1 and ForwardIterator2 have the same value type.
• ForwardIterator1 and ForwardIterator2 are dereferenceable.
See swap for a discussion.
int x = 1;
int y = 2;
assert(x == 1 && y == 2);
iter_swap(&x, &y);
assert(x == 2 && y == 1);
[1] Strictly speaking, iter_swap is redundant. It exists only for technical reasons: in some circumstances, some compilers have difficulty performing the type deduction required to interpret swap(*a, *b).
swap, swap_ranges
Category: algorithms
Component type: function
template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator2 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2);
Swap_ranges swaps each of the elements in the range [first1, last1) with the corresponding element in the range [first2, first2 + (last1 – first1)). That is, for each integer n such that 0 <= n < (last1 – first1), it swaps *(first1 + n) and *(first2 + n). The return value is first2 + (last1 – first1).
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
ForwardIterator1 and ForwardIterator2 must both be models of Forward Iterator. The value types of ForwardIterator1 and ForwardIterator2 must be convertible to each other.
• [first1, last1) is a valid range.
• [first2, first2 + (last1 – first1)) is a valid range.
• The two ranges [first1, last1) and [first2, first2 + (last1 – first1)) do not overlap.
Linear. Exactly last1 – first1 swaps are performed.
vector<int> V1, V2;
V1.push_back(1);
V1.push_back(2);
V2.push_back(3);
V2.push_back(4);
assert(V1[0] == 1 && V1[1] == 2 && V2[0] == 3 && V2[1] == 4);
swap_ranges(V1.begin(), V1.end(), V2.begin());
assert(V1[0] == 3 && V1[1] == 4 && V2[0] == 1 && V2[1] == 2);
swap, iter_swap.
Category: algorithms
Component type: function
Transform is an overloaded name; there are actually two transform functions.
template <class InputIterator, class OutputIterator, class UnaryFunction>
OutputIterator transform(InputIterator first, InputIterator last, OutputIterator result, UnaryFunction op);
template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryFunction>
OutputIterator transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryFunction binary_op);
Transform performs an operation on objects; there are two versions of transform, one of which uses a single range of Input Iterators and one of which uses two ranges of Input Iterators.
The first version of transform performs the operation op(*i) for each iterator i in the range [first, last) , and assigns the result of that operation to *o, where o is the corresponding output iterator. That is, for each n such that 0 <= n < last – first, it performs the assignment *(result + n) = op(*(first + n)). The return value is result + (last – first).
The second version of transform is very similar, except that it uses a Binary Function instead of a Unary Function: it performs the operation op(*i1, *i2) for each iterator i1 in the range [first1, last1) and assigns the result to *o, where i2 is the corresponding iterator in the second input range and where o is the corresponding output iterator. That is, for each n such that 0 <= n < last1 – first1, it performs the assignment *(result + n) = op(*(first1 + n), *(first2 + n). The return value is result + (last1 – first1).
Note that transform may be used to modify a sequence "in place": it is permissible for the iterators first and result to be the same. [1]
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
For the first (unary) version:
• InputIterator must be a model of Input Iterator.
• OutputIterator must be a model of Output Iterator.
• UnaryFunction must be a model of Unary Function.
• InputIterator's value type must be convertible to UnaryFunction's argument type.
• UnaryFunction's result type must be convertible to a type in OutputIterator's set of value types.
For the second (binary) version:
• InputIterator1 and InputIterator2 must be models of Input Iterator.
• OutputIterator must be a model of Output Iterator.
• BinaryFunction must be a model of Binary Function.
• InputIterator1's and InputIterator2's value types must be convertible, respectively, to BinaryFunction's first and second argument types.
• UnaryFunction's result type must be convertible to a type in OutputIterator's set of value types.
For the first (unary) version:
• [first, last) is a valid range.
• result is not an iterator within the range [first+1, last). [1]
• There is enough space to hold all of the elements being copied. More formally, the requirement is that [result, result + (last – first)) is a valid range.
For the second (binary) version:
• [first1, last1) is a valid range.
• [first2, first2 + (last1 – first1)) is a valid range.
• result is not an iterator within the range [first1+1, last1) or [first2 + 1, first2 + (last1 – first1)).
• There is enough space to hold all of the elements being copied. More formally, the requirement is that [result, result + (last1 – first1)) is a valid range.
Linear. The operation is applied exactly last – first times in the case of the unary version, or last1 – first1 in the case of the binary version.
Replace every number in an array with its negative.
const int N = 1000;
double A[N];
iota (A, A+N, 1);
transform(A, A+N, A, negate<double>());
Calculate the sum of two vectors, storing the result in a third vector.
const int N = 1000;
vector<int> V1(N);
vector<int> V2(N);
vector <int> V3(N);
iota(V1.begin(), V1.end(), 1);
fill(V2.begin(), V2.end(), 75);
assert(V2.size() >= V1.size() && V3.size() >= V1.size());
transform(V1.begin(), V1.end(), V2.begin(), V3.begin(), plus <int>());
[1] The Output Iterator result is not permitted to be the same as any of the Input Iterators in the range [first, last), with the exception of first itself. That is: transform(V.begin(), V.end(), V.begin(), fabs) is valid, but transform(V.begin(), V.end(), V.begin() + 1, fabs) is not.
The function object overview, copy, generate, fill
Category: algorithms
Component type: function
template <class ForwardIterator, class T>
void replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value)
Replace replaces every element in the range [first, last) equal to old_value with new_value. That is: for every iterator i , if *i == old_value then it performs the assignment *i = new_value.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
• ForwardIterator is a model of Forward Iterator.
• ForwardIterator is mutable.
• T is convertible to ForwardIterator's value type.
• T is Assignable.
• T is EqualityComparable, and may be compared for equality with objects of ForwardIterator's value type.
• [first, last) is a valid range.
Linear. Replace performs exactly last – first comparisons for equality, and at most last – first assignments.
vector<int> V;
V.push_back(1);
V.push_back(2);
V.push_back(3);
V.push_back(1);
replace(V.begin(), V.end(), 1, 99);
assert(V[0] == 99 && V[3] == 99);
replace_if, replace_copy, replace_copy_if
Category: algorithms
Component type: function
template <class ForwardIterator, class Predicate, class T>
void replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value)
Replace_if replaces every element in the range [first, last) for which pred returns true with new_value. That is: for every iterator i, if pred(*i) is true then it performs the assignment *i = new_value.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
• ForwardIterator is a model of Forward Iterator.
• ForwardIterator is mutable.
• Predicate is a model of Predicate.
• ForwardIterator's value type is convertible to Predicate's argument type.
• T is convertible to Forward Iterator's value type.
• T is Assignable.
• [first, last) is a valid range.
Linear. Replace_if performs exactly last – first applications of pred, and at most last – first assignments.
Replace every negative number with 0.
vector<int> V;
V.push_back(1);
V.push_back(-3);
V.push_back(2);
V.push_back(-1);
replace_if(V.begin(), V.end(), bind2nd(less<int>(), 0), –1);
assert(V[1] == 0 && V[3] == 0);
replace, replace_copy, replace_copy_if
Category: algorithms
Component type: function
template <class InputIterator, class OutputIterator, class T>
OutputIterator replace_copy(InputIterator first, InputIterator last, OutputIterator result, const T& old_value, const T& new_value);
Replace_copy copies elements from the range [first, last) to the range [result, result + (last-first)), except that any element equal to old_value is not copied; new_value is copied instead. More precisely, for every integer n such that 0 <= n < last-first, replace_copy performs the assignment *(result+n) = new_value if *(first+n) == old_value, and *(result+n) = *(first+n) otherwise.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
• InputIterator is a model of Input Iterator.
• OutputIterator is a model of Output Iterator.
• T is EqualityComparable, and may be compared for equality with objects of InputIterator's value type.
• T is Assignable.
• T is convertible to a type in OutputIterator's set of value types.
• [first, last) is a valid range.
• There is enough space in the output range to store the copied values. That is, [result, result + (last-first)) is a valid range.
• result is not an iterator within the range [first, last).
Linear. Replace_copy performs exactly last – first comparisons for equality and exactly last – first assignments.
vector<int> V1;
V1.push_back(1);
V1.push_back(2);
V1.push_back(3);
V1.push_back(1);
vector<int> V2(4);
replace_copy(V1.begin(), V1.end(), V2.begin(), 1, 99);
assert(V[0] == 99 && V[1] == 2 && V[2] == 3 && V[3] == 99);
copy, replace, replace_if, replace_copy_if
Category: algorithms
Component type: function
template <class InputIterator, class OutputIterator, class Predicate, class T>
OutputIterator replace_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred, const T& new_value)
Replace_copy_if copies elements from the range [first, last) to the range [result, result + (last-first)), except that any element for which pred is true is not copied; new_value is copied instead. More precisely, for every integer n such that 0 <= n < last-first, replace_copy_if performs the assignment *(result+n) = new_value if pred(*(first+n)) , and *(result+n) = *(first+n) otherwise.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
• InputIterator is a model of Input Iterator.
• OutputIterator is a model of Output Iterator.
• Predicate is a model of Predicate.
• T is convertible to Predicate's argument type.
• T is Assignable.
• T is convertible to a type in OutputIterator's set of value types.
• [first, last) is a valid range.
• There is enough space in the output range to store the copied values. That is, [result, result + (last-first)) is a valid range.
• result is not an iterator within the range [first, last).
Linear. Replace_copy performs exactly last – first applications of pred and exactly last – first assignments.
Copy elements from one vector to another, replacing all negative numbers with 0.
vector<int> V1;
V1.push_back(1);
V1.push_back(-1);
V1.push_back(-5);
V1.push_back(2);
vector<int> V2(4);
replace_copy_if(V1.begin(), V1.end(), V2.begin(), bind2nd(less<int>(), 0), 0);
assert(V[0] == 1 && V[1] == 0 && V[2] == 0 && V[3] == 2);
copy, replace, replace_if, replace_copy
Category: algorithms
Component type: function
template <class ForwardIterator, class T>
void fill(ForwardIterator first, ForwardIterator last, const T& value);
Fill assigns the value value to every element in the range [first, last). That is, for every iterator i in [first, last), it performs the assignment *i = value.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
• ForwardIterator is a model of Forward Iterator . [1]
• ForwardIterator is mutable.
• T is a model of Assignable.
• T is convertible to Forward Iterator's value type.
• [first, last) is a valid range.
Complexity
Linear. Fill performs exactly last – first assignments.
vector <double> V(4);
fill(V.begin(), V.end(), 137);
assert(V[0] == 137 && V[1] == 137 && V[2] == 137 && V[3] == 137);
[1] The reason that fill requires its argument to be a mutable forward iterator, rather than merely an output iterator, is that it uses a range [first, last) of iterators. There is no sensible way to describe a range of output iterators, because it is impossible to compare two output iterators for equality. The fill_n algorithm does have an interface that permits use of an output iterator.
copy, fill_n, generate, generate_n, iota
Category: algorithms
Component type: function
template <class OutputIterator, class Size, class T>
OutputIterator fill_n(OutputIterator first, Size n, const T& value);
Fill_n assigns the value value to every element in the range [first, first+n). That is, for every iterator i in [first, first+n), it performs the assignment *i = value. The return value is first + n.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
• OutputIterator is a model of Output Iterator.
• Size is an integral type (either signed or unsigned).
• T is a model of Assignable.
• T is convertible to a type in OutputIterator's set of value types.
• n >= 0.
• There is enough space to hold n values. That is, [first, first+n) is a valid range.
Linear. Fill_n performs exactly n assignments.
vector<double> V;
fill_n(back_inserter(V), 4, 137);
assert(V.size() == 4 && V[0] == 42 && V[1] == 42 && V[2] == 42 && V[3] == 42);
copy, fill, generate, generate_n, iota
Category: algorithms
Component type: function
template <class ForwardIterator, class Generator>
void generate(ForwardIterator first, ForwardIterator last, Generator gen);
Generate assigns the result of invoking gen, a function object that takes no arguments, to each element in the range [first, last). [1]
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
• ForwardIterator is a model of Forward Iterator. [2]
• ForwardIterator is mutable.
• Generator is a model of Generator.
• Generator's result type is convertible to ForwardIterator's value type.
Preconditions
• [first, last) is a valid range.
Complexity
Linear. Exactly last – first invocations of gen. [1]
Fill a vector with random numbers, using the standard C library function rand.
vector<int> V;
…
generate(V.begin(), V.end(), rand);
[1] The function object gen is invoked for each iterator in the range [first, last), as opposed to just being invoked a single time outside the loop. This distinction is important because a Generator need not return the same result each time it is invoked; it is permitted to read from a file, refer to and modify local state, and so on.
[2] The reason that generate requires its argument to be a mutable Forward Iterator, rather than just an Output Iterator, is that it uses a range [first, last) of iterators. There is no sensible way to describe a range of Output Iterators, because it is impossible to compare two Output Iterators for equality. The generate_n algorithm does have an interface that permits use of an Output Iterator.
copy, fill, fill_n, generate_n, iota
Category: algorithms
Component type: function
template <class OutputIterator, class Size, class Generator>
OutputIterator generate_n(OutputIterator first, Size n, Generator gen);
Generate_n assigns the result of invoking gen, a function object that takes no arguments, to each element in the range [first, first+n). [1] The return value is first + n.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
• OutputIterator is a model of Output Iterator.
• Size is an integral type (either signed or unsigned).
• Generator is a model of Generator.
• Generator's result type is convertible to a type in OutputIterator 's set of value types.
• n >= 0.
• There is enough space to hold n values. That is, [first, first+n) is a valid range.
Linear. Exactly n invocations of gen. [1]
Print 100 random numbers, using the C standard library function rand.
generate_n(ostream_iterator<int>(cout, "\n"), 100, rand);
[1] The function object gen is invoked n times (once for each iterator in the range [first, first+n) ), as opposed to just being invoked a single time outside the loop. This distinction is important because a Generator need not return the same result each time it is invoked; it is permitted to read from a file, refer to and modify local state, and so on.
copy, fill, fill_n, generate, iota
Category: algorithms
Component type: function
template <class ForwardIterator, class T>
ForwardIterator remove(ForwardIterator first, ForwardIterator last, const T& value);
Remove removes from the range [first, last) all elements that are equal to value. That is, remove returns an iterator new_last such that the range [first, new_last) contains no elements equal to value. [1] The iterators in the range [new_last, last) are all still dereferenceable, but the elements that they point to are unspecified. Remove is stable, meaning that the relative order of elements that are not equal to value is unchanged.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
• ForwardIterator is a model of Forward Iterator.
• ForwardIterator is mutable.
• T is a model of Equality Comparable.
• Objects of type T can be compared for equality with objects of ForwardIterator's value type.
• [first, last) is a valid range.
Linear. Remove performs exactly last – first comparisons for equality.
vector<int> V;
V.push_back(3);
V.push_back(1);
V.push_back(4);
V.push_back(1);
V.push_back(5);
V.push_back(9);
copy(V.begin(), V.end(), ostream_iterator<int>(cout, " "));
// The output is "3 1 4 1 5 9".
vector<int>::iterator new_end = remove(V.begin(), V.end(), 1);
copy(V.begin(), new_end, ostream_iterator<int>(cout, " "));
// The output is "3 4 5 9".
[1] The meaning of "removal" is somewhat subtle. Remove does not destroy any iterators, and does not change the distance between first and last. (There's no way that it could do anything of the sort.) So, for example, if V is a vector, remove(V.begin(), V.end(), 0) does not change V.size(): V will contain just as many elements as it did before. Remove returns an iterator that points to the end of the resulting range after elements have been removed from it; it follows that the elements after that iterator are of no interest, and may be discarded. If you are removing elements from a Sequence, you may simply erase them. That is, a reasonable way of removing elements from a Sequence is S.erase(remove(S.begin(), S.end(), x), S.end()).
remove_if, remove_copy, remove_copy_if, unique, unique_copy.
Category: algorithms
Component type: function
template <class ForwardIterator, class Predicate>
ForwardIterator remove_if(ForwardIterator first, ForwardIterator last, Predicate pred);
Remove_if removes from the range [first, last) every element x such that pred(x) is true. That is, remove_if returns an iterator new_last such that the range [first, new_last) contains no elements for which pred is true. [1] The iterators in the range [new_last, last) are all still dereferenceable, but the elements that they point to are unspecified. Remove_if is stable, meaning that the relative order of elements that are not removed is unchanged.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
• ForwardIterator is a model of Forward Iterator.
• ForwardIterator is mutable.
• Predicate is a model of Predicate.
• ForwardIterator's value type is convertible to Predicate's argument type.
• [first, last) is a valid range.
Linear. Remove_if performs exactly last – first applications of pred.
Remove all even numbers from a vector.
vector<int> V;
V.push_back(1);
V.push_back(4);
V.push_back(2);
V.push_back(8);
V.push_back(5);
V.push_back(7);
copy(V.begin(), V.end(), ostream_iterator<int>(cout, " "));
// The output is "1 4 2 8 5 7"
vector<int>::iterator new_end = remove_if(V.begin(), V.end(), compose1(bind2nd(equal_to<int>(), 0), bind2nd( modulus<int>(), 2)));
V.erase(new_end, V.end()); [1]
copy(V.begin(), V.end(), ostream_iterator<int>(cout, " "));
// The output is "1 5 7".
[1] The meaning of "removal" is somewhat subtle. Remove_if does not destroy any iterators, and does not change the distance between first and last. (There's no way that it could do anything of the sort.) So, for example, if V is a vector, remove_if(V.begin(), V.end(), pred) does not change V.size(): V will contain just as many elements as it did before. Remove_if returns an iterator that points to the end of the resulting range after elements have been removed from it; it follows that the elements after that iterator are of no interest, and may be discarded. If you are removing elements from a Sequence, you may simply erase them. That is, a reasonable way of removing elements from a Sequence is S.erase(remove_if(S.begin(), S.end(), pred), S.end()).
remove, remove_copy, remove_copy_if, unique, unique_copy.
Category: algorithms
Component type: function
template <class InputIterator, class OutputIterator, class T>
OutputIterator remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value);
Remove_copy copies elements that are not equal to value from the range [first, last) to a range beginning at result. The return value is the end of the resulting range. This operation is stable, meaning that the relative order of the elements that are copied is the same as in the range [first, last).
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
• InputIterator is a model of Input Iterator.
• OutputIterator is a model of Output Iterator.
• InputIterator's value type is convertible to a type in OutputIterator's set of value types.
• T is a model of Equality Comparable.
• Objects of type T can be compared for equality with objects of InputIterator's value type.
• [first, last) is a valid range.
• There is enough space in the output range to store the copied values. That is, if there are n elements in [first, last) that are not equal to value, then [result, result+n) is a valid range.
• result is not an iterator in the range [first, last) .
Linear. Exactly last – first comparisons for equality, and at most last – first assignments.
Print all nonzero elements of a vector on the standard output.
vector<int> V;
V.push_back(-2);
V.push_back(0);
V.push_back(-1);
V.push_back(0);
V.push_back(1);
V.push_back(2);
remove_copy(V.begin(), V.end(), ostream_iterator<int>(cout, "\n"), 0);
copy, remove, remove_if, remove_copy_if, unique, unique_copy.
Category: algorithms
Component type: function
template <class InputIterator, class OutputIterator, class Predicate>
OutputIterator remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred);
Remove_copy_if copies elements from the range [first, last) to a range beginning at result , except that elements for which pred is true are not copied. The return value is the end of the resulting range. This operation is stable, meaning that the relative order of the elements that are copied is the same as in the range [first, last).
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
• InputIterator is a model of Input Iterator.
• OutputIterator is a model of Output Iterator.
• InputIterator's value type is convertible to a type in OutputIterator's set of value types.
• Predicate is a model of Predicate.
• InputIterator's value type is convertible to Predicate's argument type.
• [first, last) is a valid range.
• There is enough space in the output range to store the copied values. That is, if there are n elements in [first, last) that do not satisfy pred, then [result, result+n) is a valid range.
• result is not an iterator in the range [first, last).
Linear. Exactly last – first applications of pred , and at most last – first assignments.
Fill a vector with the nonnegative elements of another vector.
vector<int> V1;
V.push_back(-2);
V.push_back(0);
V.push_back(-1);
V.push_back(0);
V.push_back(1);
V.push_back(2);
vector<int> V2; remove_copy_if(V1.begin(), V1.end(), back_inserter(V2), bind2nd(less<int>(), 0));
copy, remove, remove_if, remove_copy, unique, unique_copy.
Category: algorithms
Component type: function
Unique is an overloaded name; there are actually two unique functions.
template <class ForwardIterator>
ForwardIterator unique(ForwardIterator first, ForwardIterator last);
template <class ForwardIterator, class BinaryPredicate>
ForwardIterator unique(ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred);
Every time a consecutive group of duplicate elements appears in the range [first, last), the algorithm unique removes all but the first element. That is, unique returns an iterator new_last such that the range [first, new_last) contains no two consecutive elements that are duplicates. [1] The iterators in the range [new_last, last) are all still dereferenceable, but the elements that they point to are unspecified. Unique is stable, meaning that the relative order of elements that are not removed is unchanged.
The reason there are two different versions of unique is that there are two different definitions of what it means for a consecutive group of elements to be duplicates. In the first version, the test is simple equality: the elements in a range [f, l) are duplicates if, for every iterator i in the range, either i == f or else *i == *(i-1). In the second, the test is an arbitrary Binary Predicate binary_pred: the elements in [f, l) are duplicates if, for every iterator i in the range, either i == f or else binary_pred(*i, *(i-1)) is true. [2]
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
For the first version:
• ForwardIterator is a model of Forward Iterator.
• ForwardIterator is mutable.
• ForwardIterator's value type is Equality Comparable.
For the second version:
• ForwardIterator is a model of Forward Iterator.
• ForwardIterator is mutable.
• BinaryPredicate is a model of Binary Predicate. [3]
• ForwardIterator's value type is convertible to BinaryPredicate's first argument type and to BinaryPredicate 's second argument type.
• [first, last) is a valid range.
Linear. Exactly (last – first) – 1 applications of operator== (in the case of the first version of unique ) or of binary_pred (in the case of the second version).
Remove duplicates from consecutive groups of equal int s.
vector<int> V;
V.push_back(1);
V.push_back(3);
V.push_back(3);
V.push_back(3);
V.push_back(2);
V.push_back(2);
V.push_back(1);
vector<int>::iterator new_end = unique(V.begin(), V.end());
copy(V.begin(), new_end, ostream_iterator<int>(cout, " "));
// The output it "1 3 2 1".
Remove all duplicates from a vector of char s, ignoring case. First sort the vector, then remove duplicates from consecutive groups.
inline bool eq_nocase(char c1, char c2) { return tolower(c1) == tolower(c2); }
inline bool lt_nocase(char c1, char c2) { return tolower(c1) < tolower(c2); }
int main() {
const char init[] = "The Standard Template Library";
vector<char> V(init, init + sizeof(init));
sort(V.begin(), V.end(), lt_nocase);
copy(V.begin(), V.end(), ostream_iterator<char>(cout));
cout << endl;
vector<char>::iterator new_end = unique(V.begin(), V.end(), eq_nocase);
copy(V.begin(), new_end, ostream_iterator<char>(cout));
cout << endl;
}
// The output is:
// aaaabddeeehiLlmnprrrStTtTy
// abdehiLmnprSty
[1] Note that the meaning of "removal" is somewhat subtle. Unique , like remove, does not destroy any iterators and does not change the distance between first and last. (There's no way that it could do anything of the sort.) So, for example, if V is a vector, remove(V.begin(), V.end(), 0) does not change V.size(): V will contain just as many elements as it did before. Unique returns an iterator that points to the end of the resulting range after elements have been removed from it; it follows that the elements after that iterator are of no interest. If you are operating on a Sequence, you may wish to use the Sequence's erase member function to discard those elements entirely.
[2] Strictly speaking, the first version of unique is redundant: you can achieve the same functionality by using an object of class equal_to as the Binary Predicate argument. The first version is provided strictly for the sake of convenience: testing for equality is an important special case.
[3] BinaryPredicate is not required to be an equivalence relation. You should be cautious, though, about using unique with a Binary Predicate that is not an equivalence relation: you could easily get unexpected results.
Binary Predicate, remove, remove_if, unique_copy, adjacent_find
Category: algorithms
Component type: function
Unique_copy is an overloaded name; there are actually two unique_copy functions.
template <class InputIterator, class OutputIterator>
OutputIterator unique_copy(InputIterator first, InputIterator last, OutputIterator result);
template <class InputIterator, class OutputIterator, class BinaryPredicate>
OutputIterator unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate binary_pred);
Unique_copy copies elements from the range [first, last) to a range beginning with result, except that in a consecutive group of duplicate elements only the first one is copied. The return value is the end of the range to which the elements are copied. This behavior is similar to the Unix filter uniq.
The reason there are two different versions of unique_copy is that there are two different definitions of what it means for a consecutive group of elements to be duplicates. In the first version, the test is simple equality: the elements in a range [f, l) are duplicates if, for every iterator i in the range, either i == f or else *i == *(i-1). In the second, the test is an arbitrary Binary Predicate binary_pred: the elements in [f, l) are duplicates if, for every iterator i in the range, either i == f or else binary_pred(*i, *(i-1)) is true. [1]
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
For the first version:
• InputIterator is a model of Input Iterator.
• InputIterator's value type is Equality Comparable.
• OutputIterator is a model of Output Iterator.
• InputIterator's value type is convertible to a type in OutputIterator's set of value types.
For the second version:
• InputIterator is a model of Input Iterator.
• BinaryPredicate is a model of Binary Predicate. [2]
• InputIterator's value type is convertible to first argument type and to BinaryPredicate's second argument type.
• OutputIterator is a model of Output Iterator.
• InputIterator's value type is convertible to a type in OutputIterator's set of value types.
• [first, last) is a valid range.
• There is enough space to hold all of the elements being copied. More formally, if there are n elements in the range [first, last) after duplicates are removed from consecutive groups, then [result, result + n) must be a valid range.
Linear. Exactly last – first applications of operator== (in the case of the first version of unique ) or of binary_pred (in the case of the second version), and at most last – first assignments.
Print all of the numbers in an array, but only print the first one in a consecutive group of identical numbers.
const int A[] = {2, 7, 7, 7, 1, 1, 8, 8, 8, 2, 8, 8};
unique_copy(A, A + sizeof(A) / sizeof(int), ostream_iterator<int>(cout, " "));
// The output is "2 7 1 8 2 8".
[1] Strictly speaking, the first version of unique_copy is redundant: you can achieve the same functionality by using an object of class equal_to as the Binary Predicate argument. The first version is provided strictly for the sake of convenience: testing for equality is an important special case.
[2] BinaryPredicate is not required to be an equivalence relation. You should be cautious, though, about using unique_copy with a Binary Predicate that is not an equivalence relation: you could easily get unexpected results.
Binary Predicate, unique, remove_copy, remove_copy_if, adjacent_find
Category: algorithms
Component type: function
template <class BidirectionalIterator>
void reverse(BidirectionalIterator first, BidirectionalIterator last);
Reverse reverses a range. That is: for every i such that 0 <= i <= (last – first) / 2), it exchanges *(first + i) and *(last – (i + 1)).
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
• BidirectionalIterator is a model of Bidirectional Iterator.
• BidirectionalIterator is mutable.
• [first, last) is a valid range.
Linear: reverse(first, last) makes (last – first) / 2 calls to swap.
vector<int> V;
V.push_back(0);
V.push_back(1);
V.push_back(2);
copy(V.begin(), V.end(), ostream_iterator<int>(cout, " "));
// Output: 0 1 2
reverse(V.begin(), V.end());
copy(V.begin(), V.end(), ostream_iterator<int>(cout, " "));
// Output: 2 1 0
reverse_copy
Category: algorithms
Component type: function
template <class BidirectionalIterator, class OutputIterator>
OutputIterator reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result);
Reverse_copy copies elements from the range [first, last) to the range [result, result + (last – first)) such that the copy is a reverse of the original range. Specifically: for every i such that 0 <= i < (last – first), reverse_copy performs the assignment *(result + (last – first) – i) = *(first + i).
The return value is result + (last – first).
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
• BidirectionalIterator is a model of Bidirectional Iterator.
• OutputIterator is a model of Output Iterator.
• The value type of BidirectionalIterator is convertible to a type in OutputIterator's set of value types.
• [first, last) is a valid range.
• There is enough space to hold all of the elements being copied. More formally, the requirement is that [result, result + (last – first)) is a valid range.
• The ranges [first, last) and [result, result + (last – first)) do not overlap.
Linear: exactly last – first assignments.
vector<int> V;
V.push_back(0);
V.push_back(1);
V.push_back(2);
copy(V.begin(), V.end(), ostream_iterator<int>(cout, " "));
// Output: 0 1 2
list<int> L(V.size());
reverse_copy(V.begin(), V.end(), L.begin());
copy(L.begin(), L.end(), ostream_iterator<int>(cout, " "));
// Output: 2 1 0
reverse, copy
Category: algorithms
Component type: function
template <class ForwardIterator>
inline ForwardIterator rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);
Rotate rotates the elements in a range. That is, the element pointed to by middle is moved to the position first, the element pointed to by middle + 1 is moved to the position first + 1, and so on. One way to think about this operation is that it exchanges the two ranges [first, middle) and [middle, last). Formally, for every integer n such that 0 <= n < last – first, the element *(first + n) is assigned to *(first + (n + (last – middle)) % (last – first)). Rotate returns first + (last – middle).
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
• ForwardIterator is a model of Forward Iterator.
• ForwardIterator is mutable.
• [first, middle) is a valid range.
• [middle, last) is a valid range. [1]
Linear. At most last – first swaps are performed. [2]
char alpha[] = "abcdefghijklmnopqrstuvwxyz";
rotate(alpha, alpha + 13, alpha + 26);
printf("%s\n", alpha);
// The output is nopqrstuvwxyzabcdefghijklm
[1] It follows from these two requirements that [first, last) is a valid range.
[2] Rotate uses a different algorithm depending on whether its arguments are Forward Iterators, Bidirectional Iterators, or Random Access Iterators. All three algorithms, however, are linear.
rotate_copy
Category: algorithms
Component type: function
template <class ForwardIterator, class OutputIterator>
OutputIterator rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result);
Rotate_copy copies elements from the range [first, last) to the range [result, result + (last – first)) such that *middle is copied to *result, *(middle + 1) is copied to *(result + 1), and so on. Formally, for every integer n such that 0 <= n < last – first, rotate_copy performs the assignment *(result + (n + (last – middle)) % (last – first)) = *(first + n). Rotate_copy is similar to copy followed by rotate, but is more efficient. The return value is result + (last – first).
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
• ForwardIterator is a model of Forward Iterator.
• OutputIterator is a model of Output Iterator.
• ForwardIterator's value type is convertible to a type in OutputIterator's set of value types.
• [first, middle) is a valid range.
• [middle, last) is a valid range. [1]
• There is enough space to hold all of the elements being copied. More formally, the requirement is that [result, result + (last – first)) is a valid range.
• The ranges [first, last) and [result, result + (last – first)) do not overlap.
Linear. Rotate_copy performs exactly last – first assignments.
const char alpha[] = "abcdefghijklmnopqrstuvwxyz";
rotate_copy(alpha, alpha + 13, alpha + 26, ostream_iterator<char>(cout));
// The output is nopqrstuvwxyzabcdefghijklm
[1] It follows from these two requirements that [first, last) is a valid range.
rotate, copy.
Category: algorithms
Component type: function
Random_shuffle is an overloaded name; there are actually two random_shuffle functions.
template <class RandomAccessIterator>
void random_shuffle(RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class RandomNumberGenerator>
void random_shuffle(RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator& rand)
Random_shuffle randomly rearranges the elements in the range [first, last): that is, it randomly picks one of the N! possible orderings, where N is last – first. [1] There are two different versions of random_shuffle. The first version uses an internal random number generator, and the second uses a Random Number Generator, a special kind of function object , that is explicitly passed as an argument.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
For the first version:
• RandomAccessIterator is a model of Random Access Iterator
For the second version:
• RandomAccessIterator is a model of Random Access Iterator
• RandomNumberGenerator is a model of Random Number Generator
• RandomAccessIterator's distance type is convertible to RandomNumberGenerator's argument type.
• [first, last) is a valid range.
• last – first is less than rand 's maximum value.
Linear in last – first . If last != first, exactly (last – first) – 1 swaps are performed.
const int N = 8;
int A[] = {1, 2, 3, 4, 5, 6, 7, 8};
random_shuffle(A, A + N);
copy(A, A + N, ostream_iterator<int>(cout, " "));
// The printed result might be 7 1 6 3 2 5 4 8,
// or any of 40,319 other possibilities.
[1] This algorithm is described in section 3.4.2 of Knuth (D. E. Knuth, The Art of Computer Programming. Volume 2: Seminumerical Algorithms, second edition. Addison-Wesley, 1981). Knuth credits Moses and Oakford (1963) and Durstenfeld (1964). Note that there are N! ways of arranging a sequence of N elements. Random_shuffle yields uniformly distributed results; that is, the probability of any particular ordering is 1/N!. The reason this comment is important is that there are a number of algorithms that seem at first sight to implement random shuffling of a sequence, but that do not in fact produce a uniform distribution over the N! possible orderings. That is, it's easy to get random shuffle wrong.
random_sample, random_sample_n, next_permutation, prev_permutation, Random Number Generator
Category: algorithms
Component type: function
Random_sample is an overloaded name; there are actually two random_sample functions.
template <class InputIterator, class RandomAccessIterator>
Random AccessIterator random_sample(InputIterator first, InputIterator last, RandomAccessIterator ofirst, RandomAccessIterator olast)
template <class InputIterator, class RandomAccessIterator, class RandomNumberGenerator>
random_sample(InputIterator first, InputIterator last, RandomAccessIterator ofirst, RandomAccessIterator olast, RandomNumberGenerator& rand)
Random_sample randomly copies a sample of the elements from the range [first, last) into the range [ofirst, olast). Each element in the input range appears at most once in the output range, and samples are chosen with uniform probability. [1] Elements in the output range might appear in any order: relative order within the input range is not guaranteed to be preserved. [2]
Random_sample copies n elements from [first, last) to [ofirst, olast) , where n is min(last – first, olast – ofirst). The return value is ofirst + n.
The first version uses an internal random number generator, and the second uses a Random Number Generator, a special kind of function object, that is explicitly passed as an argument.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h. This function is an SGI extension; it is not part of the C++ standard.
For the first version:
• InputIterator is a model of Input Iterator
• RandomAccessIterator is a model of Random Access Iterator
• RandomAccessIterator is mutable.
• InputIterator's value type is convertible to RandomAccessIterator's value type.
For the second version:
• InputIterator is a model of Input Iterator
• RandomAccessIterator is a model of Random Access Iterator
• RandomAccessIterator is mutable.
• RandomNumberGenerator is a model of Random Number Generator
• InputIterator's value type is convertible to RandomAccessIterator's value type.
• RandomAccessIterator's distance type is convertible to RandomNumberGenerator's argument type.
• [first, last) is a valid range.
• [ofirst, olast) is a valid range.
• [first, last) and [ofirst, olast) do not overlap.
• last – first is less than rand 's maximum value.
Linear in last – first . At most last – first elements are copied from the input range to the output range.
int main() {
const int N = 10;
const int n = 4;
int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int B[n];
random_sample(A, A+N, B, B+n);
copy(B, B + n, ostream_iterator<int>(cout, " "));
// The printed value might be 1 6 3 5,
// or any of 5039 other possibilities.
}
[1] This is "Algorithm R" from section 3.4.2 of Knuth (D. E. Knuth, The Art of Computer Programming. Volume 2: Seminumerical Algorithms, second edition. Addison-Wesley, 1981). Knuth credits Alan Waterman. Note that there are N! / n! / (N – n)! ways of selecting a sample of n elements from a range of N elements. Random_sample yields uniformly distributed results; that is, the probability of selecting any particular element is n / N, and the probability of any particular sampling (not considering order of elements) is n! * (N – n)! / N!.
[2] If preservation of the relative ordering within the input range is important for your application, you should use random_sample_n instead. The main restriction of random_sample_n is that the input range must consist of Forward Iterators, rather than Input Iterators.
random_shuffle, random_sample_n, Random Number Generator
Category: algorithms
Component type: function
Random_sample_n is an overloaded name; there are actually two random_sample_n functions.
template <class ForwardIterator, class OutputIterator, class Distance>
OutputIterator random_sample_n(ForwardIterator first, ForwardIterator last, OutputIterator out, Distance n)
template <class ForwardIterator, class OutputIterator, class Distance, class RandomNumberGenerator>
OutputIterator random_sample_n(ForwardIterator first, ForwardIterator last, OutputIterator out, Distance n, RandomNumberGenerator& rand)
Random_sample_n randomly copies a sample of the elements from the range [first, last) into the range [out, out + n). Each element in the input range appears at most once in the output range, and samples are chosen with uniform probability. [1] Elements in the output range appear in the same relative order as their relative order within the input range. [2]
Random_sample copies m elements from [first, last) to [out, out + m) , where m is min(last – first, n) . The return value is out + m.
The first version uses an internal random number generator, and the second uses a Random Number Generator, a special kind of function object, that is explicitly passed as an argument.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h. This function is an SGI extension; it is not part of the C++ standard.
For the first version:
• ForwardIterator is a model of Forward Iterator
• OutputIterator is a model of Output Iterator
• ForwardIterator's value type is convertible to a type in OutputIterator's set of value types.
• Distance is an integral type that is large enough to represent the value last – first.
For the second version:
• ForwardIterator is a model of Forward Iterator
• OutputIterator is a model of Output Iterator
• RandomNumberGenerator is a model of Random Number Generator
• Distance is an integral type that is large enough to represent the value last – first.
• ForwardIterator's value type is convertible to a type in OutputIterator's set of value types.
• Distance is convertible to RandomNumberGenerator's argument type.
• [first, last) is a valid range.
• n is nonnegative.
• [first, last) and [out, out + n) do not overlap.
• There is enough space to hold all of the elements being copied. More formally, the requirement is that [out, out + min(n, last – first)) is a valid range.
• last – first is less than rand 's maximum value.
Linear in last – first . At most last – first elements from the input range are examined, and exactly min(n, last – first) elements are copied to the output range.
int main() {
const int N = 10;
int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
random_sample_n(A, A+N, ostream_iterator<int>(cout, " "), 4);
// The printed value might be 3 5 6 10,
// or any of 209 other possibilities.
}
[1] This is "Algorithm S" from section 3.4.2 of Knuth (D. E. Knuth, The Art of Computer Programming. Volume 2: Seminumerical Algorithms , second edition. Addison-Wesley, 1981). Knuth credits C. T. Fan, M. E. Muller, and I. Rezucha (1962) and T. G. Jones (1962). Note that there are N! / n! / (N – n)! ways of selecting a sample of n elements from a range of N elements. Random_sample_n yields uniformly distributed results; that is, the probability of selecting any particular element is n / N, and the probability of any particular sampling is n! * (N – n)! / N!.
[2] In contrast, the random_sample algorithm does not preserve relative ordering within the input range. The other major distinction between the two algorithms is that random_sample_n requires its input range to be Forward Iterators and only requires its output range to be Output Iterators, while random_sample only requires its input range to be Input Iterators and requires its output range to be Random Access Iterators.
random_shuffle, random_sample, Random Number Generator
Category: algorithms
Component type: function
template <class ForwardIterator, class Predicate>
ForwardIterator partition(ForwardIterator first, ForwardIterator last, Predicate pred)
Partition reorders the elements in the range [first, last) based on the function object pred, such that the elements that satisfy pred precede the elements that fail to satisfy it. The postcondition is that, for some iterator middle in the range [first, last), pred(*i) is true for every iterator i in the range [first, middle) and false for every iterator i in the range [middle, last). [1] The return value of partition is middle.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
• ForwardIterator is a model of Forward Iterator.
• Predicate is a model of Predicate.
• ForwardIterator's value type is convertible to Predicate's argument type.
• [first, last) is a valid range.
Linear. Exactly last – first applications of pred , and at most (last – first)/2 swaps.
Reorder a sequence so that even numbers precede odd numbers.
int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
const int N = sizeof(A)/sizeof(int);
partition(A, A + N, compose1(bind2nd(equal_to<int>(), 0), bind2nd(modulus<int>(), 2)));
copy(A, A + N, ostream_iterator<int>(cout, " "));
// The output is "10 2 8 4 6 5 7 3 9 1". [1]
[1] The relative order of elements in these two blocks is not necessarily the same as it was in the original sequence. A different algorithm, stable_partition, does guarantee to preserve the relative order.
stable_partition, Predicate, function object
Category: algorithms
Component type: function
template <class ForwardIterator, class Predicate>
ForwardIterator stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred);
Stable_partition is much like partition: it reorders the elements in the range [first, last) based on the function object pred, such that all of the elements that satisfy pred appear before all of the elements that fail to satisfy it. The postcondition is that, for some iterator middle in the range [first, last), pred(*i) is true for every iterator i in the range [first, middle) and false for every iterator i in the range [middle, last). The return value of stable_partition is middle.
Stable_partition differs from partition in that stable_partition is guaranteed to preserve relative order. That is, if x and y are elements in [first, last) such that pred(x) == pred(y), and if x precedes y, then it will still be true after stable_partition is true that x precedes y. [1]
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
• ForwardIterator is a model of Forward Iterator
• Predicate is a model of Predicate
• ForwardIterator's value type is convertible to Predicate's argument type.
• [first, last) is a valid range.
Stable_partition is an adaptive algorithm: it attempts to allocate a temporary memory buffer, and its run-time complexity depends on how much memory is available. Worst-case behavior (if no auxiliary memory is available) is at most N*log(N) swaps, where N is last – first, and best case (if a large enough auxiliary memory buffer is available) is linear in N. In either case, pred is applied exactly N times.
Reorder a sequence so that even numbers precede odd numbers.
int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
const int N = sizeof(A)/sizeof(int);
stable_partition(A, A + N, compose1(bind2nd(equal_to<int>(), 0), bind2nd(modulus<int>(), 2)));
copy(A, A + N, ostream_iterator<int>(cout, " "));
// The output is "2 4 6 8 10 1 3 5 7 9". [1]
[1] Note that the complexity of stable_partition is greater than that of partition: the guarantee that relative order will be preserved has a significant runtime cost. If this guarantee isn't important to you, you should use partition.
partition, Predicate, function object
Category: algorithms
Component type: function
Sort is an overloaded name; there are actually two sort functions.
template <class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class StrictWeakOrdering>
void sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp);
Sort sorts the elements in [first, last) into ascending order, meaning that if i and j are any two valid iterators in [first, last) such that i precedes j, then *j is not less than *i. Note: sort is not guaranteed to be stable. That is, suppose that *i and *j are equivalent: neither one is less than the other. It is not guaranteed that the relative order of these two elements will be preserved by sort. [1]
The two versions of sort differ in how they define whether one element is less than another. The first version compares objects using operator< , and the second compares objects using a function object comp.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
For the first version, the one that takes two arguments:
• RandomAccessIterator is a model of Random Access Iterator.
• RandomAccessIterator is mutable.
• RandomAccessIterator's value type is LessThan Comparable.
• The ordering relation on RandomAccessIterator's value type is a strict weak ordering, as defined in the LessThan Comparable requirements.
For the second version, the one that takes three arguments:
• RandomAccessIterator is a model of Random Access Iterator.
• RandomAccessIterator is mutable.
• StrictWeakOrdering is a model of Strict Weak Ordering.
• RandomAccessIterator's value type is convertible to StrictWeakOrdering's argument type.
• [first, last) is a valid range.
O(N log(N)) comparisons (both average and worst-case), where N is last – first. [2]
int A[] = {1, 4, 2, 8, 5, 7};
const int N = sizeof(A) / sizeof(int);
sort(A, A + N);
copy(A, A + N, ostream_iterator<int>(cout, " "));
// The output is " 1 2 4 5 7 8".
[1] Stable sorting is sometimes important if you are sorting records that have multiple fields: you might, for example, want to sort a list of people by first name and then by last name. The algorithm stable_sort does guarantee to preserve the relative ordering of equivalent elements.
[2] Earlier versions of sort used the quicksort algorithm (C. A. R. Hoare, Comp. J. 5, 1962), using a pivot chosen by median of three (R. C. Singleton, CACM 12, 1969). quicksort has O(N log(N)) average complexity, but quadratic worst-case complexity. See section 5.2.2 of Knuth for a discussion. (D. E. Knuth, The Art of Computer Programming. Volume 3: Sorting and Searching. Addison-Wesley, 1975.) The current implementation of sort, however, uses the introsort algorithm (D. R. Musser, "Introspective Sorting and Selection Algorithms", Software Practice and Experience 27(8):983, 1997.) whose worst case complexity is O(N log(N)). Introsort is very similar to median-of-three quicksort, and is at least as fast as quicksort on average.
stable_sort, partial_sort, partial_sort_copy, sort_heap, is_sorted, binary_search, lower_bound, upper_bound, less<T>, StrictWeakOrdering, LessThan Comparable
Category: algorithms
Component type: function
Stable_sort is an overloaded name; there are actually two stable_sort functions.
template <class RandomAccessIterator>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class StrictWeakOrdering>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp);
Stable_sort is much like sort: it sorts the elements in [first, last) into ascending order, meaning that if i and j are any two valid iterators in [first, last) such that i precedes j, then *j is not less than *i. Stable_sort differs from sort in two ways. First, stable_sort uses an algorithm that has different run-time complexity than sort. Second, as the name suggests, stable_sort is stable: it preserves the relative ordering of equivalent elements. That is, if x and y are elements in [first, last) such that x precedes y, and if the two elements are equivalent (neither x < y nor y < x) then a postcondition of stable_sort is that x still precedes y. [1]
The two versions of stable_sort differ in how they define whether one element is less than another. The first version compares objects using operator< , and the second compares objects using a function object comp.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
For the first version, the one that takes two arguments:
• RandomAccessIterator is a model of Random Access Iterator.
• RandomAccessIterator is mutable.
• RandomAccessIterator's value type is LessThan Comparable.
• The ordering relation on RandomAccessIterator's value type is a strict weak ordering, as defined in the LessThan Comparable requirements.
For the second version, the one that takes three arguments:
• RandomAccessIterator is a model of Random Access Iterator.
• RandomAccessIterator is mutable.
• StrictWeakOrdering is a model of Strict Weak Ordering.
• RandomAccessIterator's value type is convertible to StrictWeakOrdering's argument type.
• [first, last) is a valid range.
Stable_sort is an adaptive algorithm: it attempts to allocate a temporary memory buffer, and its run-time complexity depends on how much memory is available. Worst-case behavior (if no auxiliary memory is available) is N (log N)^2 comparisons, where N is last – first, and best case (if a large enough auxiliary memory buffer is available) is N (log N). [2]
Sort a sequence of characters, ignoring their case. Note that the relative order of characters that differ only by case is preserved.
inline bool lt_nocase(char c1, char c2) { return tolower(c1) < tolower(c2); }
int main() {
char A[] = "fdBeACFDbEac";
const int N = sizeof(A) – 1;
stable_sort(A, A+N, lt_nocase);
printf("%s\n", A);
// The printed result is ""AaBbCcdDeEfF".
}
[1] Note that two elements may be equivalent without being equal. One standard example is sorting a sequence of names by last name: if two people have the same last name but different first names, then they are equivalent but not equal. This is why stable_sort is sometimes useful: if you are sorting a sequence of records that have several different fields, then you may want to sort it by one field without completely destroying the ordering that you previously obtained from sorting it by a different field. You might, for example, sort by first name and then do a stable sort by last name.
[2] Stable_sort uses the merge sort algorithm; see section 5.2.4 of Knuth. (D. E. Knuth, The Art of Computer Programming. Volume 3: Sorting and Searching. Addison-Wesley, 1975.)
sort, partial_sort, partial_sort_copy, binary_search, lower_bound, upper_bound, less<T>, StrictWeakOrdering, LessThan Comparable
Category: algorithms
Component type: function
Partial_sort is an overloaded name; there are actually two partial_sort functions.
template <class RandomAccessIterator>
void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);
template <class RandomAccessIterator, class StrictWeakOrdering>
void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, StrictWeakOrdering comp);
Partial_sort rearranges the elements in the range [first, last) so that they are partially in ascending order. Specifically, it places the smallest middle – first elements, sorted in ascending order, into the range [first, middle). The remaining last – middle elements are placed, in an unspecified order, into the range [middle, last). [1] [2]
The two versions of partial_sort differ in how they define whether one element is less than another. The first version compares objects using operator<, and the second compares objects using a function object comp.
The postcondition for the first version of partial_sort is as follows. If i and j are any two valid iterators in the range [first, middle) such that i precedes j, and if k is a valid iterator in the range [middle, last), then *j < *i and *k < *i will both be false. The corresponding postcondition for the second version of partial_sort is that comp(*j, *i) and comp(*k, *i) are both false. Informally, this postcondition means that the first middle – first elements are in ascending order and that none of the elements in [middle, last) is less than any of the elements in [first, middle).
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
For the first version:
• RandomAccessIterator is a model of Random Access Iterator.
• RandomAccessIterator is mutable.
• RandomAccessIterator's value type is LessThan Comparable.
• The ordering relation on RandomAccessIterator's value type is a strict weak ordering, as defined in the LessThan Comparable requirements.
For the second version:
• RandomAccessIterator is a model of Random Access Iterator.
• RandomAccessIterator is mutable.
• StrictWeakOrdering is a model of Strict Weak Ordering.
• RandomAccessIterator's value type is convertible to StrictWeakOrdering's argument type.
• [first, middle) is a valid range.
• [middle, last) is a valid range. (It follows from these two conditions that [first, last) is a valid range.)
Approximately (last – first) * log(middle – first) comparisons.
int A[] = {7, 2, 6, 11, 9, 3, 12, 10, 8, 4, 1, 5};
const int N = sizeof(A) / sizeof(int);
partial_sort(A, A + 5, A + N);
copy(A, A + N, ostream_iterator<int>(cout, " "));
// The printed result is "1 2 3 4 5 11 12 10 9 8 7 6".
[1] Note that the elements in the range [first, middle) will be the same (ignoring, for the moment, equivalent elements) as if you had sorted the entire range using sort(first, last). The reason for using partial_sort in preference to sort is simply efficiency: a partial sort, in general, takes less time.
[2] partial_sort(first, last, last) has the effect of sorting the entire range [first, last), just like sort(first, last). They use different algorithms, however: sort uses the introsort algorithm (a variant of quicksort), and partial_sort uses heapsort. See section 5.2.3 of Knuth (D. E. Knuth, The Art of Computer Programming. Volume 3: Sorting and Searching. Addison-Wesley, 1975.), and J. W. J. Williams (CACM 7, 347, 1964). Both heapsort and introsort have complexity of order N log(N), but introsort is usually faster by a factor of 2 to 5.
partial_sort_copy, sort, stable_sort, binary_search, lower_bound, upper_bound, less<T>, StrictWeakOrdering, LessThan Comparable
Category: algorithms
Component type: function
Partial_sort_copy is an overloaded name; there are actually two partial_sort_copy functions.
template <class InputIterator, class RandomAccessIterator>
RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last);
template <class InputIterator, class RandomAccessIterator, class StrictWeakOrdering>
RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp);
Partial_sort_copy copies the smallest N elements from the range [first, last) to the range [result_first, result_first + N), where N is the smaller of last – first and result_last – result_first. The elements in [result_first, result_first + N) will be in ascending order.
The two versions of partial_sort_copy differ in how they define whether one element is less than another. The first version compares objects using operator<, and the second compares objects using a function object comp.
The postcondition for the first version of partial_sort_copy is as follows. If i and j are any two valid iterators in the range [result_first, result_first + N) such that i precedes j, then *j < *i will be false. The corresponding postcondition for the second version is that comp(*j, *i) will be false.
The return value is result_first + N.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
For the first version:
• InputIterator is a model of InputIterator.
• RandomAccessIterator is a model of Random Access Iterator.
• RandomAccessIterator is mutable.
• The value types of InputIterator and RandomAccessIterator are the same.
• RandomAccessIterator's value type is LessThan Comparable.
• The ordering relation on RandomAccessIterator's value type is a strict weak ordering, as defined in the LessThan Comparable requirements.
For the second version:
• InputIterator is a model of InputIterator.
• RandomAccessIterator is a model of Random Access Iterator.
• RandomAccessIterator is mutable.
• The value types of InputIterator and RandomAccessIterator are the same.
• StrictWeakOrdering is a model of Strict Weak Ordering.
• RandomAccessIterator's value type is convertible to StrictWeakOrdering's argument type.
• [first, last) is a valid range.
• [result_first, result_last) is a valid range.
• [first, last) and [result_first, result_last) do not overlap.
Approximately (last – first) * log(N) comparisons, where N is the smaller of last – first and result_last – result_first.
int A[] = {7, 2, 6, 11, 9, 3, 12, 10, 8, 4, 1, 5};
const int N = sizeof(A) / sizeof(int);
vector<int>V(4);
partial_sort_copy(A, A + N, V.begin(), V.end());
copy(V.begin(), V.end(), ostream_iterator<int>(cout, " "));
// The printed result is "1 2 3 4".
partial_sort, sort, stable_sort, binary_search, lower_bound, upper_bound, less<T>, StrictWeakOrdering, LessThan Comparable
Category: algorithms
Component type: function
Is_sorted is an overloaded name; there are actually two is_sorted functions.
template <class ForwardIterator>
bool is_sorted(ForwardIterator first, ForwardIterator last)
template <class ForwardIterator, class StrictWeakOrdering>
bool is_sorted(ForwardIterator first, ForwardIterator last, StrictWeakOrdering comp)
Is_sorted returns true if the range [first, last) is sorted in ascending order, and false otherwise.
The two versions of is_sorted differ in how they define whether one element is less than another. The first version compares objects using operator< , and the second compares objects using the function object comp. The first version of is_sorted returns true if and only if, for every iterator i in the range [first, last – 1), *(i + 1) < *i is false. The second version returns true if and only if, for every iterator i in the range [first, last – 1), comp(*(i + 1), *i) is false.
Defined in algo.h.
For the first version:
• ForwardIterator is a model of Forward Iterator.
• ForwardIterator's value type is a model of LessThan Comparable.
• The ordering on objects of ForwardIterator's value type is a strict weak ordering, as defined in the LessThan Comparable requirements.
For the second version:
• ForwardIterator is a model of Forward Iterator.
• StrictWeakOrdering is a model of Strict Weak Ordering.
• ForwardIterator's value type is convertible to StrictWeakOrdering's argument type.
• [first, last) is a valid range.
Linear. Zero comparisons if [first, last) is an empty range, otherwise at most (last – first) – 1 comparisons.
int A[] = {1, 4, 2, 8, 5, 7};
const int N = sizeof(A) / sizeof(int);
assert(!is_sorted(A, A + N));
sort(A, A + N);
assert(is_sorted(A, A + N));
sort, stable_sort, partial_sort, partial_sort_copy, sort_heap, binary_search, lower_bound, upper_bound, less<T>, StrictWeakOrdering, LessThan Comparable
Category: algorithms
Component type: function
Nth_element is an overloaded name; there are actually two nth_element functions.
template <class RandomAccessIterator>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);
template <class RandomAccessIterator, class StrictWeakOrdering>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, StrictWeakOrdering comp);
Nth_element is similar to partial_sort, in that it partially orders a range of elements: it arranges the range [first, last) such that the element pointed to by the iterator nth is the same as the element that would be in that position if the entire range [first, last) had been sorted. Additionally, none of the elements in the range [nth, last) is less than any of the elements in the range [first, nth). [1]
The two versions of nth_element differ in how they define whether one element is less than another. The first version compares objects using operator<, and the second compares objects using a function object comp.
The postcondition for the first version of nth_element is as follows. There exists no iterator i in the range [first, nth) such that *nth < *i, and there exists no iterator j in the range [nth + 1, last) such that *j < *nth.
The postcondition for the second version of nth_element is as follows. There exists no iterator i in the range [first, nth) such that comp(*nth, *i) is true, and there exists no iterator j in the range [nth + 1, last) such that comp(*j, *nth) is true.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
For the first version, the one that takes three arguments:
• RandomAccessIterator is a model of Random Access Iterator.
• RandomAccessIterator is mutable.
• RandomAccessIterator's value type is LessThan Comparable.
• The ordering relation on RandomAccessIterator's value type is a strict weak ordering, as defined in the LessThan Comparable requirements.
For the second version, the one that takes four arguments:
• RandomAccessIterator is a model of Random Access Iterator.
• RandomAccessIterator is mutable.
• StrictWeakOrdering is a model of Strict Weak Ordering.
• RandomAccessIterator's value type is convertible to StrictWeakOrdering's argument type.
• [first, nth) is a valid range.
• [nth, last) is a valid range. (It follows from these two conditions that [first, last) is a valid range.)
On average, linear in last – first. [2]
int A[] = {7, 2, 6, 11, 9, 3, 12, 10, 8, 4, 1, 5};
const int N = sizeof(A) / sizeof(int);
nth_element(A, A + 6, A + N);
copy(A, A + N, ostream_iterator<int>(cout, " "));
// The printed result is "5 2 6 1 4 3 7 8 9 10 11 12".
[1] The way in which this differs from partial_sort is that neither the range [first, nth) nor the range [nth, last) is be sorted: it is simply guaranteed that none of the elements in [nth, last) is less than any of the elements in [first, nth). In that sense, nth_element is more similar to partition than to sort. Nth_element does less work than partial_sort, so, reasonably enough, it is faster. That's the main reason to use nth_element instead of partial_sort.
[2] Note that this is significantly less than the run-time complexity of partial_sort.
partial_sort, partition, sort, StrictWeakOrdering, LessThan Comparable
Category: algorithms
Component type: function
Lower_bound is an overloaded name; there are actually two lower_bound functions.
template <class ForwardIterator, class LessThanComparable>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const LessThanComparable& value);
template <class ForwardIterator, class T, class StrictWeakOrdering>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering comp);
Lower_bound is a version of binary search: it attempts to find the element value in an ordered range [first, last) [1]. Specifically, it returns the first position where value could be inserted without violating the ordering. [2] The first version of lower_bound uses operator< for comparison, and the second uses the function object comp.
The first version of lower_bound returns the furthermost iterator i in [first, last) such that, for every iterator j in [first, i), *j < value.
The second version of lower_bound returns the furthermost iterator i in [first, last) such that, for every iterator j in [first, i), comp(*j, value) is true.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
For the first version:
• ForwardIterator is a model of Forward Iterator.
• LessThanComparable is a model of LessThan Comparable.
• The ordering on objects of type LessThanComparable is a strict weak ordering, as defined in the LessThan Comparable requirements.
• ForwardIterator's value type is the same type as LessThanComparable.
For the second version:
• ForwardIterator is a model of Forward Iterator.
• StrictWeakOrdering is a model of Strict Weak Ordering.
• ForwardIterator's value type is the same type as T.
• ForwardIterator's value type is convertible to StrictWeakOrdering's argument type.
For the first version:
• [first, last) is a valid range.
• [first, last) is ordered in ascending order according to operator<. That is, for every pair of iterators i and j in [first, last) such that i precedes j, *j < *i is false.
For the second version:
• [first, last) is a valid range.
• [first, last) is ordered in ascending order according to the function object comp. That is, for every pair of iterators i and j in [first, last) such that i precedes j, comp(*j, *i) is false.
The number of comparisons is logarithmic: at most log(last – first) + 1. If ForwardIterator is a Random Access Iterator then the number of steps through the range is also logarithmic; otherwise, the number of steps is proportional to last – first. [3]
int main() {
int A[] = { 1, 2, 3, 3, 3, 5, 8 };
const int N = sizeof(A) / sizeof(int);
for (int i = 1; i <= 10; ++i) {
int* p = lower_bound(A, A + N, i);
cout << "Searching for " << i << ". ";
cout << "Result: index = " << p – A << ", ";
if (p != A + N) cout << "A[" << p – A << "] == " << *p << endl;
else cout << "which is off-the-end." << endl;
}
}
The output is:
Searching for 1. Result: index = 0, A[0] == 1
Searching for 2. Result: index = 1, A[1] == 2
Searching for 3. Result: index = 2, A[2] == 3
Searching for 4. Result: index = 5, A[5] == 5
Searching for 5. Result: index = 5, A[5] == 5
Searching for 6. Result: index = 6, A[6] == 8
Searching for 7. Result: index = 6, A[6] == 8
Searching for 8. Result: index = 6, A[6] == 8
Searching for 9. Result: index = 7, which is off-the-end.
Searching for 10. Result: index = 7, which is off-the-end.
[1] Note that you may use an ordering that is a strict weak ordering but not a total ordering; that is, there might be values x and y such that x < y, x > y, and x == y are all false. (See the LessThan Comparable requirements for a more complete discussion.) Finding value in the range [first, last) , then, doesn't mean finding an element that is equal to value but rather one that is equivalent to value: one that is neither greater than nor less than value . If you're using a total ordering, however (if you're using strcmp, for example, or if you're using ordinary arithmetic comparison on integers), then you can ignore this technical distinction: for a total ordering, equality and equivalence are the same.
[2] If an element that is equivalent to [1] value is already present in the range [first, last), then the return value of lower_bound will be an iterator that points to that element.
[3] This difference between Random Access Iterators and Forward Iterators is simply because advance is constant time for Random Access Iterators and linear time for Forward Iterators.
upper_bound, equal_range, binary_search
Category: algorithms
Component type: function
Upper_bound is an overloaded name; there are actually two upper_bound functions.
template <class ForwardIterator, class LessThanComparable>
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const LessThanComparable& value);
template <class ForwardIterator, class T, class StrictWeakOrdering>
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering comp);
Upper_bound is a version of binary search: it attempts to find the element value in an ordered range [first, last) [1]. Specifically, it returns the last position where value could be inserted without violating the ordering. [2] The first version of upper_bound uses operator< for comparison, and the second uses the function object comp.
The first version of upper_bound returns the furthermost iterator i in [first, last) such that, for every iterator j in [first, i), value < *j is false.
The second version of upper_bound returns the furthermost iterator i in [first, last) such that, for every iterator j in [first, i), comp(value, *j) is false.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
For the first version:
• ForwardIterator is a model of Forward Iterator.
• LessThanComparable is a model of LessThan Comparable.
• The ordering on objects of type LessThanComparable is a strict weak ordering, as defined in the LessThan Comparable requirements.
• ForwardIterator's value type is the same type as LessThanComparable.
For the second version:
• ForwardIterator is a model of Forward Iterator.
• StrictWeakOrdering is a model of Strict Weak Ordering.
• ForwardIterator's value type is the same type as T.
• ForwardIterator's value type is convertible to StrictWeakOrdering's argument type.
For the first version:
• [first, last) is a valid range.
• [first, last) is ordered in ascending order according to operator<. That is, for every pair of iterators i and j in [first, last) such that i precedes j, *j < *i is false.
For the second version:
• [first, last) is a valid range.
• [first, last) is ordered in ascending order according to the function object comp. That is, for every pair of iterators i and j in [first, last) such that i precedes j, comp(*j, *i) is false.
The number of comparisons is logarithmic: at most log(last – first) + 1. If ForwardIterator is a Random Access Iterator then the number of steps through the range is also logarithmic; otherwise, the number of steps is proportional to last – first. [3]
int main() {
int A[] = { 1, 2, 3, 3, 3, 5, 8 };
const int N = sizeof(A) / sizeof(int);
for (int i = 1; i <= 10; ++i) {
int* p = upper_bound(A, A + N, i);
cout << "Searching for " << i << ". ";
cout << "Result: index = " << p – A << ", ";
if (p != A + N) cout << "A[" << p – A << "] == " << *p << endl;
else cout << "which is off-the-end." << endl;
}
}
The output is:
Searching for 1. Result: index = 1, A[1] == 2
Searching for 2. Result: index = 2, A[2] == 3
Searching for 3. Result: index = 5, A[5] == 5
Searching for 4. Result: index = 5, A[5] == 5
Searching for 5. Result: index = 6, A[6] == 8
Searching for 6. Result: index = 6, A[6] == 8
Searching for 7. Result: index = 6, A[6] == 8
Searching for 8. Result: index = 7, which is off-the-end.
Searching for 9. Result: index = 7, which is off-the-end.
Searching for 10. Result: index = 7, which is off-the-end.
[1] Note that you may use an ordering that is a strict weak ordering but not a total ordering; that is, there might be values x and y such that x < y, x > y, and x == y are all false. (See the LessThan Comparable requirements for a more complete discussion.) Finding value in the range [first, last) , then, doesn't mean finding an element that is equal to value but rather one that is equivalent to value: one that is neither greater than nor less than value. If you're using a total ordering, however (if you're using strcmp, for example, or if you're using ordinary arithmetic comparison on integers), then you can ignore this technical distinction: for a total ordering, equality and equivalence are the same.
[2] Note that even if an element that is equivalent to [1] value is already present in the range [first, last), the return value of upper_bound will not point to that element. The return value is either last or else an iterator i such that value < *i. If i is not equal to first, however, then *(i – 1) is less than or equivalent to value.
[3] This difference between Random Access Iterators and Forward Iterators is simply because advance is constant time for Random Access Iterators and linear time for Forward Iterators.
lower_bound, equal_range, binary_search
Category: algorithms
Component type: function
Equal_range is an overloaded name; there are actually two equal_range functions.
template <class ForwardIterator, class LessThanComparable>
pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, const LessThanComparable& value);
template <class ForwardIterator, class T, class StrictWeakOrdering>
pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering comp);
Equal_range is a version of binary search: it attempts to find the element value in an ordered range [first, last) [1]. The value returned by equal_range is essentially a combination of the values returned by lower_bound and upper_bound: it returns a pair of iterators i and j such that i is the first position where value could be inserted without violating the ordering and j is the last position where value could be inserted without violating the ordering. It follows that every element in the range [i, j) is equivalent to [1] value, and that [i, j) is the largest subrange of [first, last) that has this property. The first version of equal_range uses operator< for comparison, and the second uses the function object comp.
The first version of equal_range returns a pair of iterators [i, j). i is the furthermost iterator in [first, last) such that, for every iterator k in [first, i), *k < value. j is the furthermost iterator in [first, last) such that, for every iterator k in [first, j), value < *k is false. For every iterator k in [i, j), neither value < *k nor *k < value is true. [2]
The second version of equal_range returns a pair of iterators [i, j). i is the furthermost iterator in [first, last) such that, for every iterator k in [first, i), comp(*k, value) is true. j is the furthermost iterator in [first, last) such that, for every iterator k in [first, j), comp(value, *k) is false. For every iterator k in [i, j), neither comp(value, *k) nor comp(*k, value) is true. [2]
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
For the first version:
• ForwardIterator is a model of Forward Iterator.
• LessThanComparable is a model of LessThan Comparable.
• The ordering on objects of type LessThanComparable is a strict weak ordering, as defined in the LessThan Comparable requirements.
• ForwardIterator's value type is the same type as LessThanComparable.
For the second version:
• ForwardIterator is a model of Forward Iterator.
• StrictWeakOrdering is a model of Strict Weak Ordering.
• ForwardIterator's value type is the same type as T.
• ForwardIterator's value type is convertible to StrictWeakOrdering's argument type.
For the first version:
• [first, last) is a valid range.
• [first, last) is ordered in ascending order according to operator<. That is, for every pair of iterators i and j in [first, last) such that i precedes j, *j < *i is false.
For the second version:
• [first, last) is a valid range.
• [first, last) is ordered in ascending order according to the function object comp. That is, for every pair of iterators i and j in [first, last) such that i precedes j, comp(*j, *i) is false.
The number of comparisons is logarithmic: at most 2 * log(last – first) + 1. If ForwardIterator is a Random Access Iterator then the number of steps through the range is also logarithmic; otherwise, the number of steps is proportional to last – first. [3]
int main() {
int A[] = { 1, 2, 3, 3, 3, 5, 8 };
const int N = sizeof(A) / sizeof(int);
for (int i = 2; i <= 4; ++i) {
pair<int*, int*> result = equal_range(A, A + N, i);
cout << endl;
cout << "Searching for " << i << endl;
cout << " First position where " << i << " could be inserted: " << result.first – A << endl;
cout << " Last position where " << i << " could be inserted: " << result.second – A << endl;
if (result.first < A + N) cout << " *result.first = " << *result.first << endl;
if (result.second < A + N) cout << " *result.second = " << *result.second << endl;
}
}
The output is:
Searching for 2
First position where 2 could be inserted: 1
Last position where 2 could be inserted: 2
*result.first = 2
*result.second = 3
Searching for 3
First position where 3 could be inserted: 2
Last position where 3 could be inserted: 5
*result.first = 3
*result.second = 5
Searching for 4
First position where 4 could be inserted: 5
Last position where 4 could be inserted: 5
*result.first = 5
*result.second = 5
[1] Note that you may use an ordering that is a strict weak ordering but not a total ordering; that is, there might be values x and y such that x < y, x > y, and x == y are all false. (See the LessThan Comparable requirements for a more complete discussion.) Finding value in the range [first, last), then, doesn't mean finding an element that is equal to value but rather one that is equivalent to value: one that is neither greater than nor less than value. If you're using a total ordering, however (if you're using strcmp, for example, or if you're using ordinary arithmetic comparison on integers), then you can ignore this technical distinction: for a total ordering, equality and equivalence are the same.
[2] Note that equal_range may return an empty range; that is, it may return a pair both of whose elements are the same iterator. Equal_range returns an empty range if and only if the range [first, last) contains no elements equivalent to value. In this case it follows that there is only one position where value could be inserted without violating the range's ordering, so the return value is a pair both of whose elements are iterators that point to that position.
[3] This difference between Random Access Iterators and Forward Iterators is simply because advance is constant time for Random Access Iterators and linear time for Forward Iterators.
lower_bound, upper_bound, binary_search
Category: algorithms
Component type: function
Binary_search is an overloaded name; there are actually two binary_search functions.
template <class ForwardIterator, class LessThanComparable>
bool binary_search(ForwardIterator first, ForwardIterator last, const LessThanComparable& value);
template <class ForwardIterator, class T, class StrictWeakOrdering>
bool binary_search(ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering comp);
Binary_search is a version of binary search: it attempts to find the element value in an ordered range [first, last) It returns true if an element that is equivalent to [1] value is present in [first, last) and false if no such element exists. [2] The first version of binary_search uses operator< for comparison, and the second uses the function object comp.
Specifically, the first version returns true if and only if there exists an iterator i in [first, last) such that *i < value and value < *i are both false. The second version returns true if and only if there exists an iterator i in [first, last) such that comp(*i, value) and comp(value, *i) are both false.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
For the first version:
• ForwardIterator is a model of Forward Iterator.
• LessThanComparable is a model of LessThan Comparable.
• The ordering on objects of type LessThanComparable is a strict weak ordering, as defined in the LessThan Comparable requirements.
• ForwardIterator's value type is the same type as LessThanComparable.
For the second version:
• ForwardIterator is a model of Forward Iterator.
• StrictWeakOrdering is a model of Strict Weak Ordering.
• ForwardIterator's value type is the same type as T.
• ForwardIterator's value type is convertible to StrictWeakOrdering's argument type.
For the first version:
• [first, last) is a valid range.
• [first, last) is ordered in ascending order according to operator<. That is, for every pair of iterators i and j in [first, last) such that i precedes j, *j < *i is false.
For the second version:
• [first, last) is a valid range.
• [first, last) is ordered in ascending order according to the function object comp. That is, for every pair of iterators i and j in [first, last) such that i precedes j, comp(*j, *i) is false.
The number of comparisons is logarithmic: at most log(last – first) + 2 . If ForwardIterator is a Random Access Iterator then the number of steps through the range is also logarithmic; otherwise, the number of steps is proportional to last – first. [3]
int main() {
int A[] = { 1, 2, 3, 3, 3, 5, 8 };
const int N = sizeof(A) / sizeof(int);
for (int i = 1; i <= 10; ++i) {
cout << "Searching for " << i << ": " << (binary_search(A, A + N, i) ? "present" : "not present") << endl;
}
}
The output is:
Searching for 1: present
Searching for 2: present
Searching for 3: present
Searching for 4: not present
Searching for 5: present
Searching for 6: not present
Searching for 7: not present
Searching for 8: present
Searching for 9: not present
Searching for 10: not present
[1] Note that you may use an ordering that is a strict weak ordering but not a total ordering; that is, there might be values x and y such that x < y, x > y, and x == y are all false. (See the LessThan Comparable requirements for a more complete discussion.) Finding value in the range [first, last), then, doesn't mean finding an element that is equal to value but rather one that is equivalent to value: one that is neither greater than nor less than value. If you're using a total ordering, however (if you're using strcmp, for example, or if you're using ordinary arithmetic comparison on integers), then you can ignore this technical distinction: for a total ordering, equality and equivalence are the same.
[2] Note that this is not necessarily the information you are interested in! Usually, if you're testing whether an element is present in a range, you'd like to know where it is (if it's present), or where it should be inserted (if it's not present). The functions lower_bound, upper_bound, and equal_range provide this information.
[3] This difference between Random Access Iterators and Forward Iterators is simply because advance is constant time for Random Access Iterators and linear time for Forward Iterators.
lower_bound, upper_bound, equal_range
Category: algorithms
Component type: function
Merge is an overloaded name: there are actually two merge functions.
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
template <class InputIterator1, class InputIterator2, class OutputIterator, class StrictWeakOrdering>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering comp);
Merge combines two sorted ranges [first1, last1) and [first2, last2) into a single sorted range. That is, it copies elements from [first1, last1) and [first2, last2) into [result, result + (last1 – first1) + (last2 – first2)) such that the resulting range is in ascending order. Merge is stable, meaning both that the relative order of elements within each input range is preserved, and that for equivalent [1] elements in both input ranges the element from the first range precedes the element from the second. The return value is result + (last1 – first1) + (last2 – first2).
The two versions of merge differ in how elements are compared. The first version uses operator<. That is, the input ranges and the output range satisfy the condition that for every pair of iterators i and j such that i precedes j, *j < *i is false. The second version uses the function object comp. That is, the input ranges and the output range satisfy the condition that for every pair of iterators i and j such that i precedes j, comp(*j, *i) is false.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
For the first version:
• InputIterator1 is a model of Input Iterator.
• InputIterator2 is a model of Input Iterator.
• InputIterator1's value type is the same type as InputIterator2's value type.
• InputIterator1's value type is a model of LessThan Comparable.
• The ordering on objects of InputIterator1's value type is a strict weak ordering, as defined in the LessThan Comparable requirements.
• InputIterator1's value type is convertible to a type in OutputIterator's set of value types.
For the second version:
• InputIterator1 is a model of Input Iterator.
• InputIterator2 is a model of Input Iterator.
• InputIterator1's value type is the same type as InputIterator2's value type.
• StrictWeakOrdering is a model of Strict Weak Ordering.
• InputIterator1's value type is convertible to StrictWeakOrdering's argument type.
• InputIterator1's value type is convertible to a type in OutputIterator's set of value types.
For the first version:
• [first1, last1) is a valid range.
• [first1, last1) is in ascending order. That is, for every pair of iterators i and j in [first1, last1) such that i precedes j, *j < *i is false.
• [first2, last2) is a valid range.
• [first2, last2) is in ascending order. That is, for every pair of iterators i and j in [first2, last2) such that i precedes j, *j < *i is false.
• The ranges [first1, last1) and [result, result + (last1 – first1) + (last2 – first2)) do not overlap.
• The ranges [first2, last2) and [result, result + (last1 – first1) + (last2 – first2)) do not overlap.
• There is enough space to hold all of the elements being copied. More formally, the requirement is that [result, result + (last1 – first1) + (last2 – first2)) is a valid range.
For the second version:
• [first1, last1) is a valid range.
• [first1, last1) is in ascending order. That is, for every pair of iterators i and j in [first1, last1) such that i precedes j, comp(*j, *i) is false.
• [first2, last2) is a valid range.
• [first2, last2) is in ascending order. That is, for every pair of iterators i and j in [first2, last2) such that i precedes j, comp(*j, *i) is false.
• The ranges [first1, last1) and [result, result + (last1 – first1) + (last2 – first2)) do not overlap.
• The ranges [first2, last2) and [result, result + (last1 – first1) + (last2 – first2)) do not overlap.
• There is enough space to hold all of the elements being copied. More formally, the requirement is that [result, result + (last1 – first1) + (last2 – first2)) is a valid range.
Linear. No comparisons if both [first1, last1) and [first2, last2) are empty ranges, otherwise at most (last1 – first1) + (last2 – first2) – 1 comparisons.
int main() {
int A1[] = { 1, 3, 5, 7 };
int A2[] = { 2, 4, 6, 8 };
const int N1 = sizeof(A1) / sizeof(int);
const int N2 = sizeof(A2) / sizeof(int);
merge(A1, A1 + N1, A2, A2 + N2, ostream_iterator<int>(cout, " "));
// The output is "1 2 3 4 5 6 7 8"
}
[1] Note that you may use an ordering that is a strict weak ordering but not a total ordering; that is, there might be values x and y such that x < y, x > y, and x == y are all false. (See the LessThan Comparable requirements for a more complete discussion.) Two elements x and y are equivalent if neither x < y nor y < x. If you're using a total ordering, however (if you're using strcmp, for example, or if you're using ordinary arithmetic comparison on integers), then you can ignore this technical distinction: for a total ordering, equality and equivalence are the same.
inplace_merge, set_union, sort
Category: algorithms
Component type: function
Inplace_merge is an overloaded name: there are actually two inplace_merge functions.
template <class BidirectionalIterator>
inline void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last);
template <class BidirectionalIterator, class StrictWeakOrdering>
inline void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, StrictWeakOrdering comp);
Inplace_merge combines two consecutive sorted ranges [first, middle) and [middle, last) into a single sorted range [first, last). That is, it starts with a range [first, last) that consists of two pieces each of which is in ascending order, and rearranges it so that the entire range is in ascending order. Inplace_merge is stable, meaning both that the relative order of elements within each input range is preserved, and that for equivalent [1] elements in both input ranges the element from the first range precedes the element from the second.
The two versions of inplace_merge differ in how elements are compared. The first version uses operator<. That is, the input ranges and the output range satisfy the condition that for every pair of iterators i and j such that i precedes j, *j < *i is false. The second version uses the function object comp. That is, the input ranges and the output range satisfy the condition that for every pair of iterators i and j such that i precedes j, comp(*j, *i) is false.
Defined in algo.h.
For the first version:
• BidirectionalIterator is a model of Bidirectional Iterator.
• BidirectionalIterator is mutable.
• BidirectionalIterator's value type is a model of LessThan Comparable.
• The ordering on objects of BidirectionalIterator's value type is a strict weak ordering, as defined in the LessThan Comparable requirements.
• BidirectionalIterator is a model of Bidirectional Iterator.
• BidirectionalIterator is mutable.
• StrictWeakOrdering is a model of Strict Weak Ordering.
• BidirectionalIterator's value type is convertible to StrictWeakOrdering's argument type.
For the first version:
• [first, middle) is a valid range.
• [middle, last) is a valid range.
• [first, middle) is in ascending order. That is, for every pair of iterators i and j in [first, middle) such that i precedes j, *j < *i is false.
• [middle, last) is in ascending order. That is, for every pair of iterators i and j in [middle, last) such that i precedes j, *j < *i is false.
For the second version:
• [first, middle) is a valid range.
• [middle, last) is a valid range.
• [first, middle) is in ascending order. That is, for every pair of iterators i and j in [first, middle) such that i precedes j, comp(*j, *i) is false.
• [middle, last) is in ascending order. That is, for every pair of iterators i and j in [middle, last) such that i precedes j, comp(*j, *i) is false.
Inplace_merge is an adaptive algorithm: it attempts to allocate a temporary memory buffer, and its run-time complexity depends on how much memory is available. Inplace_merge performs no comparisons if [first, last) is an empty range. Otherwise, worst-case behavior (if no auxiliary memory is available) is O(N log(N)), where N is last – first , and best case (if a large enough auxiliary memory buffer is available) is at most (last – first) – 1 comparisons.
int main() {
int A[] = { 1, 3, 5, 7, 2, 4, 6, 8 };
inplace_merge(A, A + 4, A + 8);
copy(A, A + 8, ostream_iterator<int>(cout, " "));
// The output is "1 2 3 4 5 6 7 8".
}
[1] Note that you may use an ordering that is a strict weak ordering but not a total ordering; that is, there might be values x and y such that x < y, x > y, and x == y are all false. (See the LessThan Comparable requirements for a fuller discussion.) Two elements x and y are equivalent if neither x < y nor y < x. If you're using a total ordering, however (if you're using strcmp, for example, or if you're using ordinary arithmetic comparison on integers), then you can ignore this technical distinction: for a total ordering, equality and equivalence are the same.
merge, set_union, sort
Category: algorithms
Component type: function
Includes is an overloaded name; there are actually two includes functions.
template <class InputIterator1, class InputIterator2>
bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
template <class InputIterator1, class InputIterator2, class StrictWeakOrdering>
bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, StrictWeakOrdering comp);
Includes tests whether one sorted range includes another sorted range. That is, it returns true if and only if, for every element in [first2, last2), an equivalent element [1] is also present in [first1, last1) [2]. Both [first1, last1) and [first2, last2) must be sorted in ascending order.
The two versions of includes differ in how they define whether one element is less than another. The first version compares objects using operator<, and the second compares objects using the function object comp.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
For the first version:
• InputIterator1 is a model of Input Iterator.
• InputIterator2 is a model of Input Iterator.
• InputIterator1 and InputIterator2 have the same value type.
• InputIterator's value type is a model of LessThan Comparable.
• The ordering on objects of InputIterator1's value type is a strict weak ordering, as defined in the LessThan Comparable requirements.
For the second version:
• InputIterator1 is a model of Input Iterator.
• InputIterator2 is a model of Input Iterator.
• InputIterator1 and InputIterator2 have the same value type.
• StrictWeakOrdering is a model of Strict Weak Ordering.
• InputIterator1's value type is convertible to StrictWeakOrdering's argument type.
For the first version:
• [first1, last1) is a valid range.
• [first2, last2) is a valid range.
• [first1, last1) is ordered in ascending order according to operator<. That is, for every pair of iterators i and j in [first1, last1) such that i precedes j, *j < *i is false.
• [first2, last2) is ordered in ascending order according to operator<. That is, for every pair of iterators i and j in [first2, last2) such that i precedes j, *j < *i is false.
For the second version:
• [first1, last1) is a valid range.
• [first2, last2) is a valid range.
• [first1, last1) is ordered in ascending order according to comp. That is, for every pair of iterators i and j in [first1, last1) such that i precedes j, comp(*j, *i) is false.
• [first2, last2) is ordered in ascending order according to comp. That is, for every pair of iterators i and j in [first2, last2) such that i precedes j, comp(*j, *i) is false.
Linear. Zero comparisons if either [first1, last1) or [first2, last2) is an empty range, otherwise at most 2 * ((last1 – first1) + (last2 – first2)) – 1 comparisons.
int A1[] = { 1, 2, 3, 4, 5, 6, 7 };
int A2[] = { 1, 4, 7 };
int A3[] = { 2, 7, 9 };
int A4[] = { 1, 1, 2, 3, 5, 8, 13, 21 };
int A5[] = { 1, 2, 13, 13 };
int A6[] = { 1, 1, 3, 21 };
const int N1 = sizeof(A1) / sizeof(int);
const int N2 = sizeof(A2) / sizeof(int);
const int N3 = sizeof(A3) / sizeof(int);
const int N4 = sizeof(A4) / sizeof(int);
const int N5 = sizeof(A5) / sizeof(int);
const int N6 = sizeof(A6) / sizeof(int);
cout << "A2 contained in A1: " << (includes(A1, A1 + N1, A2, A2 + N2) ? "true" : "false") << endl;
cout << "A3 contained in A1: " << (includes(A1, A1 + N2, A3, A3 + N3) ? "true" : "false") << endl;
cout << "A5 contained in A4: " << (includes(A4, A4 + N4, A5, A5 + N5) ? "true" : "false") << endl;
cout << "A6 contained in A4: " << (includes(A4, A4 + N4, A6, A6 + N6) ? "true" : "false") << endl;
The output is:
A2 contained in A1: true
A3 contained in A1: false
A5 contained in A4: false
A6 contained in A4: true
[1] This reads "an equivalent element" rather than "the same element" because the ordering by which the input ranges are sorted is permitted to be a strict weak ordering that is not a total ordering: there might be values x and y that are equivalent (that is, neither x < y nor y < x is true) but not equal. See the LessThan Comparable requirements for a fuller discussion.) If you're using a total ordering (if you're using strcmp , for example, or if you're using ordinary arithmetic comparison on integers), then you can ignore this technical distinction: for a total ordering, equality and equivalence are the same.
[2] Note that the range [first2, last2) may contain a consecutive range of equivalent elements: there is no requirement that every element in the range be unique. In this case, includes will return false unless, for every element in [first2, last2), a distinct equivalent element is also present in [first1, last1). That is, if a certain value appears n times in [first2, last2) and m times in [first1, last1), then includes will return false if m < n.
set_union, set_intersection, set_difference, set_symmetric_difference, sort
Category: algorithms
Component type: function
Set_union is an overloaded name; there are actually two set_union functions.
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
template <class InputIterator1, class InputIterator2, class OutputIterator, class StrictWeakOrdering>
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering comp);
Set_union constructs a sorted range that is the union of the sorted ranges [first1, last1) and [first2, last2) . The return value is the end of the output range.
In the simplest case, set_union performs the "union" operation from set theory: the output range contains a copy of every element that is contained in [first1, last1), [first2, last2), or both. The general case is more complicated, because the input ranges may contain duplicate elements. The generalization is that if a value appears m times in [first1, last1) and n times in [first2, last2) (where m or n may be zero), then it appears max(m,n) times in the output range. [1] Set_union is stable, meaning both that the relative order of elements within each input range is preserved, and that if an element is present in both input ranges it is copied from the first range rather than the second.
The two versions of set_union differ in how they define whether one element is less than another. The first version compares objects using operator<, and the second compares objects using a function object comp.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
For the first version:
• InputIterator1 is a model of Input Iterator.
• InputIterator2 is a model of Input Iterator.
• OutputIterator is a model of Output Iterator.
• InputIterator1 and InputIterator2 have the same value type.
• InputIterator's value type is a model of LessThan Comparable.
• The ordering on objects of InputIterator1's value type is a strict weak ordering, as defined in the LessThan Comparable requirements.
• InputIterator's value type is convertible to a type in OutputIterator's set of value types.
For the second version:
• InputIterator1 is a model of Input Iterator.
• InputIterator2 is a model of Input Iterator.
• OutputIterator is a model of Output Iterator.
• StrictWeakOrdering is a model of Strict Weak Ordering.
• InputIterator1 and InputIterator2 have the same value type.
• InputIterator1's value type is convertible to StrictWeakOrdering's argument type.
• InputIterator's value type is convertible to a type in OutputIterator's set of value types.
For the first version:
• [first1, last1) is a valid range.
• [first2, last2) is a valid range.
• [first1, last1) is ordered in ascending order according to operator<. That is, for every pair of iterators i and j in [first1, last1) such that i precedes j, *j < *i is false.
• [first2, last2) is ordered in ascending order according to operator<. That is, for every pair of iterators i and j in [first2, last2) such that i precedes j, *j < *i is false.
• There is enough space to hold all of the elements being copied. More formally, the requirement is that [result, result + n) is a valid range, where n is the number of elements in the union of the two input ranges.
• [first1, last1) and [result, result + n) do not overlap.
• [first2, last2) and [result, result + n) do not overlap.
For the second version:
• [first1, last1) is a valid range.
• [first2, last2) is a valid range.
• [first1, last1) is ordered in ascending order according to comp. That is, for every pair of iterators i and j in [first1, last1) such that i precedes j, comp(*j, *i) is false.
• [first2, last2) is ordered in ascending order according to comp. That is, for every pair of iterators i and j in [first2, last2) such that i precedes j, comp(*j, *i) is false.
• There is enough space to hold all of the elements being copied. More formally, the requirement is that [result, result + n) is a valid range, where n is the number of elements in the union of the two input ranges.
• [first1, last1) and [result, result + n) do not overlap.
• [first2, last2) and [result, result + n) do not overlap.
Linear. Zero comparisons if either [first1, last1) or [first2, last2) is empty, otherwise at most 2 * ((last1 – first1) + (last2 – first2)) – 1 comparisons.
inline bool lt_nocase(char c1, char c2) { return tolower(c1) < tolower(c2); }
int main() {
int A1[] = {1, 3, 5, 7, 9, 11};
int A2[] = {1, 1, 2, 3, 5, 8, 13};
char A3[] = {'a', 'b', 'B', 'B', 'f', 'H'};
char A4[] = {'A', 'B', 'b', 'C', 'D', 'F', 'F', 'h', 'h'};
const int N1 = sizeof(A1) / sizeof(int);
const int N2 = sizeof(A2) / sizeof(int);
const int N3 = sizeof(A3);
const int N4 = sizeof(A4);
cout << "Union of A1 and A2: ";
set_union(A1, A1 + N1, A2, A2 + N2, ostream_iterator<int>(cout, " "));
cout << endl << "Union of A3 and A4: ";
set_union(A3, A3 + N3, A4, A4 + N4, ostream_iterator<char>(cout, " "), lt_nocase);
cout << endl;
}
The output is
Union of A1 and A2: 1 1 2 3 5 7 8 9 11 13
Union of A3 and A4: a b B B C D f F H h
[1] Even this is not a completely precise description, because the ordering by which the input ranges are sorted is permitted to be a strict weak ordering that is not a total ordering: there might be values x and y that are equivalent (that is, neither x < y nor y < x) but not equal. See the LessThan Comparable requirements for a more complete discussion. If the range [first1, last1) contains m elements that are equivalent to each other and the range [first2, last2) contains n elements from that equivalence class (where either m or n may be zero), then the output range contains max(m, n) elements from that equivalence class. Specifically, m of these elements will be copied from [first1, last1) and max(n-m, 0) of them will be copied from [first2, last2). Note that this precision is only important if elements can be equivalent but not equal. If you're using a total ordering (if you're using strcmp, for example, or if you're using ordinary arithmetic comparison on integers), then you can ignore this technical distinction: for a total ordering, equality and equivalence are the same.
includes, set_intersection, set_difference, set_symmetric_difference, sort, merge
Category: algorithms
Component type: function
Set_intersection is an overloaded name; there are actually two set_intersection functions.
template <class InputIterator1, class InputIterato2, class OutputIterator>
OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
template <class InputIterator1, class InputIterator2, class OutputIterator, class StrictWeakOrdering>
OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering comp);
Set_intersection constructs a sorted range that is the intersection of the sorted ranges [first1, last1) and [first2, last2). The return value is the end of the output range.
In the simplest case, set_intersection performs the "intersection" operation from set theory: the output range contains a copy of every element that is contained in both [first1, last1) and [first2, last2). The general case is more complicated, because the input ranges may contain duplicate elements. The generalization is that if a value appears m times in [first1, last1) and n times in [first2, last2) (where m or n may be zero), then it appears min(m,n) times in the output range. [1] Set_intersection is stable, meaning both that elements are copied from the first range rather than the second, and that the relative order of elements in the output range is the same as in the first input range.
The two versions of set_intersection differ in how they define whether one element is less than another. The first version compares objects using operator<, and the second compares objects using a function object comp.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
For the first version:
• InputIterator1 is a model of Input Iterator.
• InputIterator2 is a model of Input Iterator.
• OutputIterator is a model of Output Iterator.
• InputIterator1 and InputIterator2 have the same value type.
• InputIterator's value type is a model of LessThan Comparable.
• The ordering on objects of InputIterator1's value type is a strict weak ordering, as defined in the LessThan Comparable requirements.
• InputIterator's value type is convertible to a type in OutputIterator's set of value types.
For the second version:
• InputIterator1 is a model of Input Iterator.
• InputIterator2 is a model of Input Iterator.
• OutputIterator is a model of Output Iterator.
• StrictWeakOrdering is a model of Strict Weak Ordering.
• InputIterator1 and InputIterator2 have the same value type.
• InputIterator1's value type is convertible to StrictWeakOrdering's argument type.
• InputIterator's value type is convertible to a type in OutputIterator's set of value types.
For the first version:
• [first1, last1) is a valid range.
• [first2, last2) is a valid range.
• [first1, last1) is ordered in ascending order according to operator<. That is, for every pair of iterators i and j in [first1, last1) such that i precedes j, *j < *i is false.
• [first2, last2) is ordered in ascending order according to operator<. That is, for every pair of iterators i and j in [first2, last2) such that i precedes j, *j < *i is false.
• There is enough space to hold all of the elements being copied. More formally, the requirement is that [result, result + n) is a valid range, where n is the number of elements in the union of the two input ranges.
• [first1, last1) and [result, result + n) do not overlap.
• [first2, last2) and [result, result + n) do not overlap.
For the second version:
• [first1, last1) is a valid range.
• [first2, last2) is a valid range.
• [first1, last1) is ordered in ascending order according to comp. That is, for every pair of iterators i and j in [first1, last1) such that i precedes j, comp(*j, *i) is false.
• [first2, last2) is ordered in ascending order according to comp. That is, for every pair of iterators i and j in [first2, last2) such that i precedes j, comp(*j, *i) is false.
• There is enough space to hold all of the elements being copied. More formally, the requirement is that [result, result + n) is a valid range, where n is the number of elements in the union of the two input ranges.
• [first1, last1) and [result, result + n) do not overlap.
• [first2, last2) and [result, result + n) do not overlap.
Linear. Zero comparisons if either [first1, last1) or [first2, last2) is empty, otherwise at most 2 * ((last1 – first1) + (last2 – first2)) – 1 comparisons.
inline bool lt_nocase(char c1, char c2) { return tolower(c1) < tolower(c2); }
int main() {
int A1[] = {1, 3, 5, 7, 9, 11};
int A2[] = {1, 1, 2, 3, 5, 8, 13};
char A3[] = {'a', 'b', 'b', 'B', 'B', 'f', 'h', 'H'};
char A4[] = {'A', 'B', 'B', 'C', 'D', 'F', 'F', 'H' };
const int N1 = sizeof(A1) / sizeof(int);
const int N2 = sizeof(A2) / sizeof(int);
const int N3 = sizeof(A3);
const int N4 = sizeof(A4);
cout << "Intersection of A1 and A2: ";
set_intersection(A1, A1 + N1, A2, A2 + N2, ostream_iterator<int>(cout, " "));
cout << endl << "Intersection of A3 and A4: ";
set_intersection(A3, A3 + N3, A4, A4 + N4, ostream_iterator<char>(cout, " "), lt_nocase);
cout << endl;
}
The output is
Intersection of A1 and A2: 1 3 5
Intersection of A3 and A4: a b b f h
[1] Even this is not a completely precise description, because the ordering by which the input ranges are sorted is permitted to be a strict weak ordering that is not a total ordering: there might be values x and y that are equivalent (that is, neither x < y nor y < x ) but not equal. See the LessThan Comparable requirements for a fuller discussion. The output range consists of those elements from [first1, last1) for which equivalent elements exist in [first2, last2). Specifically, if the range [first1, last1) contains n elements that are equivalent to each other and the range [first1, last1) contains m elements from that equivalence class (where either m or n may be zero), then the output range contains the first min(m, n) of these elements from [first1, last1). Note that this precision is only important if elements can be equivalent but not equal. If you're using a total ordering (if you're using strcmp, for example, or if you're using ordinary arithmetic comparison on integers), then you can ignore this technical distinction: for a total ordering, equality and equivalence are the same.
includes, set_union, set_difference, set_symmetric_difference, sort
Category: algorithms
Component type: function
Set_difference is an overloaded name; there are actually two set_difference functions.
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
template <class InputIterator1, class InputIterator2, class OutputIterator, class StrictWeakOrdering>
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering comp);
Set_difference constructs a sorted range that is the set difference of the sorted ranges [first1, last1) and [first2, last2). The return value is the end of the output range.
In the simplest case, set_difference performs the "difference" operation from set theory: the output range contains a copy of every element that is contained in [first1, last1) and not contained in [first2, last2). The general case is more complicated, because the input ranges may contain duplicate elements. The generalization is that if a value appears m times in [first1, last1) and n times in [first2, last2) (where m or n may be zero), then it appears max(m-n, 0) times in the output range. [1] Set_difference is stable, meaning both that elements are copied from the first range rather than the second, and that the relative order of elements in the output range is the same as in the first input range.
The two versions of set_difference differ in how they define whether one element is less than another. The first version compares objects using operator<, and the second compares objects using a function object comp.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
For the first version:
• InputIterator1 is a model of Input Iterator.
• InputIterator2 is a model of Input Iterator.
• OutputIterator is a model of Output Iterator.
• InputIterator1 and InputIterator2 have the same value type.
• InputIterator's value type is a model of LessThan Comparable.
• The ordering on objects of InputIterator1's value type is a strict weak ordering, as defined in the LessThan Comparable requirements.
• InputIterator's value type is convertible to a type in OutputIterator's set of value types.
For the second version:
• InputIterator1 is a model of Input Iterator.
• InputIterator2 is a model of Input Iterator.
• OutputIterator is a model of Output Iterator.
• StrictWeakOrdering is a model of Strict Weak Ordering.
• InputIterator1 and InputIterator2 have the same value type.
• InputIterator1's value type is convertible to StrictWeakOrdering's argument type.
• InputIterator's value type is convertible to a type in OutputIterator's set of value types.
For the first version:
• [first1, last1) is a valid range.
• [first2, last2) is a valid range.
• [first1, last1) is ordered in ascending order according to operator<. That is, for every pair of iterators i and j in [first1, last1) such that i precedes j, *j < *i is false.
• [first2, last2) is ordered in ascending order according to operator<. That is, for every pair of iterators i and j in [first2, last2) such that i precedes j, *j < *i is false.
• There is enough space to hold all of the elements being copied. More formally, the requirement is that [result, result + n) is a valid range, where n is the number of elements in the union of the two input ranges.
• [first1, last1) and [result, result + n) do not overlap.
• [first2, last2) and [result, result + n) do not overlap.
For the second version:
• [first1, last1) is a valid range.
• [first2, last2) is a valid range.
• [first1, last1) is ordered in ascending order according to comp. That is, for every pair of iterators i and j in [first1, last1) such that i precedes j, comp(*j, *i) is false.
• [first2, last2) is ordered in ascending order according to comp. That is, for every pair of iterators i and j in [first2, last2) such that i precedes j, comp(*j, *i) is false.
• There is enough space to hold all of the elements being copied. More formally, the requirement is that [result, result + n) is a valid range, where n is the number of elements in the union of the two input ranges.
• [first1, last1) and [result, result + n) do not overlap.
• [first2, last2) and [result, result + n) do not overlap.
Linear. Zero comparisons if either [first1, last1) or [first2, last2) is empty, otherwise at most 2 * ((last1 – first1) + (last2 – first2)) – 1 comparisons.
inline bool lt_nocase(char c1, char c2) { return tolower(c1) < tolower(c2); }
int main() {
int A1[] = {1, 3, 5, 7, 9, 11};
int A2[] = {1, 1, 2, 3, 5, 8, 13};
char A3[] = {'a', 'b', 'b', 'B', 'B', 'f', 'g', 'h', 'H'};
char A4[] = {'A', 'B', 'B', 'C', 'D', 'F', 'F', 'H' };
const int N1 = sizeof(A1) / sizeof(int);
const int N2 = sizeof(A2) / sizeof(int);
const int N3 = sizeof(A3);
const int N4 = sizeof(A4);
cout << "Difference of A1 and A2: ";
set_difference(A1, A1 + N1, A2, A2 + N2, ostream_iterator<int>(cout, " "));
cout << endl << "Difference of A3 and A4: ";
set_difference(A3, A3 + N3, A4, A4 + N4, ostream_iterator<char>(cout, " "), lt_nocase);
cout << endl;
}
The output is
Difference of A1 and A2: 7 9 11
Difference of A3 and A4: B B g H
[1] Even this is not a completely precise description, because the ordering by which the input ranges are sorted is permitted to be a strict weak ordering that is not a total ordering: there might be values x and y that are equivalent (that is, neither x < y nor y < x) but not equal. See the LessThan Comparable requirements for a fuller discussion. The output range consists of those elements from [first1, last1) for which equivalent elements do not exist in [first2, last2). Specifically, if the range [first1, last1) contains m elements that are equivalent to each other and the range [first2, last2) contains n elements from that equivalence class (where either m or n may be zero), then the output range contains the lastmax(m – n, 0) of these elements from [first1, last1). Note that this precision is only important if elements can be equivalent but not equal. If you're using a total ordering (if you're using strcmp, for example, or if you're using ordinary arithmetic comparison on integers), then you can ignore this technical distinction: for a total ordering, equality and equivalence are the same.
includes, set_union, set_intersection, set_symmetric_difference, sort
Category: algorithms
Component type: function
Set_symmetric_difference is an overloaded name; there are actually two set_symmetric_difference functions.
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
template <class InputIterator1, class InputIterator2, class OutputIterator, class StrictWeakOrdering>
OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering comp);
Set_symmetric_difference constructs a sorted range that is the set symmetric difference of the sorted ranges [first1, last1) and [first2, last2) . The return value is the end of the output range.
In the simplest case, set_symmetric_difference performs a set theoretic calculation: it constructs the union of the two sets A – B and B – A, where A and B are the two input ranges. That is, the output range contains a copy of every element that is contained in [first1, last1) but not [first2, last2), and a copy of every element that is contained in [first2, last2) but not [first1, last1). The general case is more complicated, because the input ranges may contain duplicate elements. The generalization is that if a value appears m times in [first1, last1) and n times in [first2, last2) (where m or n may be zero), then it appears |m-n| times in the output range. [1] Set_symmetric_difference is stable, meaning that the relative order of elements within each input range is preserved.
The two versions of set_symmetric_difference differ in how they define whether one element is less than another. The first version compares objects using operator< , and the second compares objects using a function object comp.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
For the first version:
• InputIterator1 is a model of Input Iterator.
• InputIterator2 is a model of Input Iterator.
• OutputIterator is a model of Output Iterator.
• InputIterator1 and InputIterator2 have the same value type.
• InputIterator's value type is a model of LessThan Comparable.
• The ordering on objects of InputIterator1's value type is a strict weak ordering, as defined in the LessThan Comparable requirements.
• InputIterator's value type is convertible to a type in OutputIterator's set of value types.
For the second version:
• InputIterator1 is a model of Input Iterator.
• InputIterator2 is a model of Input Iterator.
• OutputIterator is a model of Output Iterator.
• StrictWeakOrdering is a model of Strict Weak Ordering.
• InputIterator1 and InputIterator2 have the same value type.
• InputIterator1's value type is convertible to StrictWeakOrdering's argument type.
• InputIterator's value type is convertible to a type in OutputIterator's set of value types.
For the first version:
• [first1, last1) is a valid range.
• [first2, last2) is a valid range.
• [first1, last1) is ordered in ascending order according to operator<. That is, for every pair of iterators i and j in [first1, last1) such that i precedes j, *j < *i is false.
• [first2, last2) is ordered in ascending order according to operator<. That is, for every pair of iterators i and j in [first2, last2) such that i precedes j, *j < *i is false.
• There is enough space to hold all of the elements being copied. More formally, the requirement is that [result, result + n) is a valid range, where n is the number of elements in the union of the two input ranges.
• [first1, last1) and [result, result + n) do not overlap.
• [first2, last2) and [result, result + n) do not overlap.
For the second version:
• [first1, last1) is a valid range.
• [first2, last2) is a valid range.
• [first1, last1) is ordered in ascending order according to comp. That is, for every pair of iterators i and j in [first1, last1) such that i precedes j, comp(*j, *i) is false.
• [first2, last2) is ordered in ascending order according to comp. That is, for every pair of iterators i and j in [first2, last2) such that i precedes j, comp(*j, *i) is false.
• There is enough space to hold all of the elements being copied. More formally, the requirement is that [result, result + n) is a valid range, where n is the number of elements in the union of the two input ranges.
• [first1, last1) and [result, result + n) do not overlap.
• [first2, last2) and [result, result + n) do not overlap.
Linear. Zero comparisons if either [first1, last1) or [first2, last2) is empty, otherwise at most 2 * ((last1 – first1) + (last2 – first2)) – 1 comparisons.
inline bool lt_nocase(char c1, char c2) { return tolower(c1) < tolower(c2); }
int main() {
int A1[] = {1, 3, 5, 7, 9, 11};
int A2[] = {1, 1, 2, 3, 5, 8, 13};
char A3[] = {'a', 'b', 'b', 'B', 'B', 'f', 'g', 'h', 'H'};
char A4[] = {'A', 'B', 'B', 'C', 'D', 'F', 'F', 'H' };
const int N1 = sizeof(A1) / sizeof(int);
const int N2 = sizeof(A2) / sizeof(int);
const int N3 = sizeof(A3);
const int N4 = sizeof(A4);
cout << "Symmetric difference of A1 and A2: ";
set_symmetric_difference(A1, A1 + N1, A2, A2 + N2, ostream_iterator<int>(cout, " "));
cout << endl << "Symmetric difference of A3 and A4: ";
set_symmetric_difference(A3, A3 + N3, A4, A4 + N4, ostream_iterator<char>(cout, " "), lt_nocase);
cout << endl;
}
The output is
Symmetric difference of A1 and A2: 1 2 7 8 9 11 13
Symmetric difference of A3 and A4: B B C D F g H
[1] Even this is not a completely precise description, because the ordering by which the input ranges are sorted is permitted to be a strict weak ordering that is not a total ordering: there might be values x and y that are equivalent (that is, neither x < y nor y < x) but not equal. See the LessThan Comparable requirements for a more complete discussion. The output range consists of those elements from [first1, last1) for which equivalent elements do not exist in [first2, last2), and those elements from [first2, last2) for which equivalent elements do not exist in [first1, last1). Specifically, suppose that the range [first1, last1) contains m elements that are equivalent to each other and the range [first2, last2) contains n elements from that equivalence class (where either m or n may be zero). If m > n then the output range contains the lastm – n of these elements elements from [first1, last1), and if m < n then the output range contains the last n – m of these elements elements from [first2, last2).
includes, set_union, set_intersection, set_difference, sort
Category: algorithms
Component type: function
Push_heap is an overloaded name; there are actually two push_heap functions.
template <class RandomAccessIterator>
void push_heap(RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class StrictWeakOrdering>
void push_heap(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp);
Push_heap adds an element to a heap [1]. It is assumed that [first, last – 1) is already a heap; the element to be added to the heap is *(last – 1).
The two versions of push_heap differ in how they define whether one element is less than another. The first version compares objects using operator<, and the second compares objects using a function object comp. The postcondition for the first version is that is_heap (first, last) is true, and the postcondition for the second version is that is_heap(first, last, comp) is true.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
For the first version:
• RandomAccessIterator is a model of Random Access Iterator.
• RandomAccessIterator is mutable.
• RandomAccessIterator's value type is a model of LessThan Comparable.
• The ordering on objects of RandomAccessIterator's value type is a strict weak ordering, as defined in the LessThan Comparable requirements.
For the second version:
• RandomAccessIterator is a model of Random Access Iterator.
• RandomAccessIterator is mutable.
• StrictWeakOrdering is a model of Strict Weak Ordering.
• RandomAccessIterator's value type is convertible to StrictWeakOrdering's argument type.
For the first version:
• [first, last) is a valid range.
• [first, last – 1) is a valid range. That is, [first, last) is nonempty.
• [first, last – 1) is a heap. That is, is_heap(first, last – 1) is true.
For the second version:
• [first, last) is a valid range.
• [first, last – 1) is a valid range. That is, [first, last) is nonempty.
• [first, last) is a heap. That is, is_heap(first, last – 1, comp) is true.
Logarithmic. At most log(last – first) comparisons.
int main() {
int A[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
make_heap(A, A + 9);
cout << "[A, A + 9) = ";
copy (A, A + 9, ostream_iterator<int>(cout, " "));
push_heap(A, A + 10);
cout << endl << "[A, A + 10) = ";
copy (A, A + 10, ostream_iterator<int>(cout, " "));
cout << endl;
}
The output is
[A, A + 9) = 8 7 6 3 4 5 2 1 0
[A, A + 10) = 9 8 6 3 7 5 2 1 0 4
Notes
[1] A heap is a particular way of ordering the elements in a range of random access iterators [f, l). The reason heaps are useful (especially for sorting, or as priority queues) is that they satisfy two important properties. First, *f is the largest element in the heap. Second, it is possible to add an element to a heap (using push_heap), or to remove *f, in logarithmic time. Internally, a heap is a tree represented as a sequential range. The tree is constructed so that that each node is less than or equal to its parent node.
make_heap, pop_heap, sort_heap, is_heap, sort
Category: algorithms
Component type: function
Pop_heap is an overloaded name; there are actually two pop_heap functions.
template <class RandomAccessIterator>
void pop_heap(RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class StrictWeakOrdering>
inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp);
Pop_heap removes the largest element (that is, *first ) from the heap [1] [first, last). The two versions of pop_heap differ in how they define whether one element is less than another. The first version compares objects using operator<, and the second compares objects using a function object comp.
The postcondition for the first version of pop_heap is that is_heap(first, last-1) is true and that *(last – 1) is the element that was removed from the heap. The postcondition for the second version is that is_heap(first, last-1, comp) is true and that *(last – 1) is the element that was removed from the heap. [2]
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
For the first version:
• RandomAccessIterator is a model of Random Access Iterator.
• RandomAccessIterator is mutable.
• RandomAccessIterator's value type is a model of LessThan Comparable.
• The ordering on objects of RandomAccessIterator's value type is a strict weak ordering, as defined in the LessThan Comparable requirements.
For the second version:
• RandomAccessIterator is a model of Random Access Iterator.
• RandomAccessIterator is mutable.
• StrictWeakOrdering is a model of Strict Weak Ordering.
• RandomAccessIterator's value type is convertible to StrictWeakOrdering's argument type.
For the first version:
• [first, last) is a valid range.
• [first, last – 1) is a valid range. That is, [first, last) is nonempty.
• [first, last – 1) is a heap. That is, is_heap(first, last – 1) is true.
For the second version:
• [first, last) is a valid range.
• [first, last – 1) is a valid range. That is, [first, last) is nonempty.
• [first, last) is a heap. That is, is_heap(first, last – 1, comp) is true.
Logarithmic. At most 2 * log(last – first) comparisons.
int main() {
int A[] = {1, 2, 3, 4, 5, 6};
const int N = sizeof(A) / sizeof(int);
make_heap(A, A+N);
cout << "Before pop: ";
copy(A, A+N, ostream_iterator<int>(cout, " "));
pop_heap(A, A+N);
cout << endl << "After pop: ";
copy(A, A+N-1, ostream_iterator<int>(cout, " "));
cout << endl << "A[N-1] = " << A[N-1] << endl;
}
The output is
Before pop: 6 5 3 4 2 1
After pop: 5 4 3 1 2
A[N-1] = 6
[1] A heap is a particular way of ordering the elements in a range of Random Access Iterators [f, l). The reason heaps are useful (especially for sorting, or as priority queues) is that they satisfy two important properties. First, *f is the largest element in the heap. Second, it is possible to add an element to a heap (using push_heap), or to remove *f, in logarithmic time. Internally, a heap is a tree represented as a sequential range. The tree is constructed so that that each node is less than or equal to its parent node.
[2] Pop_heap removes the largest element from a heap, and shrinks the heap. This means that if you call keep calling pop_heap until only a single element is left in the heap, you will end up with a sorted range where the heap used to be. This, in fact, is exactly how sort_heap is implemented.
make_heap, push_heap, sort_heap, is_heap, sort
Category: algorithms
Component type: function
Make_heap is an overloaded name; there are actually two make_heap functions.
template <class RandomAccessIterator>
void make_heap(RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class StrictWeakOrdering>
void make_heap(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp);
Make_heap turns the range [first, last) into a heap [1].
The two versions of make_heap differ in how they define whether one element is less than another. The first version compares objects using operator<, and the second compares objects using a function object comp. In the first version the postcondition is that is_heap(first, last) is true, and in the second version the postcondition is that is_heap(first, last, comp) is true.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
For the first version:
• RandomAccessIterator is a model of Random Access Iterator.
• RandomAccessIterator is mutable.
• RandomAccessIterator's value type is a model of LessThan Comparable.
• The ordering on objects of RandomAccessIterator's value type is a strict weak ordering, as defined in the LessThan Comparable requirements.
For the second version:
• RandomAccessIterator is a model of Random Access Iterator.
• RandomAccessIterator is mutable.
• StrictWeakOrdering is a model of Strict Weak Ordering.
• RandomAccessIterator's value type is convertible to StrictWeakOrdering's argument type.
• [first, last) is a valid range.
Linear. At most 3*(last – first) comparisons.
int main() {
int A[] = {1, 4, 2, 8, 5, 7};
const int N = sizeof(A) / sizeof(int);
make_heap(A, A+N);
copy(A, A+N, ostream_iterator<int>(cout, " "));
cout << endl;
sort_heap (A, A+N);
copy(A, A+N, ostream_iterator <int>(cout, " "));
cout << endl;
}
[1] A heap is a particular way of ordering the elements in a range of Random Access Iterators [f, l). The reason heaps are useful (especially for sorting, or as priority queues) is that they satisfy two important properties. First, *f is the largest element in the heap. Second, it is possible to add an element to a heap (using push_heap), or to remove *f, in logarithmic time. Internally, a heap is simply a tree represented as a sequential range. The tree is constructed so that that each node is less than or equal to its parent node.
push_heap , pop_heap , sort_heap , sort , is_heap
Category: algorithms
Component type: function
Sort_heap is an overloaded name; there are actually two sort_heap functions.
template <class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class StrictWeakOrdering>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp);
Sort_heap turns a heap [1] [first, last) into a sorted range. Note that this is not a stable sort: the relative order of equivalent elements is not guaranteed to be preserved.
The two versions of sort_heap differ in how they define whether one element is less than another. The first version compares objects using operator<, and the second compares objects using a function object comp.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
For the first version, the one that takes two arguments:
• RandomAccessIterator is a model of Random Access Iterator.
• RandomAccessIterator is mutable.
• RandomAccessIterator's value type is a model of LessThan Comparable.
• The ordering on objects of RandomAccessIterator's value type is a strict weak ordering, as defined in the LessThan Comparable requirements.
For the second version, the one that takes three arguments:
• RandomAccessIterator is a model of Random Access Iterator.
• RandomAccessIterator is mutable.
• StrictWeakOrdering is a model of Strict Weak Ordering.
• RandomAccessIterator's value type is convertible to StrictWeakOrdering's argument type.
For the first version, the one that takes two arguments:
• [first, last) is a valid range.
• [first, last) is a heap. That is, is_heap(first, last) is true.
For the second version, the one that takes three arguments:
• [first, last) is a valid range.
• [first, last) is a heap. That is, is_heap(first, last, comp) is true.
At most N * log(N) comparisons, where N is last – first.
int main() {
int A[] = {1, 4, 2, 8, 5, 7};
const int N = sizeof(A) / sizeof(int);
make_heap(A, A+N);
copy(A, A+N, ostream_iterator<int>(cout, " "));
cout << endl;
sort_heap(A, A+N);
copy(A, A+N, ostream_iterator<int>(cout, " "));
cout << endl;
}
[1] A heap is a particular way of ordering the elements in a range of Random Access Iterators [f, l). The reason heaps are useful (especially for sorting, or as priority queues) is that they satisfy two important properties. First, *f is the largest element in the heap. Second, it is possible to add an element to a heap (using push_heap ), or to remove *f, in logarithmic time. Internally, a heap is a tree represented as a sequential range. The tree is constructed so that that each node is less than or equal to its parent node.
push_heap, pop_heap, make_heap, is_heap, sort, stable_sort, partial_sort, partial_sort_copy
Category: algorithms
Component type: function
Is_heap is an overloaded name; there are actually two is_heap functions.
template <class RandomAccessIterator>
bool is_heap(RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class StrictWeakOrdering>
inline bool is_heap(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp)
Is_heap returns true if the range [first, last) is a heap [1], and false otherwise. The two versions differ in how they define whether one element is less than another: the first version compares objects using operator<, and the second compares objects using a function object comp.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h. This function is an SGI extension; it is not part of the C++ standard.
For the first version:
• RandomAccessIterator is a model of Random Access Iterator.
• RandomAccessIterator's value type is a model of LessThan Comparable.
• The ordering on objects of RandomAccessIterator's value type is a strict weak ordering, as defined in the LessThan Comparable requirements.
For the second version:
• RandomAccessIterator is a model of Random Access Iterator.
• StrictWeakOrdering is a model of Strict Weak Ordering.
• RandomAccessIterator's value type is convertible to StrictWeakOrdering's argument type.
• [first, last) is a valid range.
Linear. Zero comparisons if [first, last) is an empty range, otherwise at most (last – first) – 1 comparisons.
int A[] = {1, 2, 3, 4, 5, 6, 7};
const int N = sizeof(A) / sizeof(int);
assert(!is_heap(A, A+N));
make_heap(A, A+N);
assert(is_heap(A, A+N));
[1] A heap is a particular way of ordering the elements in a range of Random Access Iterators [f, l). The reason heaps are useful (especially for sorting, or as priority queues) is that they satisfy two important properties. First, *f is the largest element in the heap. Second, it is possible to add an element to a heap (using push_heap), or to remove *f, in logarithmic time. Internally, a heap is a tree represented as a sequential range. The tree is constructed so that that each node is less than or equal to its parent node.
make_heap, push_heap, pop_heap, sort_heap
Categories: algorithms, utilities
Component type: function
Min is an overloaded name; there are actually two min functions.
template <class T>
const T& min(const T& a, const T& b);
template <class T, class BinaryPredicate>
const T& min(const T& a, const T& b, BinaryPredicate comp);
Min returns the lesser of its two arguments; it returns the first argument if neither is less than the other.
The two versions of min differ in how they define whether one element is less than another. The first version compares objects using operator<, and the second compares objects using the function object comp.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
For the first version:
• T is a model of LessThan Comparable.
For the second version:
• BinaryPredicate is a model of Binary Predicate.
• T is convertible to BinaryPredicate's first argument type and to its second argument type.
const int x = min(3, 9);
assert(x == 3);
max, min_element, max_element, LessThan Comparable
Categories: algorithms, utilities
Component type: function
Max is an overloaded name; there are actually two max functions.
template <class T>
const T& max(const T& a, const T& b);
template <class T, class BinaryPredicate>
const T& max(const T& a, const T& b, BinaryPredicate comp);
Max returns the greater of its two arguments; it returns the first argument if neither is greater than the other.
The two versions of max differ in how they define whether one element is less than another. The first version compares objects using operator<, and the second compares objects using the function object comp.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
For the first version:
• T is a model of LessThan Comparable.
For the second version:
• BinaryPredicate is a model of Binary Predicate.
• T is convertible to BinaryPredicate's first argument type and to its second argument type.
const int x = max(3, 9);
assert(x == 9);
min, min_element, max_element, LessThan Comparable
Category: algorithms
Component type: function
Min_element is an overloaded name; there are actually two min_element functions.
template <class ForwardIterator>
ForwardIterator min_element(ForwardIterator first, ForwardIterator last);
template <class ForwardIterator, class BinaryPredicate>
ForwardIterator min_element(ForwardIterator first, ForwardIterator last, BinaryPredicate comp);
Min_element finds the smallest element in the range [first, last). It returns the first iterator i in [first, last) such that no other iterator in [first, last) points to a value smaller than *i. The return value is last if and only if [first, last) is an empty range.
The two versions of min_element differ in how they define whether one element is less than another. The first version compares objects using operator<, and the second compares objects using a function object comp.
The first version of min_element returns the first iterator i in [first, last) such that, for every iterator j in [first, last), *j < *i is false. The second version returns the first iterator i in [first, last) such that, for every iterator j in [first, last), comp(*j, *i) is false.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
For the first version:
• ForwardIterator is a model of Forward Iterator.
• ForwardIterator's value type is LessThan Comparable.
For the second version:
• ForwardIterator is a model of Forward Iterator.
• BinaryPredicate is a model of Binary Predicate.
• ForwardIterator's value type is convertible to BinaryPredicate's first argument type and second argument type.
• [first, last) is a valid range.
Linear. Zero comparisons if [first, last) is an empty range, otherwise exactly (last – first) – 1 comparisons.
int main() {
list<int> L;
generate_n(front_inserter(L), 1000, rand);
list<int>::const_iterator it = min_element(L.begin(), L.end());
cout << "The smallest element is " << *it << endl;
}
min, max max_element, LessThan Comparable, sort, nth_element
Category: algorithms
Component type: function
Max_element is an overloaded name; there are actually two max_element functions.
template <class ForwardIterator>
ForwardIterator max_element(ForwardIterator first, ForwardIterator last);
template <class ForwardIterator, class BinaryPredicate>
ForwardIterator max_element(ForwardIterator first, ForwardIterator last, BinaryPredicate comp);
Max_element finds the largest element in the range [first, last). It returns the first iterator i in [first, last) such that no other iterator in [first, last) points to a value greater than *i. The return value is last if and only if [first, last) is an empty range.
The two versions of max_element differ in how they define whether one element is less than another. The first version compares objects using operator<, and the second compares objects using a function object comp.
The first version of max_element returns the first iterator i in [first, last) such that, for every iterator j in [first, last), *i < *j is false. The second version returns the first iterator i in [first, last) such that, for every iterator j in [first, last), comp(*i, *j) is false.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
For the first version:
• ForwardIterator is a model of Forward Iterator.
• ForwardIterator's value type is LessThan Comparable.
For the second version:
• ForwardIterator is a model of Forward Iterator.
• BinaryPredicate is a model of Binary Predicate.
• ForwardIterator's value type is convertible to BinaryPredicate's first argument type and second argument type.
• [first, last) is a valid range.
Linear. Zero comparisons if [first, last) is an empty range, otherwise exactly (last – first) – 1 comparisons.
int main() {
list<int> L;
generate_n(front_inserter(L), 1000, rand);
list<int>::const_iterator it = max_element(L.begin(), L.end());
cout << "The largest element is " << *it << endl;
}
min, max, min_element, LessThan Comparable, sort, nth_element
Category: algorithms
Component type: function
Lexicographical_compare is an overloaded name; there are actually two lexicographical_compare functions.
template <class InputIterator1, class InputIterator2>
bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
template <class InputIterator1, class InputIterator2, class BinaryPredicate>
bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, BinaryPredicate comp);
Lexicographical_compare returns true if the range of elements [first1, last1) is lexicographically less than the range of elements [first2, last2), and false otherwise. Lexicographical comparison means "dictionary" (element-by-element) ordering. That is, [first1, last1) is less than [first2, last2) if *first1 is less than *first2 , and greater if *first1 is greater than *first2. If the two first elements are equivalent then lexicographical_compare compares the two second elements, and so on. As with ordinary dictionary order, the first range is considered to be less than the second if every element in the first range is equal to the corresponding element in the second but the second contains more elements.
The two versions of lexicographical_compare differ in how they define whether one element is less than another. The first version compares objects using operator<, and the second compares objects using a function object comp.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
For the first version:
• InputIterator1 is a model of Input Iterator.
• InputIterator2 is a model of Input Iterator.
• InputIterator1's value type is a model of LessThan Comparable.
• InputIterator2's value type is a model of LessThan Comparable.
• If v1 is an object of InputIterator1's value type and v2 is an object of InputIterator2's value type, then both v1 < v2 and v2 < v1 are defined.
For the second version:
• InputIterator1 is a model of Input Iterator.
• InputIterator2 is a model of Input Iterator.
• BinaryPredicate is a model of Binary Predicate.
• InputIterator1's value type is convertible to BinaryPredicate's first argument type and second argument type.
• InputIterator2's value type is convertible to BinaryPredicate's first argument type and second argument type.
• [first1, last1) is a valid range.
• [first2, last2) is a valid range.
Linear. At most 2 * min(last1 – first1, last2 – first2) comparisons.
int main() {
int A1[] = {3, 1, 4, 1, 5, 9, 3};
int A2[] = {3, 1, 4, 2, 8, 5, 7};
int A3[] = {1, 2, 3, 4};
int A4[] = {1, 2, 3, 4, 5};
const int N1 = sizeof(A1) / sizeof(int);
const int N2 = sizeof(A2) / sizeof(int);
const int N3 = sizeof(A3) / sizeof(int);
const int N4 = sizeof(A4) / sizeof(int);
bool C12 = lexicographical_compare(A1, A1 + N1, A2, A2 + N2);
bool C34 = lexicographical_compare(A3, A3 + N3, A4, A4 + N4);
cout << "A1[] < A2[]: " << (C12 ? "true" : "false") << endl;
cout << "A3[] < A4[]: " << (C34 ? "true" : "false") << endl;
}
equal, mismatch, lexicographical_compare_3way, search, LessThan Comparable, Strict Weak Ordering, sort
Category: algorithms
Component type: function
template <class InputIterator1, class InputIterator2>
int lexicographical_compare_3way(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
Lexicographical_compare_3way is essentially a generalization of the function strcmp from the standard C library: it returns a negative number if the range [first1, last1) is lexicographically less than the range [first2, last2), a positive number if [first2, last2) is lexicographically less than [first1, last1), and zero if neither range is lexicographically less than the other. [1]
As with lexicographical_compare, lexicographical comparison means "dictionary" (element-by-element) ordering. That is, lexicographical_compare_3way returns a negative number if *first1 is less than *first2, and a positive number if *first1 is greater than *first2. If the two first elements are equivalent [2] then lexicographical_compare_3way compares the two second elements, and so on. Lexicographical_compare_3way returns 0 only if the two ranges [first1, last1) and [first2, last2) have the same length and if every element in the first range is equivalent to its corresponding element in the second.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h. This function is an SGI extension; it is not part of the C++ standard.
• InputIterator1 is a model of Input Iterator.
• InputIterator2 is a model of Input Iterator.
• InputIterator1's value type is a model of LessThan Comparable.
• InputIterator2's value type is a model of LessThan Comparable.
• If v1 is an object of InputIterator1's value type and v2 is an object of InputIterator2's value type, then both v1 < v2 and v2 < v1 are defined.
• Operator< is a strict weak ordering, as defined in the LessThan Comparable requirements.
• [first1, last1) is a valid range.
• [first2, last2) is a valid range.
Linear. At most 2 * min(last1 – first1, last2 – first2) comparisons.
int main() {
int A1[] = {3, 1, 4, 2, 8, 5, 7};
int A2[] = {3, 1, 4, 1, 5, 9, 3};
int A3[] = {1, 2, 3, 4};
int A4[] = {1, 2, 3, 4, 5};
const int N1 = sizeof(A1) / sizeof(int);
const int N2 = sizeof(A2) / sizeof(int);
const int N3 = sizeof(A3) / sizeof(int);
const int N4 = sizeof(A4) / sizeof(int);
int C12 = lexicographical_compare_3way(A1, A1 + N1, A2, A2 + N2);
int C34 = lexicographical_compare_3way(A3, A3 + N3, A4, A4 + N4);
cout << "A1[] and A2[]: " << C12 << endl;
cout << "A3[] and A4[]: " << C34 << endl;
}
[1] Lexicographical_compare_3way is almost, but not quite, redundant: the call lexicographical_compare_3way(f1,l1, f2,l2) could be written as lexicographical_compare(f1,l1, f2,l2) ? –1 : (lexicographical_compare(f2,l2, f1,l1) ? 1 : 0). The single call to lexicographical_compare_3way, however, is much faster than the two calls to lexicographical_compare.
[2] "Equivalent", not "equal", because two equivalent elements (that is, two elements with the property that neither one is less than the other) are not necessarily equal. Operator< is required to induce a strict weak ordering, not necessarily a total ordering. See the LessThan Comparable requirements for a discussion.
lexicographical_compare, equal, mismatch, search, LessThan Comparable, Strict Weak Ordering, sort
Category: algorithms
Component type: function
Next_permutation is an overloaded name; there are actually two next_permutation functions.
template <class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last);
template <class BidirectionalIterator, class StrictWeakOrdering>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, StrictWeakOrdering comp);
Next_permutation transforms the range of elements [first, last) into the lexicographically next greater permutation of the elements. There is a finite number of distinct permutations (at most N! [1], where N is last – first), so, if the permutations are ordered by lexicographical_compare, there is an unambiguous definition of which permutation is lexicographically next. If such a permutation exists, next_permutation transforms [first, last) into that permutation and returns true. Otherwise it transforms [first, last) into the lexicographically smallest permutation [2] and returns false.
The postcondition is that the new permutation of elements is lexicographically greater than the old (as determined by lexicographical_compare) if and only if the return value is true.
The two versions of next_permutation differ in how they define whether one element is less than another. The first version compares objects using operator<, and the second compares objects using a function object comp.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
For the first version, the one that takes two arguments:
• BidirectionalIterator is a model of Bidirectional Iterator.
• BidirectionalIterator is mutable.
• BidirectionalIterator's value type is LessThan Comparable.
• The ordering relation on BidirectionalIterator's value type is a strict weak ordering, as defined in the LessThan Comparable requirements.
For the second version, the one that takes three arguments:
• BidirectionalIterator is a model of Bidirectional Iterator.
• BidirectionalIterator is mutable.
• StrictWeakOrdering is a model of Strict Weak Ordering.
• BidirectionalIterator's value type is convertible to StrictWeakOrdering's argument type.
• [first, last) is a valid range.
Linear. At most (last – first) / 2 swaps.
This example uses next_permutation to implement the worst known deterministic sorting algorithm. Most sorting algorithms are O(N log(N)), and even bubble sort is only O(N^2) . This algorithm is actually O(N!).
template <class BidirectionalIterator>
void snail_sort(BidirectionalIterator first, BidirectionalIterator last) {
while (next_permutation(first, last)) {};
}
int main() {
int A[] = {8, 3, 6, 1, 2, 5, 7, 4};
const int N = sizeof(A) / sizeof(int);
snail_sort(A, A+N);
copy (A, A+N, ostream_iterator<int>(cout, "\n"));
}
[1] If all of the elements in [first, last) are distinct from each other, then there are exactly N! permutations. If some elements are the same as each other, though, then there are fewer. There are, for example, only three (3!/2!) permutations of the elements 1 1 2.
[2] Note that the lexicographically smallest permutation is, by definition, sorted in nondecreasing order.
prev_permutation, lexicographical_compare, LessThan Comparable, Strict Weak Ordering, sort
Category: algorithms
Component type: function
Prev_permutation is an overloaded name; there are actually two prev_permutation functions.
template <class BidirectionalIterator>
bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last);
template <class BidirectionalIterator, class StrictWeakOrdering>
bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last, StrictWeakOrdering comp);
Prev_permutation transforms the range of elements [first, last) into the lexicographically next smaller permutation of the elements. There is a finite number of distinct permutations (at most N! [1], where N is last – first ), so, if the permutations are ordered by lexicographical_compare, there is an unambiguous definition of which permutation is lexicographically previous. If such a permutation exists, prev_permutation transforms [first, last) into that permutation and returns true. Otherwise it transforms [first, last) into the lexicographically greatest permutation [2] and returns false.
The postcondition is that the new permutation of elements is lexicographically less than the old (as determined by lexicographical_compare) if and only if the return value is true.
The two versions of prev_permutation differ in how they define whether one element is less than another. The first version compares objects using operator<, and the second compares objects using a function object comp.
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
For the first version, the one that takes two arguments:
• BidirectionalIterator is a model of Bidirectional Iterator.
• BidirectionalIterator is mutable.
• BidirectionalIterator's value type is LessThan Comparable.
• The ordering relation on BidirectionalIterator's value type is a strict weak ordering, as defined in the LessThan Comparable requirements.
For the second version, the one that takes three arguments:
• BidirectionalIterator is a model of Bidirectional Iterator.
• BidirectionalIterator is mutable.
• StrictWeakOrdering is a model of Strict Weak Ordering.
• BidirectionalIterator's value type is convertible to StrictWeakOrdering's argument type.
• [first, last) is a valid range.
Linear. At most (last – first) / 2 swaps.
int main() {
int A[] = {2, 3, 4, 5, 6, 1};
const int N = sizeof(A) / sizeof(int);
cout << "Initially: ";
copy (A, A+N, ostream_iterator<int>(cout, " "));
cout << endl;
prev_permutation(A, A+N);
cout << "After prev_permutation: ";
copy (A, A+N, ostream_iterator<int>(cout, " "));
cout << endl;
next_permutation(A, A+N);
cout << "After next_permutation: ";
copy (A, A+N, ostream_iterator<int>(cout, " "));
cout << endl;
}
[1] If all of the elements in [first, last) are distinct from each other, then there are exactly N! permutations. If some elements are the same as each other, though, then there are fewer. There are, for example, only three (3!/2!) permutations of the elements 1 1 2.
[2] Note that the lexicographically greatest permutation is, by definition, sorted in nonascending order.
next_permutation, lexicographical_compare, LessThan Comparable, Strict Weak Ordering, sort
Category: algorithms
Component type: function
template <class ForwardIterator, class T>
void iota(ForwardIterator first, ForwardIterator last, T value);
Iota assigns sequentially increasing values to a range. That is, it assigns value to *first, value + 1 to *(first + 1) and so on. In general, each iterator i in the range [first, last) is assigned value + (i – first). [1]
Defined in the standard header numeric, and in the nonstandard backward-compatibility header algo.h. This function is an SGI extension; it is not part of the C++ standard.
• ForwardIterator is a model of Forward Iterator.
• ForwardIterator is mutable.
• T is Assignable.
• If x is an object of type T, then x++ is defined.
• T is convertible to ForwardIterator's value type.
• [first, last) is a valid range.
Linear. Exactly last – first assignments.
int main() {
vector<int> V(10);
iota(V.begin(), V.end(), 7);
copy(V.begin(), V.end(), ostream_iterator<int>(cout, " "));
cout << endl;
}
[1] The name iota is taken from the programming language APL.
fill, generate, partial_sum
Category: algorithms
Component type: function
Accumulate is an overloaded name; there are actually two accumulate functions.
template <class InputIterator, class T>
T accumulate(InputIterator first, InputIterator last, T init);
template <class InputIterator, class T, class BinaryFunction>
T accumulate(InputIterator first, InputIterator last, T init, BinaryFunction binary_op);
Accumulate is a generalization of summation: it computes the sum (or some other binary operation) of init and all of the elements in the range [first, last). [1]
The function object binary_op is not required to be either commutative or associative: the order of all of accumulate's operations is specified. The result is first initialized to init. Then, for each iterator i in [first, last), in order from beginning to end, it is updated by result = result + *i (in the first version) or result = binary_op(result, *i) (in the second version).
Defined in the standard header numeric, and in the nonstandard backward-compatibility header algo.h.
For the first version, the one that takes two arguments:
• InputIterator is a model of Input Iterator.
• T is a model of Assignable.
• If x is an object of type T and y is an object of InputIterator's value type, then x + y is defined.
• The return type of x + y is convertible to T.
For the second version, the one that takes three arguments:
• InputIterator is a model of Input Iterator.
• T is a model of Assignable.
• BinaryFunction is a model of Binary Function.
• T is convertible to BinaryFunction's first argument type.
• The value type of InputIterator is convertible to BinaryFunction's second argument type.
• BinaryFunction's return type is convertible to T.
• [first, last) is a valid range.
Linear. Exactly last – first invocations of the binary operation.
int main() {
int A[] = {1, 2, 3, 4, 5};
const int N = sizeof(A) / sizeof(int);
cout << "The sum of all elements in A is " << accumulate(A, A + N, 0) << endl;
cout << "The product of all elements in A is " << accumulate(A, A + N, 1, multiplies<int>()) << endl;
}
[1] There are several reasons why it is important that accumulate starts with the value init. One of the most basic is that this allows accumulate to have a well-defined result even if [first, last) is an empty range: if it is empty, the return value is init. If you want to find the sum of all of the elements in [first, last), you can just pass 0 as init.
inner_product, partial_sum, adjacent_difference, count
Category: algorithms
Component type: function
Inner_product is an overloaded name; there are actually two inner_product functions.
template <class InputIterator1, class InputIterator2, class T>
T inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init);
template <class InputIterator1, class InputIterator2, class T, class BinaryFunction1, class BinaryFunction2>
T inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init, BinaryFunction1 binary_op1, BinaryFunction2 binary_op2);
Inner_product calculates a generalized inner product of the ranges [first1, last1) and [first2, last2).
The first version of inner_product returns init plus the inner product of the two ranges [1]. That is, it first initializes the result to init and then, for each iterator i in [first1, last1) , in order from the beginning to the end of the range, updates the result by result = result + (*i) * *(first2 + (i – first1)).
The second version of inner_product is identical to the first, except that it uses two user-supplied function objects instead of operator+ and operator*. That is, it first initializes the result to init and then, for each iterator i in [first1, last1), in order from the beginning to the end of the range, updates the result by result = binary_op1(result, binary_op2(*i, *(first2 + (i – first1))). [2]
Defined in the standard header numeric, and in the nonstandard backward-compatibility header algo.h.
For the first version:
• InputIterator1 is a model of Input Iterator.
• InputIterator2 is a model of Input Iterator.
• T is a model of Assignable.
• If x is an object of type T, y is an object of InputIterator1's value type, and z is an object of InputIterator2's value type, then x + y * z is defined.
• The type of x + y * z is convertible to T.
For the second version:
• InputIterator1 is a model of Input Iterator.
• InputIterator2 is a model of Input Iterator.
• T is a model of Assignable.
• BinaryFunction1 is a model of Binary Function.
• BinaryFunction2 is a model of Binary Function.
• InputIterator1's value type is convertible to BinaryFunction2's first argument type.
• InputIterator2's value type is convertible to BinaryFunction2's second argument type.
• T is convertible to BinaryFunction1's first argument type.
• BinaryFunction2's return type is convertible to BinaryFunction1's second argument type.
• BinaryFunction1's return type is convertible to T.
• [first1, last1) is a valid range.
• [first2, first2 + (last1 – first1)) is a valid range.
Linear. Exactly last1 – first1 applications of each binary operation.
int main() {
int A1[] = {1, 2, 3};
int A2[] = {4, 1, –2};
const int N1 = sizeof(A1) / sizeof(int);
cout << "The inner product of A1 and A2 is " << inner_product(A1, A1 + N1, A2, 0) << endl;
}
[1] There are several reasons why it is important that inner_product starts with the value init. One of the most basic is that this allows inner_product to have a well-defined result even if [first1, last1) is an empty range: if it is empty, the return value is init. The ordinary inner product corresponds to setting init to 0.
[2] Neither binary operation is required to be either associative or commutative: the order of all operations is specified.
accumulate, partial_sum, adjacent_difference, count
Category: algorithms
Component type: function
Partial_sum is an overloaded name; there are actually two partial_sum functions.
template <class InputIterator, class OutputIterator>
OutputIterator partial_sum(InputIterator first, InputIterator last, OutputIterator result);
template <class InputIterator, class OutputIterator, class BinaryOperation>
OutputIterator partial_sum(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op);
Partial_sum calculates a generalized partial sum: *first is assigned to *result, the sum of *first and *(first + 1) is assigned to *(result + 1), and so on. [1]
More precisely, a running sum is first initialized to *first and assigned to *result. For each iterator i in [first + 1, last), in order from beginning to end, the sum is updated by sum = sum + *i (in the first version) or sum = binary_op(sum, *i) (in the second version) and is assigned to *(result + (i – first)). [2]
Defined in the standard header numeric, and in the nonstandard backward-compatibility header algo.h.
For the first version:
• InputIterator is a model of Input Iterator.
• OutputIterator is a model of Output Iterator.
• If x and y are objects of InputIterator's value type, then x + y is defined.
• The return type of x + y is convertible to InputIterator's value type.
• InputIterator's value type is convertible to a type in OutputIterator's set of value types.
For the second version:
• InputIterator is a model of Input Iterator.
• OutputIterator is a model of Output Iterator.
• BinaryFunction is a model of BinaryFunction.
• InputIterator's value type is convertible to BinaryFunction's first argument type and second argument type.
• BinaryFunction's result type is convertible to InputIterator's value type.
• InputIterator's value type is convertible to a type in OutputIterator's set of value types.
• [first, last) is a valid range.
• [result, result + (last – first)) is a valid range.
Linear. Zero applications of the binary operation if [first, last) is a empty range, otherwise exactly (last – first) – 1 applications.
int main() {
const int N = 10;
int A[N];
fill(A, A+N, 1);
cout << "A: ";
copy(A, A+N, ostream_iterator<int>(cout, " "));
cout << endl;
cout << "Partial sums of A: ";
partial_sum(A, A+N, ostream_iterator<int>(cout, " "));
cout << endl;
}
[1] Note that result is permitted to be the same iterator as first. This is useful for computing partial sums "in place".
[2] The binary operation is not required to be either associative or commutative: the order of all operations is specified.
adjacent_difference, accumulate, inner_product, count
Category: algorithms
Component type: function
Adjacent_difference is an overloaded name; there are actually two adjacent_difference functions.
template <class InputIterator, class OutputIterator>
OutputIterator adjacent_difference(InputIterator first, InputIterator last, OutputIterator result);
template <class InputIterator, class OutputIterator, class BinaryFunction>
OutputIterator adjacent_difference(InputIterator first, InputIterator last, OutputIterator result, BinaryFunction binary_op);
Adjacent_difference calculates the differences of adjacent elements in the range [first, last). This is, *first is assigned to *result[1], and, for each iterator i in the range [first + 1, last), the difference of *i and *(i – 1) is assigned to *(result + (i – first)). [2]
The first version of adjacent_difference uses operator- to calculate differences, and the second version uses a user-supplied binary function. In the first version, for each iterator i in the range [first + 1, last), *i – *(i – 1) is assigned to *(result + (i – first)). In the second version, the value that is assigned to *(result + 1) is instead binary_op(*i, *(i – 1)).
Defined in the standard header numeric, and in the nonstandard backward-compatibility header algo.h.
For the first version:
• ForwardIterator is a model of Forward Iterator.
• OutputIterator is a model of Output Iterator.
• If x and y are objects of ForwardIterator's value type, then x – y is defined.
• InputIterator's value type is convertible to a type in OutputIterator's set of value types.
• The return type of x – y is convertible to a type in OutputIterator's set of value types. For the second version:
• ForwardIterator is a model of Forward Iterator.
• OutputIterator is a model of Output Iterator.
• BinaryFunction is a model of Binary Function.
• InputIterator's value type is convertible to a BinaryFunction's first argument type and second argument type.
• InputIterator's value type is convertible to a type in OutputIterator's set of value types.
• BinaryFunction's result type is convertible to a type in OutputIterator's set of value types.
• [first, last) is a valid range.
• [result, result + (last – first)) is a valid range.
Linear. Zero applications of the binary operation if [first, last) is an empty range, otherwise exactly (last – first) – 1 applications.
int main() {
int A[] = {1, 4, 9, 16, 25, 36, 49, 64, 81, 100};
const int N = sizeof(A) / sizeof(int);
int B[N];
cout << "A[]: ";
copy(A, A + N, ostream_iterator<int>(cout, " "));
cout << endl;
adjacent_difference(A, A + N, B);
cout << "Differences: ";
copy(B, B + N, ostream_iterator<int>(cout, " "));
cout << endl;
cout << "Reconstruct: ";
partial_sum(B, B + N, ostream_iterator<int>(cout, " "));
cout << endl;
}
[1] The reason it is useful to store the value of the first element, as well as simply storing the differences, is that this provides enough information to reconstruct the input range. In particular, if addition and subtraction have the usual arithmetic definitions, then adjacent_difference and partial_sum are inverses of each other.
[2] Note that result is permitted to be the same iterator as first. This is useful for computing differences "in place".
partial_sum, accumulate, inner_product, count
Category: algorithms
Component type: function
Power is an overloaded name; there are actually two power functions.
template <class T, class Integer>
inline T power(T x, Integer n);
template <class T, class Integer, class MonoidOperation>
T power(T x, Integer n, MonoidOperation op);
Power is generalized exponentiation: it raises the value x to the power n, where n is a non-negative integer.
The first version of power returns x raised to the nth power; that is, it returns x * x … * x , where x is repeated n times. [1] If n == 0, then it returns identity_element(multiplies<T>()).
The second version of power is just like the first except that it uses an arbitrary Monoid Operation instead of multiplies<T>, returning identity_element(op) when n == 0.
Important note: power does not assume that multiplication is commutative, but it does rely crucially on the fact that multiplication is associative. If you have defined * or MonoidOperation to be a non-associative operation, then powerwill give you the wrong answer. [2]
Defined in the standard header numeric, and in the nonstandard backward-compatibility header algo.h. This function is an SGI extension; it is not part of the C++ standard.
For the first version:
• multiplies<T> is a model of Monoid Operation.
• Integer is an integral type.
For the second version:
• MonoidOperation is a model of Monoid Operation.
• T is MonoidOperation's argument type.
• n is an integral type.
• n >= 0.
The number of multiplications (or, in the case of the second version, the number of applications of MonoidOperation ) is lg(n) + nu(n) where lg is the base 2 logarithm and nu(n) is the number of 1s in the binary representation of n. [3]
int main() {
cout << "2 ** 30 = " << power(2, 30) << endl;
}
[1] This is a conceptual description of what power's return value is; it is not how power is actually implemented. If power were implemented that way then it would require n-1 multiplications, which would be grossly inefficient. Power is implemented using the "Russian peasant algorithm", which requires only O(log n) multiplications. See section 4.6.3 of Knuth (D. E. Knuth, The Art of Computer Programming. Volume 2: Seminumerical Algorithms, Addison-Wesley, 1981) for a discussion.
[2] See the Monoid Operation requirements for a discussion of associativity.
[3] This is in fact not the minimum possible number of multiplications: it is possible to compute the fifteenth power of x using only five multiplications, but power(x, 15) uses six.
Monoid Operation, multiplies, plus