The Algorithm Library
Queries
Modifiers
Manipulators
There are many operations commonly used in different problems involving containers or arrays
For example:
→ Sorting
→ Applying a transformation
→ Finding elements that match a specific criteria
The algorithm library implements methods to efficiently solve these problems
"By default, ... prefer algorithms to loops"
Bjarne Stroustrup, creator of C++
These methods can be orders of magnitude faster than using simple loops
#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
#include <random>
void bubble_sort(std::vector<int>& arr) {
size_t n = arr.size();
for (size_t i = 0; i < n - 1; ++i) {
for (size_t j = 0; j < n - 1 - i; ++j) {
if (arr[j] > arr[j + 1]) {
std::swap(arr[j], arr[j + 1]);
}
}
}
}
int main() {
const size_t SIZE = 10000;
std::vector<int> numbers(SIZE);
std::srand(31234); //seed for random number generator
std::generate(numbers.begin(), numbers.end(), []() {
return std::rand() % 10000; }
);
std::vector<int> numbers_copy = numbers;
auto start1 = std::chrono::high_resolution_clock::now();
bubble_sort(numbers);
auto end1 = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> duration1 = end1 - start1;
auto start2 = std::chrono::high_resolution_clock::now();
std::sort(numbers_copy.begin(), numbers_copy.end());
auto end2 = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> duration2 = end2 - start2;
std::cout << "Bubble sort: " << duration1.count()
<< " seconds" << std::endl;
std::cout << "std::sort: " << duration2.count()
<< " seconds" << std::endl;
return 0;
}
The C++ algorithms library covers different areas:
→ Performing queries
→ Applying modifiers
→ Manipulating containers
Queries do not modify the containers that they are applied to
Examples of queries:
for_each performs an action for each element
find and find_if return an iterator to the first element that satisfies a condition
count and count_if count the number of elements that satisfy a condition
It is important to ensure the use of proper arguments for each method
Many methods expect iterators to indicate the start and the end of the range
Some methods return iterators
Some methods expect pointers to functions or lambda expressions as arguments
#include <iostream>
#include <vector>
#include <algorithm>
void print(int n) {
std::cout << n << " ";
}
void inc(int& n) {
n += 1;
}
int main() {
std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7};
std::cout << "Original vector: ";
std::for_each(numbers.begin(), numbers.end(), print);
std::cout << std::endl;
std::for_each(numbers.begin(), numbers.end(), inc);
std::cout << "Modified vector: ";
std::for_each(numbers.begin(), numbers.end(), print);
std::cout << std::endl;
return 0;
}
#include <iostream>
#include <vector>
#include <algorithm>
bool isEven(int n) {
return n % 2 == 0;
}
int main() {
std::vector<int> numbers = {1, 3, 5, 7, 8, 10, 11};
//note that find returns an iterator
auto it = std::find(numbers.begin(), numbers.end(), 11);
if (it != numbers.end()) {
std::cout << "I found a 5! " << std::endl;
} else {
std::cout << "I could not find a 5." << std::endl;
}
//note that find_if returns an iterator
it = std::find_if(numbers.begin(),
numbers.end(), isEven);
if (it != numbers.end()) {
std::cout << "The first even number is: "
<< *it << std::endl;
} else {
std::cout << "There are no even numbers."
<< std::endl;
}
return 0;
}
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> numbers = {1, 3, 5, 7, 8, 10, 12, 5};
int num = std::count(numbers.begin(), numbers.end(), 5);
std::cout << "I found " << num << " 5s! " << std::endl;
//note the use of a lambda expression
num = std::count_if(numbers.begin(),
numbers.end(), [](int n){
return n % 2 == 0;
});
std::cout << "I found " << num
<< " even numbers." << std::endl;
return 0;
}
Modifiers produce a "modified" version of the containers that they are applied to
Note that the original container is not altered
Examples of modifiers:
copy and copy_if copies all elements of the original container that satisfy a condition
transform applies a transformation to each element of the original container
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
void print(int n) {
std::cout << n << " ";
}
int main() {
std::vector<int> source = {1, 2, 3, 4, 5, 6, 7, 8};
//preallocated
//std::vector<int> copied(source.size());
//not preallocated
std::vector<int> copied;
//std::copy(source.begin(), source.end(), copied.begin());
//if copied is not preallocated
std::copy(source.begin(), source.end(),
std::back_inserter(copied));
//print copied
std::cout << "Copied elements (std::copy): ";
std::for_each(copied.begin(), copied.end(), print);
std::cout << std::endl;
std::vector<int> even_numbers(source.size());
//copy_if returns an iterator to the end of destination
auto it = std::copy_if(source.begin(), source.end(),
even_numbers.begin(), [](int n) {
return n % 2 == 0;
});
//eliminate extra elements of destination
even_numbers.resize(
std::distance(even_numbers.begin(), it));
//print even_numbers
std::cout << "Even elements (std::copy_if): ";
std::for_each(even_numbers.begin(),
even_numbers.end(), print);
std::cout << std::endl;
return 0;
}
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <cmath>
void print(double n) {
std::cout << n << " ";
}
int main() {
std::vector<double> numbers = {1.0, 2.0, 3.0, 4.0, 5.0};
std::vector<double> squares(numbers.size());
std::vector<double> sqrts(numbers.size());
std::transform(numbers.begin(), numbers.end(),
squares.begin(), [](int n) {
return n * n;
});
std::transform(numbers.begin(), numbers.end(),
sqrts.begin(), [](double n) {
return std::sqrt(n);
});
//print squares
std::cout << "Squares: ";
std::for_each(squares.begin(), squares.end(), print);
std::cout << std::endl;
std::cout << "Square roots: ";
std::for_each(sqrts.begin(), sqrts.end(), print);
std::cout << std::endl;
return 0;
}
Manipulators modify the container in which they are applied
Examples of manipulators:
remove Removes all elements of the container that match a condition
shuffle randomly shuffles the elelemtns of the container
sort Sorts all ellements in the container in ascending order*
#include <iostream>
#include <vector>
#include <algorithm>
void print(int n) {
std::cout << n << " ";
}
int main() {
std::vector<int> numbers = {1, 2, 3, 4, 2, 5, 2, 6};
auto it = std::remove(numbers.begin(),
numbers.end(), 2);
numbers.resize(std::distance(numbers.begin(), it));
std::cout << "After removal, numbers contains:";
std::for_each(numbers.begin(), numbers.end(), print);
std::cout << std::endl;
return 0;
}
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
void print(int n) {
std::cout << n << " ";
}
int main() {
std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8};
//obtain a seed and random engine
std::random_device rd;
std::default_random_engine rng(rd());
std::shuffle(numbers.begin(), numbers.end(), rng);
std::cout << "Shuffled numbers:";
std::for_each(numbers.begin(), numbers.end(), print);
std::cout << std::endl;
return 0;
}
#include <iostream>
#include <vector>
#include <algorithm>
void print(int n) {
std::cout << n << " ";
}
int main() {
std::vector<int> numbers = {5, 2, 9, 1, 5, 6};
std::sort(numbers.begin(), numbers.end());
std::cout << "Sorted numbers in ascending order:";
std::for_each(numbers.begin(), numbers.end(), print);
std::cout << std::endl;
//the lambda expression makes the sort descending
std::sort(numbers.begin(), numbers.end(),
[](int a, int b) {
return a > b;
});
std::cout << "Sorted numbers in descending order:";
std::for_each(numbers.begin(), numbers.end(), print);
std::cout << std::endl;
return 0;
}