The algorithms library, included from <algorithm>, contains functions that operate on element ranges through the use of iterators.
Many of these function are intended for sequence containers. 2 useful, non-modifying sequence operations are:
| Expression | Meaning |
|---|---|
| std::count(first, last, x) | Returns the number of elements from the range [first, last) that equal x. |
| std::find(first, last, x) | Returns an iterator to the first element from the range [first, last) that equals x. Returns last if not found. |
There is also std::count_if(first, last, p) and std::find_if(first, last p) that work similarly but they require a "predicate" instead of a value for the last argument.
A predicate is either of the following:
A function call to a predicate returns true if it's argument satisfies some criteria. If there is a std::vector<int> v and I wanted to count all the odd numbers in that vector, then count_if could be used:
// In namespace scope:
bool is_odd(int x) { return x % 2 == 1; }
// ...
// In block scope:
std::cout << "v contains " << std::count_if(v.begin(), v.end(), is_odd) << " odd integers" << std::endl;
If the element type has an object size larger than a fundamental type, then your predicate's parameter should be a constant reference to the element type rather than a copy of it.
| Expression | Meaning |
|---|---|
| std::copy(first, last, d_first) | Assigns the elements from the range [first, last) to the elements beginning at d_first |
| std::fill(first, last, x) | Assigns x to all the elements in the range [first, last) |
| std::generate(first, last, g) | Assigns each return value of g() to each element in the range [first, last) |
| std::replace(first, last, x, y) | Replaces all occurrences of the value x with the value y in the range [first, last) |
| std::reverse(first, last) | Reverses the order of elements in the range [first, last) |
You can generate a vector of 100 random integers using the following code:
std::vector<int> v;
v.resize(100);
std::srand(std::time(0));
std::generate(v.begin(), v.end(), std::rand);
In addition to std::find:
| Expression | Meaning |
|---|---|
| std::sort(first, last) | Sorts the element in the range [first, last) |
| std::binary_search(first, last, x) | Like std::find except the range to search in must already be sorted. This function also works with predicates. |
| std::min_element(first, last) | Returns an iterator to the element containing the minimum value |
| std::max_element(first, last) | Returns an iterator to the element containing the maximum value |
min_element and max_element can optionally take a third argument, a function to use for comparing the elements; this third argument is useful when, for example, you wanted to find an element in a map that contains the maximum mapped value.
Suppose you have a map<string, double> grades; which stores the name and current assignment grade of each student. You also have the following function defined:
bool compare_grades(const pair<const string, double>& a, const pair<const string, double>& b)
{
return a.second < b.second;
}
Then to acquire an iterator to the student with the highest grade, max_element would be called as follows:
map<string, double>::iterator it = max_element(grades.begin(), grades.end(), compare_grades);
cout << "The student " << it->first << " has the highest grade with a score of " << it->second; << endl;
swap, min, and max have two parameters
std::swap swaps the contents of two variables. This function works with std::string, any standard container type, any fundamental type, and any aggregate type.
std::min and std::max return the value that is lesser or greater respectively.
random_shuffle shuffles the element in a range, usually by using std::rand within the implementation. To shuffle a vector named v, just call std::random_shuffle(v.begin(), v.end()) after making sure the random number generator has been seeded once with std::srand.