Which STL algorithms replace the hand-written loops is a question worth asking every time that you write one. The standard library already has the sorting, the searching, the counting, the transforming, the accumulating, the copying, the removing and the unique-ing, and they are written, tested and optimised. Reaching for them is usually shorter, faster and easier to read than the loop that you were about to write.
The previous lesson in this module covered "How Do Iterators Walk Containers?", and this lesson is the last one in the The Standard Template Library module.
Finding things
The std::find looks for a value and it gives back an iterator to the first match, or end() if there is none. The std::find_if does the same with a predicate.
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
int main() {
std::vector<std::string> parcels = {"p-001", "p-002", "p-003", "p-004"};
auto found = std::find(parcels.begin(), parcels.end(), "p-003");
if (found != parcels.end()) {
std::cout << "found at " << (found - parcels.begin()) << '\n';
} else {
std::cout << "not found\n";
}
auto heavy = std::find_if(parcels.begin(), parcels.end(),
[](const std::string& id) { return id.size() > 4; });
if (heavy != parcels.end()) {
std::cout << "first long id: " << *heavy << '\n';
}
return 0;
}The output shows both of the searches.
found at 2
first long id: p-001Counting things
The std::count counts the matching elements and the std::count_if counts those that satisfy a predicate.
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
int main() {
std::vector<int> weights = {4, 30, 12, 30, 8};
std::cout << "heavy parcels: " << std::count(weights.begin(), weights.end(), 30) << '\n';
std::cout << "over 10kg: "
<< std::count_if(weights.begin(), weights.end(),
[](int weight) { return weight > 10; }) << '\n';
return 0;
}The output shows the two counts.
heavy parcels: 2
over 10kg: 3Sorting and rearranging
The std::sort sorts in place, the std::stable_sort sorts while it preserves the order of the equal elements, and the std::sort with a comparator lets you choose the ordering.
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
struct Parcel {
std::string id;
int weight;
};
int main() {
std::vector<Parcel> parcels = {
{"p-001", 30}, {"p-002", 4}, {"p-003", 30}, {"p-004", 12}
};
std::sort(parcels.begin(), parcels.end(),
[](const Parcel& left, const Parcel& right) {
return left.weight < right.weight;
});
for (const Parcel& parcel : parcels) {
std::cout << parcel.id << '=' << parcel.weight << ' ';
}
std::cout << '\n';
return 0;
}The output shows the parcels sorted by weight.
p-002=4 p-004=12 p-001=30 p-003=30And note that a stable sort would keep p-001 before p-003, because they have the same weight.
Transforming and accumulating
The std::transform applies a function to every element and writes the results somewhere. The std::accumulate folds a range into a single value.
#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <vector>
int main() {
std::vector<int> weights = {4, 30, 12, 8};
std::vector<int> kilos;
std::transform(weights.begin(), weights.end(),
std::back_inserter(kilos),
[](int grams) { return grams / 1000; });
std::cout << "kilos: ";
for (int value : kilos) {
std::cout << value << ' ';
}
std::cout << '\n';
int total = std::accumulate(weights.begin(), weights.end(), 0);
std::cout << "total grams: " << total << '\n';
return 0;
}The output shows the transformed values and the total.
kilos: 0 0 0 0
total grams: 54And the initial value of zero in the std::accumulate is the starting point, and it also determines the return type. Passing a zero with the integer elements gives an int result.
Removing and deduplicating
The std::remove moves the unwanted elements to the end and it gives back an iterator to the new logical end. It does not change the size of the container, and you have to call erase() with the iterator that came back.
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> weights = {4, 30, 12, 30, 8};
auto new_end = std::remove(weights.begin(), weights.end(), 30);
weights.erase(new_end, weights.end());
std::cout << "after remove: ";
for (int weight : weights) {
std::cout << weight << ' ';
}
std::cout << '\n';
std::vector<int> duplicates = {4, 4, 8, 8, 8, 12};
auto unique_end = std::unique(duplicates.begin(), duplicates.end());
duplicates.erase(unique_end, duplicates.end());
std::cout << "after unique: ";
for (int value : duplicates) {
std::cout << value << ' ';
}
std::cout << '\n';
return 0;
}The output shows the vector with the duplicates removed.
after remove: 4 12 8
after unique: 4 8 12And the erase-the-tail pattern is worth learning, because the std::remove on its own leaves the container at the same size.
A summary of the useful ones
the job the algorithms
----------------- ----------------------------------------------
the searching find, find_if, search, binary_search,
lower_bound, upper_bound
the counting count, count_if, distance
the ordering sort, stable_sort, nth_element, reverse,
rotate
the transforming transform, copy, copy_if, fill, generate
the folding accumulate, reduce, partial_sum
the removing remove, remove_if, unique, remove_duplicates
the merging merge, set_union, set_intersection
Why prefer the algorithm
The loop version of "find the first element that is greater than ten" is three lines of the bookkeeping that you have to get right every time. The algorithm version is one call that has been correct for thirty years, and that the compiler can optimise.
And there is one catch. Some of the algorithms need the random access iterators, so they work on a vector but not on a list. The member functions of the container, such as list::sort and list::remove, exist for exactly that reason.
Binary search on sorted data
If the data is sorted, then a linear search does far more work than it needs to. The std::lower_bound, the std::upper_bound and the std::binary_search all use the sorted order to halve the search space at every step.
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> weights = {4, 8, 12, 30, 30, 42};
auto first_at_least_30 = std::lower_bound(weights.begin(), weights.end(), 30);
auto first_above_30 = std::upper_bound(weights.begin(), weights.end(), 30);
std::cout << "lower bound: " << *first_at_least_30 << '\n';
std::cout << "upper bound: " << *first_above_30 << '\n';
std::cout << "count of 30s: "
<< (first_above_30 - first_at_least_30) << '\n';
if (std::binary_search(weights.begin(), weights.end(), 12)) {
std::cout << "12 is present\n";
}
return 0;
}The output shows the range of the elements that equal 30, which is exactly the difference between the two bounds.
lower bound: 30
upper bound: 42
count of 30s: 2
12 is presentAnd the requirement is that the range is sorted with the same comparator that you pass to the search. If it is not, then the result is undefined.
When to write the loop anyway
The algorithms are not always the answer, and knowing when to write your own loop is a part of using them well.
- When you need the early exit with a side effect. The
std::find_ifscans the whole range unless the predicate throws, and a loop with a return is clearer when you are searching for the first match. - When the loop needs several unrelated accumulators. A loop that updates a total, a maximum and a count in one pass is often clearer than three algorithms over the same range.
- When you need the index. The algorithms give back the iterators, and converting an iterator to an index means subtracting it from
begin(). - When the work is not a general pattern. A one-off piece of the business logic is often clearest as a plain loop with a good name.
And the guidance is not "always use an algorithm" but "use an algorithm when the pattern is one that the library already models".
Quick reference
- The
std::findgives back an iterator, and you compare it withend()to test for the failure. - The
std::removedoes not change the size, and you callerase(new_end, end)afterwards. - The
std::uniqueremoves the consecutive duplicates, and it needs the same erase. - The
std::accumulatetakes a starting value that also fixes the return type. - The
std::transformwith astd::back_inserterwrites into a growing container. - Some of the algorithms need the random access, and you use the member function of the container otherwise.
Try it yourself: take a vector of the parcel records and replace a hand-written loop that finds the heaviest with std::max_element, one that totals the weights with std::accumulate, and one that removes every parcel under a threshold with std::remove_if and erase(). Then sort them with a custom comparator and print the first three.