|
This section uses a number of abbreviations and conventions. First, each algorithm is described using plain English. Then, a more mathematical description of the algorithm, which tends to be harder to read, is given in a "Technical Notes" section.
The names of the template parameters tell you which category of iterator is expected. The iterator category is the minimal functionality needed, so you can, for example, use a random access iterator where at least a forward iterator is needed. (See Chapter 10 for more information on iterators and iterator categories.) To keep the syntax summaries short and readable, the iterator categories are abbreviated, as shown in Table 13-1.
Parameter name | Iterator category |
---|---|
BidiIter | Bidirectional iterator |
FwdIter | Forward iterator |
InIter | Input iterator |
OutIter | Output iterator |
RandIter | Random access iterator |
Other template parameter names are chosen to be self-explanatory. For example, any name that ends in Predicate is a function that returns a Boolean result (which can be type bool or any other type that is convertible to bool ) or a Boolean functional object (an object that has a function call operator that returns a Boolean result).
A number of algorithms require sorted ranges or otherwise use a comparison function to test the less-than relationship. The library overloads each algorithm: the first function uses operator< , and the second accepts a function pointer or function object to perform the comparison. The comparison function takes two arguments and returns a Boolean result. In the "Technical Notes" sections, the < relationship signifies operator< or the caller-supplied function, depending on the version of the algorithm you are using. If you overload operator< or provide your own comparison function, make sure it correctly implements a less-than relationship. In particular, a < a must be false for any a .
In this section, the following conventions are used:
Iterators are usually used in ranges that represent all the elements in the range or sequence. A range is written using standard mathematical notation: a square bracket denotes an inclusive endpoint of a range, and a parenthesis denotes an exclusive endpoint of a range. Thus, [ x, y ) is a range that starts at x , including x , and ends at y , excluding y . Chapter 10 also discusses this aspect of iterators.
Arithmetic expressions that involve iterators work as though each iterator were a random access iterator, even if the iterator is from a different category. For example, i - 1 for an input iterator is not allowed in C++ code, but in this section, it means the input iterator that points to one position before i .
The names used for input ranges are typically first and last , in which first is an iterator that points to first the element of the range, and last is an iterator that points to one past the end of the range. Thus, the range is written as [first , last) .
An iterator that advances from first to last is typically called iter .
Output iterators are typically named result . Most algorithms specify only the start of the output range. It is your responsibility to ensure that the output range has room to accommodate the entire output. The behavior is undefined if the output range overflows.
In each "Technical Notes" section, conventional mathematical notation is used with some aspects of C++ notation, such as * , which dereferences an iterator. Also, a single equal sign (=) means assignment, and a double equal sign (==) means comparison for equality. The following conventions are used for names:
Denote iterators, and * i , * j , and * k denote the values that the iterators point to.
Denote integers.
Denote values, which are usually of types that can be assigned to or from a dereferenced iterator (e.g., * i = a ).
adjacent_find function template | Searches for a pair of adjacent, equal items |
template<typename FwdIter> FwdIter adjacent_find (FwdIter first, FwdIter last); template<typename FwdIter, typename BinaryPredicate> FwdIter adjacent_find (FwdIter first, FwdIter last, BinaryPredicate pred); |
The adjacent_find function template looks for the first set of adjacent items in the range [ first , last ) that are equal (first version) or in which pred(*iter , (* iter+1)) is true (second version). Items are "adjacent" when their iterators differ by one position.
The return value is an iterator that points to the first of the adjacent items, or last if no matching items are found. See Figure 13-1 for an example.
The adjacent_find function template returns i , in which i = first + n , and n is the smallest value such that *( first + n ) == *( first + n + 1) and first + n + 1 < last , or, if there is no such n , i = last .
Complexity is linear: the standard is muddled, but any reasonable implementation calls the predicate ( operator== or pred ) exactly n + 1 times.
find function template, find_if function template
binary_search function template | Searches using a binary search |
template<typename FwdIter, typename T> bool binary_search (FwdIter first, FwdIter last, const T& value); template<typename FwdIter, typename T, typename Compare> bool binary_search (FwdIter first, FwdIter last, const T& value, Compare comp); |
The binary_search function template uses a binary search to test whether value is in the range [ first , last ). It returns true upon success and false if the value is not found. The contents of the range must be sorted in ascending order.
The first version compares items using the < operator. The second version uses comp(X , Y) to test whether X < Y .
Precondition: !(*( i + 1) < * i ) for all i in [ first , last - 1).
The binary_search function template returns true if there is an i in [ first , last ) such that !(* i < value ) and !( value < * i ). It returns false if there is no such i .
Complexity is logarithmic . The number of comparisons is at most log( last - first ) + 2. Although the iterator can be a forward iterator, the best performance is obtained with a random access iterator. With a forward or bidirectional iterator, the iterator is advanced a linear number of times, even though the number of comparisons is logarithmic.
equal_range function template, find function template, find_if function template, lower_bound function template, upper_bound function template
copy function template | Copies every item in a range |
template<typename InIter, typename OutIter> OutIter copy (InIter first, InIter last, OutIter result); |
The copy function template copies items from [ first , last ) to the output iterator starting at result . You must ensure that the output sequence has enough room for last - first items. The return value is the value of the result iterator after copying all the items, as shown in Figure 13-2.
The result iterator cannot be in the source range [ first , last ), but other parts of the destination range can overlap with the source.
See Example 13-2 (under generate ).
The copy function template assigns *( result + n ) = *( first + n ) for all n in the range [0, last - first ).
Complexity is linear: exactly last - first assignments are performed.
copy_backward function template, partial_sort_copy function template, replace_copy function template, remove_copy function template, reverse_copy function template, rotate_copy function template, unique_copy function template
copy_backward function template | Copies a range, starting at the end |
template<typename BidiIter1, typename BidiIter2> BidiIter2 copy_backward (BidiIter1 first, BidiIter1 last, BidiIter2 result); |
The copy_backward function template does the same thing as copy , but it works backward, starting at the element before last and copying elements toward first . The result iterator must point to one past the end of the destination and is decremented before copying each element. The return value is an iterator that points to the first element of the destination, as shown in Figure 13-3.
The result iterator cannot be in the source range [ first , last ), but other parts of the destination range can overlap with the source.
The copy_backward function template assigns *( result - n ) = *( last - n ) for all n in the range [1, last - first ].
Complexity is linear: exactly last - first assignments are performed.
copy function template, reverse_copy function template
count function template | Counts the occurrences of a value |
template<typename InIter, typename T> typename iterator_traits<InIter>::difference_type count (InIter first, InIter last, const T& value); |
The count function template returns the number of elements in the range [ first , last ) that are equal to value .
Complexity is linear: exactly last - first comparisons are performed.
count_if function template, equal_range function template
count_if function template | Counts the number of times a predicate returns true |
template<typename InIter, typename Predicate> typename iterator_traits<InIter>::difference_type count_if (InIter first, InIter last, Predicate pred); |
The count_if function template returns the number of elements in the range [ first , last ) for which pred(*iter) returns true.
Complexity is linear: pred is called exactly last - first times.
count function template, find_if function template
equal function template | Tests whether ranges have same contents |
template<typename InIter1, typename InIter2> bool equal (InIter1 first1, InIter1 last1, InIter2 first2); template<typename InIter1, typename InIter2, typename BinaryPredicate> bool equal (InIter1 first1, InIter1 last1, InIter2 first2, BinaryPredicate pred); |
The equal function template returns true if two ranges contain the same elements in the same order. The first range is [ first1 , last1 ), and the second range has the same number of elements, starting at first2 . The ranges can overlap.
The first form compares items using the == operator. The second form calls pred(*iter1 , *iter2) .
The equal function template returns true if *( first1 + n ) == *( first2 + n ) for all n in the range [0, last1 - first1 ).
Complexity is linear: at most last1 - first1 comparisons are performed.
lexicographical_compare function template, mismatch function template, search function template
equal_range function template | Finds all occurrences of a value in a sorted range using binary search |
template<typename FwdIter, typename T> pair<FwdIter, FwdIter> equal_range (FwdIter first, FwdIter last, const T& value); template<typename FwdIter, typename T, typename Compare> pair<FwdIter, FwdIter> equal_range (FwdIter first, FwdIter last, const T& value, Compare comp); |
The equal_range function template determines where value belongs in the sorted range [ first , last ). It returns a pair of iterators that specify the start and one past the end of the range of items that are equivalent to value , or both iterators in the pair point to where you can insert value and preserve the sorted nature of the range.
The first form compares values using the < operator. The second form calls comp(*iter , value) .
Figure 13-4 shows how bounds are found with the value 36 . The result of calling equal_range is pair(lb , ub) . Note that for values in the range [ 19 , 35 ], the upper and lower bound are both equal to lb , and for values in the range [ 37 , 41 ], the upper and lower bound are both equal to ub .
Precondition: !(*( i + 1) < * i ) for all i in [ first , last - 1).
The equal_range function template returns the equivalent of calling the following, although the actual implementation might be different:
std::make_pair(std::lower_bound(first, last, value), std::upper_bound(first, last, value))
or:
std::make_pair(std::lower_bound(first, last, value, comp), std::upper_bound(first, last, value, comp))
Complexity is logarithmic. The number of comparisons is at most 2 x log( last - first ) + 1. Although the iterator can be a forward iterator, the best performance is obtained with a random access iterator. With a forward or bidirectional iterator, the iterator is advanced a linear number of times, even though the number of comparisons is logarithmic.
binary_search function template, lower_bound function template, upper_bound function template, pair in <utility>
fill function template | Fills a range with copies of a value |
template<typename FwdIter, typename T> void fill (FwdIter first, FwdIter last, const T& value); |
The fill function template fills the destination range [ first , last ) by assigning value to each item in the range.
The fill function template assigns * i = value for all i in the range [ first , last ).
Complexity is linear: exactly last - first assignments are performed.
fill_n function template, generate function template
fill_n function template | Fills a counted range with copies of a value |
template<typename OutIter, typename Size, typename T> void fill_n (OutIter first, Size n, const T& value); |
The fill_n function template assigns value to successive items in the destination range, starting at first and assigning exactly n items.
The Size template parameter must be convertible to an integral type.
The fill_n function template assigns *( first + n ) = value for all n in the range [0, n ).
Complexity is linear: exactly n assignments are performed.
fill function template, generate_n function template
find function template | Searches for a value using linear search |
template<typename InIter, typename T> InIter find (InIter first, InIter last, const T& value); |
The find function template returns an iterator that points to the first occurrence of value in [ first , last ). It returns last if value is not found. The == operator is used to compare items.
The find function template returns i = first + n , in which n is the smallest value such that *( first + n ) == value . If there is no such n , i = last .
Complexity is linear: at most last - first comparisons are performed.
find_end function template, find_first function template, find_if function template, search function template
find_end function template | Searches for the last occurrence of a sequence |
template<typename FwdIter1, typename FwdIter2> FwdIter1 find_end (FwdIter1 first1, FwdIter1 last1, FwdIter2 first2, FwdIter2 last2); template<typename FwdIter1, typename FwdIter2, typename BinaryPredicate> FwdIter1 find_end (FwdIter1 first1, FwdIter1 last1, FwdIter2 first2, FwdIter2 last2, BinaryPredicate pred); |
The find_end function template finds the last (rightmost) subsequence [ first2 , last2 ) within the range [ first1 , last1 ), as illustrated in Figure 13-5. It returns an iterator, find_end in Figure 13-5, that points to the start of the matching subsequence or last1 if a match cannot be found.
The first form compares items with the == operator. The second form calls pred(*iter1 , *iter2) .
Let length1 = last1 - first1 and length2 = last2 - first2 .
The find_end function template returns first1 + n , in which n is the highest value in the range [0, length1 - length2 ) such that *( i + n + m ) == ( first2 + m ) for all i in the range [ first1 , last1 ) and m in the range [0, length2 ). It returns last1 if no such n can be found.
Complexity: at most length1 x length2 comparisons are performed.
find function template, search function template
find_first_of function template | Searches for any one of a sequence of values |
template<typename FwdIter1, typename FwdIter2> FwdIter1 find_first_of (FwdIter1 first1, FwdIter1 last1, FwdIter2 first2, FwdIter2 last2); template<typename FwdIter1, typename FwdIter2, typename BinaryPredicate> FwdIter1 find_first_of (FwdIter1 first1, FwdIter1 last1, FwdIter2 first2, FwdIter2 last2, BinaryPredicate pred); |
The find_first_of function template searches the range [ first1 , last1 ) for any one of the items in [ first2 , last2 ). If it finds a matching item, it returns an iterator that points to the matching item, in the range [ first1 , last1 ). It returns last1 if no matching item is found. Figure 13-6 shows an example.
The first form compares items with the == operator. The second form calls pred(*iter1 , *iter2) .
Let length1 = last1 - first1 and length2 = last2 - first2 .
The find_first_of function template returns first1 + n where n is the smallest value in the range [0, length1 ) such that *( first1 + n ) == ( first2 + m ) for some m in the range [0, length2 ). It returns last1 if no such n and m can be found.
Complexity: at most length1 x length2 comparisons are performed.
find function template
find_if function template | Searches for when a predicate returns true |
template<typename InIter, typename Predicate> InIter find_if (InIter first, InIter last, Predicate pred); |
The find_if function template (similar to find ) searches the range [ first , last ) for the first item for which pred(*iter) is true. It returns an iterator that points to the matching item. If no matching item is found, last is returned.
The find_if function template returns i = first + n , in which n is the smallest value such that pred (*( first + n ), value ) is true. If there is no such n , i = last .
Complexity is linear: pred is called at most last - first times.
find function template
for_each function template | Calls a function for each item in a range |
template<typename InIter, typename Func> Function for_each (InIter first, InIter last, Func f); |
The for_each function template calls f for each item in the range [ first , last ), passing the item as the sole argument to f . It returns f .
Example 13-1 shows how the use for_each to test whether a sequence is sorted. The is_sorted object remembers the previous item in the sequence, which it compares with the current item. The overloaded bool operator returns true if the sequence is sorted so far or false if the sequence is out of order. The example takes advantage of the fact that for_each returns the f parameter as its result.
#include <iostream> #include <algorithm> #include <list> template<typename T> class is_sorted { public: is_sorted( ) : first_time(true), sorted(true) {} void operator( )(const T& item) { // for_each calls operator( ) for each item. if (first_time) first_time = false; else if (item < prev_item) sorted = false; prev_item = item; } operator bool( ) { return sorted; } private: bool first_time; bool sorted; T prev_item; }; int main( ) { std::list<int> l; l.push_back(10); l.push_back(20); ... if (std::for_each(l.begin( ), l.end( ), is_sorted<int>( ))) std::cout << "list is sorted" << '\n'; }
Complexity is linear: f is called exactly last - first times.
copy function template, accumulate in <numeric>
generate function template | Fills a range with values returned from a function |
template<typename FwdIter, typename Generator> void generate (FwdIter first, FwdIter last, Generator gen); |
The generate function template fills the sequence [ first , last ) by assigning the result of calling gen( ) repeatedly.
Example 13-2 shows a simple way to fill a sequence with successive integers.
#include <algorithm> #include <iostream> #include <iterator> #include <vector> // Generate a series of objects, starting with "start". template <typename T> class series { public: series(const T& start) : next(start) {} T operator( )( ) { return next++; } private: T next; }; int main( ) { std::vector<int> v; v.resize(10); // Generate integers from 1 to 10. std::generate(v.begin( ), v.end( ), series<int>(1)); // Print the integers, one per line. std::copy(v.begin( ), v.end( ), std::ostream_iterator<int>(std::cout, "\n")); }
Complexity is linear: gen is called exactly last - first times.
fill function template, generate_n function template
generate_n function template | Fills a counted range with values returned from a function |
template<typename OutIter, typename Size, typename Generator> void generate_n (OutIter first, Size n, Generator gen); |
The generate_n function template calls gen( ) exactly n times, assigning the results to fill the sequence that starts at first . You must ensure that the sequence has room for at least n items. The Size type must be convertible to an integral type.
Example 13-3 shows a simple way to print a sequence of integers.
#include <algorithm> #include <iostream> #include <iterator> // Use the same series template from Example 13-2. int main( ) { // Print integers from 1 to 10. std::generate_n(std::ostream_iterator<int>(std::cout,"\n"), 10, series<int>(1)); }
Complexity is linear: gen is called exactly n times.
fill_n function template , generate function template
includes function template | Tests sorted ranges for subset |
template<typename InIter1, typename InIter2> bool includes (InIter1 first1, InIter1 last1, InIter2 first2, InIter2 last2); template<typename InIter1, typename InIter2, typename Compare> bool includes (InIter1 first1, InIter1 last1, InIter2 first2, InIter2 last2, Compare comp); |
The includes function template checks for a subset relationship, that is, it returns true if every element in the sorted sequence [ first2 , last2 ) is contained in the sorted sequence [ first1 , last1 ). It returns false otherwise.
Both sequences must be sorted. The first form uses the < operator to compare the elements. The second form calls comp(*iter1 , *iter2) .
Precondition: !(*( i + 1) < * i ) for all i in [ first1 , last1 - 1) and !(*( j + 1) < * j ) for all j in [ first2 , last2 - 1).
The includes function template returns true if there is an i in [ first1 , last1 ) such that *( i + n ) = *( first2 + n ) for all n in [0, ( last2 - first2 )). It returns last1 if there is no such i .
Complexity is linear: at most, 2 x (( last1 - first1 ) + ( last2 - first2 )) - 1 comparisons are performed.
set_difference function template, set_intersection function template, set_symmetric_difference function template, set_union function template
inplace_merge function template | Merges sorted, adjacent ranges in place |
template<typename BidiIter> void inplace_merge (BidiIter first, BidiIter middle, BidiIter last); template<typename BidiIter, typename Compare> void inplace_merge (BidiIter first, BidiIter middle, BidiIter last, Compare comp); |
The inplace_merge function template merges two sorted, consecutive ranges in place, creating a single sorted range. The two ranges are [ first , middle ) and [ middle , last ). The resulting range is [ first , last ).
The merge is stable, so elements retain their respective orders, with equivalent elements in the first range coming before elements in the second.
Both sequences must be sorted. The first form uses the < operator to compare elements. The second form calls comp(*iter1 , *iter2) .
Figure 13-7 shows how inplace_merge operates.
Precondition: !(*( i + 1) < * i ) for all i in [ first , middle - 1) and !(*( j + 1) < * j ) for all j in [ middle , last - 1).
Postcondition: !(*( i + 1) < * i ) for all i in [ first , last - 1).
Complexity is usually linear with n + 1 comparisons, but if enough temporary memory is not available, the complexity might be n log n , in which n is last - first .
merge function template, sort function template
iter_swap function template | Swaps values that iterators point to |
template<typename FwdIter1, typename FwdIter2> void iter_swap (FwdIter1 a, FwdIter2 b); |
The iter_swap function template swaps the values pointed to by a and b . You can think of its functionality as:
FdwIter1::value_type tmp = *b*; *b = *a; *a = tmp;
Complexity is constant.
copy function template, swap function template, swap_ranges function template
lexicographical_compare function template | Compares ranges for less-than |
template<typename InIter1, typename InIter2> bool lexicographical_compare (InIter1 first1, InIter1 last1, InIter2 first2, InIter2 last2); template<typename InIter1, typename InIter2, typename Compare> bool lexicographical_compare (InIter1 first1, InIter1 last1, InIter2 first2, InIter2 last2, Compare comp); |
The lexicographical_compare function template returns true if the sequence [ first1 , last1 ) is less than the sequence [ first2 , last2 ). If the sequences have the same length and contents, the return value is false . If the second sequence is a prefix of the first, true is returned. (The use of " lexicographical " emphasizes that the ranges are compared element-wise, like letters in words.)
The first form uses the < operator to compare elements. The second form calls comp(*iter1 , *iter2) .
Let length1 = last1 - first1 , length2 = last2 - first2 , and minlength = min( length1 , length2 ).
The lexicographical_compare function template returns true if either of the following conditions is true:
There is an n in [0, minlength ) such that *( first1 + m ) == *( first2 + m ) for all m in [0, n - 1), and *( first1 + n ) < *( first2 + n ).
*( first1 + n ) == *( first2 + n ) for all n in [0, length2 ) and length2 < length1 .
Complexity is linear: at most, minlength comparisons are performed.
#include <algorithm> #include <iostream> #include <ostream> int main( ) { using namespace std; int a[] = { 1, 10, 3, 42 }; int b[] = { 1, 10, 42, 3 }; int c[] = { 1, 10 }; cout << boolalpha; cout << lexicographical_compare(a, a+4, b, b+4); // true cout << lexicographical_compare(a, a+4, c, c+2); // false cout << lexicographical_compare(a, a+4, a, a+4); // false cout << lexicographical_compare(c, c+2, b, b+4); // true }
equal function template
lower_bound function template | Finds lower bound for a value's position in a sorted range using binary search |
template<typename FwdIter, typename T> FwdIter lower_bound (FwdIter first, FwdIter last, const T& value); template<typename FwdIter, typename T, typename Compare> FwdIter lower_bound (FwdIter first, FwdIter last, const T& value, Compare comp); |
The lower_bound function template determines where value belongs in the sorted range [ first , last ). The return value is an iterator that points to the first (leftmost) occurrence of value in the range, if value is present. Otherwise, the iterator points to the first position where you can insert value and preserve the sorted nature of the range.
The first form compares values using the < operator. The second form calls comp(*iter , value) .
Figure 13-4 (under equal_range ) shows how to find the bounds for the value 36 . The lower_bound function returns lb as the lower bound of 36 in the given range. Note that lb is the lower bound for all values in the range [19, 36], and for values in the range [37, 41], the lower bound is equal to ub .
Precondition: !(*( i + 1) < * i ) for all i in [ first , last - 1).
The lower_bound function template returns first + n , in which n is the highest value in [0, last - first ) such that *( first + m ) < value for all m in [0, n ).
Complexity is logarithmic. The number of comparisons is at most log( last - first ) + 1. Although the iterator can be a forward iterator, the best performance is obtained with a random access iterator. With a forward or bidirectional iterator, the iterator is advanced a linear number of times, even though the number of comparisons is logarithmic.
binary_search function template, equal_range function template, upper_bound function template
make_heap function template | Reorders a range to convert it into a heap |
template<typename RandIter> void make_heap (RandIter first, RandIter last); template<typename RandIter, typename Compare> void make_heap (RandIter first, RandIter last, Compare comp); |
The make_heap function template reorders the elements in the range [ first , last ) to form a heap in place.
The first form compares values using the < operator. The second form calls comp(*iter , value) .
Heap Data StructureA heap is a data structure that is ideally suited for implementing priority queues. C++ defines a range as a heap if two properties are satisfied:
The classic example of a heap is a binary tree, in which each node is greater than or equal to its children, but the relative order of the children is not specified. Thus, the root of the tree is the largest element in the entire tree. |
Postcondition: [ first , last ) is a heap.
Complexity is linear: at most, 3 x ( last - first ) comparisons are performed.
pop_heap function template, push_heap function template, sort_heap function template, <queue>
max function template | Returns the maximum of two values |
template<typename T> const T& max (const T& a, const T& b); template<typename T, typename Compare> const T& max (const T& a, const T& b, Compare comp); |
The max function template returns the larger of a and b . If neither is larger, it returns a .
The first form compares values using the < operator. The second form calls comp(a , b) .
max_element function template, min function template
max_element function template | Finds the largest element in a range |
template<typename FwdIter> FwdIter max_element (FwdIter first, FwdIter last); template<typename FwdIter, typename Compare> FwdIter max_element (FwdIter first, FwdIter last, Compare comp); |
The max_element function template returns an iterator that points to the largest element in the range [ first , last ). If there are multiple instances of the largest element, the iterator points to the first such instance.
The first form compares values using the < operator. The second form calls comp(*iter1 , *iter2) .
The max_element function template returns first + n , in which n is the smallest value in [0, last - first ) such that for all m in [0, last - first ), *( first + n ) < *( first + m ) is false.
Complexity is linear: exactly max( last - first - 1, 0) comparisons are performed.
max function template, min_element function template
merge function template | Merges sorted ranges |
template<typename InIter1, typename InIter2, typename OutIter> OutIter merge (InIter1 first1, InIter1 last1, InIter2 first2, InIter2 last2, OutIter result); template<typename InIter1, typename InIter2, typename OutIter, typename Compare> OutIter merge (InIter1 first1, InIter1 last1, InIter2 first2, InIter2 last2, OutIter result, Compare comp); |
The merge function template merges the sorted ranges [ first1 , last1 ) and [ first2 , last2 ), copying the results into the sequence that starts with result . You must ensure that the destination has enough room for the entire merged sequence.
The return value is the end value of the destination iterator, that is, result + ( last1 - first1 ) + ( last2 - first2 ).
The destination range must not overlap either of the input ranges.
The merge is stable, so elements preserve their relative order. Equivalent elements are copied , so elements from the first range come before elements from the second range.
The first form compares values using the < operator. The second form calls comp(*iter1 , *iter2) .
Let length1 = last1 - first1 and length2 = last2 - first2 .
Precondition: !(*( i + 1) < * i ) for all i in [ first1 , last1 - 1) and !(*( j + 1) < * j ) for all j in [ first2 , last2 - 1).
Postcondition: !(*( i + 1) < * i ) for all i in [ result , result + length1 + length2 - 1).
Complexity is linear: at most, length1 + length2 - 1 comparisons are performed.
inplace_merge function template, sort function template
min function template | Returns the minimum of two values |
template<typename T> const T& min (const T& a, const T& b); template<typename T, typename Compare> const T& min (const T& a, const T& b, Compare comp); |
The min function template returns the smaller of a and b . If neither is smaller, it returns a .
The first form compares values using the < operator. The second form calls comp(a , b) .
max function template, min_element function template
min_element function template | Finds the smallest value in a range |
template<typename FwdIter> FwdIter min_element (FwdIter first, FwdIter last); template<typename FwdIter, typename Compare> FwdIter min_element (FwdIter first, FwdIter last, Compare comp); |
The min_element function template returns an iterator that points to the smallest element in the range [ first , last ). If there are multiple instances of the smallest element, the iterator points to the first such instance.
The first form compares values using the < operator. The second form calls comp(*iter1 , *iter2) .
The min_element function template returns first + n , in which n is the smallest value in [0, last - first ) such that for all m in [0, last - first ), *( first + m ) < *( first + n ) is false.
Complexity is linear: exactly max( last - first - 1, 0) comparisons are performed.
max_element function template, min function template
mismatch function template | Finds first position where two ranges differ |
template<typename InIter1, typename InIter2> pair<InIter1, InIter2> mismatch (InIter1 first1, InIter1 last1, InIter2 first2); template<typename InIter1, typename InIter2, typename BinaryPredicate> pair<InIter1, InIter2> mismatch (InIter1 first1, InIter1 last1, InIter2 first2, BinaryPredicate pred); |
The mismatch function template compares two sequences pairwise and returns a pair of iterators that identifies the first elements at which the sequences differ. The first sequence is [ first1 , last1 ), and the second sequence starts at first2 and has at least as many elements as the first sequence.
The return value is a pair of iterators; the first member of the pair points to an element of the first sequence, and second member of the pair points to an element of the second sequence. The two iterators have the same offset within their respective ranges. If the two sequences are equivalent, the pair returned is last1 and an iterator that points to the second sequence at the same offset (let's call it last2 ).
The first form compares items with the == operator. The second form calls pred(*iter1 , *iter2) .
Figure 13-8 illustrates how the mismatch function template works.
The mismatch function template returns the pair ( first1 + n , first2 + n ), in which n is the smallest value in [0, last1 - first1 ) such that *( first1 + n ) == *( first2 + n ) is false and *( first1 + m ) == *( first2 + m ) is true for all m in [0, n ). If there is no such n , n = last1 - first1 .
Complexity is linear: at most last1 - first1 comparisons are performed.
equal function template, search function template, pair in <utility>
next_permutation function template | Generates next permutation |
template<typename BidiIter> bool next_permutation (BidiIter first, BidiIter last); template<typename BidiIter, typename Compare> bool next_permutation (BidiIter first, BidiIter last, Compare comp); |
The next_permutation function template rearranges the contents of the range [ first , last ) for the next permutation, assuming that there is a set of lexicographically ordered permutations . The return value is true if the next permutation is generated, or false if the range is at the last permutation, in which case the function cycles, and the first permutation is generated (that is, with all elements in ascending order).
Figure 13-9 shows all the permutations, in order, for a sequence. The next_permutation function swaps elements to form the next permutation. For example, if the input is permutation 2, the result is permutation 3. If the input is permutation 6, the result is permutation 1, and next_permutation returns false .
Example 13-4 shows a simple program that prints all the permutations of a sequence of integers. You can use this program to better understand the next_permutation function template.
#include <algorithm> #include <iostream> #include <istream> #include <iterator> #include <ostream> #include <vector> void print(const std::vector<int>& v) { std::copy(v.begin( ), v.end( ), std::ostream_iterator<int>(std::cout, " ")); std::cout << '\n'; } int main( ) { std::cout << "Enter a few integers, followed by EOF:"; std::istream_iterator<int> start(std::cin); std::istream_iterator<int> end; std::vector<int> v(start, end); // Start with the first permutation (ascending order). std::sort(v.begin( ), v.end( )); print(v); // Print all the subsequent permutations. while (std::next_permutation(v.begin( ), v.end( ))) print(v); }
Complexity is linear: at most, there are ( last - first ) / 2 swaps.
lexicographical_compare function template, prev_permutation function template, swap function template
nth_element function template | Reorders a range to properly place an item at the nth position |
template<typename RandIter> void nth_element (RandIter first, RandIter nth, RandIter last); template<typename RandIter, typename Compare> void nth_element (RandIter first, RandIter nth, RandIter last, Compare comp); |
The nth_element function template reorders the range [ first , last ) so that *nth is assigned the value that would be there if the entire range were sorted. It also partitions the range so that all elements in the range [ first , nth ) are less than or equal to the elements in the range [ nth , last ).
The order is not stablethat is, if there are multiple elements that could be moved to position nth and preserve the sorted order, you cannot predict which element will be moved to that position.
Figure 13-10 illustrates how the nth_element function template works.
Precondition: nth is in the range [ first , last ).
Postcondition: * i < * nth for all i in [ first , nth ), !(* j < * nth ) for all j in [ nth , last ), and !(* k < * nth ) for all k in [ nth + 1, last ).
Complexity is linear for the average case but is allowed to perform worse in the worst case.
partition function template, partial_sort function template, sort function template
partial_sort function template | Sorts the first part of a range |
template<typename RandIter> void partial_sort (RandIter first, RandIter middle, RandIter last); template<typename RandIter, typename Compare> void partial_sort (RandIter first, RandIter middle, RandIter last, Compare comp); |
The partial_sort function template sorts the initial middle - first elements of the range [ first , last ) into the range [ first , middle ). The remaining elements at [ middle , last ) are not in any particular order.
The first form compares values using the < operator. The second form calls comp(*iter1 , *iter2) .
See Figure 13-11 for an illustration of the partial-sort algorithm.
Postcondition: for all i in [ first , middle - 1), *( i + 1) < * i is false, and for all j in [ middle , last ) and for all i in [ first , middle ), * j < * i is false.
Complexity is logarithmic, taking about ( last - first ) x log( middle - first ) comparisons.
nth_element function template, partial_sort_copy function template, partition function template, sort function template
partial_sort_copy function template | Sorts and copies the first part of a range |
template<typename InIter, typename RandIter> RandIter partial_sort_copy (InIter first, InIter last, RandIter result_first, RandIter result_last); template<typename InIter, typename RandIter, typename Compare> RandIter partial_sort_copy (InIter first, InIter last, RandIter result_first, RandIter result_last, Compare comp); |
The partial_sort_copy function template copies and sorts elements from the range [ first , last ) into the range [ result_first , result_last ). The number of items copied ( N ) is the smaller of last - first and result_last - result_first . If the source range is smaller than the result range, the sorted elements are taken from the entire source range [ first , last ) and copied into the first N positions of the result range, starting at result_first . If the source range is larger, it is copied and sorted into the first N positions of the result range, leaving the elements in [ result_first + N , result_last ) unmodified. The return value is result_first + N .
The first form compares values using the < operator. The second form calls comp(*iter1 , *iter2) .
Let n = min( last - first , result_last - result_first ).
Postcondition: for all i in [ result_first , result_first + n - 1), *( i + 1) < * i is false.
Complexity is logarithmic, taking about ( last - first ) x log n comparisons.
nth_element function template, partial_sort_copy function template, partition function template, sort function template
partition function template | Partitions a range according to a predicate |
template<typename BidiIter, typename Predicate> BidiIter partition (BidiIter first, BidiIter last, Predicate pred); |
The partition function template swaps elements in the range [ first , last ) so that all elements that satisfy pred come before those that do not. The relative order of elements is not preserved.
The return value is an iterator that points to the first element for which pred is false, or last if there is no such element.
Figure 13-12 illustrates the partition function template for a predicate that tests whether a number is even:
function iseven(int n) { return n % 2 == 0; }
Postcondition: Let r be an iterator in the range [ first , last ] such that pred (* i ) is true for all i in [ first , r ), and pred (* j ) is false for all j in [ r , last ).
The partition function template returns r .
Complexity is linear: pred is called exactly last - first times, and at most ( last - first ) / 2 swaps are performed.
nth_element function template, partial_sort function template, sort function template, stable_partition function template
pop_heap function template | Removes largest element from a heap |
template<typename RandIter> void pop_heap (RandIter first, RandIter last); template<typename RandIter, typename Compare> void pop_heap (RandIter first, RandIter last, Compare comp); |
The pop_heap function template copies the first (largest) element from the heap in [ first , last ) to the end of the range, that is, * ( last - 1). It then ensures that the elements remaining in [ first , last - 1) form a heap.
The first form compares values using the < operator. The second form calls comp(*iter1 , *iter2) .
Precondition: [ first , last ) is a heap (see make_heap for the definition of a heap).
Postcondition: [ first , last - 1) is a heap, and !(*( last - 1) < * i ) for all i in [ first , last - 1).
Complexity is logarithmic: at most 2 x log( last - first ) comparisons are performed.
make_heap function template, push_heap function template, sort_heap function template, <queue>
prev_permutation function template | Generates previous permutation |
template<typename BidiIter> bool prev_permutation (BidiIter first, BidiIter last); template<typename BidiIter, typename Compare> bool prev_permutation (BidiIter first, BidiIter last, Compare comp); |
The prev_permutation function template rearranges the contents of the range [ first , last ) to the previous permutation, assuming that there is a set of lexicographically ordered permutations. The return value is true if the previous permutation is generated, or false if the range is at the first permutation, in which case the function cycles and generates the last permutation (that is, with all elements in descending order).
Figure 13-9 (under next_permutation ) shows all the permutations, in order, for a sequence. The prev_permutation function swaps elements to form the previous permutation. For example, if the input is permutation 3, the result is permutation 2. If the input is permutation 1, the result is permutation 6, and prev_permutation returns false .
Complexity is linear: at most ( last - first ) / 2 swaps are performed.
lexicographical_compare function template, next_permutation function template, swap function template
push_heap function template | Adds a value to a heap |
template<typename RandIter> void push_heap (RandIter first, RandIter last); template<typename RandIter, typename Compare> void push_heap (RandIter first, RandIter last, Compare comp); |
The push_heap function template adds the item at last - 1 to the heap in [ first , last - 1), forming a new heap in the range [ first , last ).
The first form compares values using the < operator. The second form calls comp(*iter1 , *iter2) .
Precondition: [ first , last - 1) is a heap (see make_heap for the definition of a heap).
Postcondition: [ first , last ) is a heap.
Complexity is logarithmic: at most log( last - first ) comparisons are performed.
make_heap function template, pop_heap function template, sort_heap function template, <queue>
random_shuffle function template | Reorders a range into a random order |
template<typename RandIter> void random_shuffle (RandIter first, RandIter last); template<typename RandIter, typename RandomNumberGenerator> void random_shuffle (RandIter first, RandIter last, RandomNumberGenerator& rand); |
The random_shuffle function template changes the order of elements in the range [ first , last ) to a random order. The first form uses an implementation-defined random number generator to produce a uniform distribution. The second form calls rand ( n ) to generate random numbers, in which n is a positive value of type iterator_traits<RandIter>::difference_type . The return value from rand must be convertible to the same difference_type and be in the range [0, n ).
Complexity is linear: exactly ( last - first ) + 1 swaps are performed.
swap function template, rand in <cstdlib>
remove function template | Reorders a range to remove all occurrences of a value |
template<typename FwdIter, typename T> FwdIter remove (FwdIter first, FwdIter last, const T& value); |
The remove function template "removes" items that are equal to value from the range [ first , last ). Nothing is actually erased from the range; instead, items to the right are copied to new positions so they overwrite the elements that are equal to value . The return value is one past the new end of the range. The relative order of items that are not removed is stable.
|
See Figure 13-13 (under remove_copy ) for an example of the removal process.
The remove function template assigns *( first + n ++) = *( first + m ), in which n starts at 0, for all values of m in [0, last - first ) in which *( first + m ) == value is false. The return value is first + n .
Complexity is linear: exactly last - first comparisons are performed.
remove_copy function template, remove_copy_if function template, remove_if function template, replace function template
remove_copy function template | Copies elements that are not equal to a value |
template<typename InIter, typename OutIter, typename T> OutIter remove_copy (InIter first, InIter last, OutIter result, const T& value); |
The remove_copy function template copies items from the range [ first , last ) to the range that starts at result . Only items that are not equal to value are copied, that is, cases in which operator== returns false.
The return value is one past the end of the result range. The relative order of items that are not removed is stable.
The source and result ranges must not overlap. Figure 13-13 illustrates the removal process.
The remove_copy function template assigns *( result + n ++) = *( first + m ), in which n starts at 0, for all values of m in [0, last - first ), in which *( first + m ) == value is false. The return value is result + n .
Complexity is linear: exactly last - first comparisons are performed.
remove function template, remove_copy_if function template, replace_copy function template
remove_copy_if function template | Copies elements for which a predicate returns false |
template<typename InIter, typename OutIter, typename Predicate> OutIter remove_copy_if (InIter first, InIter last, OutIter result, Predicate pred); |
The remove_copy_if function template copies items from the range [ first , last ) to the range that starts at result . Only items for which pred returns false are copied.
The return value is one past the end of the result range. The relative order of items that are not removed is stable.
The source and result ranges must not overlap. See Figure 13-13 (under remove_copy ) for an example of the removal process.
The remove_copy_if function template assigns *( result + n ++) = *( first + m ), in which n starts at 0, for all values of m in [0, last - first ), in which pred (*( first + m )) is false. The return value is result + n .
Complexity is linear: exactly last - first comparisons are performed.
remove function template, remove_copy function template, replace_copy_if function template
remove_if function template | Reorders a range to remove elements for which a predicate returns false |
template<typename FwdIter, typename Predicate> FwdIter remove_if (FwdIter first, FwdIter last, Predicate pred); |
The remove_if function template "removes" items for which pred returns false from the range [ first , last ). The return value is one past the new end of the range. The relative order of items that are not removed is stable.
Nothing is actually erased from the underlying container; instead, items to the right are assigned to new positions so they overwrite the elements for which pred returns false . See Figure 13-13 (under remove_copy ) for an example of the removal process.
The remove_if function template assigns *( first + n ++) = *( first + m ), in which n starts at 0, for all values of m in [0, last - first ), in which pred (*( first + m )) is false. The return value is first + n .
Complexity is linear: exactly last - first comparisons are performed.
remove function template, remove_copy_if function template, replace_if function template
replace function template | Replaces all occurrences of one value with another value |
template<typename FwdIter, typename T> void replace (FwdIter first, FwdIter last, const T& old_value, const T& new_value); |
The replace function template replaces all occurrences of old_value in [ first , last ) with new_value . See Figure 13-14 (under replace_copy ) for an example of the replacement process.
The replace function template assigns * i = (* i == old_value ) ? new_value : * i for all i in [ first , last ).
Complexity is linear: exactly last - first comparisons are performed.
remove function template, replace_copy function template, replace_copy_if function template, replace_if function template, transform function template
replace_copy function template | Copies a range, replacing occurrences of one value with another value |
template<typename InIter, typename OutIter, typename T> OutIter replace_copy (InIter first, InIter last, OutIter result, const T& old_value, const T& new_value); |
The replace_copy function template copies values from [ first , last ) to the range that starts at result . Values that are equal to old_value are replaced with new_value ; other values are copied without modification.
The return value is an iterator that points to one past the end of the result range. The source and result ranges must not overlap. Figure 13-14 illustrates the replacement process.
The replace_copy function template assigns *( result + n ) = *( first + n ) == old_value ? new_value : *( first + n ) for all n in [0, last - first ).
Complexity is linear: exactly last - first comparisons are performed.
remove_copy function template, replace function template, replace_copy_if function template, transform function template
replace_copy_if function template | Copies values, replacing those that satisfy a predicate |
template<typename Iter, typename OutIter, typename Predicate, typename T> OutIter replace_copy_if (Iter first, Iter last, OutIter result, Predicate pred, const T& new_value); |
The replace_copy_if function template copies values from [ first , last ) to the range that starts at result . Elements for which pred returns true are replaced with new_value ; other elements are copied without modification.
The return value is an iterator that points to one past the end of the result range. The source and result ranges must not overlap. See Figure 13-14 (under replace_copy ) for an example of the replacement process.
The replace_copy_if function template assigns *( result + n ) = *( first + n ) == pred (*( first + n )) ? new_value : *( first + n ) for all n in [0, last - first ).
Complexity is linear: exactly last - first comparisons are performed.
remove_copy_if function template, replace function template, replace_copy function template, replace_if function template, transform function template
replace_if function template | Replaces values that satisfy a predicate |
template<typename FwdIter, typename Predicate, typename T> void replace_if (FwdIter first, FwdIter last, Predicate pred, const T& new_value); |
The replace_if function template replaces all values in [ first , last ) for which pred is true with new_value . See Figure 13-14 (under replace_copy ) for an example of the replacement process.
The replace_if function template assigns * i = pred (* i ) ? new_value : * i for all i in [ first , last ).
Complexity is linear: exactly last - first comparisons are performed.
remove_if function template, replace function template, replace_copy function template, transform function template
reverse function template | Reverses the values in a range |
template<typename BidiIter> void reverse (BidiIter first, BidiIter last); |
The reverse function template reverses the order of the items in the range [ first , last ). See Figure 13-15 (under reverse_copy ) for an example.
The reverse function template swaps *( first + n ) with *( last - n - 1) for all n in [0, ( last - first ) / 2].
Complexity is linear: exactly ( last - first ) / 2 swaps are performed.
reverse_copy function template, rotate function template, swap function template
reverse_copy function template | Copies a range in reverse order |
template<typename BidiIter, typename OutIter> OutIter reverse_copy (BidiIter first, BidiIter last, OutIter result); |
The reverse_copy function template copies items in reverse order from the range [ first , last ) to the range that starts at result . In other words, *(last - 1) is first copied to *result , then *(last - 2) is copied to *(result + 1) , and so on. The return value is an iterator that points to one past the end of the result range. The source and result ranges must not overlap. Figure 13-15 shows an example of reversing a range.
The reverse_copy function template assigns *( result + n ) = *( last - n - 1) for all n in [0, last - first ).
Complexity is linear: exactly last - first assignments are performed.
copy_backward function template, reverse function template, rotate_copy function template
rotate function template | Rotates elements in a range |
template<typename FwdIter> void rotate (FwdIter first, FwdIter middle, FwdIter last); |
The rotate function template rotates elements in the range [ first , last ) to the left so that the items in the range [ middle , last ) are moved to the start of the new sequence. Elements in the range [ first , middle ) are rotated to the end. See Figure 13-16 for an example.
For all n in [0, last - first ), the rotate function template moves *( first + n ) into position first + ( n + ( last - middle )) % ( last - first ).
Complexity is linear: at most last - first swaps are performed.
reverse function template, rotate_copy function template
rotate_copy function template | Rotates and copies items in a range |
template<typename FwdIter, typename OutIter> OutIter rotate_copy (FwdIter first, FwdIter middle, FwdIter last, OutIter result); |
The rotate_copy function template copies elements from the range [ middle , last ) to the range that starts at result followed by the elements from [ first , middle ), thereby effecting a rotation to the left. The return value is one past the end of the result range.
The source and result ranges must not overlap. Figure 13-16 shows an example of rotation.
The rotate_copy function template assigns *( result + ( n + ( last - middle )) % ( last - first )) = *( first + n ) for all n in [0, last - first ). It returns result + ( last - first ).
Complexity is linear: exactly last - first assignments are performed.
reverse_copy function template, rotate function template
search function template | Searches a range for a subsequence |
template<typename FwdIter1, typename FwdIter2> FwdIter1 search (FwdIter1 first1, FwdIter1 last1, FwdIter2 first2, FwdIter2 last2); template<typename FwdIter1, typename FwdIter2, typename BinaryPredicate> FwdIter1 search (FwdIter1 first1, FwdIter1 last1, FwdIter2 first2, FwdIter2 last2, BinaryPredicate pred); |
The search function template finds the first (leftmost) subsequence [ first2 , last2 ) within the range [ first1 , last1 ). It returns an iterator that points to the start of the subsequence or last1 if the subsequence is not found.
The first form compares items with the == operator. The second form calls pred(*iter1 , *iter2) .
Figure 13-5 (under find_end ) illustrates the search function template.
Let length1 = last1 - first1 and length2 = last2 - first2 .
The search function template returns first1 + n , in which n is the smallest value in the range [0, length1 - length2 ) such that *( i + n + m ) == ( first2 + m ) for all m in the range [0, length2 ). It returns last1 if no such n can be found.
Complexity: at most length1 x length2 comparisons are performed.
find function template, find_end function template, search_n function template
search_n function template | Searches a range for a repeated value |
template<typename FwdIter, typename Size, typename T> FwdIter search_n (FwdIter first, FwdIter last, Size count, const T& value); template<typename FwdIter, typename Size, typename T, typename BinaryPredicate> FwdIter search_n (FwdIter first, FwdIter last, Size count, const T& value, BinaryPredicate pred); |
The search_n function template finds the first (leftmost) subsequence of count adjacent occurrences of value in the range [ first , last ). It returns an iterator that points to the start of the subsequence or last if the subsequence is not found.
The first form compares items with the == operator. The second form calls pred(*iter , value) .
The search_n function template returns first + n , in which n is the smallest value in the range [0, last - first ) such that *( i + n + m ) == value for all m in the range [0, count ). It returns last if no such n can be found.
Complexity: at most n x ( last - first ) comparisons are performed.
find function template, search function template
set_difference function template | Computes set difference of sorted ranges |
template<typename InIter1, typename InIter2, typename OutIter> OutIter set_difference (InIter1 first1, InIter1 last1, InIter2 first2, InIter2 last2, OutIter result); template<typename InIter1, typename InIter2, typename OutIter, typename Compare> OutIter set_difference (InIter1 first1, InIter1 last1, InIter2 first2, InIter2 last2, OutIter result, Compare comp); |
The set_difference function template copies elements from the sorted range [ first1 , last1 ) to the range starting at result . Only those elements that are not also present in the sorted range [ first2 , last2 ) are copied. An iterator that points to one past the end of the result range is returned.
The result range must not overlap either source range.
The first version compares items using the < operator. The second version uses comp(X , Y) to test whether X < Y .
Figure 13-17 shows an example of a set difference using multisets.
Precondition: !(*( i + 1) < * i ) for all i in [ first1 , last1 - 1) and !(*( j + 1) < * j ) for all j in [ first2 , last2 - 1).
Postcondition: !(*( i + 1) < * i ) for all i in [ result , return - 1).
The set_difference function template assigns *( result + n ++) = *( first1 + m ) for all m in [ first1 , last1 ), in which *( first1 + m ) is not in [ first2 , last2 ). It returns result + n .
Complexity is linear: at most 2 x (( last1 - first1 ) + ( last2 - first2 )) - 1 comparisons are performed.
includes function template, set_intersection function template, set_symmetric_difference function template, set_union function template
set_intersection function template | Computes intersection of sorted ranges |
template<typename InIter1, typename InIter2, typename OutIter> OutIter set_intersection (InIter1 first1, InIter1 last1, InIter2 first2, InIter2 last2, OutIter result); template<typename InIter1, typename InIter2, typename OutIter, typename Compare> OutIter set_intersection (InIter1 first1, InIter1 last1, InIter2 first2, InIter2 last2, OutIter result, Compare comp); |
The set_intersection function template copies elements from the sorted range [ first1 , last1 ) to the range starting at result . Only those elements that are also present in the sorted range [ first2 , last2 ) are copied. An iterator that points to one past the end of the result range is returned.
The result range must not overlap either source range.
The first version compares items using the < operator. The second version uses comp(X , Y) to test whether X < Y .
Figure 13-18 shows an example of intersection using multisets.
Precondition: !(*( i + 1) < * i ) for all i in [ first1 , last1 - 1) and !(*( j + 1) < * j ) for all j in [ first2 , last2 - 1).
Postcondition: !(*( i + 1) < * i ) for all i in [ result , return - 1).
The set_intersection function template assigns *( result + n ++) = *( first1 + m ) for all m in [ first1 , last1 ), in which *( first1 + m ) is in [ first2 , last2 ). It returns result + n .
Complexity is linear: at most 2 x (( last1 - first1 ) + ( last2 - first2 )) - 1 comparisons are performed.
includes function template, set_difference function template, set_symmetric_difference function template, set_union function template
set_symmetric_difference function template | Computes symmetric difference of sorted ranges |
template<typename InIter1, typename InIter2, typename OutIter> OutIter set_symmetric_difference (InIter1 first1, InIter1 last1, InIter2 first2, InIter2 last2, OutIter result); template<typename InIter1, typename InIter2, typename OutIter, typename Compare> OutIter set_symmetric_difference (InIter1 first1, InIter1 last1, InIter2 first2, InIter2 last2, OutIter result, Compare comp); |
The set_symmetric_difference function template merges elements from the sorted ranges [ first1 , last1 ) and [ first2 , last2 ), copying the sorted, merged results to the range starting at result . Only those elements that are not also present in the sorted range [ first2 , last2 ) are copied from [ first1 , last1 ), and only those not present in the range [ first1 , last1 ) are copied from [ first2 , last2 ). An iterator that points to one past the end of the result range is returned.
The result range must not overlap either source range.
The first version compares items using the < operator. The second version uses comp(X , Y) to test whether X < Y .
Figure 13-19 shows an example of a set symmetric difference using multisets.
Precondition: !(*( i + 1) < * i ) for all i in [ first1 , last1 - 1) and !(*( j + 1) < * j ) for all j in [ first2 , last2 - 1).
Postcondition: !(*( i + 1) < * i ) for all i in [ result , return - 1).
Complexity is linear: at most 2 x (( last1 - first1 ) + ( last2 - first2 )) - 1 comparisons are performed.
includes function template, set_difference function template, set_intersection function template, set_union function template
set_union function template | Computes union of sorted ranges |
template<typename InIter1, typename InIter2, typename OutIter> OutIter set_union (InIter1 first1, InIter1 last1, InIter2 first2, InIter2 last2, OutIter result); template<typename InIter1, typename InIter2, typename OutIter, typename Compare> OutIter set_union (InIter1 first1, InIter1 last1, InIter2 first2, InIter2 last2, OutIter result, Compare comp); |
The set_union function template merges elements from the sorted ranges [ first1 , last1 ) and [ first2 , last2 ), copying the sorted, merged results to the range starting at result . If an element is present in both ranges, only one element is copied to the result range. If the input ranges contain duplicates, each occurrence of an element in an input range results in a copy in the result range. An iterator that points to one past the end of the result range is returned.
The result range must not overlap either source range.
The first version compares items using the < operator. The second version uses comp(X , Y) to test whether X < Y .
Figure 13-20 shows an example of a set union using multisets.
Precondition: !(*( i + 1) < * i ) for all i in [ first1 , last1 - 1) and !(*( j + 1) < * j ) for all j in [ first2 , last2 - 1).
Postcondition: !(*( i + 1) < * i ) for all i in [ result , return - 1).
Complexity is linear: at most 2 x (( last1 - first1 ) + ( last2 - first2 )) - 1 comparisons are performed.
includes function template, merge function template, set_difference function template, set_intersection function template, set_symmetric_difference function template
sort function template | Sorts a range in place |
template<typename RandIter> void sort (RandIter first, RandIter last); template<typename RandIter, typename Compare> void sort (RandIter first, RandIter last, Compare comp); |
The sort function template sorts the range [ first , last ) in place. The sort is not stable, so equivalent elements do not preserve their original order.
The first version compares items using the < operator. The second version uses comp(X , Y) to test whether X < Y .
Postcondition: !(*( i + 1) < * i ) for all i in [ first , last - 1).
Complexity is n log n comparisons in the average case, in which n = last - first . Worst case performance might be worse. Use stable_sort if the worst-case performance is more important than the average performance.
merge function template, nth_element function template, partial_sort function template, partition function template, sort_heap function template, stable_sort function template
sort_heap function template | Sorts a heap in place |
template<typename RandIter> void sort_heap (RandIter first, RandIter last); template<typename RandIter, typename Compare> void sort_heap (RandIter first, RandIter last, Compare comp); |
The sort_heap function template sorts a heap in the range [ first , last ). The sort is not stable, so equivalent elements do not preserve their original order.
The first version compares items using the < operator. The second version uses comp(X , Y) to test whether X < Y .
Precondition: [ first , last ) is a heap (see make_heap for the definition of a heap).
Postcondition: !(*( i + 1) < * i ) for all i in [ first , last - 1).
Complexity is at most n log n comparisons, in which n = last - first .
make_heap function template, pop_heap function template, push_heap function template, sort function template, <queue>
stable_partition function template | Partitions a range in stable order |
template<typename BidiIter, typename Predicate> BidiIter stable_partition (BidiIter first, BidiIter last, Predicate pred); |
The stable_partition function template swaps elements in the range [ first , last ) so that all elements that satisfy pred come before those that do not. The relative order of elements in each partition is preserved.
The return value is an iterator that points to the first element for which pred is false, or last if there is no such element.
Figure 13-12 (under partition ) illustrates the partition functionality.
Postcondition: Let r be an iterator in the range [ first , last ] such that pred (* i ) is true for all i in [ first , r ), and pred (* j )is false for all j in [ r , last ).
The stable_partition function template returns r .
Complexity is linear if there is enough memory. Otherwise, at most n log n swaps are performed, in which n = last - first . In all cases, pred is called exactly n times.
nth_element function template, partial_sort function template, partition function template, stable_sort function template
stable_sort function template | Sorts a range in place in stable order |
template<typename RandIter> void stable_sort (RandIter first, RandIter last); template<typename RandIter, typename Compare> void stable_sort (RandIter first, RandIter last, Compare comp); |
The stable_sort function template sorts the range [ first , last ) in place. The sort is stable, so equivalent elements preserve their original order.
The first version compares items using the < operator. The second version uses comp(X , Y) to test whether X < Y .
Postcondition: !(*( i + 1) < * i ) for all i in [ first , last - 1).
Complexity is at most n log n comparisons, in which n = last - first , provided that enough memory is available for temporary results. If memory is limited, the complexity is at most n (log n ) 2 comparisons.
merge function template, nth_element function template, partial_sort function template, sort function template, sort_heap function template, stable_partition function template
swap function template | Swaps two values |
template<typename T> void swap (T& a, T& b); |
The swap function template swaps the values of a and b .
The standard containers all specialize the swap template to call their swap member functions, which usually run in constant time, regardless of the number of elements in the containers.
iter_swap function template, swap_ranges function template
swap_ranges function template | Swaps all values in two ranges |
template<typename FwdIter1, typename FwdIter2> FwdIter2 swap_ranges (FwdIter1 first1, FwdIter1 last1, FwdIter2 first2); |
The swap_ranges function template swaps all the elements in [ first1 , last1 ) with corresponding elements in the range that starts at first2 (and has the same length as the first range). The return value is one past the end of the second range. The two ranges must not overlap.
The swap_ranges function template performs the equivalent of swap (*( first1 + n ), *( first2 + n )) for all n in [0, last1 - first1 ).
Complexity is linear: exactly last1 - first1 swaps are performed.
iter_swap function template, swap function template
transform function template | Copies one or two ranges after applying an operator to each element |
template<typename InIter, typename OutIter, typename UnaryOperation> OutIter transform (InIter first, InIter last, OutIter result, UnaryOperation unop); template<typename InIter1, typename InIter2, typename OutIter, typename BinaryOperation> OutIter transform (InIter1 first1, InIter1 last1, InIter2 first2, OutIter result, BinaryOperation binop); |
The transform function template assigns a new value to each element in the range that starts at result . In the first case, the new value is unop(*iter) , in which iter is an iterator over [ first , last ).
In the second case, the new value is binop(*iter1 , *iter2) , in which iter1 ranges over [ first1 , last1 ) and iter2 iterates over the range that starts at first2 . The second input range must be at least as long as the first.
The return value is one past the end of the result range. The result range can be the same as any of the input ranges.
The first form of transform assigns *( result + n ) = unop (*( first + n )) for all n in [0, last - first ).
The second form assigns *( result + n ) = binop (*( first1 + n ), *( first2 + n )) for all n in [0, last1 - first1 ).
Complexity is linear: unop or binop is called exactly n times, in which n = last - first for a unary operator or last1 - first1 for a binary operator.
copy function template, for_each function template
unique function template | Removes adjacent, equal values from a range |
template<typename FwdIter> FwdIter unique (FwdIter first, FwdIter last); template<typename FwdIter, typename BinaryPredicate> FwdIter unique (FwdIter first, FwdIter last, BinaryPredicate pred); |
The unique function template "removes" repetitions of adjacent, identical elements from the range [ first , last ). The return value is one past the new end of the range. For each sequence of identical elements, only the first is kept. The input range does not have to be sorted, but if it is, all duplicates are "removed," leaving only unique values (hence the function's name).
Nothing is actually erased from the underlying container; instead, items to the right are copied to new positions at lower indices (to the left) so they overwrite the elements that are duplicates. See Figure 13-21 (under unique_copy ) for an example of the removal process.
The first form compares items with the == operator. The second form calls pred(a , b) .
The unique function template assigns *( first + n ++) = *( first + m ) for all m in [0, last - first ), in which m == 0 or *( first + m ) == *( first + m - 1) is false. It returns first + n .
Complexity is linear: exactly max(0, last - first - 1) comparisons are performed.
remove function template, unique_copy function template
unique_copy function template | Copies unique values |
template<typename InIter, typename OutIter> OutIter unique_copy (InIter first, InIter last, OutIter result); template<typename InIter, typename OutIter, typename BinaryPredicate> OutIter unique_copy (InIter first, InIter last, OutIter result, BinaryPredicate pred); |
The unique_copy function template copies items from [ first , last ) to the range that starts at result , removing duplicates. For each sequence of identical elements, only the first is kept. The return value is one past the end of the result range.
The first form compares items with the == operator. The second form calls pred(a , b) .
See Figure 13-21 for an example that calls unique_copy .
The unique_copy function template assigns *( result + n ++) = *( first + m ) for all m in [0, last - first ), in which m == 0 or *( first + m ) == *( first + m - 1) is false. It returns result + n .
Complexity is linear: exactly last - first comparisons are performed.
remove_copy function template, unique function template
upper_bound function template | Finds upper bound for a value's position in a sorted range using binary search |
template<typename FwdIter, typename T> FwdIter upper_bound (FwdIter first, FwdIter last, const T& value); template<typename FwdIter, typename T, typename Compare> FwdIter upper_bound (FwdIter first, FwdIter last, const T& value, Compare comp); |
The upper_bound function template determines where value belongs in the sorted range [ first , last ). The return value is an iterator that points to one past the last (rightmost) occurrence of value in the range, if value is present. Otherwise, the iterator points to the last position where you can insert value and preserve the sorted nature of the range.
The first form compares values using the < operator. The second form calls comp(*iter , value) .
Figure 13-4 (under equal_range ) shows an example of finding the bounds for the value 36 . The upper_bound function returns ub as the upper bound of 36 in the given range. Note that it returns ub as the upper bound for all values in the range [ 36 , 41 ]. For values in the range [ 19 , 35 ], the upper bound is equal to lb .
Precondition: !(*( i + 1) < * i ) for all i in [ first , last - 1).
The upper_bound function template returns first + n , in which n is the highest value in [0, last - first ) such that *( first + m ) < value is false for all m in [0, n ).
Complexity is logarithmic. The number of comparisons is at most log( last - first ) + 1. Although the iterator can be a forward iterator, the best performance is obtained with a random access iterator. With a forward or bidirectional iterator, the iterator is advanced a linear number of times, even though the number of comparisons is logarithmic.
binary_search function template, equal_range function template, lower_bound function template