| CONTENTS | |
The STL aims to provide efficient implementations of common algorithms. It expresses these algorithms in general functions that can be used with any container satisfying the requirements for the particular algorithm and in methods that can be used with instantiations of particular container classes. This appendix assumes that you have some familiarity with the STL, such as might be gained from reading Chapter 16, "The string Class and the Standard Template Library." For example, this chapter assumes you know about iterators and constructors.
All containers define the types in Table G.1. In this table, X is a container type, such as vector<int>, and T is the type stored in the container, such as int.
| Type | Value |
|---|---|
| X::value_type | T, the element type |
| X::reference | Behaves like T & |
| X::const_reference | Behaves like const T & |
| X::iterator | Iterator type pointing to T, behaves like T * |
| X::const_iterator | Iterator type pointing to const T, behaves like const T * |
| X::difference_type | Signed integral type used to represent the distance from one iterator to another; for example, the difference between two pointers |
| X::size_type | Unsigned integral type size_type can represent size of data objects, number of elements, and subscripts |
The class definition will use a typedef to define these members. You can use these types, to declare suitable variables. For example, the following takes a roundabout way to replace the first occurrence of "bonus" in a vector of string objects with "bogus" in order to show how you can use member types to declare variables.
vector<string> input;
string temp;
while (cin >> temp && temp != "quit")
input.push_back(temp);
vector<string>::iterator want=
find(input.begin(), input.end(), string("bonus"));
if (want != input.end())
{
vector<string>::reference r = *want;
r = "bogus";
}
This code makes r a reference to the element in input to which want points.
These types also can be used in more general code in which the type of container and element are generic. For example, suppose you want a min() function that takes as its argument a reference to a container and returns the smallest item in the container. This assumes that the < operator is defined for the value type and that you don't want to use the STL min_element() algorithm, which uses an iterator interface. Because the argument could be vector<int> or list<string> or deque<double>, use a template with a template parameter, such as Bag, to represent the container. So the argument type for the function will be const Bag & b. What about the return type? It should be the value type for the container, that is, Bag::value_type. However, at this point, Bag is just a template parameter, and the compiler has no way of knowing that the value_type member is actually a type. But you can use the typename keyword to clarify that a class member is a typedef:
vector<string>::value_type st; // vector<string> a defined class typename Bag::value_type m; // Bag an as yet undefined type
For the first definition, the compiler has access to the vector template definition, which states that value_type is a typedef. For the second definition, the typename keyword promises that the combination Bag::value_type is a typedef. These considerations lead to the following definition:
template<typename Bag>
typename Bag::value_type min(const Bag & b)
{
typename Bag::const_iterator it;
typename Bag::value_type m = *b.begin();
for (it = b.begin(); it != b.end(); ++it)
if (*it < m)
m = *it;
return m;
}
You then could use this template function as follows:
vector<int> temperatures; // input temperature values into the vector int coldest = min(temperatures);
The temperatures parameter would cause Bag to be evaluated as vector<int> and typename Bag::value_type to be evaluated as int.
All containers also contain the member functions or operations listed in Table G.2. Again, X is a container type, such as vector<int>, and T is the type stored in the container, such as int. Also, a and b are values of type X.
| Method/Operation | Description |
|---|---|
| begin() | Returns an iterator to the first element |
| end() | Returns an iterator to past-the-end |
| rbegin() | Returns a reverse iterator to past-the-end |
| rend() | Returns a reverse iterator to first element |
| size() | Returns number of elements |
| maxsize() | Returns the size of the largest possible container |
| empty() | Returns true if the container is empty |
| swap() | Swaps the contents of two containers |
| == | Returns true if two containers are the same size and have the same elements in the same order |
| != | a != b is the same as !(a == b) |
| < | Returns true if a lexicographically precedes b |
| > operator>> | a > b is the same as b < a |
| <= | a <= b is the same as !(a > b) |
| >== operator>=> | a >= b is the same as !(a < b) |
The > operator for a container assumes that the > operator is defined for the value type. A lexicographical comparison is a generalization of alphabetical sorting. It compares two containers element by element until encountering an element in one container that doesn't equal the corresponding element in the other container. In that case, the containers are considered to be in the same order as the non-corresponding pair of elements. For example, if two containers are identical through the first ten elements, but the eleventh element in the first container is less than the eleventh element in the second container, the first container precedes the second. If two containers compare equal until one runs out of elements, the shorter container precedes the longer.
Vectors, lists, and deques are all sequences, and they all have the methods listed in Table G.3. Again, X is a container type, such as vector<int>, and T is the type stored in the container, such as int, a is a value of type X, t is a value of type X::value_type, i and j are input iterators, q2 and p are iterators, q and q1 are dereferenceable iterators (you can apply the * operator to them), and n is an integer of X::size_type.
| Method | Description |
|---|---|
| a.insert(p,t) | Inserts a copy of t before p; returns an iterator pointing to the inserted copy of t. The default value for t is T(), that is, the value used for type T in the absence of explicit initialization. |
| a.insert(p,n,t) | Inserts n copies of t before p; no return value. |
| a.insert(p,i,j) | Inserts copies of the elements in range [i,j) before p, no return value. |
| a.resize(n,t) | If n > a.size(), inserts n - a.size() copies of t before a.end(); t has a default value of T(), that is, the value used for type T in the absence of explicit initialization. If n < a.size(), the elements following the nth element are erased. |
| a.assign(i,j) | Replaces the current contents of a with copies of the elements in range [i,j). |
| a.assign(n,t) | Replaces the current contents of a with n copies of t. The default value for t is T(),the value used for type T in the absence of explicit initialization. |
| a.erase(q) | Erases the element pointed to by q; returns an iterator to the element that had followed q. |
| a.erase(q1,q2) | Erases the elements in the range [q1,q2); returns an iterator pointing to the element q2 originally pointed to. |
| a.clear() | Same as erase(a.begin(), a.end()). |
| a.front() | Returns *a.begin() (the first element). |
| a.back() | Returns *--a.end() (the last element). |
| a.push_back(t) | Inserts t before a.end(). |
| a.pop_back() | Erases the last element. |
Table G.4 lists methods common to two out of the three sequence classes.
| Method | Description | Container |
|---|---|---|
| a.push_front(t) | Inserts a copy of t before the first element. | list, deque |
| a.pop_front() | Erases the first element. | list, deque |
| a[n] | Returns *(a.begin() + n). | vector, deque |
| a.at(n) | Returns *(a.begin() + n), throws out_of_range exception if n > a.size(). | vector, deque |
The vector template additionally has the methods in Table G.5. Here, a is a vector container and n is an integer of X::size_type.
| Method | Description |
|---|---|
| a.capacity() | Returns the total number of elements the vector can hold without requiring reallocation. |
| a.reserve(n) | Alerts object a that memory for at least n elements is needed. After the method call, the capacity will be at least n elements. Reallocation occurs if n is greater than the current capacity. If n is greater than a.max_size(), the method throws a length_error exception. |
The list template additionally has the methods in Table G.6. Here, a and b are list containers, and T is the type stored in the list, such as int, t is a value of type T, i and j are input iterators, q2 and p are iterators, q and q1 are dereferenceable iterators, and n is an integer of X::size_type. The table uses the standard STL notation of [i, j) meaning the range from i up to, but not including j.
| Method | Description |
|---|---|
| a.splice(p,b) | Moves the contents of list b to list a, inserting them before p. |
| a.splice(p,b,i) | Moves the element in list b pointed to by i to before position p in list a. |
| a.splice(p,b,i,j) | Moves the elements in range [i,j) of list b to before position p in list a. |
| a.remove(const T& t) | Erases all elements in list a having the value t. |
| a.remove_if(Predicate pred) | Given that i is an iterator into the list a, erases all values for which pred(*i) is true. (A Predicate is a Boolean function or function object, as discussed in Chapter 15, "Friends, Exceptions, and More.") |
| a.unique() | Erases all but the first element from each group of consecutive equal elements. |
| a.unique(BinaryPredicate bin_pred) | Erases all but the first element from each group of consecutive elements for which bin_pred(*i, * (i - 1)) is true. (A BinaryPredicate is a Boolean function or function object, as discussed in Chapter 15.) |
| a.merge(b) | Merges the contents of list b with list a using the < operator defined for the value type. If an element in a is equivalent to an element in b, the element from a is placed first. List b is empty after the merge. |
| a.merge(b, Compare comp) | Merges the contents of list b with list a using the comp function or function object. If an element in a is equivalent to an element in b, the element from a is placed first. List b is empty after the merge. |
| a.sort() | Sorts list a using the < operator. |
| a.sort(Compare comp) | Sorts list a using the comp function or function object. |
| a.reverse() | Reverses the order of the elements in list a. |
Associative containers, of which sets and maps are models, have a Key template parameter and a Compare template parameter indicating, respectively, the type of the key used to order the contents and the function object, termed a comparison object, used to compare key values. For the set and multiset containers, the stored keys are the stored values, so the key type is the same as the value type. For the map and multimap containers, the stored values of one type (template parameter T) are associated with a key type (template parameter Key), and the value type is pair<const Key, T>. Associative containers introduce additional members to describe these features, as listed in Table G.7.
| Type | Value |
|---|---|
| X::key_type | Key, the key type |
| X::key_compare | Compare, which has a default value of less<key_type> |
| X::value_compare | A binary predicate type that is the same as key_compare for set and multiset and which supplies ordering for the pair<const Key, T> values in a map or multimap. |
| X::mapped_type | T, the type of the associated data (map and multimap only) |
Associative containers provide the methods listed in Table G.8. In general, the comparison object need not require that values with the same key are identical; the term equivalent keys means that two values, which may or may not be equal, have the same key. In the table, X is a container class, a is an object of type X. If X uses unique keys (that is, is a set or map), a_uniq is an object of type X. If X uses multiple keys (that is, is a multiset or multimap), a_eq is an object of type X. As before, i and j are input iterators referring to elements of value_type, [i, j) is a valid range, p and q2 are iterators to a, q and q1 are dereferenceable iterators to a, [q1, q2) is a valid range, t is a value of X::value_type (which may be a pair). Also, k is a value of X::key_type.
| Method | Description |
|---|---|
| a.key_comp() | Returns the comparison object used in constructing a. |
| a.value_comp() | Returns an object of the value_compare type. |
| a_uniq.insert(t) | Inserts the value t into the container a if and only if a does not yet contain a value with an equivalent key. The method returns a value of type pair<iterator,bool>. The bool component is true if insertion occurred and false otherwise. The iterator component points to the element whose key is equivalent to the key of t. |
| a_eq.insert(t) | Inserts t and returns an iterator pointing to its location. |
| a.insert(p,t) | Inserts t using p as a hint to where insert() should begin its search. If a is a container with unique keys, insertion takes place if and only if a doesn't contain an element with an equivalent key; otherwise, insertion takes place. Whether or not insertion takes place, the method returns an iterator pointing to the location with an equivalent key. |
| a.insert(i,j) | Inserts elements from the range [i,j) into a. |
| a.erase(k) | Erases all elements in a whose keys are equivalent to k and returns the number of elements erased. |
| a.erase(q) | Erases the element pointed to by q. |
| a.erase(q1,q2) | Erases the elements in the range [q1,q2). |
| a.clear() | Same as erase(a.begin(), a.end()). |
| a.find(k) | Returns an iterator pointing to an element whose key is equivalent to k; returns a.end() if no such element is found. |
| a.count(k) | Returns the number of elements having keys equivalent to k. |
| a.lower_bound(k) | Returns an iterator to the first element with a key not less than k. |
| a.upper_bound(k) | Returns an iterator to the first element with a key greater than k. |
| a.equal_range(k) | Returns a pair whose first member is a.lower_bound(k) and whose second member is a.upper_bound(k). |
| a.operator[](k) | Returns a reference to the value associated with the key k (map containers only). |
The STL algorithm library, supported by the algorithm and numeric header files, provides a large number of non-member, iterator-based template functions. As discussed in Chapter 16, the template parameter names are chosen to indicate what concept particular parameters should model. For example, ForwardIterator is used to indicate that a parameter should, at the minimum, model the requirements of a forward iterator, and Predicate is used to indicate a parameter that should be a function object with one argument and a bool return value. The standard divides the algorithms into four groups: non-modifying sequence operations, mutating sequence operations, sorting and related operators, and numeric operations. The term sequence operation indicates the function takes a pair of iterators as arguments to define a range, or sequence, to be operated upon. The term mutating means the function is allowed to alter the container.
Table G.9 summarizes the non-modifying sequence operations. Arguments are not shown, and overloaded functions are listed just once. A fuller description including the prototypes follows the table. Thus, you can scan the table to get an idea of what a function does and then look up the details if you find the function appealing.
| Function | Description |
|---|---|
| for_each() | Applies a non-modifying function object to each element in a range. |
| find() | Finds the first occurrence of a value in a range. |
| find_if() | Finds the first value satisfying a predicate test criterion in a range. |
| find_end() | Finds the last occurrence of a subsequence whose values match the values of a second sequence. Matching may be by equality or by applying a binary predicate. |
| find_first_of() | Finds the first occurrence of any element of a second sequence that matches a value in the first sequence. Matching may be by equality or be evaluated with a binary predicate. |
| adjacent_find() | Finds the first element that matches the element immediately following it. Matching may be by equality or be evaluated with a binary predicate. |
| count() | Returns the number of times a given value occurs in a range. |
| count_if() | Returns the number of times a given value matches values in a range, with a match determined by using a binary predicate. |
| mismatch() | Finds the first element in one range that does not match the corresponding element in a second range and returns iterators to both. Matching may be by equality or be evaluated with a binary predicate. |
| equal() | Returns true if each element in one range matches the corresponding element in a second range. Matching may be by equality or be evaluated with a binary predicate. |
| search() | Finds the first occurrence of a subsequence whose values match the values of a second sequence. Matching may be by equality or by applying a binary predicate. |
| search_n() | Finds the first subsequence of n elements that each match a given value. Matching may be by equality or by applying a binary predicate. |
Now let's look at the prototypes. Pairs of iterators indicate ranges, with the chosen template parameter name indicating the type of iterator. As usual a range of the form [first, last) goes from first up to, but not including last. Some functions take two ranges, which need not be in the same kind of container. For example, you can use equal() to compare a list to a vector. Functions passed as arguments are function objects, which can be pointers (of which function names are an example) or objects for which the () operation is defined. As in Chapter 16, a predicate is a Boolean function with one argument, and a binary predicate is a Boolean function with two arguments. (The functions need not be type bool as long as they return a 0 value for false and a non-zero for true.)
template<class InputIterator, class Function> Function for_each(InputIterator first, InputIterator last, Function f);
The for_each() function applies function object f to each element in the range [first, last). It also returns f.
template<class InputIterator, class T> InputIterator find(InputIterator first, InputIterator last, const T& value);
The find() function returns an iterator to the first element in the range [first, last) that has the value value; it returns last if the item is not found.
template<class InputIterator, class Predicate>
InputIterator find_if(InputIterator first, InputIterator last,
Predicate pred);
The find_if() function returns an iterator it to the first element in the range [first, last) for which the function object call pred(*i) is true; it returns last if the item is not found.
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 pred);
The find_end() function returns an iterator it to the last element in the range [first1, last1) that marks the beginning of a subsequence that matches the contents of the range [first2, last2). The first version uses the == operator for the value type to compare elements. The second version uses the binary predicate function object pred to compare elements. That is, elements pointed to by it1 and it2 match if pred(*it1, *it2) is true. Both return last1 if the item is not found.
template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 find_first_of(
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);
template<class ForwardIterator1, class ForwardIterator2,
class BinaryPredicate>
ForwardIterator1 find_first_of(
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
BinaryPredicate pred);
The find_first_of() function returns an iterator it to the first element in the range [first1, last1) that matches any element of the range [first2, last2). The first version uses the == operator for the value type to compare elements. The second version uses the binary predicate function object pred to compare elements. That is, elements pointed to by it1 and it2 match if pred(*it1, *it2) is true. Both return last1 if the item is not found.
template<class ForwardIterator>
ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class BinaryPredicate>
ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last,
BinaryPredicate pred);
The adjacent_find() function returns an iterator it to the first element in the range [first1, last1) such that the element matches the following element. The function returns last if no such pair is found. The first version uses the == operator for the value type to compare elements. The second version uses the binary predicate function object pred to compare elements. That is, elements pointed to by it1 and it2 match if pred(*it1, *it2) is true.
template<class InputIterator, class T>
iterator_traits<InputIterator>::difference_type count(
InputIterator first, InputIterator last, const T& value);
The count() function returns the number of elements in the range [first, last) that match the value value. The == operator for the value type is used to compare values. The return type is an integer type large enough to contain the maximum number of items the container can hold.
template<class InputIterator, class Predicate>
iterator_traits<InputIterator>::difference_type count_if(
InputIterator first, InputIterator last, Predicate pred);
The count if() function returns the number of elements in the range [first, last) for which the function object pred returns a true value when passed the element as an argument.
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 pred);
Each of the mismatch() functions finds the first element in range [first1, last1) that doesn't match the corresponding element in the range beginning at first2 and returns a pair holding iterators to the two mismatching elements. If no mismatch is found, the return value is pair<last1, first2 + (last1 - first1)>. The first version uses the == operator to test matching. The second version uses the binary predicate function object pred to compare elements. That is, elements pointed to by it1 and it2 don't match if pred(*it1, *it2) is false.
template<class InputIterator1, class InputIterator2>
bool equal(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2);
template<class InputIterator1, class InputIterator2, class BinaryPredicate>
bool equal(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, BinaryPredicate pred);
The equal() function returns true if each element in the range [first1, last1) matches the corresponding element in the sequence beginning at first2 and false otherwise. The first version uses the == operator for the value type to compare elements. The second version uses the binary predicate function object pred to compare elements. That is, elements pointed to by it1 and it2 match if pred(*it1, *it2) is true.
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 pred);
The search() function finds the first occurrence in the range [first1, last1) that matches the corresponding sequence found in range [first2, last2). It returns last1 if no such sequence is found. The first version uses the == operator for the value type to compare elements. The second version uses the binary predicate function object pred to compare elements. That is, elements pointed to by it1 and it2 match if pred(*it1, *it2) is true.
template<class ForwardIterator, class Size, class T>
ForwardIterator search_n(ForwardIterator first, ForwardIterator last,
Size count, const T& value);
template<class ForwardIterator, class Size, class T, class BinaryPredicate>
ForwardIterator search_n(ForwardIterator first, ForwardIterator last,
Size count, const T& value, BinaryPredicate pred);
The search_n() function finds the first occurrence in the range [first1, last1) that matches the sequence consisting of count consecutive occurrences of value. It returns last1 if no such sequence is found. The first version uses the == operator for the value type to compare elements. The second version uses the binary predicate function object pred to compare elements. That is, elements pointed to by it1 and it2 match if pred(*it1, *it2) is true.
Table G.10 summarizes the mutating sequence operations. Arguments are not shown, and overloaded functions are listed just once. A fuller description including the prototypes follows the table. Thus, you can scan the table to get an idea of what a function does; then look up the details if you find the function appealing.
| Function | Description |
|---|---|
| copy() | Copies elements from a range to a location identified by an iterator. |
| copy_backward() | Copies elements from a range to a location identified by an iterator. Copying begins at the end of the range and proceeds backwards. |
| swap() | Exchanges two values stored at locations specified by references. |
| swap_ranges() | Exchanges corresponding values in two ranges. |
| iter_swap() | Exchanges two values stored at locations specified by iterators. |
| transform() | Applies a function object to each element in a range (or to each pair of elements in a pair of ranges), copying the return value to the corresponding location of another range. |
| replace() | Replaces each occurrence of a value in a range with another value. |
| replace_if() | Replaces each occurrence of a value in a range with another value if a predicate function object applied to the original value returns true. |
| replace_copy() | Copies one range to another, replacing each occurrence of a specified value with another value. |
| replace_copy_if() | Copies one range to another, replacing each value for which a predicate function object is true with an indicated value. |
| fill() | Sets each value in a range to an indicated value. |
| fill_n() | Sets n consecutive elements to a value. |
| generate() | Sets each value in a range to the return value of a generator, which is a function object that takes no arguments. |
| generate_n() | Sets the first n values in a range to the return value of a generator, which is a function object that takes no arguments. |
| remove() | Removes all occurrences of an indicated value from a range and returns a past-the-end iterator for the resulting range. |
| remove_if() | Removes all occurrences of values for which a predicate object returns true from a range and returns a past-the-end iterator for the resulting range. |
| remove_copy() | Copies elements from one range to another, omitting elements that equal a specified value. |
| remove_copy_if() | Copies elements from one range to another, omitting elements for which a predicate function object returns true. |
| unique() | Reduces each sequence of two or more equivalent elements in a range to a single element. |
| unique_copy() | Copies elements from one range to another, reducing each sequence of two or more equivalent elements to one. |
| reverse() | Reverses the elements in a range. |
| reverse_copy() | Copies a range in reverse order to a second range. |
| rotate() | Treats a range as a circular ordering and rotates the elements left. |
| rotate_copy() | Copies one range to another in a rotated order. |
| random_shuffle() | Randomly rearranges the elements in a range. |
| partition() | Places all the elements that satisfy a predicate function object before all elements that don't. |
| stable_partition() | Places all the elements that satisfy a predicate function object before all elements that don't. The relative order of elements in each group is preserved. |
Now let's go to the prototypes. As you saw earlier, pairs of iterators indicate ranges, with the chosen template parameter name indicating the type of iterator. As usual a range of the form [first, last) goes from first up to, but not including last. Functions passed as arguments are function objects, which can be function pointers or objects for which the () operation is defined. As in Chapter 16, a predicate is a Boolean function with one argument, and a binary predicate is a Boolean function with two arguments. (The functions need not be type bool as long as they return a 0 value for false and a non-zero for true.) Also, as in Chapter 15, a unary function object is one taking a single argument, and a binary function object is one taking two arguments.
template<class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last,
OutputIterator result);
The copy() function copies the elements in the range [first, last) into the range [result, result + (last - first)). It returns result + (last - first), that is, an iterator pointing one past the last copied-to location. The function requires that result not be in the range [first, last), that is, the target can't overlap the source.
template<class BidirectionalIterator1, class BidirectionalIterator2>
BidirectionalIterator2 copy_backward(BidirectionalIterator1 first,
BidirectionalIterator1 last, BidirectionalIterator2 result);
The copy_backward() function copies the elements in the range [first, last) into the range [result -(last - first), result). Copying begins with the element at last -1 being copied to location result - 1, and proceeds backwards from there to first. It returns result - (last - first), that is, an iterator pointing one past the last copied-to location. The function requires that result not be in the range [first, last). However, because copying is done backwards, it is possible for the target and source to overlap.
template<class T> void swap(T& a, T& b);
The swap() function exchanges values stored at two locations specified by references.
template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator2 swap_ranges(
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2);
The swap_ranges() function exchanges values in the range [first1, last1) with the corresponding values in the range beginning at first2. The two ranges should not overlap.
template<class ForwardIterator1, class ForwardIterator2> void iter_swap(ForwardIterator1 a, ForwardIterator2 b);
The iter_swap() function exchanges values stored at two locations specified by iterators.
template<class InputIterator, class OutputIterator, class UnaryOperation> OutputIterator transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op);
This version of transform() applies the unary function object op to each element in the range [first, last) and assigns the return value to the corresponding element in the range beginning at result. So *result is set to op(*first), and so on. It returns result + (last - first), that is, the past-the-end value for the target range.
template<class InputIterator1, class InputIterator2, class OutputIterator,
class BinaryOperation>
OutputIterator transform(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, OutputIterator result,
BinaryOperation binary_op);
This version of transform() applies the binary function object op to each element in the range [first1, last1) and to each element in the range [first2, last2) and assigns the return value to the corresponding element in the range beginning at result. So *result is set to op(*first1, *first2), and so on. It returns result + (last - first), the past-the-end value for the target range.
template<class ForwardIterator, class T>
void replace(ForwardIterator first, ForwardIterator last,
const T& old_value, const T& new_value);
The replace() function replaces each occurrence of the value old_value in the range [first, last) with the value new_value.
template<class ForwardIterator, class Predicate, class T>
void replace_if(ForwardIterator first, ForwardIterator last,
Predicate pred, const T& new_value);
The replace()_if function replaces each value old in the range [first, last) for which pred(old) is true with the value new_value.
template<class InputIterator, class OutputIterator, class T>
OutputIterator replace_copy(InputIterator first, InputIterator last,
OutputIterator result,const T& old_ value, const T& new_ value);
The replace_copy() function copies the elements in the range [first, last) to a range beginning at result, but substituting new_value for each occurrence of old_value. It returns result + (last - first), the past-the-end value for the target range.
template<class Iterator, class OutputIterator, class Predicate, class T>
OutputIterator replace_copy_if(Iterator first, Iterator last,
OutputIterator result, Predicate pred, const T& new_ value);
The replace_copy_if() function copies the elements in the range [first, last) to a range beginning at result, but substituting new_value for each value old for which pred(old) is true. It returns result + (last - first), the past-the-end value for the target range.
template<class ForwardIterator, class T> void fill(ForwardIterator first, ForwardIterator last, const T& value);
The fill() function sets each element in the range [first, last) to value.
template<class OutputIterator, class Size, class T> void fill_n(OutputIterator first, Size n, const T& value);
The fill_n() function sets each of the first n elements beginning at location first to value.
template<class ForwardIterator, class Generator> void generate(ForwardIterator first, ForwardIterator last, Generator gen);
The generator() function sets each element in the range [first, last) to gen(), where gen is a generator function object, that is, one that takes no arguments. For example, gen can be a pointer to rand().
template<class OutputIterator, class Size, class Generator> void generate_n(OutputIterator first, Size n, Generator gen);
The generator_n() function sets each of the first n elements in the range beginning at first to gen(), where gen is a generator function object, that is, one that takes no arguments. For example, gen can be a pointer to rand().
template<class ForwardIterator, class T>
ForwardIterator remove(ForwardIterator first, ForwardIterator last,
const T& value);
The remove() function removes all occurrences of value from the range [first, last) and returns a past-the-end iterator for the resulting range. The function is stable, meaning the order of the unremoved elements is unaltered.
Note
|
|
Because the various remove() and unique() functions are not member functions, and also because they aren't restricted to STL containers, they can't reset the size of a container. Instead, they return an iterator indicating the new past-the-end location. Typically, the removed items simply are shifted to the end of the container. However, for STL containers you can use the returned iterator and one of the erase() methods to reset end(). |
template<class ForwardIterator, class Predicate>
ForwardIterator remove_if(ForwardIterator first, ForwardIterator last,
Predicate pred);
The remove_if() function removes all occurrences of values val for which pred(val) is true from the range [first, last) and returns a past-the-end iterator for the resulting range. The function is stable, meaning the order of the unremoved elements is unaltered.
template<class InputIterator, class OutputIterator, class T>
OutputIterator remove_copy(InputIterator first, InputIterator last,
OutputIterator result, const T& value);
The remove_copy() function copies values from the range [first, last) to the range beginning at result, skipping instances of value as it copies. It returns a past-the-end iterator for the resulting range. The function is stable, meaning the order of the unremoved elements is unaltered.
template<class InputIterator, class OutputIterator, class Predicate>
OutputIterator remove_copy_if(InputIterator first, InputIterator last,
OutputIterator result, Predicate pred);
The remove_copy_if() function copies values from the range [first, last) to the range beginning at result, but skipping instances of val for which pred(val) is true as it copies. It returns a past-the-end iterator for the resulting range. The function is stable, meaning the order of the unremoved elements is unaltered.
template<class ForwardIterator>
ForwardIterator unique(ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class BinaryPredicate>
ForwardIterator unique(ForwardIterator first, ForwardIterator last,
BinaryPredicate pred);
The unique() function reduces each sequence of two or more equivalent elements in a range [first, last) to a single element and returns a past-the-end iterator for the new range. The first version uses the == operator for the value type to compare elements. The second version uses the binary predicate function object pred to compare elements. That is, elements pointed to by it1 and it2 match if pred(*it1, *it2) is true.
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 pred);
The unique_copy() function copies elements from a range [first, last) to the range beginning at result, reducing each sequence of two or more identical elements to a single element. It returns a past-the-end iterator for the new range. The first version uses the == operator for the value type to compare elements. The second version uses the binary predicate function object pred to compare elements. That is, elements pointed to by it1 and it2 match if pred(*it1, *it2) is true.
template<class BidirectionalIterator> void reverse(BidirectionalIterator first, BidirectionalIterator last);
The reverse() function reverses the elements in the range [first, last) by invoking swap(first, last - 1), and so on.
template<class BidirectionalIterator, class OutputIterator>
OutputIterator reverse_copy(BidirectionalIterator first,
BidirectionalIterator last,
OutputIterator result);
The reverse copy() function copies the elements in the range [first, last) to the range beginning at result in reverse order. The two ranges should not overlap.
template<class ForwardIterator>
void rotate(ForwardIterator first, ForwardIterator middle,
ForwardIterator last);
The rotate() function performs a left-rotate on the elements in the range [first, last). The element at middle is moved to first, the element at middle + 1 to first + 1, and so on. The elements preceding middle are wrapped around to the end of the container so that the element at first follows that formerly at last - 1.
template<class ForwardIterator, class OutputIterator>
OutputIterator rotate_copy(ForwardIterator first, ForwardIterator middle,
ForwardIterator last, OutputIterator result);
The rotate_copy() function copies the elements in the range [first, last) to the range beginning at result using the rotated sequence described for rotate().
template<class RandomAccessIterator> void random_shuffle(RandomAccessIterator first, RandomAccessIterator last);
This version of the random_shuffle() function shuffles the elements in the range [first, last). The distribution is uniform; that is, each possible permutation of the original order is equally likely.
template<class RandomAccessIterator, class RandomNumberGenerator>
void random_shuffle(RandomAccessIterator first, RandomAccessIterator last,
RandomNumberGenerator& random);
This version of the random_shuffle() function shuffles the elements in the range [first, last). The function object random determines the distribution. Given n elements, the expression random(n) should return a value in the range [0,n).
template<class BidirectionalIterator, class Predicate>
BidirectionalIterator partition(BidirectionalIterator first,
BidirectionalIterator last,
Predicate pred);
The partition() function places each element whose value val is such that pred(val) is true before all elements that don't meet that test. It returns an iterator to the position following that last position holding a value for which the predicate object function was true.
template<class BidirectionalIterator, class Predicate>
BidirectionalIterator stable_partition(BidirectionalIterator first,
BidirectionalIterator last,
Predicate pred);
The stable_partition() function places each element whose value val is such that pred(val) is true before all elements that don't meet that test. The function preserves the relative ordering within each of the two groups. It returns an iterator to the position following that last position holding a value for which the predicate object function was true.
Table G.11 summarizes the sorting and related operations. Arguments are not shown, and overloaded functions are listed just once. Each function has a version that uses < for ordering elements and a version that uses a comparison function object for ordering elements. A fuller description including the prototypes follows the table. Thus, you can scan the table to get an idea of what a function does, then look up the details if you find the function appealing.
| Function | Description |
|---|---|
| sort() | Sorts a range. |
| stable_sort() | Sorts a range, preserving the relative order of equivalent elements. |
| partial_sort() | Partially sorts a range, providing the first n elements of a full sort. |
| partial_sort_copy() | Copies a partially sorted range to another range. |
| nth_element() | Given an iterator into a range, finds the element that would be there if the range were sorted, and places that element there. |
| lower_bound() | Given a value, finds the first position in a sorted range before which the value can be inserted while maintaining the ordering. |
| upper_bound() | Given a value, finds the last position in a sorted range before which the value can be inserted while maintaining the ordering. |
| equal_range() | Given a value, finds the largest subrange of a sorted range such that the value can be inserted before any element in the subrange without violating the ordering. |
| binary_search() | Returns true if a sorted range contains a value equivalent to a given value, and false otherwise. |
| merge() | Merges two sorted ranges into a third range. |
| inplace_merge() | Merges two consecutive sorted ranges in place. |
| includes() | Returns true if every element in one set also is found in another set. |
| set_union() | Constructs the union of two sets, which is a set containing all elements present in either set. |
| set_intersection() | Constructs the intersection of two sets, which is a set containing only those elements found in both sets. |
| set_difference() | Constructs the difference of two sets, which is a set containing only those elements found in the first set but not the second. |
| set_symmetric_difference() | Constructs a set consisting of elements found in one set or the other, but not both. |
| make_heap | Converts a range to heap. |
| push_heap() | Adds an element to a heap. |
| pop_heap() | Removes the largest element from a heap. |
| sort_heap() | Sorts a heap. |
| min() | Returns the lesser of two values. |
| max() | Returns the greater of two values. |
| min_element() | Finds the first occurrence of the smallest value in a range. |
| max_element() | Finds the first occurrence of the largest value in a range. |
| lexicographic_compare() | Compares two sequences lexicographically, returning true if the first sequence is lexicographically less than the second, and false otherwise. |
| next_permutation() | Generates the next permutation in a sequence. |
| previous_permutation() | Generates the preceding permutation in a sequence. |
The functions in this section determine the order of two elements by using the < operator defined for the elements or by using a comparison object designated by the template type Compare. If comp is an object of type Compare, then comp(a,b) is a generalization of a < b and returns true if a precedes b in the ordering scheme. If a < b is false and b < a also is false, a and b are equivalent. A comparison object must provide at least strict weak ordering. This means the following:
The expression comp(a,a) must be false, a generalization of the fact that a value can't be less than itself. (This is the strict part.)
If comp(a,b) is true and comp(b,c) is true, then comp(a,c) is true (that is, comparison is a transitive relationship).
If a is equivalent to b, and b is equivalent to c, then a is equivalent to c (that is, equivalency is a transitive relationship).
If you think of applying < to integers, then equivalency implies equality, but this doesn't have to hold for more general cases. For example, you could define a structure with several members describing a mailing address and define a comp comparison object that orders the structures according to ZIP code. Then any two addresses with the same ZIP code would be equivalent but not equal.
Now let's go to the prototypes. We'll divide this section into several subsections. As you saw earlier, pairs of iterators indicate ranges, with the chosen template parameter name indicating the type of iterator. As usual a range of the form [first, last) goes from first up to, but not including, last. Functions passed as arguments are function objects, which can be pointers or objects for which the () operation is defined. As you learned in Chapter 16, a predicate is a Boolean function with one argument, and a binary predicate is a Boolean function with two arguments. (The functions need not be type bool as long as they return a 0 value for false and a non-zero for true.) Also, as in Chapter 16, a unary function object is one taking a single argument, and a binary function object is one taking two arguments.
First, let's examine the sorting algorithms.
template<class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void sort(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
The sort() function sorts the range [first, last) in increasing order, using the value type < operator for comparison. The first version uses < and the second uses the comparison object comp to determine the order.
template<class RandomAccessIterator>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
The stable_sort() function sorts the range [first, last) preserving the relative order of equivalent elements. The first version uses < and the second uses the comparison object comp to determine the order.
template<class RandomAccessIterator>
void partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
RandomAccessIterator last, Compare comp);
The partial_sort() function partially sorts the range [first, last). The first middle - first elements of the sorted range are placed in the range [first, middle), and the remaining elements are unsorted. The first version uses < and the second uses the comparison object comp to determine the order.
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 Compare>
RandomAccessIterator
partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last,
Compare comp);
The partial_sort_copy() function copies the first n elements of the sorted range [first, last) to the range [result_first, result_first + n). The value of n is the lesser of last - first and result_last - result_first. The function returns result_first + n. The first version uses < and the second uses the comparison object comp to determine the order.
template<class RandomAccessIterator>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last, Compare comp);
The nth_element() function finds the element in range [first, last) that would be at position nth were the range sorted, and it places that element at position nth. The first version uses < and the second uses the comparison object comp to determine the order.
The algorithms in the binary search group assume the range is sorted. They only require a forward iterator but are most efficient for random iterators.
template<class ForwardIterator, class T>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
const T& value);
template<class ForwardIterator, class T, class Compare>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);
The lower_bound() function finds the first position in a sorted range [first, last) in front of which value can be inserted without violating the order. It returns an iterator pointing to this position. The first version uses < and the second uses the comparison object comp to determine the order.
template<class ForwardIterator, class T>
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
const T& value);
template<class ForwardIterator, class T, class Compare>
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);
The upper_bound() function finds the last position in a sorted range [first, last) in front of which value can be inserted without violating the order. It returns an iterator pointing to this position. The first version uses < and the second uses the comparison object comp to determine the order.
template<class ForwardIterator, class T>
pair<ForwardIterator, ForwardIterator> equal_range(
ForwardIterator first, ForwardIterator last, const T& value);
template<class ForwardIterator, class T, class Compare>
pair<ForwardIterator, ForwardIterator> equal_range(
ForwardIterator first, ForwardIterator last, const T& value,
Compare comp);
The equal_range() function finds the largest subrange [it1, it2) in a sorted range [first, last) such that value can be inserted in front of any iterator in this range without violating the order. The function returns a pair formed of it1 and it2. The first version uses < and the second uses the comparison object comp to determine the order.
template<class ForwardIterator, class T>
bool binary_search(ForwardIterator first, ForwardIterator last,
const T& value);
template<class ForwardIterator, class T, class Compare>
bool binary_search(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);
The binary_search() function returns true if the equivalent of value is found in the sorted range [first, last) and false otherwise. The first version uses < and the second uses the comparison object comp to determine the order.
Note
|
|
Recall that if < is used for ordering, values a and b are equivalent if both a < b and b < a are false. For ordinary numbers, equivalency implies equality, but this is not the case for structures sorted on the basis of just one member. Thus, there may be more than one location where a new value can be inserted and still keep the data ordered. Similarly, if the comparison object comp is used for ordering, equivalency means both comp(a,b) and comp(b,a) are false. (This is a generalization of the statement that a and b are equivalent if a is not less than b and b is not less than a.) |
The merging functions assume ranges are sorted.
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 Compare>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
The merge() function merges elements from sorted range [first1, last1) and from sorted range [first2, last2), placing the result in the range starting at result. The target range should not overlap either of the merged ranges. When equivalent elements are found in both ranges, elements from the first range precede elements of the second. The return value is the past-the-end iterator for the resulting merge. The first version uses < and the second uses the comparison object comp to determine the order.
template<class BidirectionalIterator>
void inplace_merge(BidirectionalIterator first,
BidirectionalIterator middle, BidirectionalIterator last);
template<class BidirectionalIterator, class Compare>
void inplace_merge(BidirectionalIterator first,
BidirectionalIterator middle, BidirectionalIterator last,
Compare comp);
The inplace_merge() function merges two consecutive sorted ranges梉first, middle) and [middle, last)梚nto a single sorted sequence stored in the range [first, last). Elements from the first range will precede equivalent elements from the second range. The first version uses < and the second uses the comparison object comp to determine the order.
Set operations work with all sorted sequences, including set and multiset. For containers holding more than one instance of a value, such as multiset, definitions are generalized. A union of two multisets contains the larger number of occurrences of each element, and an intersection contains the lesser number of occurrences of each element. For example, suppose multiset A contains the string "apple" seven times and multiset B contains the same string four times. Then the union of A and B will contain seven instances of "apple" and the intersection will contain four instances.
template<class InputIterator1, class InputIterator2>
bool includes(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2);
template<class InputIterator1, class InputIterator2, class Compare>
bool includes(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2, Compare comp);
The includes() function returns true if every element in range [first2, last2) also is found in the range [first1, last1) and false otherwise. The first version uses < and the second uses the comparison object comp to determine the order.
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 Compare>
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
The set_union() function constructs the set that is the union of the ranges [first1, last1) and [first2, last2) and copies the result to the location pointed to by result. The resulting range should not overlap either of the original ranges. The function returns a past-the-end iterator for the constructed range. The union is the set containing all elements found in either or both sets. The first version uses < and the second uses the comparison object comp to determine the order.
template<class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
template<class InputIterator1, class InputIterator2, class OutputIterator,
class Compare>
OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
The set_intersection() function constructs the set that is the intersection of the ranges [first1, last1) and [first2, last2) and copies the result to the location pointed to by result. The resulting range should not overlap either of the original ranges. The function returns a past-the-end iterator for the constructed range. The intersection is the set containing those elements common to both sets. The first version uses < and the second uses the comparison object comp to determine the order.
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 Compare>
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
The set_difference() function constructs the set that is the difference of the ranges [first1, last1) and [first2, last2) and copies the result to the location pointed to by result. The resulting range should not overlap either of the original ranges. The function returns a past-the-end iterator for the constructed range. The difference is the set containing those elements found in the first set but not in the second. The first version uses < and the second uses the comparison object comp to determine the order.
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 Compare>
OutputIterator set_symmetric_difference(
InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
The set_symmetric_difference() function constructs the set that is the symmetric difference of the ranges [first1, last1) and [first2, last2) and copies the result to the location pointed to by result. The resulting range should not overlap either of the original ranges. The function returns a past-the-end iterator for the constructed range. The symmetric difference is the set containing those elements found in the first set but not in the second and those elements found in the second set but not the first. It's the same as the difference between the union and the intersection. The first version uses < and the second uses the comparison object comp to determine the order.
A heap is a common data form with the property that the first element in a heap is the largest. Whenever the first element is removed or any element is added, the heap may have to be rearranged to maintain that property. A heap is designed so that these two operations are done efficiently.
template<class RandomAccessIterator>
void make_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void make_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
The make_heap() function makes a heap of the range [first, last). The first version use < to determine the ordering, while the second version uses the comp comparison object.
template<class RandomAccessIterator>
void push_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void push_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
The push_heap() function assumes that the range [first, last - 1) is a valid heap, and it adds the value at location last - 1 (that is, one past the end of the assumed valid heap) into the heap, making [first, last) a valid heap. The first version use < to determine the ordering, while the second version uses the comp comparison object.
template<class RandomAccessIterator>
void pop_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void pop_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
The pop_heap() function assumes that the range [first, last) is a valid heap. It swaps the value at location last - 1 with the value at first and makes the range [first, last - 1) a valid heap. The first version uses < to determine the ordering, while the second version uses the comp comparison object.
template<class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
The sort_heap() function assumes the range [first, last) is a heap and sorts it. The first version uses < to determine the ordering, while the second version uses the comp comparison object.
The minimum and maximum functions return the minimum and maximum values of pairs of values and of sequences of values.
template<class T> const T& min(const T& a, const T& b); template<class T, class Compare> const T& min(const T& a, const T& b, Compare comp);
The min() function returns the lesser of two values. If the two values are equivalent, it returns the first value. The first version uses < to determine the ordering, while the second version uses the comp comparison object.
template<class T> const T& max(const T& a, const T& b); template<class T, class Compare> const T& max(const T& a, const T& b, Compare comp);
The max() function returns the greater of two values. If the two values are equivalent, it returns the first value. The first version uses < to determine the ordering, while the second version uses the comp comparison object.
template<class ForwardIterator> ForwardIterator min_element(ForwardIterator first, ForwardIterator last); template<class ForwardIterator, class Compare> ForwardIterator min_element(ForwardIterator first, ForwardIterator last, Compare comp);
The min_element() function returns the first iterator it in the range [first, last) such that no element in the range is less than *it. The first version uses < to determine the ordering, while the second version uses the comp comparison object.
template<class ForwardIterator> ForwardIterator max_element(ForwardIterator first, ForwardIterator last); template<class ForwardIterator, class Compare> ForwardIterator max_element(ForwardIterator first, ForwardIterator last, Compare comp);
The max_element() function returns the first iterator it in the range [first, last) such that there is no element that *it is less than. The first version uses < to determine the ordering, while the second version uses the comp comparison object.
template<class InputIterator1, class InputIterator2>
bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2);
template<class InputIterator1, class InputIterator2, class Compare>
bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
Compare comp);
The lexicographical_compare() function returns true if the sequence of elements in range [first1, last1) is lexicographically less than the sequence of elements in range [first2, last2) and false otherwise. A lexicographical comparison compares the first element of one sequence to the first of the second, that is, it compares *first1 to *first2. If *first1 is less than *first2, the function returns true. If *first2 is less than *first1, the function returns false. If the two are equivalent, comparison proceeds to the next element in each sequence. This process continues until two corresponding elements are not equivalent or until the end of a sequence is reached. If two sequences are equivalent until the end of one is reached, the shorter sequence is less. If the two sequences are equivalent and of the same length, neither is less, so the function returns false. The first version of the function uses < to compare elements and the second version uses the comp comparison object. The lexicographic comparison is a generalization of an alphabetic comparison.
A permutation of a sequence is a reordering of the elements. For example, a sequence of three elements has six possible orderings, because you have a choice of three elements for the first element. Choosing a particular element for the first position leaves a choice of two for the second, and one for the third. For example, the six permutations of the digits 1, 3, and 5 are as follows:
123 132 213 232 312 321
In general, a sequence of n elements has n*(n-1)*?1, or n! possible permutations.
The permutation functions assume that the set of all possible permutations can be arranged in lexicographical order, as in the previous example of six permutations. That means, in general, that there is a specific permutation that precedes and follows each permutation. For example, 213 immediately precedes 232, and 312 immediately follows it. However, the first permutation (123 in the example) has no predecessor, and the last permutation (321) has no follower.
template<class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first,
BidirectionalIterator last);
template<class BidirectionalIterator, class Compare>
bool next_permutation(BidirectionalIterator first,
BidirectionalIterator last, Compare comp);
The next_permutation() function transforms the sequence in range [first, last) to the next permutation in lexicographic order. If the next permutation exists, the function returns true. If it doesn't exist (that is, the range contains the last permutation in lexicographic order), the function returns false and transforms the range to the first permutation in lexicographic order. The first version uses < to determine the ordering, while the second version uses the comp comparison object.
template<class BidirectionalIterator>
bool prev_permutation(BidirectionalIterator first,
BidirectionalIterator last);
template<class BidirectionalIterator, class Compare>
bool prev_permutation(BidirectionalIterator first,
BidirectionalIterator last, Compare comp);
The previous_permutation() function transforms the sequence in range [first, last) to the previous permutation in lexicographic order. If the previous permutation exists, the function returns true. If it doesn't exist (that is, the range contains the first permutation in lexicographic order), the function returns false and transforms the range to the last permutation in lexicographic order. The first version uses < to determine the ordering, while the second version uses the comp comparison object.
Table G.12 summarizes the numeric operations, which are described by the numeric header file. Arguments are not shown, and overloaded functions are listed just once. Each function has a version that uses < for ordering elements and a version that uses a comparison function object for ordering elements. A fuller description including the prototypes follows the table. Thus, you can scan the table to get an idea of what a function does; then look up the details if you find the function appealing.
| Function | Description |
|---|---|
| accumulate() | Calculates a cumulative total for values in a range. |
| inner_product() | Calculates the inner product of two ranges. |
| partial_sum() | Copies partial sums calculated from one range into a second range. |
| adjacent_difference() | Copies adjacent differences calculated from elements in one range to a second range. |
template <class InputIterator, class T>
T accumulate(InputIterator first, InputIterator last, T init);
template <class InputIterator, class T, class BinaryOperation>
T accumulate(InputIterator first, InputIterator last, T init,
BinaryOperation binary_op);
The accumulate() function initializes a value acc to init; then it performs the operation acc = acc + *i (first version) or acc = binary_op(acc, *i) (second version) for each iterator i in the range [first, last) in order. It then returns the resulting value of acc.
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 BinaryOperation1, class BinaryOperation2>
T inner_product(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, T init,
BinaryOperation1 binary_op1, BinaryOperation2 binary_op2);
The inner_product() function initializes a value acc to init; then it performs the operation acc = *i * *j (first version) or acc = binary_op(*i, *j) (second version) for each iterator i in the range [first1, last1) in order and each corresponding iterator j in the range [first2, first2 + (last1 - first1)). That is, it calculates a value from the first elements from each sequence, then from the second elements of each sequence, and so on, until it reaches the end of the first sequence. (Hence the second sequence should be at least as long as the first.) The function then returns the resulting value of acc.
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);
The partial_sum() function assigns *first to *result, *first + *(first + 1) to *(result + 1), (first version) or binary_op(*first, *(first + 1)) to *(result + 1) (second version, and so on. That is, the nth element of the sequence beginning at result contains the sum (or binary_op equivalent) of the first n elements of the sequence beginning at first. The function returns the past-the-end iterator for the result. The algorithm allows result to be first, that is, it allows the result to be copied over the original sequence, if desired.
template <class InputIterator, class OutputIterator>
OutputIterator adjacent_difference(InputIterator first, InputIterator last,
OutputIterator result);
template <class InputIterator, class OutputIterator, class BinaryOperation>
OutputIterator adjacent_difference(InputIterator first, InputIterator last,
OutputIterator result,
BinaryOperation binary_op);
The adjacent_difference() function assigns *first to the location result (*result = *first). Subsequent locations in the target range are assigned the differences (or binary_op equivalent) of adjacent locations in the source range. That is, the next location in the target range (result + 1) is assigned *(first + 1) - *first (first version) or binary_op(*(first + 1), *first) (second version, and so on. The function returns the past-the-end iterator for the result. The algorithm allows result to be first, that is, it allows the result to be copied over the original sequence, if desired.
| CONTENTS | |