C++ STL Algorithms Cheat Sheet
The C++ Standard Template Library provides algorithms for functions that are commonly needed in everyday-scenarios, and for commonly used containerss.
Now, I'm sure you're a gr8 coder and all and could write your own functions, but you should probably use the Standard Library's functions whenever possible. They're very efficient, both memory and space wise, especially if you use STL containers.
The rest of this README is going to contain short explanations of each STL algorithm, as well as very concise sample code showing how to use the algorithms. Star/bookmark this repository and use it as a reference.
You can also watch this youtube video as a guide for how to best use this resource (since it'll also teach you the prerequisites you'll need to learn and also goes over a few examples).
Prerequisites: Pairs, Lambda Expressions, and Iterators
To truly understand how to use the STL algorithms, you should know how STL pairs, lambda expressions, and iterators work.
If you don't know how they work (or even if you do), I strongly recommend that you read this short blog post about how they work, since they're used in the STL algorithms and you won't understand how to use the algorithms without them.
C++ Pairs, Lambda Expressions, and Iterators Tutorial
Base Code and C++ version
For the sake of testing this code, we'll specify a very basic C++ file that our code would run in. Note that we include vector, because that's the container the examples will use, we're including iostream for cout, and we including algorithm for the actual STL algorithms.
main.cpp
#include <iostream>
#include <vector>
#include <algorithm>
int main()
{
// INSERT STD:ALGORITHM EXAMPLE CODE HERE
return 0;
}
We'll use a simple makefile to compile and run, specifying C++11.
makefile
all:
g++ main.cpp -std=c++11 -o run
./run
And so to actually run this code, in a UNIX operating system, in the terminal, simply type make in the directory where your makefile and main.cpp are.
Figure Something Out About Data
Need to do something with the data in your container? Look here.
all_of
Check if every element in the range satisfies the condition.
- Pass in an iterator to the beginning of the range, and an iterator to the end of the range, and a lambda function that does something with the element of the container.
- Returns a bool. True if all elements satisfied the condition, false otherwise.
std::vector<int> v{ 5, 3, 7, 9, 4 };
auto lambda = [](int i) { return i > 1; };
bool allGreaterThanOne = std::all_of(v.begin(), v.end(), lambda); // true
any_of
Check if any element in the range satisfies the condition.
- Pass in an iterator to the beginning of the range, and an iterator to the end of the range, and a lambda function that does something with the element of the container.
- Returns a bool. True if any element satisfied the condition, false otherwise.
std::vector<int> v{ 5, 3, 7, 9, 4 };
auto lambda = [](int i) { return i > 8; };
bool anyGreaterThanEight = std::any_of(v.begin(), v.end(), lambda); // true
none_of
Check if none of the elements in the range satisfies the condition.
- Pass in an iterator to the beginning of the range, and an iterator to the end of the range, and a lambda function that does something with the element of the container.
- Returns a bool. True if all elements fail the condition, false if any element passes the condition.
std::vector<int> v{ 5, 3, 7, 9, 4 };
auto lambda = [](int i) { return i > 10; };
bool noneGreaterThanTen = std::none_of(v.begin(), v.end(), lambda); // true
for_each
Does something for each item in a range.
- Pass in an iterator to the beginning of the range, and an iterator to the end of the range, and a lambda function that does something with the element of the container.
- Returns void.
std::vector<int> v{ 5, 3, 7, 2, 1 };
auto lambda = [](int i) { std::cout << i << " "; };
std::for_each(v.begin(), v.end(), lambda); // Prints each element in the container.
find
Find an item in a given range.
- Pass in an iterator to the beginning of the range, and an iterator to the end of the range, and an item that you want to find.
- Returns an iterator to the first element in the range that is equal to the item we specified.
std::vector<int> v{ 5, 3, 7, 9, 4 };
std::vector<int>::iterator it = std::find(v.begin(), v.end(), 3);
find_if
Find the first item that satisfies a condition.
- Pass in an iterator to the beginning of the range, and an iterator to the end of the range, and a lambda function that returns a bool.
- Returns an iterator to the first element in the range that satisfies the lambda's condition.
std::vector<int> v{ 5, 3, 7, 9, 4 };
auto lambda = [](int i) { return i > 6; };
std::vector<int>::iterator it = std::find_if(v.begin(), v.end(), lambda);
int firstElementGreaterThanSix = *it; // 7
find_if_not
Find the first item that does not satisfy a condition.
- Pass in an iterator to the beginning of the range, and an iterator to the end of the range, and a lambda function that returns a bool.
- Returns an iterator to the first element in the range that does not satisfy the lambda's condition.
std::vector<int> v{ 5, 3, 7, 9, 4 };
auto lambda = [](int i) { return i > 6; };
std::vector<int>::iterator it = std::find_if_not(v.begin(), v.end(), lambda);
int firstElementLessThanSix = *it; // 5
find_end
For a range, find the last occurence of a sequence in that range. (Ex. Get the last "oo" in "moo_cookies".)
- Pass in an iterator to the beginning of the first range, and an iterator to the end of the first range, and an iterator to the beginning of the sequence, and an iterator to the end of the sequence,
- Returns an iterator to the first item of the sequence.
std::string s = "moo_cookies";
std::string t = "oo";
std::string::iterator it = std::find_end(s.begin(), s.end(), t.begin(), t.end());
// Points to the 'o' after the 'c'
find_first_of
For a range, find the first occurence of a sequence in that range. (Ex. Get the first "oo" in "moo_cookies".)
- Pass in an iterator to the beginning of the first range, and an iterator to the end of the first range, and an iterator to the beginning of the sequence, and an iterator to the end of the sequence,
- Returns an iterator to the first item of the sequence.
std::string s = "moo_cookies";
std::string t = "oo";
std::string::iterator it = std::find_first_of(s.begin(), s.end(), t.begin(), t.end());
// Points to the 'o' after the 'm
adjacent_find
Find the first occurrence of two consecutive elements that match in a range. (Ex. The "cc" in "accentt".)
- Pass in an iterator to the beginning of the range, and an iterator to the end of the range.
- Returns an iterator to the first item in the match.
std::string s = "accentt";
std::string::iterator it = std::adjacent_find(s.begin(), s.end()); // Points to the first 'c'
count
Count the number of times an item appears in the range.
- Pass in an iterator to the beginning of the range, and an iterator to the end of the range, and the item we want to count.
- Returns an integer.
std::vector<int> v{ 5, 3, 7, 9, 3, 4 };
int countOfThree = std::count(v.begin(), v.end(), 3); // 2
count_if
Count the number of occurrences satisfying the lambda function.
- Pass in an iterator to the beginning of the range, and an iterator to the end of the range, and a lambda function that returns true or false.
- Returns an integer.
std::vector<int> v{ 5, 3, 7, 2, 1 };
auto lambda = [](int i) { return i > 2; };
int count = count_if(v.begin(), v.end(), lambda);
mismatch
Finds the first occurrence where two rangers differ.
- Pass in an iterator to the beginning of the range, and an iterator to the end of the range, and an iterator to the beginning of the second range.
- Returns a
pair of iterators to the positions where the ranges occur.
std::vector<int> v1{ 5, 3, 7, 9 };
std::vector<int> v2{ 5, 3, 2, 9 };
std::pair<std::vector<int>::iterator, std::vector<int>::iterator> p = std::mismatch(v1.begin(), v1.end(), v2.begin());
int element1 = *p.first; // 7
int element2 = *p.second; // 2
equal
Check if the elements in two ranges are equal.
- Pass in an iterator to the beginning of the range, and an iterator to the end of the range, and an iterator to the beginning of the second range.
- Returns a bool. True if the elements are equal, false otherwise.
std::vector<int> v1{ 5, 4, 6 };
std::vector<int> v2{ 5, 4, 6 };
bool isEqual = std::equal(v1.begin(), v1.end(), v2.begin()); // true
is_permutation
Check if a range is a permutation of another.
A "permutation" is if the items in one range can be rearranged to form the other range. (Ex. "dog" can be rearranged to form "god".)
- Pass in an iterator to the beginning of the range, and an iterator to the end of the range, and an iterator to the beginning of the second range.
- Returns a bool. True if the elements are permutations, false otherwise.
std::vector<char> v1{ 'g', 'o', 'd' };
std::vector<char> v2{ 'd', 'o', 'g' };
bool isPermutation = std::is_permutation(v1.begin(), v1.end(), v2.begin()); // true
search
Check if a range contains a certain sequence. (Ex. Does "this" contain "is"?)
- Pass in an iterator to the beginning of the first range, and an iterator to the end of the first range, and an iterator to the beginning of the second range (sequence), and an iterator to the end of the second range (sequence).
- Returns an iterator to the first item in the range that begins the sequence.
std::vector<char> v1{ 't', 'h', 'i', 's' };
std::vector<char> v2{ 'i', 's' };
std::vector<char>::iterator it = std::search(v1.begin(), v1.end(), v2.begin(), v2.end());
// Points to the 'i' in v1
search_n
Search a range for a certain number of a specific item. (Ex. Find two 'e's in a row in the word 'esteem'.)
- Pass in an iterator to the beginning of the range, and an iterator to the end of the range, and the count of the number of the item we need to find, and the item we're trying to find.
- Returns an iterator to the first item in the range that begins the sequence.
std::vector<char> v{ 'e', 's', 't', 'e', 'e', 'm' };
std::vector<char>::iterator it = std::search_n(v.begin(), v.end(), 2, 'e');
// Points to the 'e' after the 't'.
lexicographical_compare
Lexographically compare two items to find out which is 'smaller'.
- Pass in an iterator to the beginning of the first range, and an iterator to the end of the first range, an iterator to the beginning of the second range, and an iterator to the end of the second range.
- Returns a bool. True if the first range is lexographically less than the second range.
std::string s = "abc";
std::string t = "def";
bool sIsSmaller = std::lexicographical_compare(s.begin(), s.end(), t.begin(), t.end()); // true
Modify/Copy A Range
A range is going to be edited or copied.
copy
Copy the elements from one range into another.
- Pass in an iterator to the beginning of the first range, an iterator to the end of the first range, and an iterator to the beginning of the copy range.
- Retur