CONTENTS |
This chapter describes all of the algorithms of the C++ standard library. It begins with an overview of all algorithms and some general remarks about the algorithms. It then presents the exact signature of each algorithm and one or more examples of its use.
To use the algorithms of the C++ standard library you must include the header file <algorithm>^{[1]}:
#include <algorithm>
This header file also includes some auxiliary functions. min(), max(). and swap() were presented in Section 4.4.1, and Section 4.4.2. The iter_swap() iterator function was discussed in Section 7.3.3.
Some of the STL algorithms are provided for numeric processing. Thus, they are defined in <numeric>^{[1]}:
#include <numeric>
In general, Chapter 12 discusses the numeric components of the C++ standard library. However, I decided to discuss the numeric algorithms here because, in my opinion, the fact that they are STL algorithms is more important than the fact that they are used for numeric processing.
When you use algorithms, you often also need function objects and function adapters. These were described in Chapter 8 and are defined in <functional>^{[2]}:
#include <functional>
This section presents an overview of all of the C++ standard library algorithms. From it you can get an idea of their abilities and be better able to find the best algorithm to solve a certain problem.
Algorithms were introduced in Chapter 5 along with the STL. In particular, Section 5.4, and Section 5.6, discuss the role of algorithms and some important constraints regarding their use. All STL algorithms process one or more iterator ranges. The first range is usually specified by its beginning and its end. For additional ranges, in most cases you need to pass only the beginning because the end follows from the number of elements of the first range. The caller must ensure that the ranges are valid. That is, the beginning must refer to a previous or the same element of the same container as the end. Additional ranges must have enough elements.
Algorithms work in overwrite mode rather than in insert mode. Thus, the caller must ensure that destination ranges have enough elements. You can use special insert iterators (see Section 7.4.2) to switch from overwrite to insert mode.
To increase their flexibility and power, several algorithms allow the user to pass user-defined operations, which they call internally. These operations might be ordinary functions or function objects. If these functions return a Boolean value they are called predicates. You can use predicates for the following tasks:
You can pass a function or function objects that specify a unary predicate as the search criterion for a search algorithm. The unary predicate is used to check whether an element fits the criterion. For example, you could search the first element that is less than 50.
You can pass a function or function objects that specify a binary predicate as the sorting criterion for a sort algorithm. The binary predicate is used to compare two elements. For example, you could pass a criterion that lets objects that represent a person sort according to their last name (see page 294 for an example).
You can pass a unary predicate as the criterion that specifies for which elements an operation should apply. For example, you could specify that only elements with an odd value should be removed.
You can specify the numeric operation of numeric algorithms. For example, you could use accumulate(), which normally processes the sum of elements, to process the product of all elements.
Note that predicates should not modify their state due to a function call (see Section 8.1.4).
See Section 5.8, Section 5.9, and Chapter 8 for examples and details about functions and function objects that are used as algorithm parameters.
Different algorithms meet different needs. Thus, they can be c1assified by their main purposes. For example, some algorithms operate as read only, some modify elements, and some change the order of elements. This subsection gives you a brief idea of the functionality of each algorithm and in which aspect it differs from similar algorithms.
The name of an algorithm gives you a first impression of its purpose. The designers of the STL introduced two special suffixes:
The _if suffix
The _if suffix is used when you can call two forms of an algorithm that have the same number of parameters either by passing a value or by passing a function or function object. In this case, the version without the suffix is used for values, and the version with the _if suffix is used for functions and function objects. For example, find() searches for an element that has a certain value, whereas find_if() searches for an element that meets the criterion passed as a function or function object.
However, not all algorithms that have a parameter for functions and function objects have the _if suffix. When the function or function object version of an algorithm has an additional argument, it has the same name. For example, min_element() called with two arguments returns the minimum element in the range according to a comparison with operator <. If you pass a third element, it is used as comparison criterion.
The _copy suffix
The _copy suffix is used as an indication that elements are not only manipulated but also copied into a destination range. For example, reverse() reverses the order of elements inside a range, whereas reverse_copy() copies the elements into another range in reverse order.
The following subsections and sections describe the algorithms according to the following c1assification:
Nonmodifying algorithms
Modifying algorithms
Removing algorithms
Mutating algorithms
Sorting algorithms
Sorted range algorithms
Numeric algorithms
If algorithms belong to more than one category I describe them in the category that I consider to be the most important.
Nonmodifying algorithms neither change the order nor the value of the elements they process. They operate with input and forward iterators; therefore, you can call them for all standard containers. Table 9.1 lists the nonmodifying algorithms of the C++ standard library. See page 330 for nonmodifying algorithms that are provided especially for sorted input ranges.
Name | Effect | Page |
---|---|---|
for_each() | Performs an operation for each element | 334 |
count() | Returns the number of elements | 338 |
count()_if() | Returns the number of elements that match a criterion | 338 |
min_element() | Returns the element with the smallest value | 340 |
max_element() | Returns the element with the largest value | 340 |
find() | Searches for the first element with the passed value | 341 |
find_if() | Searches for the first element that matches a criterion | 341 |
search_n() | Searches for the first n consecutive elements with certain properties | 344 |
search() | Searches for the first occurrence of a subrange | 347 |
find_end() | Searches for the last occurrence of a subrange | 350 |
find_first_of() | Searches the first of several possible elements | 352 |
adjacent_find() | Searches for two adjacent elements that are equal(by some criterion) | 354 |
equal() | Returns whether two ranges are equal | 356 |
mismatch() | Returns the first elements of two sequences that differ | 358 |
lexicographical_compare() | Returns whether a range is lexicographically less than another range | 360 |
One of the most important algorithms is for_each(). for_each() calls an operation provided by the caller for each element. That operation is usually used to process each element of the range individually. For example, you can pass for_each() a function that prints each element. However, for_each() can also call a modifying operation for the elements. So for_each() can be used as both a nonmodifying and a modifying algorithm. However, you should avoid using for_each() when possible, and use other algorithms to meet your needs because the other algorithms are implemented specifically for that purpose.
Several of the nonmodifying algorithms perform searching. Unfortunately, the naming scheme of searching algorithms is a mess. In addition, the naming schemes of searching algorithms and searching string functions differ (Table 9.2). As is often the case, there are historical reasons for this. First, the STL and string c1asses were designed independently. Second, the find_end(), find_first_of(), and search_n() algorithms were not part of the original STL. So, for example, by accident the name find_end() instead of search_end() was chosen (it is easy to forget aspects of the whole picture, such as consistency, when you are caught up in the details). Also by accident, a form of search_n() breaks the general concept of the original STL. See page 346 for a description of this problem.
Search for | String Function | STL Algorithm |
---|---|---|
First occurrence of one element | find() | find() |
Last occurrence of one element | rfind() | find() with reverse iterators |
First occurrence of a subrange | find() | search() |
Last occurrence of a subrange | rfind() | find_end() |
First occurrence of several elements | find_first_of() | find_first_of() |
Last occurrence of several elements | find_last_of() | find_ first_of() with reverse iterators |
First occurrence of n consecutive Elements | search_n() |
Modifying algorithms change the value of elements. They might modify the elements of a range directly or modify them while they are being copied into another range. If elements are copied into a destination range, the source range is not changed. Table 9.3 lists the modifying algorithms of the C++ standard library.
The fundamental modifying algorithms are for_each() (again) and transform(). You can use both to modify elements of a sequence. However, their behavior differs as follows:
for_each() accepts an operation that modifies its argument. Thus, the argument has to be passed by reference. For example:
void square (int& elem) // call-by-reference { elem = elem * elem; // assign processed value directly } ... for_each(coll.begin(),coll.end(), // range square) ; // opertion
transform() uses an operation that returns the modified argument. The trick is that it can be used to assign the result to the original element. For example:
int square (int elem) // call-by-value { return elem * elem; // return processed value } ... transform (coll.begin(), coll.end(), // source range coll.begin(), // destination range square); // operation
Name | Effect | Page |
---|---|---|
for_each() | Performs an operation for each element | 334 |
copy() | Copies a range starting with the first element | 363 |
copy _backward() | Copies a range starting with the last element | 363 |
transform() | Modifies (and copies) elements; combines elements of two ranges | 367 |
merge() | Merges two ranges | 416 |
swap_ranges() | Swaps elements of two ranges | 370 |
fill() | Replaces each element with a given value | 372 |
fill_n() | Replaces n elements with a given value | 372 |
generate() | Replaces each element with the result of an operation | 373 |
generate_n() | Replaces n elements with the result of an operation | 373 |
replace() | Replaces elements that have a special value with another value | 375 |
replace()_if() | Replaces elements that match a criterion with another value | 375 |
replace_copy() | Replaces elements that have a special value while copying the whole range | 376 |
replace_copy_if() | Replaces elements that match a criterion while copying the whole range | 376 |
The approach of transform() is a bit slower because it returns and assigns the result instead of modifying the element directly. However, it is more flexible because it can also be used to modify elements while they are being copied into a different destination sequence, transform() also has another version, one that can process and combine elements of two source ranges.
Strictly speaking, merge() does not necessarily have to be part of the list of modifying algorithms. This is because it requires that its input ranges must be sorted. So it should be part of the algorithms for sorted ranges (see page 330). However, in practice, merge() also merges the elements of unsorted ranges. Of course, then the result is unsorted. Nevertheless, to be safe you should call merge() only for sorted ranges.
Note that elements of associative algorithms are constant to ensure that you can't compromise the sorted order of the elements due to an element modification. Therefore, you can't use associative containers as a destination for modifying algorithms.
In addition to these modifying algorithms, the C++ standard library provides modifying algorithms for sorted ranges. See page 330 for details.
Removing algorithms are a special form of modifying algorithms. They can remove the elements either in a single range or while they are being copied into another range. As with modifying algorithms, you can't use an associative container as a destination because the elements of the associative container are considered to be constant. Table 9.4 lists the removing algorithms of the C++ standard library.
Name | Effect | Page |
---|---|---|
remove() | Removes elements with a given value | 378 |
remove_if() | Removes elements that match a given criterion | 378 |
remove_copy() | Copies elements that do not match a given value | 380 |
remove_copy()_if() | Copies elements that do not match a given criterion | 380 |
unique() | Removes adjacent duplicates (elements that are equal to their predecessor) | 381 |
unique_copy() | Copies elements while removing adjacent duplicates | 384 |
Note that removing algorithms remove elements logically only by overwriting them with the following elements that were not removed. Thus, they do not change the number of elements in the ranges on which they operate. Instead, they return the position of the new "end" of the range. It's up to the caller to use that new end, such as to remove the elements physically. See Section 5.6.1, for a detailed discussion of this behavior.
Mutating algorithms are algorithms that change the order of elements (and not their values) by assigning and swapping their values. Table 9.5 lists the mutating algorithms of the C++ standard library. As with modifying algorithms, you can't use an associative container as a destination because the elements of the associative container are considered to be constant.
Name | Effect | Page |
---|---|---|
reverse() | Reverses the order of the elements | 386 |
reverse_copy() | Copies the elements while reversing their order | 386 |
rotate() | Rotates the order of the elements | 388 |
rotate_copy() | Copies the elements while rotating their order | 389 |
next_permutation() | Permutates the order of the elements | 391 |
prev_permutation() | Permutates the order of the elements | 391 |
random_shuffle() | Brings the elements into a random order | 393 |
partition() | Changes the order of the elements so that elements that match a criterion are at the front | 395 |
stable_partition() | Same as partition() but preserves the relative order of matching and nonmatching elements | 395 |
Sorting algorithms are a special kind of mutating algorithm because they also change the order of the elements. However, sorting is more complicated and therefore usually takes more time than simple mutating operations. In fact, these algorithms usually have worse than linear complexity^{[3]} and require random access iterators (for the destination). Table 9.6 lists the sorting algorithms.
Name | Effect | Page |
---|---|---|
sort() | Sorts all elements | 397 |
stable_sort() | Sorts while preserving order of equal elements | 397 |
partial_sort() | Sorts until the first n elements are correct | 400 |
partial_sort_copy() | Copies elements in sorted order | 402 |
nth_element() | Sorts according to the nth position | 404 |
partition() | Changes the order of the elements so that elements that match a criterion are at the front | 395 |
stable_partition() | Same as partition() but preserves the relative order of matching and nonmatching elements | 395 |
make_heap() | Converts a range into a heap | 406 |
push_heap() | Adds an element to a heap | 406 |
pop_heap() | Removes an element from a heap | 407 |
sort_heap() | Sorts the heap (it is no longer a heap after the call) | 407 |
Time often is critical for sorting algorithms. Therefore, the C++ standard library provides more than one sorting algorithm. The algorithms use different ways of sorting, and some algorithms don't sort all elements. For example, nth_element() stops when the nth element of the sequence is correct according to the sorting criterion. For the other elements it guarantees only that the previous elements have a lesser or equal value and that the following elements have a greater or equal value. To sort all elements of a sequence, you should consider the following algorithms:
sort() is based historically on quicksort. Thus, it guarantees a good runtime (n * log(n) complexity) on average but may have a very bad runtime (quadratic complexity) in the worst case:
/*sort all elements *-best n*log(n) complexity on average *-n*n complexity in worst case */ sort (coll.begin(), coll.end());
So if avoiding the worst-case behavior is important, you should use another algorithm, such as partial_sort() or stable_sort(), which are discussed next.
partial_sort() is based historically on heapsort. Thus, it guarantees n*log(n) complexity in any case. However, in most circumstances, heapsort is slower than quicksort by a factor of two to five. So, provided sort() is implemented as quicksort and partial_sort() is implemented as heapsort, partial_sort() has the better complexity, but sort() has the better runtime in most cases. The advantage of partial_sort() is that it guarantees n * log(n) complexity in any case, so it never becomes quadratic complexity.
partial_sort() also has the special ability to stop sorting when only the first n elements need to be sorted. To sort all the elements you have to pass the end of the sequence as second and last argument:
/*sort all elements *-always n*log(n) complexity *-but usually twice as long as sort() */ partial_sort (coll.begin(), coll.end(), coll.end());
stable_sort() is also based historically on heapsort. It sorts all the elements:
/*sort all elements *-n*log(n) or n*log(n)*log(n) complexity */ stable_sort (coll.begin(), coll.end());
However, it needs enough additional memory to have n * log(n) complexity. Otherwise, it has n * log(n) * log(n) complexity. The advantage of stable_sort() is that it preserves the order of equal elements.
Now you have a brief idea of which sorting algorithm might best meet your needs. But the story doesn't end here. The standard guarantees complexity, but not how it is implemented. This is an advantage in that an implementation could benefit from algorithm innovations and use a better way of sorting without breaking the standard. For example, the sort() algorithm in the SGI implementation of the STL is implemented by using introsort. Introsort is a new algorithm that, by default, operates like quicksort, but switches to heapsort when it is going to have quadratic complexity. The disadvantage of the fact that the standard does not guarantee exact complexity is that an implementation could use a standard-conforming but very bad algorithm. For example, using heapsort to implement sort() would be standard conforming. Of course, you simply could test which algorithm fits best, but be aware that measurements might not be portable.
There are even more algorithms to sort elements. For example, the heap algorithms are provided to call the functions that implement a heap directly (a heap is a binary tree, which is used internally by heapsort). The heap algorithms are provided and used as the base for efficient implementations of priority queues (see Section 10.3). You can use them to sort all elements of a collection by calling them as follows:
/*sort all elements *-n+n*log(n) complexity */ make_heap (coll.begin(), coll.end()); sort_heap (coll.begin(), coll.end());
See Section 9.9.4, for details about heaps and heap algorithms.
The nth_element() algorithms are provided if you need only the nth sorted element or the set of the n highest or n lowest elements (not sorted). Thus, nth_element() is a way to split elements into two subsets according to a sorting criterion. However, you could also use partition() or stable_partition() to do this. The difference is as follows:
For nth_element() you pass the number of elements you want to have in the first part (and therefore also in the second part). For example:
// move the four lowest elements to the front nth_element (coll.begin(), // beginning of range coll.begin()+3, // position between first and second part coll.end()) ; // end of range
However, after the call you don't know the exact criterion that is the difference between the first and the second parts. Both parts may, in fact, have elements with the same value as the nth element.
For partition() you pass the exact sorting criterion that serves as the difference between the first and the second parts:
// move all elements less than seven to the front vector<int>::iterator pos; pos = partition (coll1.begin(), coll1.end(), // range bind2nd(less<int>(),7)); // criterion
Here, after the call, you don't know how many elements are owned by the first and the second parts. The return value pos refers to the first element of the second part that contains all elements that don't match the criterion, if any.
stable_partition() behaves similarly to partition(), with an additional ability. It guarantees that the order of the elements in both parts remains stable according to their relative positions to the other elements in the same part.
You can always pass the sorting criterion to all sorting algorithms as an optional argument. The default sorting argument is the function object less<>, so that elements are sorted in ascending order of their values.
As with modifying algorithms, you can't use an associative container as a destination because the elements of the associative containers are considered to be constant.
Lists do not provide random access iterators, so you can't call sorting algorithms for them either. However, lists provide a member function sort() to sort their elements; see page 245.
Sorted range algorithms require that the ranges on which they operate are sorted according to their sorting criterion. Table 9.7 lists all algorithms of the C++ standard library that are especially written for sorted ranges. Like associative containers, these algorithms have the advantage of a better complexity.
Name | Effect | Page |
---|---|---|
binary_search() | Returns whether the range contains an element | 410 |
includes() | Returns whether each element of a range is also an element of another range | 411 |
lower_bound() | Finds the first element greater than or equal to a given value | 413 |
upper _bound() | Finds the first element greater than a given value | 413 |
equal_range() | Returns the range of elements equal to a given value | 415 |
merge() | Merges the elements of two ranges | 416 |
set_union() | Processes the sorted union of two ranges | 418 |
set.intersection() | Processes the sorted intersection of two ranges | 419 |
set_difference() | Processes a sorted range that contains all elements of a range that are not part of another | 420 |
set_symmetric_difference() | Processes a sorted range that contains all elements that are in exactly one of two ranges | 421 |
inplace_merge() | Merges two consecutive sorted ranges | 423 |
The first five sorted range algorithms in Table 9.7 are nonmodifying because they search only according to their purpose. The other algorithms combine two sorted input ranges and write the result to a destination range. In general, the result of these algorithms is also sorted.
These algorithms combine numeric elements in different ways. Table 9.8 lists the numeric algorithms of the C++ standard library. If you understand the names, you get an idea of the purpose of the algorithms. However, these algorithms are more flexible and more powerful than they may seem at first. For example, by default, accumulate() processes the sum of all elements. When you use strings as elements, you concatenate them using this algorithm. When you switch from operator + to operator *, you get the product of all elements. As another example, you should know that adjacent_difference() and partial_sum() transfer a range of absolute values into a range of relative values and vice versa.
accumulate() and inner_product() process and return a single value without modifying the ranges. The other algorithms write the results to a destination range that has the same number of elements as the source range.
Name | Effect | Page |
---|---|---|
accumulate() | Combines all element values (processes sum, product, and so forth) | 425 |
inner_product() | Combines all elements of two ranges | 427 |
adjacent_difference() | Combines each element with its predecessor | 431 |
partial_sum() | Combines each element with all of its predecessors | 429 |
The rest of this chapter discusses the algorithms in detail. It includes at least one example of each algorithm. To simplify the examples, I use some auxiliary functions so that you can concentrate on the essence of the examples:
// algo/algostuff.hpp #ifndef ALGOSTUFF_HPP #define ALGOSTUFF_HPP #include <iostream> #include <vector> #include <deque> #include <list> #include <set> #include <map> #include <string> #include <algorithm> #include <functional> #include <numeric> /*PRINT_ELEMENTS() *-prints optional C-string optcstr followed by *-all elements of the collection coll *-separated by spaces */ template <c1ass T> inline void PRINT_ELEMENTS (const T& coll, const char* optcstr="") { typename T::const_iterator pos; std::cout << optcstr; for (pos=coll.begin(); pos!=coll.end(); ++pos) { std::cout << *pos << ' '; } std::cout << std::endl; } /*INSERT_ELEMENTS (collection, first, last) *-fill values from first to last into the collection *-NOTE: NO half-open range */ template <c1ass T> inline void INSERT_ELEMENTS (T& coll, int first, int last) { for (int i=first; i<=last; ++i) { coll.insert(coll.end(),i); } } #endif /*ALGOSTUFF_HPP*/
First, algostuff.hpp includes all header files that may be necessary to implement the examples, thus the program doesn't have to do it. Second, it defines two auxiliary functions:
PRINT_ELEMENTS() prints all elements of the container that is passed as the first argument separated by spaces. You can pass a second argument optionally for a string that is used as a prefix in front of the elements (see page 118).
INSERT_ELEMENTS() inserts elements into the container that is passed as the first argument. These elements get the values from the value passed as the second argument up to the value passed as the third argument. Both argument values are included (so this is not a half-open range).
The for_each() algorithm is very flexible because it allows you to access, process, and modify each element in many different ways.
UnaryProc
for_each (InputIterator beg, InputIterator end, UnaryProc op)
Calls
op (elem)
for each element in the range [beg,end).
Returns a copy of the (internally modified) op.
op might modify the elements. However, see page 325 for a comparison with the transform() algorithm, which is able to do the same thing in a slightly different way.
Any return value of op is ignored.
See page 126 for the implementation of the for_each() algorithm.
Complexity: linear (numberOfElements calls of op()).
The following example of for_each() calls the print() function, which is passed as the operation for each element. Thus, the call prints each element:
// algo/foreach1.cpp #include "algostuff.hpp" using namespace std; // function called for each element void print (int elem) { cout << elem << ' '; } int main() { vector<int> coll; INSERT_ELEMENTS(coll,1,9); // call print() for each element for_each (coll.begin(), coll.end(), // range print); // operation cout << endl; }
The program has the following output:
1 2 3 4 5 6 7 8 9
To call a member function of the elements you can use the mem_fun adapters. See Section 8.2.2, for details and an example.
The following example demonstrates how to modify each element using a function object:
// algo/foreach2.cpp #include "algostuff.hpp" using namespace std; // function object that adds the value with which it is initialized template <c1ass T> c1ass AddValue { private: T theValue; // value to add public: // constructor initializes the value to add AddValue (const T& v) : theValue(v) { } // the function call for the element adds the value void operator() (T& elem) const { elem += theValue; } }; int main() { vector<int> coll; INSERT_ELEMENTS(coll,1,9); // add ten to each element for_each (coll.begin(), coll.end(), // range AddValue<int>(10)); // operation PRINT_ELEMENTS(coll); // add value of first element to each element for_each (coll.begin(), coll.end(), // range AddValue<int>(*coll.begin())); // operation PRINT_ELEMENTS(coll); }
The AddValue<> c1ass defines function objects that add a value to each element that is passed to the constructor. Using the function object has the advantage that you can process the added value at runtime. The program has the following output:
11 12 13 14 15 16 17 18 19 22 23 24 25 26 27 28 29 30
See page 128 for more details regarding this example. Note also that you can do the same by using the transform() algorithm (see page 367) in the following way:
transform (coll.begin(), coll.end(), // source range coll.begin(), // destination range bind2nd(plus<int>(), 10)); // operation ... transform (coll.begin(), coll.end(), // source range coll.begin(), // destination range bind2nd(plus<int>(),*coll.begin())); // operation
See page 325 for a general comparison between for_each() and transform().
A third example demonstrates how to use the return value of the for_each() algorithm. Because for_each() has the special property that it returns its operation, you can process and return a result inside the operation:
// algo/foreach3.cpp #include "algostuff.hpp" using namespace std; // function object to process the mean value c1ass MeanValue { private: long num; // number of elements long sum; // sum of all element values public: // constructor MeanValue () : num(0), sum(0) { } // function call // - process one more element of the sequence void operator() (int elem) { num++; // increment count sum += elem; // add value } // return mean value (implicit type conversion) operator double() { return static_cast<double>(sum) / static_cast<double>(num); } }; int main() { vector<int> coll; INSERT_ELEMENTS(coll,1,8); // process and print mean value double mv = for_each (coll.begin(), coll.end(), // range MeanValue()); // operation cout << "mean value: " << mv << endl; }
The program has the following output:
mean value: 4.5
This example, in a slightly different form, is discussed in detail on page 300.
The algorithms presented in this section enable you to access elements without modifying their values or changing their order.
difference _type
count (InputIterator beg, InputIterator end, const T& value)
difference _type
count_if (InputIterator beg, InputIterator end, UnaryPredicate op)
The first form counts the elements in the range [beg,end) that are equal to value value.
The second form counts the elements in the range [beg,end) for which the unary predicate
op (elem)
yields true.
The type of the return value, difference_type, is the difference type of the iterator:
typename iterator_traits<lnputIterator>::difference_type
(Section 7.5, introduces iterator traits.)^{[4]}
Note that op should not change its state during a function call. See Section 8.1.4, for details.
op should not modify the passed arguments.
Associative containers (sets, multisets, maps, and multimaps) provide a similar member function, count(), to count the number of elements that have a certain value as key (see page 234).
Complexity: linear (numberOfElements comparisons or calls of op() respectively).
The following example counts elements according to different criteria:
// algo/count1.cpp #include "algostuff.hpp" using namespace std; bool isEven (int elem) { return elem % 2 == 0; } int main() { vector<int> coll; int num; INSERT_ELEMENTS(coll,1,9); PRINT_ELEMENTS(coll,"coll: "); // count and print elements with value 4 num = count (coll.begin(), coll.end(), // range 4); // value cout << "number of elements equal to 4: " << num << endl; // count elements with even value num = count_if (coll.begin(), coll.end(), // range isEven); // criterion cout << "number of elements with even value: " num << endl; // count elements that are greater than value 4 num = count_if (coll.begin(), coll.end(), // range bind2nd(greater<int>(),4)); // criterion cout << "number of elements greater than 4: " << num << endl; }
The program has the following output:
coll: 1 2 3 4 5 6 7 8 9 number of elements equal to 4: 1 number of elements with even value: 4 number of elements greater than 4: 5
Instead of using the self-written isEven() function, you could use the following expression:
not1(bind2nd(modulus<int>(),2))
See page 306 for more details regarding this expression.
InputIterator
min_element (InputIterator beg, InputIterator end)
InputIterator
min_element (InputIterator beg, InputIterator end, CompFunc op)
InputIterator
max_element (InputIterator beg, InputIterator end)
InputIterator
max_element (InputIterator beg, InputIterator end, CompFunc op)
All algorithms return the position of the minimum or maximum element in the range [beg,end).
The versions without op compare the elements with operator <.
op is used to compare two elements:
op(elem1 ,elem2)
It should return true when the first element is less than the second element.
If more than one minimum or maximum element exists, they return the first found.
op should not modify the passed arguments.
Complexity: linear (numberOfElements-1 comparisons or calls of op() respectively).
The following program prints the minimum and the maximum of the elements in coll and, by using absLess(), prints the minimum and the maximum of the absolute values:
// algo/minmax1.cpp #include <cstdlib> #include "algostuff.hpp" using namespace std; bool absLess (int elem1, int elem2) { return abs(elem1) < abs (elem2); } int main() { deque<int> coll; INSERT_ELEMENTS(coll,2,8); INSERT_ELEMENTS(coll,-3,5); PRINT_ELEMENTS(coll); // process and print minimum and maximum cout << "minimum: " << *min_element(coll.begin(),coll.end()) << endl; cout << "maximum: " << *max_element(coll.begin(),coll.end()) << endl; // process and print minimum and maximum of absolute values cout << "minimum of absolute values: " << *min_element(coll.begin(),coll.end(), absLess) << endl; cout << "maximum of absolute values: " << *max_element(coll.begin(),coll.end(), absLess) << endl; }
The program has the following output:
2 3 4 5 6 7 8 -3 -2 -1 0 1 2 3 4 5 minimum: -3 maximum: 8 minimum of absolute values: 0 maximum of absolute values: 8
Note that the algorithms return the, position of the maximum or minimum element respectively. Thus, you must use the unary operator * to print their values.
InputIterator
find (InputIterator beg, InputIterator end, const T& value)
InputIterator
find_if (InputIterator beg, InputIterator end, UnaryPredicate op)
The first form returns the position of the first element in the range [beg,end) that has a value equal to value.
The second form returns the position of the first element in the range [beg,end) for which the unary predicate
op(elem)
yields true.
Both forms return end if no matching elements are found.
Note that op should not change its state during a function call. See Section 8.1.4, for details.
op should not modify the passed arguments.
If the range is sorted, you should use the lower_bound(), upper_bound(), equal_range(), or binary_search() algorithms (see Section 9.10).
Associative containers (sets, multisets, maps, and multimaps) provide an equivalent member function, find(), that has logarithmic instead of linear complexity (see page 235).
Complexity: linear (at most, numberOfElements comparisons or calls of op() respectively).
The following example demonstrates how to use find() to find a subrange starting with the first element with value 4 and ending after the second 4, if any:
// algo/find1.cpp #include "algostuff.hpp" using namespace std; int main() { list<int> coll; INSERT_ELEMENTS(coll,1,9); INSERT_ELEMENTS(coll,1,9); PRINT_ELEMENTS(coll,"coll: "); // find first element with value 4 list<int>::iterator pos1; pos1 = find (coll.begin(), coll.end(), // range 4); // value /*find second element with value 4 *- note: continue the search behind the first 4 (if any) */ list<int>::iterator pos2; if (pos1 != coll.end()) { pos2 = find (++pos1, coll.end(), // range 4); // value } /*print all elements from first to second 4 (both included) *- note: now we need the position of the first 4 again (if any) *- note: we have to pass the position behind the second 4 (if any) */ if (pos1!=coll.end() && pos2!=coll.end()) { copy (--pos1, ++pos2, ostream_iterator<int>(cout," ")); cout << endl; } }
To find the second 4 you must increment the position of the first 4. However, incrementing the end() of a collection results in undefined behavior. Thus, if you are not sure, you should check the return value of find() before you increment it. The program has the following output:
coll: 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 4 5 6 7 8 9 1 2 3 4
You can call find() twice for the same range but with two different values. However, you have to be careful to use the results as the beginning and the end of a subrange of elements; otherwise, the subrange might not be valid. See page 97 for a discussion of possible problems and for an example.
The following example demonstrates how to use find_if() to find elements according to very different search criteria:
// algo/find2.cpp #include "algostuff.hpp" using namespace std; int main() { vector<int> coll; vector<int>::iterator pos; INSERT_ELEMENTS(coll,1,9); PRINT_ELEMENTS(coll,"coll: "); // find first element greater than 3 pos = find_if (coll.begin(), coll.end(), // range bind2nd(greater<int>(),3)); // criterion // print its position cout << "the " << distance(coll.begin(),pos) + 1 << ". element is the first greater than 3" << endl; // find first element divisible by 3 pos = find_if (coll.begin(), coll.end(), not1(bind2nd(modulus<int>(),3))); // print its position cout << "the " << distance(coll.begin(),pos) + 1 << ". element is the first divisible by 3" << endl; }
The first call of find() uses a simple function object combined with the bind2nd adapter to search for the first element that is greater than 3. The second call uses a more complicated combination to find the first element that is divisible by 3 without rest.
The program has the following output:
coll: 1 2 3 4 5 6 7 8 9 the 4. element is the first greater than 3 the 3. element is the first divisible by 3
See page 121 for an example that lets find() find the first prime number.
InputIterator
search_n (InputIterator beg, InputIterator end, Size count, const T& value)
InputIterator
search_n (InputIterator beg, InputIterator end, Size count, const T& value, BinaryPredicate op)
The first form returns the position of the first of count consecutive elements in the range [beg,end) that all have a value equal to value.
The second form returns the position of the first of count consecutive elements in the range [beg,end) for which the binary predicate
op(elem, value)
yields true.
Both forms return end if no matching elements are found.
Note that op should not change its state during a function call. See Section 8.1.4, for details.
op should not modify the passed arguments.
These algorithms were not part of the original STL and were not introduced very carefully.
The fact that the second form uses a binary predicate instead of a unary predicate breaks the consistency of the original STL. See the remarks on page 346.
Complexity: linear (at most, numberOfElements*count comparisons or calls of op() respectively).
The following example searches for three consecutive elements that have a value equal to or greater than 3:
// algo/searchn1.cpp #include "algostuff.hpp" using namespace std; int main() { deque<int> coll; INSERT_ELEMENTS(coll,1,9); PRINT_ELEMENTS(coll); // find three consecutive elements with value 4 deque<int>::iterator pos; pos = search_n (coll.begin(), coll.end(), // range 4, // count 3); // value // print result if (pos != coll.end()) { cout << "four consecutive elements with value 3 " << "start with " << distance(coll.begin(),pos) +1 << ". element" << endl; } else { cout << "no four consecutive elements with value 3 found" << endl; } // find three consecutive elements with value greater than 4 pos = search_n (coll.begin(), coll.end(), // range 4, // count 3, // value greater<int>()); // criterion // print result if (pos != coll.end()) { cout << "four consecutive elements with value > 3 " << "start with " << distance(coll.begin(),pos) +1 << ". element" << endl; } else { cout << "no four consecutive elements with value > 3 found" << endl; } }
The program has the following output:
1 2 3 4 5 6 7 8 9 no four consecutive elements with value 3 found four consecutive elements with value > 3 start with 4. element
There is a nasty problem with the second form of search_n(). Consider the second call of search_n():
pos = search_n (coll.begin(), coll.end(), // range 4, // count 3, // value greater<int>()); // criterion
This kind of searching for elements that matches a special criterion does not conform with the rest of the STL. Following the usual concepts of the STL, the call should be as follows:
pos = search_n_if (coll.begin(), coll.end(), // range 4, // count bind2nd(greater<int>(),3)); // criterion
Unfortunately, nobody noticed this inconsistency when these new algorithms were introduced to the standard (they were not part of the original STL). You might argue that the version with four arguments is more convenient. However, it requires a binary predicate even if you only need a unary predicate. For example, to use a self-written unary predicate function, normally you would write:
bool isPrime (int elem); ... pos = search_n_if (coll.begin(), coll.end(), // range 4, // count isPrime); //criterion
However, with the actual definition you must use a binary predicate. So, either you change the signature of your function or you write a simple wrapper:
bool binaryIsPrime (int elem1, int) { return isPrime(elem1); } ... pos = search_n (coll.begin(), coll.end(), // range 4, // count 0, // required dummy value binaryIsPrime); // binary criterion
ForwardIterator1
search (ForwardIterator1 beg, ForwardIterator1 end, ForwardIterator2 searchBeg, ForwardIterator2 searchEnd)
ForwardIterator1
search (ForwardIterator1 beg, ForwardIterator1 end, ForwardIterator2 searchBeg, ForwardIterator2 searchEnd, BinaryPredicate op)
Both forms return the position of the first element of the first subrange matching the range [searchBeg,searchEnd) in the range [beg,end).
In the first form the elements of the subrange have to be equal to the elements of the whole range.
In the second form for every comparison between elements, the call of the binary predicate
op (elem, searchElem)
has to yield true.
Both forms return end if no matching elements are found.
Note that op should not change its state during a function call. See Section 8.1.4, for details.
op should not modify the passed arguments.
See page 97 for a discussion of how to find a subrange for which you know only the first and the last elements.
Complexity: linear (at most, numberOfElements*numberOfSearchElements comparisons or calls of op() respectively).
The following example demonstrates how to find a sequence as the first subrange of another sequence (compare with the example of find_end() on page 351):
// algo/search1.cpp #include "algostuff.hpp" using namespace std; int main() { deque<int> coll; list<int> subcoll; INSERT_ELEMENTS(coll,1,7); INSERT.ELEMENTS(coll,1,7); INSERT_ELEMENTS(subcoll,3,6); PRINT_ELEMENTS(coll, "coll: "); PRINT_ELEMENTS(subcoll,"subcoll: "); // search first occurrence of subcoll in coll deque<int>::iterator pos; pos = search (coll.begin(), coll.end(), // range subcoll.begin(), subcoll.end()); //subrange // loop while subcoll found as subrange of coll while (pos != coll.end()) { // print position of first element cout << "subcoll found starting with element " << distance (coll.begin(),pos) + 1 << endl; // search next occurrence of subcoll ++pos; pos = search (pos, coll.end(), // range subcoll.begin(), subcoll.end()); // subrange } }
The program has the following output:
coll: 1 2 3 4 5 6 7 1 2 3 4 5 6 7 subcoll: 3 4 5 6 subcoll found starting with element 3 subcoll found starting with element 10
The next example demonstrates how to use the second form of the search() algorithm to find a subsequence that matches a more complicated criterion. Here, the subsequence even, odd, and even value is searched:
// algo/search2.cpp #include "algostuff.hpp" using namespace std; // checks whether an element is even or odd bool checkEven (int elem, bool even) { if (even) { return elem % 2 == 0; } else { return elem % 2 == 1; } } int main() { vector<int> coll; INSERT_ELEMENTS(coll,1,9); PRINT_ELEMENTS(coll,"coll: "); /* arguments for checkEven() * - check for: "even odd even" */ bool checkEvenArgs[3] = { true, false, true }; // search first subrange in coll vector<int>::iterator pos; pos = search (coll.begin(), coll.end(), // range checkEvenArgs, checkEvenArgs+3, // subrange values checkEven); // subrange criterion // loop while subrange found while (pos != coll.end()) { // print position of first element cout << "subrange found starting with element " << distance(coll.begin(),pos) + 1 << endl; // search next subrange in coll pos = search (++pos, coll.end(), // range checkEvenArgs, checkEvenArgs+3, // subr. values checkEven); // subr. criterion } }
The program has the following output:
coll: 1 2 3 4 5 6 7 8 9 subrange found starting with element 2 subrange found starting with element 4 subrange found starting with element 6
ForwardIterator
find_end (ForwardIterator beg, ForwardIterator end, ForwardIterator searchBeg, ForwardIterator searchEnd)
ForwardIterator
find_end (ForwardIterator beg, ForwardIterator end, ForwardIterator searchBeg, ForwardIterator searchEnd, BinaryPredicate op)
Both forms return the position of the first element of the last subrange matching the range [saarchBeg,searchEnd) in the range [beg,end).
In the first form the elements of the subrange have to be equal to the elements of the whole range.
In the second form, for every comparison between elements, the call of the binary predicate
op(elem,searchElem)
has to yield true.
Both forms return end if no matching elements are found.
Note that op should not change its state during a function call. See Section 8.1.4, for details.
op should not modify the passed arguments.
See page 97 for a discussion of how to find a subrange for which you only know the first and the last elements.
These algorithms were not part of the original STL. Unfortunately they were called find_end() instead of search_end(), which would be more consistent, because the algorithm used to search the first subrange is called search().
Complexity: linear (at most, numberOfElements*numberOfSearchElements comparisons or calls of op() respectively).
The following example demonstrates how to find a sequence as the last subrange of another sequence (compare with the example of search() on page 348):
// algo/findend1.cpp #include "algostuff.hpp" using namespace std; int main() { deque<int> coll; list<int> subcoll; INSERT_ELEMENTS(coll,1,7); INSERT_ELEMENTS(coll,1,7); INSERT_ELEMENTS(subcoll,3,6); PRINT_ELEMENTS(coll, "coll: "); PRINT_ELEMENTS(subcoll,"subcoll: "); // search last occurrence of subcoll in coll deque<int>::iterator pos; pos = find_end (coll.begin(), coll.end(), // range subcoll.begin(), subcoll.end()); // subrange // loop while subcoll found as subrange of coll deque<int>::iterator end(coll.end()); while (pos != end) { // print position of first element cout << "subcoll found starting with element " << distance(coll.begin(),pos) + 1 << endl; // search next occurrence of subcoll end = pos; pos = find_end (coll.begin(), end, // range subcoll.begin(), subcoll.end()); // subrange } }
The program has the following output:
coll: 1 2 3 4 5 6 7 1 2 3 4 5 6 7 subcoll: 3 4 5 6 subcoll found starting with element 10 subcoll found starting with element 3
For the second form of this algorithm, see the second example of search() on page 349. You can use find_end() in a similar manner.
ForwardIterator
find_first_of (ForwardIterator1 beg, ForwardIterator1 end, ForwardIterator2 searchBeg, ForwardIterator2 searchEnd)
ForwardIterator
find_first_of (ForwardIterator1 beg, ForwardIterator1 end, ForwardIterator2 searchBeg, ForwardIterator2 searchEnd, BinaryPredicate op)
The first form returns the position of the first element in the range [beg,end) that is also in the range [searchBeg,searchEnd).
The second form returns the position of the first element in the range [beg,end) for which any call with all elements of [searchBeg,searchEnd)
op (elem,searchElem)
yields true.
Both forms return end if no matching elements are found.
Note that op should not change its state during a function call. See Section 8.1.4, for details.
op should not modify the passed arguments.
By using reverse iterators, you can find the last of several possible values.
These algorithms were not part of the original STL.
Complexity: linear (at most, numberOfElements comparisons or calls of op() respectively).
The following example demonstrates the use of find_first_of():
// algo/findof1.cpp #include "algostuff.hpp" using namespace std; int main() { vector<int> coll; list<int> searchcoll; INSERT_ELEMENTS(coll,1,11); INSERT_ELEMENTS(searchcoll,3,5); PRINT_ELEMENTS(coll, "coll: "); PRINT_ELEMENTS(searchcoll,"searchcoll: "); // search first occurrence of an element of searchcoll in coll vector<int>::iterator pos; pos = find_first_of (coll.begin(), coll.end(), // range searchcoll.begin(), // beginning of search set searchcoll.end()); // end of search set cout << "first element of searchcoll in coll is element " << distance(coll.begin(),pos) + 1 << endl; // search last occurrence of an element of searchcoll in coll vector<int>::reverse_iterator rpos; rpos = find_first_of (coll.rbegin(), coll.rend(), // range searchcoll.begin(), // beginning of search set searchcoll.end()); // end of search set cout << "last element of searchcoll in coll is element " << distance (coll.begin(),rpos.base()) << endl; }
The second call uses reverse iterators to find the last element that has a value equal to one element in searchcoll. To print the position of the element, base() is called to transform the reverse iterator into an iterator. Thus, you can process the distance from the beginning. Normally you would have to add 1 to the result of distance() because the first element has distance 0 but actually is element 1. However, because base() moves the position of the value to which it refers, you have the same effect (see Section 7.4.1, for the description of base()).
The program has the following output:
coll: 1 2 3 4 5 6 7 8 9 10 11 searchcoll: 3 4 5 first element of searchcoll in coll is element 3 last element of searchcoll in coll is element 5
InputIterator
adjacent_find (InputIterator beg, InputIterator end)
InputIterator
adjacent_find_if (InputIterator beg, InputIterator end, BinaryPredicate op)
The first algorithm returns the first element in the range [beg,end) that has a value equal to the value of the following element.
The second algorithm returns the first element in the range [beg,end) for which the binary predicate
op(elem,nextElem)
yields true.
Both algorithms return end if no matching elements are found.
Note that op should not change its state during a function call. See Section 8.1.4, for details.
op should not modify the passed arguments.
Complexity: linear (at most, numberOfElements comparisons or calls of op() respectively).
The following program demonstrates both forms of adjacent_find():
// algo/adjfindl.cpp #include "algostuff.hpp" using namespace std; // return whether the second object has double the value of the first bool doubled (int elem1, int elem2) { return elem1 * 2 == elem2; } int main() { vector<int> coll; coll.push_back(l); coll.push_back(3); coll.push_back(2); coll.push_back(4); coll.push_back(5); coll.push_back(5); coll.push_back(0); PRINT_ELEMENTS(coll,"coll: "); // search first two elements with equal value vector<int>::iterator pos; pos = adjacent_find (coll.begin(), coll.end()); if (pos != coll.end()) { cout << "first two elements with equal value have position " << distance(coll.begin(),pos) + 1 << endl; } //search first two elements for which the second has double the value of the first pos = adjacent_find (coll.begin(), coll.end(), // range doubled); // criterion if (pos != coll.end()) { cout << "first two elements with second value twice the " << "first have pos. " << distance (coll.begin(),pos) + 1 << endl; } }
The first call of adjacent_find() searches for equal values. The second form uses doubled() to find the first element for which the successor has the double value. The program has the following output:
coll: 1 3 2 4 5 5 0 first two elements with equal value have position 5 first two elements with second value twice the first have pos. 3
bool
equal (InputIterator1 beg, InputIterator1 end, InputIterator2 cmpBeg)
bool
equal (InputIterator1 beg, InputIterator1 end, InputIterator2 cmpBeg, BinaryPredicate op)
The first form returns whether the elements in the range [beg,end) are equal to the elements in the range starting with cmpBeg.
The second form returns whether each call of the binary predicate
op (elem, cmpElem)
with the corresponding elements in the range [beg,end) and in the range starting with cmpBeg yields true.
Note that op should not change its state during a function call. See Section 8.1.4, for details.
op should not modify the passed arguments.
The caller must ensure that the range starting with cmpBeg contains enough elements.
To determine the differences when the sequences are not equal, you should use the mismatch() algorithm (see page 358).
Complexity: linear (at most, numberOfElements comparisons or calls of op() respectively).
The following example demonstrates both forms of equal(). The first call checks whether the elements have values with equal elements. The second call uses an auxiliary predicate function to check whether the elements of both collections have corresponding even and odd elements:
// algo/equal1.cpp #include "algostuff.hpp" using namespace std; bool bothEvenOrOdd (int elem1, int elem2) { return elem1 % 2 == elem2 % 2; } int main() { vector<int> coll1; list<int> coll2; INSERT_ELEMENTS(coll1,1,7); INSERT_ELEMENTS(coll2,3,9); PRINT_ELEMENTS(coll1,"coll1: "); PRINT_ELEMENTS(col12,"col12: "); //check whether both collections are equal if (equal (coll1. begin(), coll1. end(), //first range coll2.begin())) { //second range cout << "coll1 == col12" << endl; } else { cout << "coll1 != coll2" << endl; } //check for corresponding even and odd elements if (equal (coll1.begin(), coll1.end(), //first range coll2. begin(), //second range bothEvenOrOdd)) { //comparison criterion cout << "even and odd elements correspond" << endl; } else { cout << "even and odd elements do not correspond" << endl; } }
The program has the following output:
coll1: 1 2 3 4 5 6 7 coll2: 3 4 5 6 7 8 9 coll1 != coll2 even and odd elements correspond
pair<InputIterator1,InputIterator2>
mismatch (InputIterator1 beg, InputIterator1 end, InputIterator2 cmpBeg)
pair<InputIterator1,InputIterator2>
mismatch (InputIterator1 beg, InputIterator1 end, InputIterator2 cmpBeg, BinaryPredicate op)
The first form returns the first two corresponding elements of range [beg,end) and the range starting with cmpBeg that differ.
The second form returns the first two corresponding elements of range [beg,end) and the range starting with cmpBeg for which the binary predicate
op (elem, cmpElem)
yields true.
If no difference is found, a pair of end and the corresponding element of the second range is returned. Note that this does not mean that both sequences are equal, because the second sequence might contain more elements.
Note that op should not change its state during a function call. See Section 8.1.4, for details.
op should not modify the passed arguments.
The caller must ensure that the range starting with cmpBeg contains enough elements.
To check whether two ranges are equal, you should use the equal() algorithm (see page 356).
Complexity: linear (at most, numberOfElements comparisons or calls of op() respectively).
The following example demonstrates both forms of mismatch():
// algo/misma1.cpp #include "algostuff.hpp" using namespace std; int main() { vector<int> coll1; list<int> coll2; INSERT_ELEMENTS(coll1,1,6); for (int i=1; i<=16; i*=2) { col12.push_back(i); } coll2.push_back(3); PRINT_ELEMENTS(coll1,"coll1: "); PRINT_ELEMENTS(coll2,"coll2: "); //find first mismatch pair<vector<int>::iterator,list<int>::iterator> values; values = mismatch (coll1.begin(), coll1.end(), //first range coll2.begin()); //second range if (values.first == coll1.end()) { cout << "no mismatch" << endl; } else { cout << "first mismatch: " << *values.first << " and " << *values.second << endl; } /*find first position where the element of coll1 is not *less than the corresponding element of coll2 */ values = mismatch (coll1.begin(), coll1.end(), //first range col12. begin(), //second range less_equal<int>() ) //criterion if (values.first == coll1.end()) { cout << "always less-or-equal" << endl; } else { cout << "not less-or-equal: " << *values.first << " and " << *values.second << endl; } }
The first call of mismatch() searches for the first corresponding elements that are not equal. If such elements exist, their values are written to standard output. The second call searches for the first pair of elements in which the element of the first collection is greater than the corresponding element of the second collection, and returns these elements. The program has the following output:
coll1: 1 2 3 4 5 6 coll2: 1 2 4 8 16 3 first mismatch: 3 and 4 not less-or-equal: 6 and 3
bool
lexicographical_compare (InputIterator1 beg1, Input Iterator1 end1, InputIterator2 beg2, InputIterator2 end2)
bool
lexicographical_compare (InputIterator1 begl, InputIterator1 end1, InputIterator2 beg2, InputIterator2 end2, CompFunc op)
Both forms return whether the elements in the range [beg1,end1) are "lexicographically less than" the elements in the range [beg2,end2).
The first form compares the elements by using operator <.
The second form compares the elements by using the binary predicate
op(elem1 ,elem2)
It should return true when elem1 is less than elem2.
Lexicographical comparison means that sequences are compared element-by-element until any of the following occurs:
When two elements are not equal, the result of their comparison is the result of the whole comparison.
When one sequence has no more elements, then the sequence that has no more elements is less than the other. Thus, the comparison yields true if the first sequence is the one that has no more elements.
When both sequences have no more elements, then both sequences are equal, and the result of the comparison is false.
Note that op should not change its state during a function call. See Section 8.1.4, for details.
op should not modify the passed arguments.
Complexity: linear (at most, 2*min(numberOfElements1,numberOfElements2) comparisons or calls of op() respectively).
The following example demonstrates the use of a lexicographical sorting of collections:
// algo/lexico1.cpp #include "algostuff.hpp" using namespace std; void printCollection (const list<int>& l) { PRINT_ELEMENTS(l); } bool lessForCollection (const list<int>& l1, const list<int>& 12) { return lexicographical_compare (l1.begin(), l1.end(), // first range 12.begin(), 12.end()); // second range } int main() { list<int> c1, c2, c3, c4; //fill all collections with the same starting values INSERT_ELEMENTS(c1,1,5); c4 = c3 = c2 = c1; //and now some differences c1.push_back(7); c3.push_back(2); c3.push_back(0); c4.push_back(2); //create collection of collections vector<list<int> > cc; cc.push_back(c1); cc.push_back(c2); cc.push_back(c3); cc.push_back(c4); cc.push_back(c3); cc.push_back(c1); cc.push_back(c4); cc.push_back(c2); //print all collections for_each (cc.begin(), cc.end(), printCollection); cout << endl; //sort collection lexicographically sort (cc.begin(), cc.end(), //range lessForCollection) ; //sorting criterion //print all collections again for_each (cc.begin(), cc.end(), printCollection); }
The vector cc is initialized with several collections (all lists). The call of sort() uses the binary predicate lessForCollection() to compare two collections (see page 397 for a description of sort()). In lessForCollection(), the lexicographical_compare() algorithm is used to compare the collections lexicographically. The program has the following output:
1 2 3 4 5 7 1 2 3 4 5 1 2 3 4 5 2 0 1 2 3 4 5 2 1 2 3 4 5 2 0 1 2 3 4 5 7 1 2 3 4 5 2 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 2 1 2 3 4 5 2 1 2 3 4 5 2 0 1 2 3 4 5 2 0 1 2 3 4 5 7 1 2 3 4 5 7
This section describes algorithms that modify the elements of a range. There are two ways to modify elements:
Modify them directly while iterating through a sequence.
Modify them while copying them from a source range to a destination range.
Several modifying algorithms provide both ways of modifying the elements of a range. In this case, the name of the latter uses the _copy suffix.
You can't use an associative container as a destination range because the elements in an associative container are constant. If you could, it would be possible to compromise the automatic sorting.
All algorithms that have a separate destination range return the position after the last copied element of that range.
OutputIterator
copy (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg)
BidirectionalIteratorl
copy_backward (BidirectionalIterator1 sourceBeg, BidirectionalIterator1 source End, BidirectionalIterator2 destEnd)
Both algorithms copy all elements of the source range [source Beg,sourceEnd) into the destination range starting with destBeg or ending with destEnd respectively.
They return the position after the last copied element in the destination range (the first element that is not overwritten).
destBeg or destEnd should not be part of [sourceBeg,sourceEnd).
copy() iterates forward through the sequence, whereas copy_backward() iterates backward. This difference matters only if the source and destination ranges overlap.
To copy a range to the front, use copy(). Thus, for copy(), destBeg should have a position in front of sourceBeg.
To copy a range to the back, use copy_backward(). Thus, for copy_backward(), destEnd should have a position after sourceEnd.
So whenever the third argument is an element of the source range specified by the first two arguments, use the other algorithm. Note that switching to the other algorithm means that you switch from passing the beginning of the destination range to passing the end. See page 365 for an example that demonstrates the differences.
There is no copy_if() algorithm provided. To copy only those elements that meet a certain criterion, use remove_copy_if() (see page 380).
Use reverse_copy() to reverse the order of the elements during the copy (see page 386). reverse_copy() may be slightly more efficient than using copy() with reverse iterators.
The caller must ensure that the destination range is big enough or that insert iterators are used.
See page 271 for the implementation of the copy() algorithm.
To assign all elements of a container, use the assignment operator (if the containers have the same type; see page 236) or the assign() member function (if the containers have different types; see page 237) of the containers.
To remove elements while they are being copied, use remove_copy() and remove_copy_if() (see page 380).
To modify elements while they are being copied, use transform() (see page 367) or replace_copy() (see page 376).
Complexity: linear (numberOfElements assignments).
The following example shows some simple calls of copy():
// algo/copy1.cpp #include "algostuff.hpp" using namespace std; int main() { vector<int> coll1; list<int> coll2; INSERT_ELEMENTS(coll1,1,9); /*copy elements of coll1 into coll2 *-use back inserter to insert instead of overwrite */ copy (coll1.begin(), coll1.end(), //source range back_inserter(coll2)) ; //destination range /*print elements of coll2 *-copy elements to cout using an ostream iterator */ copy (coll2.begin(), coll2.end(), //source range ostream_iterator<int>(cout," ")); //destination range cout << endl; /*copy elements of coll1 into coll2 in reverse order *-now overwriting */ copy (coll1.rbegin(), coll1.rend(), //source range coll2.begin()); //destination range //print elements of coll2 again copy (coll2.begin(), coll2.end(), //source range ostream_iterator<int>(cout, " ")); //destination range cout << endl; }
In this example, back inserters (see Section 7.4.2,) are used to insert the elements in the destination range. Without using inserters, copy() would overwrite the empty collection coll2, which results in undefined behavior. Similarly, the example uses ostream iterators (see Section 7.4.3,) to use standard output as the destination.
The program has the following output:
1 2 3 4 5 6 7 8 9 9 8 7 6 5 4 3 2 1
The following example demonstrates the difference between copy() and copy_backward():
// algo/copy2.cpp #include "algostuff.hpp" using namespace std; int main() { /*initialize source collection with ".......... abcdef.........." */ vector<char> source(10,'.'); for (int c='a'; c<='f'; C++) { source.push_back(c); } source.insert(source.end(),10,'.'); PRINT_ELEMENTS(source,"source: "); //copy all letters three elements in front of the 'a' vector<char> c1(source.begin(),source.end()); copy (c1.begin()+10, c1.begin()+16, //source range c1.begin()+7); //destination range PRINT_ELEMENTS(c1,"c1: "); //copy all letters three elements behind the 'f' vector<char> c2(source.begin(),source.end()); copy_backward (c2.begin()+10, c2.begin()+16, //source range c2.begin()+19); //destination range PRINT_ELEMENTS(c2,"c2: "); }
Note that in both calls of copy() and copy_backward(), the third argument is not part of the source range. The program has the following output:
source: . . . . . . . . . . a b c d e f . . . . . . . . . . c1: . . . . . . . a b c d e f d e f . . . . . . . . . . c2: . . . . . . . . . . a b c a b c d e f . . . . . . .
A third example demonstrates how to use copy() as a data filter between standard input and standard output. he program reads strings and prints them, each on one line:
// algo/copy3.cpp #include <iostream> #include <algorithm> #include <string> using namespace std; int main() { copy (istream_iterator<string>(cin), //beginning of source istream_iterator<string>(), //end of source ostream_iterator<string>(cout, "\n")); //destination }
The transform() algorithms provide two abilities:
The first form has four arguments. It transforms elements from a source to a destination range. Thus, it copies and modifies elements in one step.
The second form has five arguments. It combines elements from two source sequences and writes the result to a destination range.
OutputIterator
transform (InputIterator sourceBeg, InputIterator sourceEnd, Output Iterator destEeg, UnaryFunc op)
Calls
op(elem)
for each element in the source range [sourceBeg,sourceEnd) and writes each result of op to the destination range starting with destBeg:
Returns the position after the last transformed element in the destination range (the first element that is not overwritten with a result).
The caller must ensure that the destination range is big enough or that insert iterators are used.
sourceBeg and destBeg may be identical. Thus, as with for_each() you can use this algorithm to modify elements inside a sequence. See the comparison with the for_each() algorithm on page 325 for this kind of usage.
To replace elements matching a criterion with a particular value, use the replace() algorithms (see page 375).
Complexity: linear (numberOfElements calls of op()).
The following program demonstrates how to use this kind of transform():
// algo/transf1.cpp #include "algostuff.hpp" using namespace std; int main() { vector<int> coll1; list<int> coll2; INSERT_ELEMENTS(coll1,1,9); PRINT_ELEMENTS(coll1,"coll1: "); //negate all elements in coll1 transform (coll1.begin(), coll1.end(), //source range coll1.begin(), //destination range negate<int>()); //operation PRINT_ELEMENTS(coll1,"negated: "); //transform elements of coll1 into coll2 with ten times their value transform (coll1.begin(), coll1.end(), //source range back_inserter(coll2), //destination range bind2nd(multiplies<int>(),10)); //operation PRINT_ELEMENTS(coll2,"coll2: "); //print coll2 negatively and in reverse order transform (coll2.rbegin(), coll2.rend(), //source range ostream_iterator<int>(cout," "), //destination range negate<int>()); //operation cout << endl; }
The program has the following output:
coll1: 1 2 3 4 5 6 7 8 9 negated: -1 -2 -3 -4 -5 -6 -7 -8 -9 coll2: -10 -20 -30 -40 -50 -60 -70 -80 -90 90 80 70 60 50 40 30 20 10
See the example on page 315 of how to combine two different operations while processing the elements.
OutputIterator
transform (InputIterator1 source1Beg, InputIterator1 source1End, InputIterator2 source2Beg, OutputIterator destBeg, BinaryFunc op)
Calls
op(source1Elem, source2Elem)
for all corresponding elements from the first source range [source1Beg,source1 End) and the second source range starting with source2Beg, and writes each result to the the destination range starting with destBeg:
Returns the position after the last transformed element in the destination range (the first element that is not overwritten with a result).
The caller must ensure that the second source range is big enough (has at least as many elements as the source range).
The caller must ensure that the destination range is big enough or that insert iterators are used.
source1Beg, source2Beg, and destBeg may be identical. Thus, you can process the results of elements that are combined with themselves and you can overwrite the elements of a source with the results.
Complexity: linear (numberOfElements calls of op()).
The following program demonstrates how to use this form of transform():
// algo/transf2.cpp #include "algostuff.hpp" using namespace std; int main() { vector<int> coll1; list<int> coll2; INSERT_ELEMENTS(coll1,1,9); PRINT_ELEMENTS(coll1,"coll1: "); //square each element transform (coll1.begin(), coll1.end(), //first source range coll1.begin(), //second source range coll1.begin(), //destination range multiplies<int>() ); //operation PRINT_ELEMENTS(coll1,"squared: "); /*add each element traversed forward with each element traversed backward *and insert result into coll2 */ transform (coll1. begin(), coll1. end(), //first source range coll1.rbegin(), //second source range back_inserter(coll2), //destination range plus<int>()); //operation PRINT_ELEMENTS(coll2,"coll2: "); // print differences of two corresponding elements cout << "diff: "; transform (coll1.begin(), coll1.end(), //first source range coll2.begin(), //second source range ostream_iterator<int>(cout, " "), //destination range minus<int>()); //operation cout << endl; }
The program has the following output:
coll1: 1 2 3 4 5 6 7 8 9 squared: 1 4 9 16 25 36 49 64 81 coll2: 82 68 58 52 50 52 58 68 82 diff: -81 -64 -49 -36 -25 -16 -9 -4 -1
ForwardIterator2
swap_ranges (ForwardIterator1 beg1, ForwardIterator1 end1, ForwardIterator2 beg2)
Swaps the elements in the range [beg1,end1) with the corresponding elements starting with beg2.
Returns the position after the last swapped element in the destination range.
The caller must ensure that the destination range is big enough or that insert iterators are used.
To swap all elements of a container of the same type, use its swap() member function because the member function usually has constant complexity (see page 237).
Complexity: linear (numberOfElements swap operations).
The following example demonstrates how to use swap_ranges():
// algo/swap1.cpp #include "algostuff.hpp" using namespace std; int main() { vector<int> coll1; deque<int> coll2; INSERT_ELEMENTS(coll1,1,9) ; INSERT_ELEMENTS(col12,11,23); PRINT_ELEMENTS(coll1,"coll1: "); PRINT_ELEMENTS(coll2,"coll2: "); //swap first four elements deque<int>::iterator pos; pos = swap_ranges (coll1.begin(), coll1.end(), //first range coll2.begin()); //second range PRINT_ELEMENTS(coll1,"\ncoll1: "); PRINT_ELEMENTS(coll2,"col12: "); if (pos != coll2.end()) { cout << "first element not modified: " << *pos << endl; } //mirror first three with last three elements in coll2 swap_ranges (coll2.begin(), coll2.begin()+3, //first range coll2.rbegin()); //second range PRINT_ELEMENTS(coll2,"\ncoll2: ") ; }
The first call of swap_ranges() swaps the elements of coll1 with the corresponding elements of coll2. The remaining elements of coll2 are not modified. The swap_ranges() algorithm returns the position of the first element not modified. The second call swaps the first and the last three elements of coll2. One of the iterators is a reverse iterator, so the elements are mirrored (swapped from outside to inside). The program has the following output:
coll1: 1 2 3 4 5 6 7 8 9 coll2: 11 12 13 14 15 16 17 18 19 20 21 22 23 coll1: 11 12 13 14 15 16 17 18 19 coll2: 1 2 3 4 5 6 7 8 9 20 21 22 23 first element not modified: 20 coll2: 23 22 21 4 5 6 7 8 9 20 3 2 1
void
fill (ForwardIterator beg, ForwardIterator end, const T& newValue)
void
fill_n (OutputIterator beg, Size num, const T& newValue)
fill() assigns newValue to each element in the range [beg,end).
fill_n() assigns newValue to the first num elements in the range starting with beg.
The caller must ensure that the destination range is big enough or that insert iterators are used.
Complexity: linear (numberOfElements or num assignments respectively).
The following program demonstrates the use of fill() and fill_n():
// algo/fill1.cpp #include "algostuff.hpp" using namespace std; int main() { //print ten times 7.7 fill_n(ostream_iterator<float>(cout, " "), //beginning of destination 10, //count 7.7); //new value cout << endl; list<string> coll; //insert "hello" nine times fill_n(back_inserter(coll), //beginning of destination 9, //count "hello"); //new value PRINT_ELEMENTS(coll,"coll: "); //overwrite all elements with "again" fill(coll.begin(), coll.end(), //destination "again"); //new value PRINT_ELEMENTS(coll,"coll: "); //replace all but two elements with "hi" fill_n(coll.begin(), //beginning of destination coll.size()-2, //count "hi"); //new value PRINT_ELEMENTS(coll,"coll: "); //replace the second and up to the last element but one with "hmmm" list<string>:: iterator posl, pos2; posl = coll.begin(); pos2 = coll.end(); fill (++pos1, --pos2, //destination "hmmm"); //new value PRINT_ELEMENTS(coll,"coll: "); }
The first call shows how to use fill_n() to print a certain number of values. The other calls of fill() and fill_n() insert and replace values in a list of strings. The program has the following output:
7.7 7.7 7.7 7.7 7.7 7.7 7.7 7.7 7.7 7.7 coll: hello hello hello hello hello hello hello hello hello coll: again again again again again again again again again coll: hi hi hi hi hi hi hi again again coll: hi hmmm hmmm hmmm hmmm hmmm hmmm hmmm again
void
generate (ForwardIterator beg, ForwardIterator end, Func op)
void
generate_n (OutputIterator beg, Size num, Func op)
generate() assigns the values that are generated by a call of
op()
to each element in the range [beg,end).
generate_n() assigns the values that are generated by a call of
op()
to the first num elements in the range starting with beg.
The caller must ensure that the destination range is big enough or that insert iterators are used.
Complexity: linear (numberOfElements or num calls of op() and assignments).
The following program demonstrates how to use generate() and generate_n() to insert or assign some random numbers:
// algo/generate.cpp #include <cstdlib> #include "algostuff.hpp" using namespace std; int main() { list<int> coll; //insert five random numbers generate_n (back_inserter(coll), //beginning of destination range 5, //count rand); //new value generator PRINT_ELEMENTS(coll); //overwrite with five new random numbers generate (coll.begin(), coll.end(), //destination range rand); //new value generator PRINT_ELEMENTS(coll); }
The rand() function is described in Section 12.3. The program might have the following output:
41 18467 6334 26500 19169 15724 11478 29358 26962 24464
The output is platform dependent because the random number sequence that rand() generates is not standardized.
See Section 8.1.2, for an example that demonstrates how to use generate() with function objects so that it generates a sequence of numbers.
void
replace (Forwardlterator beg, ForwardIterator end, const T& oldValue, const T& newValue)
void
replace_if (ForwardIterator beg, ForwardIterator end, UnaryPredicate op, const T& newValue)
replace() replaces each element in the range [beg,end) that is equal to oldValue with newValue.
replace_if() replaces each element in the range [beg,end) for which the unary predicate
op(elem)
yields true with newValue.
Note that op should not change its state during a function call. See Section 8.1.4, for details.
Complexity: linear (numberOfElements comparisons or calls of op() respectively).
The following program demonstrates some examples of the use of replace() and replace_if():
// algo/replace1.cpp #include "algostuff.hpp" using namespace std; int main() { list<int> coll; INSERT_ELEMENTS(coll,2,7); INSERT_ELEMENTS(coll,4,9); PRINT_ELEMENTS(coll,"coll: "); //replace all elements with value 6 with 42 replace (coll.begin(), coll.end(), //range 6, //old value 42); //new value PRINT_ELEMENTS(coll,"coll: "); //replace all elements with value less than 5 with 0 replace_if (coll.begin(), coll.end(), //range bind2nd(less<int>(),5), //criterion for replacement 0); //new value PRINT_ELEMENTS(coll,"coll: "); }
The program has the following output:
coll: 2 3 4 5 6 7 4 5 6 7 8 9 coll: 2 3 4 5 42 7 4 5 42 7 8 9 coll: 0 0 0 5 42 7 0 5 42 7 8 9
OutputIterator
replace_copy (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg, const T& oldValue, const T& newValue)
OutputIterator
replace_copy_if (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg, UnaryPredicate op, const T& newValue)
replace_copy() is a combination of copy() and replace(). It replaces each element in the source range [beg,end) that is equal to oldValue with newValue while the elements are copied into the destination range starting with destBeg.
replace_copy_if() is a combination of copy() and replace_if(). It replaces each element in the source range [beg,end) for which the unary predicate
op(elem)
yields true with newValue while the elements are copied into the destination range starting with destBeg.
Both algorithms return the position after the last copied element in the destination range (the first element that is not overwritten).
Note that op should not change its state during a function call. See Section 8.1.4, for details.
The caller must ensure that the destination range is big enough or that insert iterators are used.
Complexity: linear (numberOfElements comparisons or calls of op() and assignments respectively).
The following program demonstrates how to use replace_copy() and replace_copy_if():
// algo/replace2.cpp #include "algostuff.hpp" using namespace std; int main() { list<int> coll; INSERT_ELEMENTS(coll,2,6); INSERT_ELEMENTS(coll,4,9); PRINT_ELEMENTS(coll); //print all elements with value 5 replaced with 55 replace_copy(coll.begin(), coll.end(), //source ostream_iterator<int>(cout," "), //destination 5, //old value 55); //new value cout << endl; //print all elements with a value less than 5 replaced with 42 replace_copy_if (coll.begin(), coll.end(), //source ostream_iterator<int>(cout," "), //destination bind2nd(less<int>(),5), //replacement criterion 42); //new value cout << endl; //print each element while each odd element is replaced with 0 replace_copy_if (coll.begin(), coll.end(), //source ostream_iterator<int>(cout," "), //destination bind2nd (modulus<int>(),2), //replacement criterion 0); //new value cout << endl; > }
The program has the following output:
2 3 4 5 6 4 5 6 7 8 9 2 3 4 55 6 4 55 6 7 8 9 42 42 42 5 6 42 5 6 7 8 9 2 0 4 0 6 4 0 6 0 8 0
The following algorithms remove elements from a range according to their value or to a criterion. These algorithms, however, cannot change the number of elements. They only move logically by overwriting "removed" elements with the following elements that were not removed. They return the new logical end of the range (the position after the last element not removed). See Section 5.6.1, for details.
ForwardIterator
remove (ForwardIterator beg, ForwardIterator end, const T& value)
ForwardIterator
remove_if (ForwardIterator beg, ForwardIterator end, UnaryPredicate op)
remove() removes each element in the range [beg,end).
remove_if() removes each element in the range [beg,end) for which the unary predicate
op(elem)
yields true.
Both algorithms return the logical new end of the modified sequence (the position after the last element not removed).
The algorithms overwrite "removed" elements by the following elements that were not removed.
The order of elements that were not removed remains stable.
It is up to the caller, after calling this algorithm, to use the returned new logical end instead of the original end end (see Section 5.6.1, for more details).
Note that op should not change its state during a function call. See Section 8.1.4, for details.
Note that remove_if() usually copies the unary predicate inside the algorithm and uses it twice. This may lead to problems if the predicate changes its state due to the function call. See Section 8.1.4, for details.
Due to modifications, you can't use these algorithms for an associative container (see Section 5.6.2). However, associative containers provide a similar member function, erase() (see page 242).
Lists provide an equivalent member function, remove(), which offers better performance because it relinks pointers instead of assigning element values (see page 242).
Complexity: linear (numberOfElements comparisons or calls of op() respectively).
The following program demonstrates how to use remove() and remove_if():
// algo/remove1.cpp #include "algostuff.hpp" using namespace std; int main() { vector<int> coll; INSERT_ELEMENTS(coll,2,6); INSERT_ELEMENTS(coll,4,9); INSERT_ELEMENTS(coll,1,7); PRINT_ELEMENTS(coll,"coll: "); //remove all elements with value 5 vector<int>::iterator pos; pos = remove (coll. begin(), coll.end(), //range 5); //value to remove PRINT_ELEMENTS(coll,"size not changed: "); //erase the "removed" elements in the container coll. erase (pos, coll.end()); PRINT_ELEMENTS(coll,"size changed: "); //remove all elements less than 4 coll.erase(remove_if (coll.begin(), coll.end(), //range bind2nd(less<int>(),4)), //remove criterion coll.end()); PRINT_ELEMENTS(coll,"<4 removed: : "); }
The program has the following output:
coll: 2 3 4 5 6 4 5 6 7 8 9 1 2 3 4 5 6 7 size not changed: 2 3 4 6 4 6 7 8 9 1 2 3 4 6 7 5 6 7 size changed: 2 3 4 6 4 6 7 8 9 1 2 3 4 6 7 <4 removed: : 4 6 4 6 7 8 9 4 6 7
OutputIterator
remove_copy (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg, const T& value)
OutputIterator
remove_copy_if (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg, UnaryPredicate op)
remove_copy() is a combination of copy() and remove(). It removes each element in the source range [beg,end) that is equal to value while the elements are copied into the destination range starting with destBeg.
remove_copy_if() is a combination of copy() and remove_if(). It removes each element in the source range [beg,end) for which the unary predicate
op(elem)
yields true while the elements are copied into the destination range starting with destBeg.
Both algorithms return the position after the last copied element in the destination range (the first element that is not overwritten).
Note that op should not change its state during a function call. See Section 8.1.4, for details.
The caller must ensure that the destination range is big enough or that insert iterators are used.
Complexity: linear (numberOfElements comparisons or calls of op() and assignments respectively).
The following program demonstrates how to use remove_copy() and remove_copy_if():
// algo/remove2.cpp #include "algostuff.hpp" using namespace std; int main() { list<int> coll1; INSERT_ELEMENTS(coll1,1,6); INSERT_ELEMENTS(coll1,l,9); PRINT_ELEMENTS(coll1); //print elements without those having the value 3 remove_copy(coll1.begin(), coll 1.end(), //source ostream_iterator<int>(cout," "), //destination 3); //removed value cout << endl; //print elements without those having a value greater than 4 remove_copy_if (coll1.begin(), coll1.end(), //source ostream_iterator<int>(cout," "), //destination bind2nd(greater<int>(),4)); //removed elements cout << endl; //copy all elements greater than 3 into a multiset multiset<int> coll2; remove_copy_if (coll1.begin(), coll1.end(), //source inserter(coll2,coll2.end()), //destination bind2nd(less<int>(),4)); //elements not copied PRINT_ELEMENTS(coll2); }
The program has the following output:
1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 1 2 4 5 6 1 2 4 5 6 7 8 9 1 2 3 4 1 2 3 4 4 4 5 5 6 6 7 8 9
void
unique (ForwardIterator beg, ForwardIterator end)
void
unique (Forwardlterator beg, ForwardIterator end, BinaryPredicate op)
Both forms collapse consecutive equal elements by removing the following duplicates.
The first form removes from the range [beg,end) all elements that are equal to the previous elements. Thus, only when the elements in the sequence are sorted (or at least when all elements of the same value are adjacent), does it remove all duplicates.
The second form removes all elements that follow an element e and for which the binary predicate
op(elem,e)
yields true. In other words, the predicate is not used to compare an element with its predecessor; the element is compared with the previous element that was not removed (see the following examples).
Both forms return the logical new end of the modified sequence (the position after the last element not removed).
The algorithms overwrite "removed" elements by the following elements that were not removed.
The order of elements that were not removed remains stable.
It is up to the caller, after calling this algorithm, to use the returned new logical end instead of the original end end (see Section 5.6.1, for more details).
Note that op should not change its state during a function call. See Section 8.1.4, for details.
Due to modifications you can't use these algorithms for an associative container (see Section 5.6.2).
Lists provide an equivalent member function, unique(), which offers better performance because it relinks pointers instead of assigning element values (see page 244).
Complexity: linear (numberOfElements comparisons or calls of op() respectively).
The following program demonstrates how to use unique():
// algo/unique1.cpp #include "algostuff.hpp" using namespace std; int main() { //source data int source[] = { 1, 4, 4, 6, 1, 2, 2, 3, 1, 6, 6, 6, 5, 7, 5, 4, 4 }; int sourceNum = sizeof(source)/sizeof(source[0]); list<int> coll;. //initialize coll with elements from source copy (source, source+sourceNum, //source back_inserter(coll)) ; //destination PRINT_ELEMENTS(coll); //remove consecutive duplicates list<int> :: iterator pos; pos = unique (coll.begin(), coll.end()); /*print elements not removed *-use new logical end */ copy (coll.begin(), pos, //source ostream_iterator<int>(cout," ")); //destination cout << "\n\n"; //reinitialize coll with elements from source copy (source, source+sourceNum, //source coll.begin()); //destination PRINT_ELEMENTS(coll); //remove elements if there was a previous greater element coll.erase (unique (coll.begin(), coll.end(), greater<int>()), coll.end()); PRINT_ELEMENTS(coll); }
The program has the following output:
1 4 4 6 1 2 2 3 1 6 6 6 5 7 5 4 4 1 4 6 1 2 3 1 6 5 7 5 4 1 4 4 6 1 2 2 3 1 6 6 6 5 7 5 4 4 1 4 4 6 6 6 6 7
The first call of unique() removes consecutive duplicates. The second call shows the behavior of the second form. It removes all the consecutive following elements of an element for which the comparison with greater yields true. For example, the first 6 is greater than the following 1, 2, 2, 3, and 1, so all these elements are removed. In other words, the predicate is not used to compare an element with its predecessor; the element is compared with the previous element that was not removed (see the following description of unique_copy() for another example).
OutputIterator
unique_copy (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg)
OutputIterator
unique_copy (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg, BinaryPredicate op)
Both forms are a combination of copy() and unique()
They copy all elements of the source range [sourceBeg,sourceEnd) into the destination range starting with destBeg except for consecutive duplicates.
Both forms return the position after the last copied element in the destination range (the first element that is not overwritten).
The caller must ensure that the destination range is big enough or that insert iterators are used.
Complexity: linear (numberOfElements comparisons or calls of op() and assignments respectively).
The following program demonstrates how to useunique_copy():
// algo/unique2.cpp #include "algostuff.hpp" using namespace std; bool differenceOne (int elem1, int elem2) { return elem1 + 1 == elem2 || elem1 - 1 == elem2; } int main() { // source data int source[] = { 1, 4, 4, 6, 1, 2, 2, 3, 1, 6, 6, 6, 5, 7, 5, 4, 4 }; int sourceNum = sizeof(source)/sizeof(source[0]); // initialize coll with elements from source list<int> coll; copy(source, source+sourceNum, // source back_inserter(coll)); // destination PRINT_ELEMENTS(coll); // print element with consecutive duplicates removed unique_copy(coll.begin(), coll.end(), // source ostream_iterator<int>(cout," ")); // destination cout << endl; // print element without consecutive duplicates that differ by one unique_copy(coll.begin(), coll.end(), // source ostream_iterator<int>(cout," "), // destination differenceOne); // duplicate criterion cout << endl; }
The program has the following output:
1 4 4 6 1 2 2 3 1 6 6 6 5 7 5 4 4 1 4 6 1 2 3 1 6 5 7 5 4 1 4 4 6 1 3 1 6 6 6 4 4
Note that the second call of unique_copy() does not remove the elements that differ from their predecessor by one. Instead it removes all elements that differ from their previous element that is not removed by one. For example, after the three occurrences of 6, the following 5, 7, and 5 differ by one compared with 6, so they are removed. However, the following two occurrences of 4 remain in the sequence because compared with 6 the difference is not one.
Another example compresses sequences of spaces:
// algo/unique3.cpp #include <iostream> #include <algorithm> using namespace std; bool bothSpaces (char elem1, char elem2) { return elem1 == ' ' && elem2 == ' '; } int main() { // don't skip leading whitespaces by default cin.unsetf(ios :: skipws); / * copy standard input to standard output *-while compressing spaces */ unique_copy(istream_iterator<char>(cin), // beginning of source:cin istream_iterator<char>(), // end of source: end-of-file ostream_iterator<char>(cout), // destination: cout bothSpaces); // duplicate criterion }
With the input of
Hello, here are sometimes more and sometimes fewer spaces.
this example produces the following output:
Hello, here are sometimes more and sometimes fewer spaces.
Mutating algorithms change the order of elements (but not their values). Because elements of associative containers have a fixed order, you can't use them as a destination for mutating algorithms.
void
reverse (BidirectionalIterator beg, BidirectionalIterator end)
OutputIterator
reverse_copy (BidirectionalIterator sourceBeg, BidirectionalIterator sourceEnd, Output Iterator destBeg)
reverse() reverses the order of the elements inside the range [beg,end).
reverse_copy() reverses the order of the elements while copying them from the source range [sourceBeg,sourceEnd) to the destination range starting with destBeg.
reverse_copy() returns the position after the last copied element in the destination range (the first element that is not overwritten).
The caller must ensure that the destination range is big enough or that insert iterators are used.
Lists provide an equivalent member function, reverse(), which offers better performance because it relinks pointers instead of assigning element values (see page 246).
Complexity: linear (numberOfElements/2 swaps or numberOfElements assignments respectively).
The following program demonstrates how to use reverse() and reverse,copy():
// algo/reverse1.cpp #include "algostuff.hpp" using namespace std; int main() { vector<int> coll; INSERT_ELEMENTS(coll,1,9); PRINT_ELEMENTS(coll,"coll: "); // reverse order of elements reverse (coll.begin(), coll.end()); PRINT_ELEMENTS(coll,"coll: "); // reverse order from second to last element but one reverse (coll.begin()+l, coll.end()-l); PRINT_ELEMENTS(coll,"coll: "); //print all of them in reverse order reverse_copy (coll.begin(), coll.end(), // source ostream_iterator<int>(cout," ")); // destination cout << endl; }
The program has the following output:
coll: 1 2 3 4 5 6 7 8 9 coll: 9 8 7 6 5 4 3 2 1 coll: 9 2 3 4 5 6 7 8 1 1 8 7 6 5 4 3 2 9
void
rotate (ForwardIterator beg, ForwardIterator newBeg, ForwardIterator end)
Rotates elements in the range [beg,end) so that *newBeg is the new first element after the call.
The caller must ensure that newBeg is a valid position in the range [beg,end); otherwise, the call results in undefined behavior.
Complexity: linear (at most, numberOfElements swaps).
The following program demonstrates how to use rotate():
// algo/rotate1.cpp #include "algostuff.hpp" using namespace std; int main() { vector<int> coll; INSERT_ELEMENTS(coll,1,9); PRINT_ELEMENTS(coll,"coll: "); // rotate one element to the left rotate (coll.begin(), // beginning of range coll.begin() + 1, // new first element coll.end()); // end of range PRINT_ELEMENTS(coll,"one left: "); // rotate two elements to the right rotate (coll.begin(), // beginning of range coll.end() - 2, // new first element coll.end()); // end of range PRINT_ELEMENTS(coll,"two right: "); // rotate so that element with value 4 is the beginning rotate (coll.begin(), // beginning of range find (coll.begin(), coll.end(),4), // new first element coll.end()); // end of range PRINT_ELEMENTS(coll,"4 first: "); }
As the example shows, you can rotate to the left with a positive offset for the beginning and rotate to the right with a negative offset to the end. However, adding the offset to the iterator is possible only when you have random access iterators, as you have for vectors. Without such iterators, you must use advance() (see the example of rotate_copy() on page 389).
The program has the following output:
coll: 1 2 3 4 5 6 7 8 9 one left: 2 3 4 5 6 7 8 9 1 two right: 9 1 2 3 4 5 6 7 8 4 first: 4 5 6 7 8 9 1 2 3
OutputIterator
rotate_copy (ForwardIterator sourceBeg, ForwardIterator newBeg, ForwardIterator ourceEnd, OutputIterator destBeg)
Is a combination of copy() and rotate().
Copies the elements of the source range [sourceBeg,sourceEnd) into the destination range starting with destBeg in rotated order so that newBeg is the new first element.
Returns the position after the last copied element in the destination range.
The caller must ensure that newBeg is an element in the range [beg,end); otherwise, the call results in undefined behavior.
The caller must ensure that the destination range is big enough or that insert iterators are used.
The source and destination ranges should not overlap.
Complexity: linear (numberOfElements assignments).
The following program demonstrates how to use rotate_copy():
// algo/rotate2.cpp #include "algostuff.hpp" using namespace std; int main() { set<int> coll; INSERT_ELEMENTS(coll,1,9); PRINT_ELEMENTS(coll); // print elements rotated one element to the left set<int>::iterator pos = coll.begin(); advance(pos,1); rotate_copy (coll.begin(), // beginning of source pos, // new first element coll.end(), // end of source ostream_iterator<int>(cout," ")); // destination cout << endl; // print elements rotated two elements to the right pos = coll.end(); advance(pos,-2); rotate_copy(coll.begin(), // beginning of source pos, // new first element coll.end(), // end of source ostream_iterator<int>(cout," ")); // destination cout << endl; // print elements rotated so that element with value 4 is the beginning rotate_copy (coll.begin(), // beginning of source coll.find(4), // new first element coll.end(), // end of source ostreamIiterator<int>(cout," ")); // destination cout << endl; }
Unlike the previous example of rotate() (see page 388), here a set is used instead of a vector. This has two consequences:
You must use advance() (see Section 7.3.1,) to change the value of the iterator because bidirectional iterators do not provide operator +.
You should use the find() member function instead of the find() algorithm because the former has better performance.
The program has the following output:
1 2 3 4 5 6 7 8 9 2 3 4 5 6 7 8 9 1 8 9 1 2 3 4 5 6 7 4 5 6 7 8 9 1 2 3
bool
next_permutation (BidirectionalIterator beg, BidirectionalIterator end)
bool
prev_permutation (BidirectionalIterator beg, BidirectionalIterator end)
next_permutation() changes the order of the elements in [beg,end) according to the next permutation.
prev_permutation() changes the order of the elements in [beg,end) according to the previous permutation.
Both algorithms return true if the elements have the "normal" (lexicographical) order; that is, ascending order for next_permutation() and descending order for prev_permutation(). So, to run through all permutations you have to sort all elements (ascending or descending), and start a loop that calls next_permutation() or prev_permutation() as long as these algorithms return false. ^{[5]} Lexicographical sorting is explained on page 360.
Complexity: linear (at most, numberOfElements/ 2 swaps).
The following example demonstrates how next_permutation() and prev_permutation() run through all permutations of the elements:
// algo/perm1.cpp #include "algostuff.hpp" using namespace std; int main() { vector<int> coll; INSERT_ELEMENTS(coll,1,3); PRINT_ELEMENTS(coll,"on entry: "); /*permute elements until they are sorted *-runs through all permutations because the elements are sorted now */ while (next_permutation(coll.begin(),coll.end())) { PRINTIELEMENTS(coll," "); } PRINT_ELEMENTS(coll."afterward: "); /*permute until descending sorted *-this is the next permutation after ascending sorting *-so the loop ends immediately */ while (prev_permutation(coll.begin(),coll.end())) { PRINT_ELEMENTS(coll," "); } PRINT_ELEMENTS(coll,"now: "); /*permute elements until they are sorted in descending order *-runs through all permutations because the elements are sorted * in descending order now */ while (prev_permutation(coll.begin(), coll.end()) { PRINT_ELEMENTS(coll," "); } PRINT_ELEMENTS(coll,"afterward: "); }
The program has the following output:
on entry: 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 afterward: 1 2 3 now: 3 2 1 3 1 2 2 3 1 2 1 3 1 3 2 1 2 3 afterward: 3 2 1
void
random_shuffle (RandomAccessIterator beg, RandomAccessIterator end)
void
random_shuffle (RandomAccessIterator beg, RandomAccessIterator end, RandomFunc& op)
The first form shuffles the order of the elements in the range [beg,end) using a uniform distribution random number generator.
The second form shuffles the order of the elements in the range [beg,end) using op. op is called with an integral value of difference_type of the iterator:
op (max)
It should return a random number greater than or equal to zero and less than max. Thus, it should not return max itself.
Note that op is a nonconstant reference, so you can't pass a temporary value or an ordinary function.
Complexity: linear (numberOfElements-1 swaps).
You might wonder why random_shuffle() uses its optional operation as a nonconstant reference. It does so because random number generators typically have a local state. Old global C functions such as rand() store their local state in a static variable. However, this has some disadvantages: For example, the random number generator is inherently thread unsafe, and you can't have two independent streams of random numbers. Therefore, function objects provide a better solution by encapsulating their local state as one or more member variables. Thus, the random number generator can't be constant because it has to change its local state while generating a new random number. However, to have the random number generator nonconstant, you could still pass it by value instead of passing it by nonconstant reference. In this case each call would copy the random number generator and its state so that you get the same random sequence each time you pass the generator to the algorithm. Thus the generator is passed as a nonconstant reference. ^{[6]}
If you need the same random number sequence twice, you can simply copy it. However, if the generator is implemented in a way that uses a global state, you would still get different sequences.
The following example demonstrates how to shuffle elements by calling random_shuffle():
// algo/random1.cpp #include <cstdlib> #include "algostuff.hpp" using namespace std; c1ass MyRandom { public: ptrdiff_t operator() (ptrdiff_t max) { double tmp; tmp = static_cast<double>(rand()) / static_cast<double>(RAND_MAX); return static_cast<ptrdiff_t>(tmp * max); } }; int Main() { vector<int> coll; INSERT_ELEMENTS(coll,1,9); PRINT_ELEMENTS(coll,"coll: "); // shuffle all elements randomly random_shuffle (coll.begin(), coll.end()); PRINT_ELEMENTS(coll."shuffled: "); // sort them again sort (coll.begin(), coll.end()); PRINT_ELEMENTS(coll,"sorted: "); /*shuffle elements with self-written random number generator *-to pass an lvalue we have to use a temporary object */ MyRandom rd; random_shuffle (coll.begin(), coll.end(), // range rd); // random number generator PRINT_ELEMENTS(coll,"shuffled: "); }
The second call of random() uses the self-written random number generator rd(). It is an object of the auxiliary function object c1ass MyRandom, which uses an algorithm for random numbers that often is better than the usual direct call of rand().^{[7]}
A possible (but not portable) output of the program is as follows:
coll: 1 2 3 4 5 6 7 8 9 shuffled: 2 6 9 5 4 3 1 7 8 sorted: 1 2 3 4 5 6 7 8 9 shuffled: 2 6 9 3 1 8 7 4 5
BidirectionalIterator
partition (BidirectionalIterator beg, BidirectionalIterator end. UnaryPredicate op)
BidirectionalIterator
stable_partition (BidirectionalIterator beg, BidirectionalIterator end, UnaryPredicate op)
Both algorithms move all elements in the range [beg,end) to the front for which the unary predicate
op (elem)
yields true.
Both algorithms return the first position for which op() yields false.
The difference between partition() and stable_partition() is that stable_partition() preserves the relative order of elements that match the criterion and those that do not.
You could use this algorithm to split elements into two parts according to a sorting criterion. The nth_element() algorithm has a similar ability. See page 330 for a discussion of the differences between these algorithms and nth_element().
Note that op should not change its state during a function call. See Section 8.1.4,for details.
Complexity:
For partition(): linear (numberOfElements calls of op() and, at most, numberOfElements/2 swaps).
For stable_partition(): linear if there is enough extra memory (numberOfElements calls of op() and swaps), or n-log-n otherwise (numberOfElements*log(numberOfElements) calls of op()).
The following program demonstrates the use of and the difference between partition() and stable_partition():
// algo/part1.cpp #include "algostuff.hpp" using namespace std; int main() { vector<int> coll1; vector<int> coll2; INSERT_ELEMENTS(coll1,1,9); INSERT_ELEMENTS(coll2,1,9); PRINT_ELEMENTS(coll1,"coll1: "); PRINTIELEMENTS(coll2,"coll2: "); cout << endl; // move all even elements to the front vector<int>::iterator pos1, pos2; pos1 = partition(coll1.begin(), coll1.end(), // range not1(bind2nd(modulus<int>(),2))); // criterion pos2 = stable_partition(coll2.begin(), coll2.end(), // range not1(bind2nd(modulus<It>(),2))); // crit // print collections and first odd element PRINT_ELEMENTS(coll1,"coll1: "); cout << "first odd element: " << *pos1 << endl; PRINT_ELEMENTS(coll2,"coll2: "); cout << "first odd element: " << *pos2 << endl; }
The program has the following output:
coll1: 1 2 3 4 5 6 7 8 9 coll2: 1 2 3 4 5 6 7 8 9 coll1: 8 2 6 4 5 3 7 1 9 first odd element: 5 coll2: 2 4 6 8 1 3 5 7 9 first odd element: 1
As this example shows, stable_partition(), unlike partition(), preserves the relative order of the even and the odd elements.
The STL provides several algorithms to sort elements of a range. In addition to full sorting, it provides different variants of partial sorting. If their result is enough, you should prefer them because they usually have better performance.
You might also use associative containers to have elements sorted automatically. However, note that sorting all elements once is usually faster than keeping them sorted always (see page 228 for details).
void
sort (RandomAccessIterator beg, RandomAccessIterator end)
void
sort (RandomAccessIterator beg, RandomAccessIterator end, BinaryPredicate op)
void
stable_sort (RandomAccessIterator beg, RandomAccessIterator end)
void
stable_sort (RandomAccessIterator beg, RandomAccessIterator end, BinaryPredicate op)
The first forms of sort() and stable_sort() sort all elements in the range [beg,end) with operator <.
The second forms of sort() and stable_sort() sort all elements by using the binary predicate
op(elem1,elem2) as the sorting criterion.
Note that op should not change its state during a function call. See Section 8.1.4,for details.
The difference between sort() and stable_sort() is that stable_sort() guarantees that the order of equal elements remains stable.
You can't call these algorithms for lists because lists do not provide random access iterators. However, lists provide a special member function to sort elements: sort() (see page 245).
sort() guarantees a good performance (n-log-n) on average. However, if avoiding worst-case performance is important, you should use partial_sort() or stable_sort(). See the discussion about sorting algorithms on page 328.
Complexity:
For sort(): n-log-n on average (approximately numberOfElements*log(numberOfElements) comparisons on average).
For stable_sort(): n-log-n if there is enough extra memory (numberOfElements* log(numberOfElements) comparisons), or n-log-n*log-n otherwise (numberOfElements* log(numberOfElements) comparisons).
The following example demonstrates the use of sort():
// algo/sort1.cpp #include "algostuff.hpp" using namespace std; int main() { deque<int> coll; INSERT_ELEMENTS(coll,1,9); INSERT_ELEMENTS(coll,1,9); PRINT_ELEMENTS(coll,"on entry: "); // sort elements sort (coll.begin(), coll.end()); PRINT_ELEMENTS(coll,"sorted: "); // sorted reverse sort (coll.begin(), coll.end(), // range greater<int>()); // sorting criterion PRINT_ELEMENTS(coll,"sorted >: "); }
The program has the following output:
on entry: 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 sorted: 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 sorted >: 9 9 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1
See page 123 for an example that demonstrates how to sort according to a member of a c1ass.
The following program demonstrates how sort() and stable_sort() differ. The program uses both algorithms to sort strings only according to their number of characters by using the sorting criterion lessLength():
// algo/sort2.cpp #include "algostuff.hpp" using namespace std; bool lessLength (const string& s1, const string& s2) { return s1.length() < s2.length(); } int Main() { vector<string> coll1; vector<string> coll2; // fill both collections with the same elements coll1.push_back ("1xxx"); coll1.push_back ("2x"); coll1.push_back ("3x"); coll1.push_back ("4x"); coll1.push_back ("5xx"); coll1.push_back ("6xxxx"); coll1.push_back ("7xx"); coll1.push_back ("8xxx"); coll1.push_back ("9xx"); coll1.push_back ("l0xxx"); coll1.push_back ("11"); coll1.push_back ("12"); coll1.push_back ("13"); coll1.push_back ("14xx"); coll1.push_back ("15"); coll1.push_back ("16"); coll1.push_back ("17"); col12 = coll1; PRINT_ELEMENTS (coll1,"on entry:\n "); // sort (according to the length of the strings) sort (coll1.begin(), coll1.end(), // range lessLength); // criterion stable_sort (coll2.begin(), coll2.end(), // range lessLength); //criterion PRINT_ELEMENTS(coll1,"\nwith sort():\n "); PRINT_ELEMENTS(coll2,"\nwith stable_sort():\n "); }
The program has the following output:
on entry: 1xxx 2x 3x 4x 5xx 6xxxx 7xx 8xxx 9xx lOxxx 11 12 13 14xx 15 16 17 with sort(): 17 2x 3x 4x 16 15 13 12 11 9xx 7xx 5xx 8xxx 14xx 1xxx lOxxx 6xxxx with stable_sort(): 2x 3x 4x 11 12 13 15 16 17 5xx 7xx 9xx 1xxx 8xxx 14xx 6xxxx lOxxx
Only stable_sort() preserves the relative order of the elements (the leading numbers tag the order of the elements on entry).
void
partial_sort (RandomAccessIterator beg, RandomAccessIterator sortEnd, RandomAccessIterator end)
void
partial_sort (RandomAccessIterator beg, RandomAccessIterator sortEnd, RandomAccessIterator end, BinaryPredicate op)
The first form sorts the elements in the range [beg,end) with operator < so that range [beg,sortEnd) contains the elements in sorted order.
The second form sorts the elements by using the binary predicate
op (elem1, elem2)
as the sorting criterion so that range [beg,sortEnd) contains the elements in sorted order.
Note that op should not change its state during a function call. See Section 8.1.4, for details.
Unlike sort(), partial_sort() does not sort all elements, but stops the sorting once the first elements up to sortEnd are sorted correctly. Thus, if after sorting the sequence you need only the first three elements, this algorithm saves time because it does not sort the remaining elements unnecessarily.
If sortEnd is equal to end, partial_sort() sorts the full sequence. It has worse performance than sort() on average but better performance in the worst case. See the discussion about sorting algorithms on page 328.
Complexity: between linear and n-log-n (approximately numberOfElements*log(numberOfSortedElements) comparisons).
The following program demonstrates how to use partial_sort():
// algo/psort1.cpp #include "algostuff.hpp" using namespace std; int Main() { deque<int> coll; INSERT_ELEMENTS(coll,3,7); INSERT_ELEMENTS(coll,2,6); INSERT_ELEMENTS(coll,1,5); PRINT_ELEMENTS(coll); // sort until the first five elements are sorted partial_sort (coll.begin(), // beginning of the range coll.begin()+5, // end of sorted range coll.end()); // end of full range PRINT_ELEMENTS(coll); // sort inversely until the first five elements are sorted partial_sort(coll.begin(), // beginning of the range coll.begin()+5, // end of sorted range coll.end(), // end of full range greater<int>()); // sorting criterion PRINT_ELEMENTS(coll); // sort all elements partial_sort (coll.begin(), // beginning of the range coll.end(), // end of sorted range coll.end()); // end of full range PRINT_ELEMENTS(coll); }
The program has the following output:
3 4 5 6 7 2 3 4 5 6 1 2 3 4 5 1 2 2 3 3 7 6 5 5 6 4 4 3 4 5 7 6 6 5 5 1 2 2 3 3 4 4 3 4 5 1 2 2 3 3 3 4 4 4 5 5 5 6 6 7
RandomAccessIterator
partial_sort_copy (InputIterator sourceBeg, InputIterator sourceEnd, RandomAccessIterator destbeg, RandomAccessIterator destEnd)
partial_sort_copy (InputIterator sourceBeg, InputIterator sourceEnd, RandomAccessIterator destbeg, RandomAccessIterator destEnd) BinaryPredicate op)
Both forms are a combination of copy() and partial_sort().
They copy elements from the source range [sourceBeg,sourceEnd) sorted into the destination range [destBeg,destEnd).
The number of elements that are sorted and copied is the minimum number of elements in the source range and in the destination range.
Both forms return the position after the last copied element in the destination range (the first element that is not overwritten).
If the destination range [destBeg,destEnd) has more or an equal number of elements than the source range [sourceBeg,sourceEnd), all elements are copied and sorted. Thus, the behavior is a combination of copy() and sort().
Complexity: between linear and n-log-n (approximately numberOfElements*log(numberOfSortedElements) comparisons).
The following program demonstrates some examples of partial_sort_copy():
// algo/psort2.cpp #include "algostuff.hpp" using namespace std; int main() { deque<int> coll1; vector<int> coll6(6); // initialize with 6 elements vector<int> coll30(30); // initialize with 30 elements INSERT_ELEMENTS(coll1,3,7); INSERTIELEMEMTS(coll1,2,6); INSERT_ELEMENTS(coll1,1,5); PRINT_ELEMENTS(coll1); // copy elements of coll1 sorted into coll6 vector<int>::iterator pos6; pos6 = partial_sort_copy (coll1.begin(), coll1.end(), coll6.begin(), coll6.end()); // print all copied elements copy (coll6.begin(), pos6, ostream_iterator<int>(cout," ")); cout << endl; // copy elements of coll1 sorted into coll30 vector<int>::iterator pos30; pos30 = partial_sort_copy (coll1.begin(), coll1.end(), coll30.begin(), coll30.end(), greater<int>()); // print all copied elements copy (coll30.begin(), pos30, ostream_iterator<int>(cout," ")); cout << endl; }
The program has the following output:
3 4 5 6 7 2 3 4 5 6 1 2 3 4 5 1 2 2 3 3 3 7 6 6 5 5 5 4 4 4 3 3 3 2 2 1
The destination of the first call of partial_sort_copy() has only six elements, so the algorithm copies only six elements and returns the end of coll6. The second call of partial_sort_copy() copies all elements of coll1 into coll30, which has enough room for them, and thus all elements are copied and sorted.
void
nth_element (RandomAccessIterator beg, RandomAccessIterator nth, RandomAccessIterator end)
void
nth_element (RandomAccessIterator beg, RandomAccessIterator nth, RandomAccessIterator end, BinaryPredicate op)
Both forms sort the elements in the range [beg,end) so that the correct element is at the nth position and all elements in front are less than or equal to this element, and all elements that follow are greater than or equal to it. Thus, you get two subsequences separated by the element at position n, whereby each element of the first subsequence is less than or equal to each element of the second subsequence. This is helpful if you need only the set of the n highest or lowest elements without having all the elements sorted.
The first form uses operator < as the sorting criterion.
The second form uses the binary predicate
op(elem1 ,elem2)
as the sorting criterion.
Note that op should not change its state during a function call. See Section 8.1.4, for details.
The partition() algorithm (see page 395) is also provided to split elements of a sequence into two parts according to a sorting criterion. See page 330 for a discussion of how nth_element() and partition() differ.
Complexity: linear on average.
The following program demonstrates how to use nth_element():
// algo/nth1.cpp #include "algostuff.hpp" using namespace std; int main() { deque<int> coll; INSERT_ELEMENTS(coll,3,7); INSERT_ELEMENTS(coll,2,6); INSERT_ELEMENTS(coll,1,5); PRINT_ELEMENTS(coll); // extract the four lowest elements nth_element (coll.begin(), // beginning of range coll.begin()+3, // element that should be sorted correctly coll.end()); // end of range // print them cout << "the four lowest elements are: "; copy (coll.begin(), coll.begin()+4, ostream_iterator<int>(cout," ")); cout << endl; // extract the four highest elements nth_element (coll.begin(), // beginning of range coll.end()-4, // element that should be sorted correctly coll.end()); // end of range // print them cout << "the four highest elements are: "; copy (coll.end()-4, coll.end(), ostream_iterator<int>(cout," ")); cout << endl; // extract the four highest elements (second version) nth_element (coll.begin(), // beginning of range coll.begin()+3, // element that should be sorted correctly coll.end(), // end of range greater<int>()); // sorting criterion // print them cout << "the four highest elements are: "; copy (coll.begin(), coll.begin()+4, ostream_iterator<int>(cout," ")); cout << endl; }
The program has the following output:
3 4 5 6 7 2 3 4 5 6 1 2 3 4 5 the four lowest elements are: 2 1 2 3 the four highest elements are: 5 6 7 6 the four highest elements are: 6 7 6 5
A heap, in the context of sorting, is used as a particular way to sort elements. It is used by heapsort. A heap can be considered a binary tree that is implemented as a sequential collection. Heaps have two properties:
The first element is always the largest element.
You can add or remove an element in logarithmic time.
A heap is the ideal way to implement a priority queue (a queue that sorts its elements automatically). Therefore, the heap algorithms are used by the priority_queue container (see Section 10.3). The STL provides four algorithms to handle a heap:
make_heap() converts a range of elements into a heap.
push_heap() adds one element to the heap.
pop_heap() removes the next element from the heap.
sort_heap() converts the heap into a sorted collection (after that, it is no longer a heap).
As usual, you can pass a binary predicate as the sorting criterion. The default sorting criterion is operator <.
void
make_heap (RandomAccesIterator beg, RandomAccesIterator end)
void
make_heap (RandomAccesIterator beg, RandomAccesIterator end, BinaryPredicate op)
Both forms convert the elements in the range [beg,end) into a heap.
op is an optional binary predicate that is used as the sorting criterion:
op(etem1 ,elem2)
You need these functions only to start processing a heap for more than one element (one element automatically is a heap).
Complexity: linear (at most, 3*numberOfElements comparisons).
void
push_heap (RandomAccesIterator beg, RandomAccesIterator end)
void
push_heap (RandomAccesIterator beg, RandomAccesIterator end, BinaryPredicate op)
Both forms add the last element that is in front of end to the existing heap in the range [beg,end-1) so that the whole range [beg,end) becomes a heap.
op is an optional binary predicate that is used as the sorting criterion:
op(elem1 ,elem2)
The caller has to ensure that, on entry, the elements in the range [beg,end-1) are a heap (according to the same sorting criterion) and that the new element immediately follows these elements.
Complexity: logarithmic (at most, log(numberOfElements) comparisons).
void
pop_heap (RandomAccesIterator beg, RandomAccesIterator end)
void
pop_heap (RandomAccesIterator beg, RandomAccesIterator end, BinaryPredicate op)
Both forms move the highest element of the heap [beg,end), which is the first element, to the last position and create a new heap from the remaining elements in the range [beg,end-1).
op is an optional binary predicate that is used as the sorting criterion:
op(elem1 ,elem2)
The caller has to ensure that, on entry, the elements in the range [beg,end) are a heap (according to the same sorting criterion).
Complexity: logarithmic (at most, 2*log(numberOfElements) comparisons).
void
sort_heap (RandomAccesIterator beg, RandomAccesIterator end)
void
sort_heap (RandomAccesIterator beg, RandomAccesIterator end, BinaryPredicate op)
Both forms convert the heap [beg,end) into a sorted sequence.
op is an optional binary predicate that is used as the sorting criterion:
op(elem1, elem2)
Note that after this call, the range is no longer a heap.
The caller has to ensure that, on entry, the elements in the range [beg,end] are a heap (according to the same sorting criterion).
Complexity: n-log-n (at most, numberOfElements*log(numberOfElements) comparisons).
The following program demonstrates how to use the different heap algorithms:
// algo/heap1.cpp #include "algostuff.hpp" using namespace std; int main() { vector<int> coll; INSERT_ELEMENTS(coll,3,7); INSERT_ELEMENTS(coll,5,9); INSERT_ELEMENTS(coll,1,4); PRINT_ELEMENTS (coll, "on entry: "); // convert collection into a heap make_heap (coll.begin(), coll.end()); PRINT_ELEMENTS (coll, "after make_heap(): "); // pop next element out of the heap pop_heap (coll.begin(), coll.end()); coll.pop_back(); PRINT_ELEMENTS (coll, "after pop_heap(): "); // push new element into the heap coll.push_back (17); push_heap (coll.begin(), coll.end()); PRINT_ELEMENTS (coll, "after push_heap(): "); /*convert heap into a sorted collection * - NOTE: after the call it is no longer a heap */ sort_heap (coll.begin(), coll.end()); PRINT_ELEMENTS (coll, "after sort_heap(): "); }
The program has the following output:
on entry: 3 4 5 6 7 5 6 7 8 9 1 2 3 4 after make_heap(): 9 8 6 7 7 5 5 3 6 4 1 2 3 4 after pop_heap(): 8 7 6 7 4 5 5 3 6 4 1 2 3 after push_heap(): 17 7 8 7 4 5 6 3 6 4 1 2 3 5 after sort_heap(): 1 2 3 3 4 4 5 5 6 6 7 7 8 17
After make_heap(), the elements are sorted as a heap:
9 8 6 7 7 5 5 3 6 4 1 2 3 4
Transform the elements into a binary tree, and you'll see that the value of each node is less than or equal to its parent node (Figure 9.1). Both push_heap() and pop_heap() change the elements so that the invariant of this binary tree structure (each node not greater than its parent node) remains stable.
Sorted range algorithms require that the source ranges have the elements sorted according to their sorting criterion. They may have significant better performance than similar algorithms for unsorted ranges (usually logarithmic instead of linear complexity). You can use these algorithms with iterators that are not random access iterators. However, in this case, the algorithms have linear complexity because they have to step through the sequence element-b-element. Nevertheless, the number of comparisons may still have logarithmic complexity.
According to the standard, calling these algorithms for sequences that are not sorted on entry results in undefined behavior. However, for most implementations calling these algorithms also works for unsorted sequences. Nevertheless, to rely on this fact is not portable.
Associative containers provide special member functions for the searching algorithms presented here. When searching for a special value or key, you should use them.
The following algorithms search certain values in sorted ranges.
bool
binary_search (ForwardIterator beg, ForwardIterator end, const T& value)
bool
binary_search (ForwardIterator beg, ForwardIterator end, const T& value, BinaryPredicate op)
Both forms return whether the sorted range [beg,end) contains an element equal to value.
op is an optional binary predicate that is used as the sorting criterion:
op(elem1 ,elem2)
To obtain the position of an element for which you are searching, use lower_bound(), upper_bound(), or equal_range() (see page 413 and page 415).
The caller has to ensure that the ranges are sorted according to the sorting criterion on entry.
Complexity: logarithmic for random access iterators, linear otherwise (at most, log(numberOfElements) + 2 comparisons, but for other than random access iterators the number of operations to step through the elements is linear, making the total complexity linear).
The following program demonstrates how to use binary_search():
// algo/bsearch1.cpp #include "algostuff.hpp" using namespace std; int main() { list<int> coll; INSERT_ELEMENTS(coll,1,9); PRINT_ELEMENTS(coll) ; // check existence of element with value 5 if (binary_search(coll.begin(), coll end(), 5)) { cout << "5 is present" << endl; } else { cout << "5 is not present" << endl; } // check existence of element with value 42 if (binary_search(coll.begin(), coll.end(), 42)) { cout << "42 is present" << endl; } else { cout << "42 is not present" << endl; } }
The program has the following output:
1 2 3 4 5 6 7 8 9 5 is present 42 is not present
bool
includes (InputIterator1 beg, InputIterator1 end, InputIterator2 searchBeg, InputIterator2 searchEnd)
bool
includes (InputIterator1 beg, InputIterator1 end, InputIterator2 searchBeg, InputIterator2 searchEnd, BinaryPredicate op)
Both forms return whether the sorted range [beg,end) contains all elements in the sorted range [searchBeg,searchEnd). That is, for each element in [searchBeg,searchEnd) there must be an equal element in [beg,end). If elements in [searchBeg,search End) are equal, [beg,end) must contain the same number of elements. Thus, [searchBeg,searchEnd) must be a subset of [beg,end).
op is an optional binary predicate that is used as the sorting criterion:
op (elem1, elem2)
The caller has to ensure that both ranges are sorted according to the same sorting criterion on entry.
Complexity: linear (at most, 2* (numberOfElements+searchElements) - 1 comparisons).
The following program demonstrates the usage of includes():
// algo/includes.cpp #include "algostuff.hpp" using namespace std; int main() { list<int> coll; vector<int> search; INSERT_ELEMENTS(coll,1,9); PRINT_ELEMENTS(coll,"coll: "); search.push_back(3); search.push_back(4); search.push_back(7); PRINT_ELEMENTS(search,"search: "); // check whether all elements in search are also in coll if (includes (coll.begin(), coll.end(), search.begin(), search.end())) { cout << "all elements of search are also in coll" << endl; } else { cout << "not all elements of search are also in coll" << endl; } }
The program has the following output:
coll: 1 2 3 4 5 6 7 8 9 search: 3 4 7 all elements of search are also in coll
ForwardIterator
lower_bound (ForwardIterator beg, ForwardIterator end, const T& value)
ForwardIterator
lower_bound (ForwardIterator beg, ForwardIterator end, const T& value, BinaryPredicate op)
ForwardIterator
upper_bound (ForwardIterator beg, ForwardIterator end, const T& value)
ForwardIterator
upper_bound (ForwardIterator beg, ForwardIterator end, const T& value, BinaryPredicate op)
lower_bound() returns the position of the first element that has a value less than or equal to value. This is the first position where an element with value value could get inserted without breaking the actual sorting of the range [beg,end).
upper_bound() returns the position of the first element that has a value greater than value. This is the last position where an element with value value could get inserted without breaking the actual sorting of the range [beg,end).
All algorithms return end if there is no such value.
op is an optional binary predicate that is used as the sorting criterion:
op (elem1 ,elem2)
The caller has to ensure that the ranges are sorted according to the sorting criterion on entry.
To obtain the result from both lower_bound() and upper_bound(), use equal_range(), which returns both (see the next algorithm).
Associative containers (set, multiset, map, and multimap) provide equivalent member functions that provide better performance (see page 235).
Complexity: logarithmic for random access iterators, linear otherwise (at most, log(numberOfElements) + 1 comparisons, but for other than random access iterators the number of operations to step through the elements is linear, making the total complexity linear).
The following program demonstrates how to use lower_bound() and upper_bound()^{[8]}:
// algo/bounds1.cpp #include "algostuff.hpp" using namespace std; int main() { list<int> coll; INSERT_ELEMENTS(coll,1,9); INSERT_ELEMENTS(coll,1,9); coll.sort(); PRINT_ELEMENTS(coll); // print first and last position 5 could get inserted list<int> :: iterator pos1, pos2; pos1 = lower_bound (coll.begin(), coll.end(), 5); pos2 = upper_bound (coll.begin(), coll.end(), 5); cout << "5 could get position " << distance(coll.begin(),pos1) + 1 << " up to " << distance(coll.begin(),pos2) + 1 << " without breaking the sorting" << endl; // insert 3 at the first possible position without breaking the sorting coll.insert (lower_bound(coll.begin(), coll.end(), 3), 3); // insert 7 at the last possible position without breaking the sorting coll.insert (upper_bound(coll.begin(),coll.end(), 7), 7); PRINT_ELEMENTS(coll); }
The program has the following output:
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 5 could get position 9 up to 11 without breaking the sorting 1 1 2 2 3 3 3 4 4 5 5 6 6 7 7 7 8 8 9 9
pair<ForwardIterator,ForwardIterator>
equal_range (ForwardIterator beg, ForwardIterator end, const T& value)
pair<ForwardIterator,ForwardIterator>
equal_range (ForwardIterator beg, ForwardIterator end, const T& value, BinaryPredicate op)
Both forms return the range of elements that is equal to value. This is the first and the last position an element with value value could get inserted without breaking the actual sorting of the range [beg,end).
This is equivalent to
make_pair (lower_bound(...), upper_bound(...))
op is an optional binary predicate that is used as the sorting criterion:
op (elem1, elem2)
The caller has to ensure that the ranges are sorted according to the sorting criterion on entry.
Associative containers (set, multiset, map, and multimap) provide an equivalent member function that has better performance (see page 236).
Complexity: logarithmic for random access iterators, linear otherwise (at most, 2*log(numberOfElements) + 1 comparisons, but for other than random access iterators the number of operations to step through the elements is linear, making the total complexity linear).
The following program demonstrates how to use equal_range()^{[9]}:
// algo/eqrange1.cpp #include "algostuff.hpp" using namespace std; int main() { list<int> coll; INSERT_ELEMENTS(coll,1,9); INSERT_ELEMENTS(coll,1,9); coll.sort(); PRINT_ELEMENTS(coll); // print first and last position 5 could get inserted pair<list<int>::iterator,list<int>::iterator> range; range = equal_range (coll.begin(), coll.end(), 5); cout << "5 could get position " << distance (coll.begin(),range, first) + 1 << " up to " << distance(coll.begin().range.second) + 1 << " without breaking the sorting" << endl; }
The program has the following output:
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 5 could get position 9 up to 11 without breaking the sorting
The following algorithms merge elements of two ranges. They process the sum, the union, the intersection, and so on.
OutputIterator
merge (InputIterator source1Beg, InputIterator source1End, InputIterator source2Beg, InputIterator source2End, Output Iterator destBeg)
OutputIterator
merge (InputIterator source1Beg, InputIterator source1End, InputIterator source2Beg, InputIterator source2End, OutputIterator destBeg, BinaryPredicate op)
Both forms merge the elements of the sorted source ranges [source1Beg,source1End) and [source2Beg,source2End) so that the destination range starting with destBeg contains all elements that are in the first source range plus those that are in the second source range. For example, calling merge() for
1 2 2 4 6 7 7 9
and
2 2 2 3 6 6 8 9
results in
1 2 2 2 2 2 3 4 6 6 6 7 7 8 9 9
All elements in the destination range are in sorted order.
Both forms return the position after the last copied element in the destination range (the first element that is not overwritten).
op is an optional binary predicate that is used as the sorting criterion:
op(elem1 ,elem2)
The source ranges are not modified.
According to the standard, the caller has to ensure that both source ranges are sorted on entry. However, in most implementations this algorithm also merges elements of two unsorted source ranges into an unsorted destination range. Nevertheless, for unsorted ranges you should call copy() twice, instead of merge(), to be portable.
The caller must ensure that the destination range is big enough or that insert iterators are used.
The destination range should not overlap the source ranges.
Lists provide a special member function, merge(), to merge the elements of two lists (see page 246).
To ensure that elements that are in both source ranges end up in the destination range only once, use set_union() (see page 418).
To process only the elements that are in both source ranges, use set_intersection() (see page 419).
Complexity: linear (at most, numberOfElement1+numberOfElements2-1 comparisons).
The following example demonstrates how to use merge():
// algo/merge1.cpp #include "algostuff.hpp" using namespace std; int main() { list<int> coll1; set<int> coll2; // fill both collections with some sorted elements INSERT_ELEMENTS(coll1,l,6); INSERT_ELEMENTS(coll2,3,8); PRINT_ELEMENTS(coll1,"coll1: "); PRINT_ELEMENTS(coll2,"coll2: "); // print merged sequence cout << "merged: "; merge (coll1.begin(), coll1.end(), coll2.begin(), coll2.end(), ostream_iterator<int>(cout," ")); cout << endl; }
The program has the following output:
coll1: 1 2 3 4 5 6 coll2: 3 4 5 6 7 8 merged: 1 2 3 3 4 4 5 5 6 6 7 8
See page 421 for another example. It demonstrates how the different algorithms that are provided to combine sorted sequences differ.
OutputIterator
set_union (InputIterator source1Beg, InputIterator source1End, InputIterator source2Beg, InputIterator source2End, OutputIterator destBeg)
OutputIterator
set_union (InputIterator source1Beg, InputIterator source1End, InputIterator source2Beg, InputIterator source2End, OutputIterator destBeg, BinaryPredicate op)
Both forms merge the elements of the sorted source ranges [source1Beg,source1End) and [source2Beg,source2End) so that the destination range starting with destBeg contains all elements that are either in the first source range, in the second source range, or in both. For example, calling set_union() for
1 2 2 4 6 7 7 9
and
2 2 2 3 6 6 8 9
results in
1 2 2 2 3 4 6 6 7 7 8 9
All elements in the destination range are in sorted order.
Elements that are in both ranges are in the union range only once. However, duplicates are possible if elements occur more than once in one of the source ranges. The number of occurrences of equal elements in the destination range is the maximum of the number of their occurrences in both source ranges.
Both forms return the position after the last copied element in the destination range (the first element that is not overwritten).
op is an optional binary predicate that is used as the sorting criterion:
op(elem1,elem2)
The source ranges are not modified.
The caller has to ensure that the ranges are sorted according to the sorting criterion on entry.
The caller must ensure that the destination range is big enough or that insert iterators are used.
The destination range should not overlap the source ranges.
To obtain all elements of both source ranges without removing elements that are in both, use merge() (see page 416).
Complexity: linear (at most, 2*(numberOfElements1+numberOfElements2) - 1 comparisons).
See page 421 for an example of the use of set_union(). This example also demonstrates how it differs from other algorithms that combine elements of two sorted sequences.
OutputIterator
set_intersection (InputIterator source1Beg, InputIterator source1End. InputIterator source2Beg, InputIterator source2End, OutputIterator destBeg)
OutputIterator
set_intersection (InputIterator source1Beg, InputIterator source1End, InputIterator source2Beg, InputIterator sotirce2End, OutputIterator destBeg, BinaryPredicate op)
Both forms merge the elements of the sorted source ranges [source1 Beg,source1 End) and [source2Beg,source2End) so that the destination range starting with destBeg contains all elements that are in both source ranges. For example, calling set_intersection() for
1 2 2 4 6 7 7 9
and
2 2 2 3 6 6 8 9
results in
2 2 6 9
All elements in the destination range are in sorted order.
Duplicates are possible if elements occur more than once in both source ranges. The number of occurrences of equal elements in the destination range is the minimum number of their occurrences in both source ranges.
Both forms return the position after the last merged element in the destination range.
op is an optional binary predicate that is used as the sorting criterion:
op (elem1,elem2)
The source ranges are not modified.
The caller has to ensure that the ranges are sorted according to the sorting criterion on entry.
The caller must ensure that the destination range is big enough or that insert iterators are used.
The destination range should not overlap the source ranges.
Complexity: linear (at most, 2* (numberOfElements 1+numberOfElements2*) - 1 comparisons).
See page 421 for an example of the use of set_intersection(). This example also demonstrates how it differs from other algorithms that combine elements of two sorted sequences.
OutputIterator
set_difference (InputIterator source1Beg, InputIterator source1End, InputIterator source2Beg, InputIterator source2End, OutputIterator destBeg)
OutputIterator
set_difference (InputIterator source1Beg, InputIterator source1End, InputIterator source2Beg, InputIterator source2End, OutputIterator destBeg, BinaryPredicate op)
Both forms merge the elements of the sorted source ranges [source1Beg,source1End) and [source2Beg,source2End) so that the destination range starting with destBeg contains all elements that are in the first source range but not in the second source range. For example, calling set_difference() for
1 2 2 4 6 7 7 9
and
2 2 2 3 6 6 8 9
results in
1 4 7 7
All elements in the destination range are in sorted order.
Duplicates are possible if elements occur more than once in the first source range. The number of occurrences of equal elements in the destination range is the difference between the number of their occurrences in the first source range less the number of occurrences in the second source range. If there are more occurrences in the second source range, the number of occurrences in the destination range is zero.
Both forms return the position after the last merged element in the destination range.
op is an optional binary predicate that is used as the sorting criterion:
op(elem1 ,elem2)
The source ranges are not modified.
The caller has to ensure that the ranges are sorted according to the sorting criterion on entry.
The caller must ensure that the destination range is big enough or that insert iterators are used.
The destination range should not overlap the source ranges.
Complexity: linear (at most, 2*(numberOfElements1+numberOfElements2) - 1 comparisons).
See page 421 for an example of the use of set_difference(). This example also demonstrates how it differs from other algorithms that combine elements of two sorted sequences.
OutputIterator
set_symmetric_difference (InputIterator source1 Beg, InputIterator source1 End, InputIterator source2Beg, InputIterator source2End, OutputIterator destBeg)
OutputIterator
set_symmetric_difference (InputIterator source1Beg, InputIterator source1End, InputIterator source2Beg, InputIterator source2End, OutputIterator destBeg, BinaryPredicate op)
Both forms merge the elements of the sorted source ranges [source1Beg,source1End) and [source2Beg,source2End) so that the destination range starting with destBeg contains all elements that are either in the first source range or in the second source range, but not in both. For example, calling set_symmetric_difference() for
1 2 2 4 6 7 7 9
and
2 2 2 3 6 6 8 9
results in
1 2 3 4 6 7 7 8
All elements in the destination range are in sorted order.
Duplicates are possible if elements occur more than once in one of the source ranges. The number of occurrences of equal elements in the destination range is the difference between the number of their occurrences in the source ranges.
Both forms return the position after the last merged element in the destination range.
op is an optional binary predicate that is used as the sorting criterion:
op(elem1,elem2)
The source ranges are not modified.
The caller has to ensure that the ranges are sorted according to the sorting criterion on entry.
The caller must ensure that the destination range is big enough or that insert iterators are used.
The destination range should not overlap the source ranges.
Complexity: linear (at most, 2* (numberOfElements1+numberOfElements2) - 1 comparisons).
See the following subsection for an example of the use of set_symmetric_difference(). This example also demonstrates how it differs from other algorithms that combine elements of two sorted sequences.
The following example compares the different algorithms that combine elements of two sorted source ranges, demonstrating how they work and differ:
// algo/setalgos.cpp #include "algostuff.hpp" using namespace std; int main() { int c1[] = { 1, 2, 2, 4, 6, 7, 7, 9 }; int num1 = sizeof(c1) / sizeof(int); int c2[] = { 2, 2, 2, 3, 6, 6, 8, 9 >; int num2 = sizeof(c2) / sizeof(int); // print source ranges cout << "c1: " ; copy (c1, c1+num1, ostream_iterator<int>(cout," ")) ; cout << endl; cout << "c2: " ; copy (c2, c2+num2, ostream_iterator<int>(cout," ")); cout << '\n' << endl; // sum the ranges by using merge() cout << "merge(): "; merge (c1, c1+num1, c2, c2+num2, ostream_iterator<int>(cout," ")); cout << endl; // unite the ranges by using set_union() cout << "set_union(): "; set_union (c1, c1+num1, c2, c2+num2, ostream_iterator<int>(cout," ")); cout << endl; // intersect the ranges by using set_intersection() cout << "set_intersection(): "; set_intersection (c1, c1+num1, c2, c2+num2, ostream_iterator<int>(cout," ")); cout << endl; // determine elements of first range without elements of second range // by using set_difference() cout << "set_difference(): "; set_difference (c1, c1+num1, c2, c2+num2, ostream_iterator<int>(cout," ")); cout << endl; // determine difference the ranges with set_symmetric_difference() cout << "set_symmetric_difference(): "; set_symmetric_difference (c1, c1+num1, c2, c2+num2, ostream_iterator<int>(cout," ")); cout << endl; }
The program has the following output:
c1: 1 2 2 4 6 7 7 9 c2: 2 2 2 3 6 6 8 9 merge(): 1 2 2 2 2 2 3 4 6 6 6 7 7 8 9 9 set_union(): 1 2 2 2 3 4 6 6 7 7 8 9 set_intersection(): 2 2 6 9 set_difference(): 1 4 7 7 set_symmetric_difference(): 1 2 3 4 6 7 7 8
void
inplace_merge (BidirectionalIterator beg1, BidirectionalIterator end1beg2, BidirectionalIterator end2)
void
inplace_merge (BidirectionalIterator beg1, BidirectionalIterator end1beg2, BidirectionalIterator end2, BinaryPredicate op)
Both forms merge the consecutive sorted source ranges [beg1,end1beg2) and [end 1 beg2 ,end2) so that the range [beg1,end2) contains the elements as a sorted summary range.
Complexity: linear (numberOfElements-1 comparisons) if enough memory available, or n-log-n otherwise (numberOfElements*log (numberOfElements) comparisons).
The following program demonstrates the use of inplace_merge():
// algo/imerge1.cpp #include "algostuff.hpp" using namespace std; int main() { list<int> coll; // insert two sorted sequences INSERT_ELEMENTS(coll,1,7); INSERT_ELEMENTS(coll,1,8); PRINT_ELEMENTS(coll); // find beginning of second part (element after 7) list<int>::iterator pos; pos = find (coll.begin(), coll.end(), // range 7) ; // value ++pos; // merge into one sorted range inplace_merge (coll.begin(), pos, coll.end()); PRINT_ELEMENTS(coll); }
The program has the following output:
1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8
This section presents the STL algorithms that are provided for numeric processing. However, you can process other than numeric values. For example, you can use accumulate() to process the sum of several strings. To use the numeric algorithms you have to include the header file <numeric>^{[10]}:
#include <numeric>
T
accumulate (InputIterator beg, InputIterator end, T initValue)
T
accumulate (InputIterator beg. InputIterator end, T initValue, BinaryFunc op)
The first form computes and returns the sum of initValue and all elements in the range [beg,end). In particular, it calls
initValue = initValue + elem
for each element.
The second form computes and returns the result of calling op for initValue and all elements in the range [beg,end). In particular, it calls
initValue = op(initValue, elem)
for each element.
Thus, for the values
a1 a2 a3 a4 ...
they compute and return either
initValue + a1 + a2 + a3 + ...
or
initValue op a1 op a2 op a3 op ...
respectively.
If the range is empty (beg==end), both forms return initValue.
op must not modify the passed arguments.
Complexity: linear (numberOfElements calls of operator + or op() respectively).
The following program demonstrates how to use accumulate() to process the sum and the product of all elements of a range:
// algo/accu1.cpp #include "algostuff.hpp" using namespace std; int main() { vector<int> coll; INSERT_ELEMENTS(coll,1,9); PRINT_ELEMENTS(coll); // process sum of elements cout << "sum: " << accumulate (coll.begin(), coll.end(), // range 0) // initial value << endl; // process sum of elements less 100 cout << "sum: " << accumulate (coll.begin(), coll.end(), // range -100) // initial value << endl; // process product of elements cout << "product: " << accumulate (coll.begin(), coll.end(), // range 1, // initial value multiplies<int>()) // operation << endl; // process product of elements (use 0 as initial value) cout << "product: " << accumulate (coll.begin(), coll.end(), // range 0, // initial value multiplies<int>()) // operation << endl; }
The program has the following output:
1 2 3 4 5 6 7 8 9 sum: 45 sum: -55 product: 362880 product: 0
The last output is 0 because any value multiplied by zero is zero.
T
inner_product (InputIterator1 beg1, InputIterator1 end1, InputIterator2 beg2, T initValue)
T
inner_product (InputIterator1 beg1. InputIterator1 end1, InputIterator2 beg2, T initValue, BinaryFunc op1. BinaryFunc op2)
The first form computes and returns the inner product of initValue and all elements in the range [beg,end) combined with the elements in the range starting with beg2. In particular, it calls
initValue = initValue + elem1 * elem2
for all corresponding elements.
The second form computes and returns the result of calling op for initValue and all elements in the range [beg,end) combined with the elements in the range starting with beg2. In particular, it calls
initValue = op1 (initValue,op2(elem1 ,elem2))
for all corresponding elements.
Thus, for the values
a1 a2 a3 ... b1 b2 b3 ...
they compute and return either
initValue + (a1 * b1) + (a2 * b2) + (a3 * b3) + ...
or
initValue op1 (a1 op2 b1) op1 (a2 op2 b2) op1 (a3 op2 b3) op1 ...
respectively.
If the first range is empty (beg1==end1), both forms return initValue.
The caller has to ensure that the range starting with beg2 contains enough elements.
op1 and op2 must not modify their arguments.
Complexity: linear (numberOfElements calls of operators + and * or numberOfElements calls of op1() and op2() respectively).
The following program demonstrates how to use inner_product(). It processes the sum of products and the product of the sums for two sequences:
// algo/inner1.cpp #include "algostuff.hpp" using namespace std; int main() { list<int> coll; INSERT_ELEMENTS(coll,1,6); PRINT_ELEMENTS(coll); / * process sum of all products * (0 + 1*1 + 2*2 + 3*3 + 4*4 + 5*5 + 6*6) */ cout << "inner product: " << inner_product (coll.begin(), coll.end(), // first range coll.begin(), // second range 0) // initial value << endl; /*process sum of 1*6 ... 6*1 *(0 + 1*6 + 2*5 + 3*4 + 4*3 + 5*2 + 6*1) */ cout << "inner reverse product: " << inner_product (coll.begin(), coll.end(), // firstrange coll.rbegin(), // second range 0) // initial value << endl; / * process product of all sums * (1 * 1+1 * 2+2 * 3+3 * 4+4 * 5+5 * 6+6) */ cout << "product of sums: " << inner_product (coll.begin(), coll.end(), // first range coll.begin(), // second range 1, // initial value multiplies<int>(), // inner operation plus<int>()) // outer operation << endl; }
The program has the following output:
1 2 3 4 5 6 inner product: 91 inner reverse product: 56 product of sums: 46080
The following two algorithms provide the ability to convert a sequence of relative values into a sequence of absolute values, and vice versa.
OutputIterator
partial_sum (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg)
OutputIterator
partial_sum (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg, BinaryFunc op)
The first form computes the partial sum for each element in the source range [sourceBeg, sourceEnd) and writes each result to the destination range starting with destBeg.
The first form calls op for each element in the source range [sourceBeg,sourceEnd) combined with all previous values and writes each result to the destination range starting with destBeg.
Thus, for the values
a1 a2 a3 ...
they compute either
a1, a1 + a2, a1 + a2 + a3, ...
or
a1, a1 op a2, a1 op a2 op a3, ...
respectively.
Both forms return the position after the last written value in the destination range (the first element that is not overwritten).
The first form is equivalent to the conversion of a sequence of relative values into a sequence of absolute values. In this regard, partial_sum() is the complement of adjacent_difference().
The source and destination range may be identical.
The caller must ensure that the destination range is big enough or that insert iterators are used.
op should not modify the passed arguments.
Complexity: linear (numberOfElements calls of operator + or op() respectively).
The following program demonstrates some examples of using partial_sum():
// algo/partsum1.cpp #include "algostuff.hpp" using namespace std; int main() { vector<int> coll; INSERT_ELEMENTS(coll,1,6); PRINT_ELEMENTS(coll); // print all partial sums partial_sum (coll.begin(), coll.end(), // source range ostream_iterator<int>(cout," ")); // destination cout << end1; // print all partial products partial_sum (coll.begin(), coll.end(), // source range ostream_iterator<int>(cout," "), // destination multiplies<int>()) ; // operation cout << endl; }
The program has the following output:
1 2 3 4 5 6 1 3 6 10 15 21 1 2 6 24 120 720
See also the example of converting relative values into absolute values, and vice versa, on page 432.
OutputIterator
adjacent_difference (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg)
OutputIterator
adjacent_difference (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg, BinaryFunc op)
The first form computes the difference of each element in the range [sourceBeg,sourceEnd) with its predecessor and writes the result to the destination range starting with destBeg.
The second form calls op for each element in the range [sourceBeg,sourceEnd) with its predecessor and writes the result to the destination range starting with destBeg.
The first element only is copied.
Thus, for the values
a1 a2 a3 a4 ...
they compute and write either the values
a1, a2 - a1, a3 - a2, a4 - a3, ...
or the values
a1, a2 op a1, a3 op a2, a4 op a3, ...
respectively.
Both forms return the position after the last written value in the destination range (the first element that is not overwritten).
The first form is equivalent to the conversion of a sequence of absolute values into a sequence of relative values. In this regard, adjacent_difference() is the complement of partial_sum().
The source and destination range may be identical.
The caller must ensure that the destination range is big enough or that insert iterators are used.
op should not modify the passed arguments.
Complexity: linear (numberOfElements-1 calls of operator - or op() respectively).
The following program demonstrates some examples of using adjacent_difference():
// algo/adjdiff1.cpp #include "algostuff.hpp" using namespace std; int main() { deque<int> coll; INSERT_ELEMENTS(coll,1,6); PRINT_ELEMENTS(coll); // print all differences between elements adjacent_difference (coll.begin(), coll.end(), // source ostream_iterator<int>(cout, " ")); // dest. cout << end1; // print all sums with the predecessors adjacent_difference (coll.begin(), coll.end(), // source ostream_iterator<int>(cout," "), // dest. plus <int>()); // operation cout << endl; // print all products between elements adjacent_difference (coll.begin(), coll.end(), // source ostream_iterator<int>(cout," "), // dest. multiplies<int>()); // operation cout << endl; }
The program has the following output:
1 2 3 4 5 6 1 1 1 1 1 1 1 3 5 7 9 1 1 1 2 6 12 20 30
See also the example of converting relative values into absolute values, and vice versa, in the next subsection.
The following example demonstrates how to use partial_sum() and adjacent_difference() to convert a sequence of relative values into a sequence of absolute values, and vice versa:
// algo/relabs.cpp #include "algostuff.hpp" using namespace std; int main() { vector<int> coll; coll.push_back(17); coll.push_back(-3); coll.push_back(22); coll.push_back(13); coll.push_back(13); coll.push_back(-9); PRINT_ELEMENTS(coll,"coll: ") ; // convert into relative values adjacent_difference (coll.begin(), coll.end(), // source coll.begin()); // destination PRINT_ELEMENTS (coll,"relative: ") ; // convert into absolute values partial_sum (coll.begin(), coll.end(), // source coll.begin()); // destination PRINT_ELEMENTS(coll,"absolute: "); }
The program has the following output:
coll: 17 -3 22 13 13 -9 relative: 17 -20 25 -9 0 -22 absolute: 17 -3 22 13 13 -9
[1] In the original STL the header file for all algorithms was <algo.h>.
[2] In the original STL the header file for function objects and function adapters was <function.h>
[3] See Section 2.3, for an introduction to and a discussion of complexity.
[4] In the original STL the count() and count_if() had a fourth input/output parameter that was used as a counter and the return type was void.
[5] next_permutation() and prev_permutation() could also be used to sort elements in a range. You just call them for a range as long as they return false. However, doing so would produce really bad performance.
[6] Thanks to Matt Austern for this explanation.
[7] The way MyRandom generates random numbers is introduced and described in Bjarne Stroustrup's The C++ Programming Language, 3rd edition.
[8] Older STL versions might need the file distance.hpp from page 263.
[9] Older STL versions might need the file distance.hpp from page 263.
[10] In the original STL the numeric algorithms were defined in <algo.h>.
CONTENTS |
Browser Based Help. Published by chm2web software. |