30 seconds of cpp: #1 - algorithm
This Post describes some features which are introduced by the latest revision of the C++ standard (2011, 2014, 2020). Older compilers may not support it.
Introduction
In this article we are going to look at algorithms library which defines functions for a variety of purposes (e.g. searching, sorting, counting, manipulating) that operate on ranges of elements.
accumulate
Description : This function is used to perform certain operations on the range of iterators provided. It takes two iterators and initial value as parameters.The function is overloaded with first type accepting only these three arguments and returning sum of all elements that can be iterated using the given iterators while the second type takes a binary operation function as additional parameter and performs certain user defined operations on pair of elements pointed by the iterators.
accumulate_example.cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
int GCD(int x, int y){
return std::__gcd(x,y);
}
int main() {
std::vector<int> v{10, 2, 4, 6};
std::cout << "The sum of elements of v is : " <<
std::accumulate(v.begin(), v.end(), 0) <<
" and GCD of all elements is : " <<
std::accumulate(v.begin(), v.end(), 0, GCD) << std::endl;
return 0;
}
all_of
Description : This function operates on whole range of array elements and checks for a given property on every element and returns true when each element in range satisfies specified property, else returns false.
all_of_example.cpp
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> v{10, 2, 4, 6};
if (std::all_of(v.begin(), v.end(), [](int i){ return i % 2 == 0; })) {
std::cout << "All numbers are even\n";
}
else{
std::cout << "All numbers are not even\n";
}
return 0;
}
any_of
Description : This function operates on whole range of array elements and checks for a given property on every element and returns true when atleast one element in range satisfies specified property, else returns false.
accumulate_example.cpp
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> v{1, 3, 5, 7, 2};
if (std::any_of(v.begin(), v.end(), [](int i){ return i % 2 == 0; })) {
std::cout << "A number is even\n";
}
else{
std::cout << "No number is even\n";
}
return 0;
}
binary_search
Description : Binary search is a widely used searching algorithm that requires the array to be sorted before search is applied. The main idea behind this algorithm is to keep dividing the array in half (divide and conquer) until the element is found, or all the elements are exhausted. The prototype for binary search is :
binary_search(startaddress, endaddress, valuetofind)
binary_search_example.cpp
#include <iostream>
#include <algorithm>
void show(int a[], int arraysize) {
for (int i = 0; i < arraysize; ++i) {
std::cout << a[i] << " ";
}
}
int main() {
int a[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 };
int asize = sizeof(a) / sizeof(a[0]);
std::cout << "\n The array is : ";
show(a, asize);
std::cout << "\n\nLet's say we want to search for 2 in the array";
std::cout << "\n So, we first sort the array";
std::sort(a, a + asize);
std::cout << "\n\n The array after sorting is : ";
show(a, asize);
std::cout << "\n\nNow, we do the binary search";
if (std::binary_search(a, a + 10, 2))
std::cout << "\nElement found in the array";
else
std::cout << "\nElement not found in the array";
std::cout << "\n\nNow, say we want to search for 10";
if (std::binary_search(a, a + 10, 10))
std::cout << "\nElement found in the array";
else
std::cout << "\nElement not found in the array";
return 0;
}
clamp
Description : Clamp is a method of restricting a number to fall within a specific range of two numbers, if Value is greater than minValue and less that maxValue it will return a reference to that number.
If the Value is less that minValue it will return minValue, likewise if Value is greater than maxValue it will return maxValue.
Note std::cout and std::endl derive from the iostream library.
Note std::max and std::min derive from the algoithm library.
clamp_example.cpp
#include <iostream>
#include <algorithm>
template<class T>
const T& clamp(const T& value, const T& minValue, const T& maxValue) {
return std::min(maxValue, std::max(value, minValue));
}
int main(void)
{
for (int i = 0; i < 20; i++)
{
std::cout << clamp(i, 0, 10) << std::endl;
}
system("pause");
return 0;
}
copy
Description : Copies the elements in the range, defined by [first, last), to another range beginning at passed argument.
copy_example.cpp
#include <iostream>
#include <vector>
#include <algorithm>
int main(){
std::vector<int> origin {1, 2, 3};
std::vector<int> destination;
// Will copy from origin [begin, end), to destination
std::copy(origin.begin(), origin.end(), std::back_inserter(destination));
// destination is now {1, 2, 3}
for (auto value : destination) {
std::cout << value << " ";
}
return 0;
}
copy_backward
Description : Copies elements from range defined by [first, last), to another range ending at passed iterator. Elements are copied in reverse order (last element is copied first), but the relative order is kept.
copy_backward_example.cpp
#include <iostream>
#include <vector>
#include <algorithm>
int main(){
std::vector<int> origin {1, 2, 3};
// destination size is required to be at least the number of values to be copied
std::vector<int> destination(origin.size());
// Copy origin to destination, starting from the last element
std::copy_backward(origin.begin(), origin.end(), destination.end());
// destination is now {1, 2, 3}
for (auto value : destination) {
std::cout << value << " ";
}
return 0;
}
copy_if
Description : Copies the elements in the range, defined by [first, last), to another range beginning at passed argument, if the value satisfy specific criteria.
copy_if_example.cpp
#include <iostream>
#include <vector>
#include <algorithm>
int main(){
auto isOdd = [](int i) {
return ((i%2) == 1);
};
std::vector<int> origin {1, 2, 3};
std::vector<int> destination;
// Will copy from origin [begin, end), to destination
std::copy_if(origin.begin(), origin.end(), std::back_inserter(destination), isOdd);
// destination is now {1, 3}
for (auto value : destination) {
std::cout << value << " ";
}
return 0;
}
copy_n
Description : Copies n elements starting in the ranged passed, to another range beginning at passed argument.
copy_n_example.cpp
#include <iostream>
#include <vector>
#include <algorithm>
int main(){
std::vector<int> origin {1, 2, 3};
std::vector<int> destination;
// Will copy 2 values starting at origin.begin, to destination
std::copy_n(origin.begin(), 2, std::back_inserter(destination));
// destination is now {1, 2}
for (auto value : destination) {
std::cout << value << " ";
}
return 0;
}
count
Description : Returns the number of elements in the range [first, last) satisfying specific criteria(counts the elements that are equal to value).
count_example.cpp
#include <iostream>
#include <vector>
#include <algorithm>
int main(){
std::vector<int> v{ 1, 2, 3, 4, 4, 3, 7, 8, 9, 10 };
// determine how many integers in a std::vector match a target value.
int target1 = 3;
int num_items1 = std::count(v.begin(), v.end(), target1);
std::cout << "number: " << target1 << " count: " << num_items1 << '\n';
return 0;
}
count_if
Description : Returns the number of elements in the range [first, last) satisfying specific criteria(counts the elements that are equal to value).
count_if_example.cpp
#include <iostream>
#include <vector>
#include <algorithm>
int main(){
std::vector<int> v{ 1, 2, 3, 4, 4, 3, 7, 8, 9, 10 };
// use a lambda expression to count elements divisible by 3.
int num_items3 = std::count_if(v.begin(), v.end(), [](int i){return i % 3 == 0;});
std::cout << "number divisible by three: " << num_items3 << '\n';
return 0;
}
equal
Description : Compares the elements of a vector in a given range to the elements of another vector in the previously defined range.
equal_example.cpp
#include <iostream>
#include <vector>
#include <algorithm>
int main(){
std::vector<int> v1 {3, 5, 3, 1, 2, 3};
std::vector<int> v2 {1, 2 ,3, 4, 5, 6};
std::vector<int> v3 {3, 5, 3, 1, 2, 3};
// Compare two equal vectors
if(std::equal(v1.begin(),v1.end(),v3.begin())){
std::cout << "Vectors are equa!";
}
else {
std::cout << "Vectors are not equal";
}
// Compare two unequal vectors
if(std::equal(v1.begin(),v1.end(),v2.begin())){
std::cout << "Vectors are equa!";
}
else {
std::cout << "Vectors are not equal";
}
return 0;
}
equal_range
Description : Returns the bounds of the subrange that includes all the elements of the range [first, last) with values equivalent to passed value.
equal_range_example.cpp
#include <iostream>
#include <vector>
#include <algorithm>
int main(){
std::vector<int> vec = {1, 2, 3, 1, 6, 1};
// equal_range requires a sorted input {1, 1, 1, 2, 3, 6}
std::sort(vec.begin(), vec.end());
// returns pair of iterators for positions 0 and 2:
// {1, 1, 1, 2, 3, 6}
// ^ ^
auto equalRangeIt = std::equal_range(vec.begin(), vec.end(), 1);
for (auto it = equalRangeIt.first; it != equalRangeIt.second; ++it) {
std::cout << " Position: " << (it - vec.begin()) << " = " << *it << std::endl;
}
return 0;
}
fill
Description : This function assigns the value val to all the elements in the range [begin, end), where begin is the initial position and end is the last position.
fill_example.cpp
#include <iostream>
#include <vector>
#include <algorithm>
int main () {
std::vector<int> myvector (8); // myvector: 0 0 0 0 0 0 0 0
std::fill (myvector.begin(),myvector.begin()+4,5); // myvector: 5 5 5 5 0 0 0 0
std::fill (myvector.begin()+3,myvector.end()-2,8); // myvector: 5 5 5 8 8 8 0 0
for(int i = 0; i<10; i++)
std::cout<< myvector[i]<<" ";
std::cout << '\n';
return 0;
}
fill_n
Description : Sets a number of elements of a range (i.e, vector) to a value. The function takes 3 arguments. The iterator of the range, the number of elements to set starting from the iterator's first element and the new value.
fill_n_example.cpp
#include <iostream>
#include <vector>
#include <algorithm>
void print_vector(const std::vector<int> &v) {
// iterate through v and print its elements
for(auto &elem:v) {
std::cout << elem << " ";
}
std::cout<<std::endl;
}
int main() {
std::vector<int> v = {1,1,1,1,1,1,1,1};
std::cout << "Before fill_n: ";
print_vector(v);
// set the first half of v's elements to zero
std::fill_n(v.begin(), v.size()/2, 0);
std::cout << "After fill_n: ";
print_vector(v);
return 0;
}
find
Description : Returns the first element in the range [first, last) that satisfies specific criteria(searches for an element equal to value).
find_example.cpp
#include <iostream>
#include <vector>
#include <algorithm>
int main () {
std::vector<int> v{ 1, 2, 3, 4, 4, 3, 7, 8, 9, 10 };
int searchme = 4;
if(std::find(std::begin(v), std::end(v), searchme) != std::end(v)){
std::cout <<"\n v contains 4";
}
else
std::cout<<"No match !!";
return 0;
}
find_first_of
Description : Return iterator to the first element in the range [first, last) that is equal to an element from the range [s_first; s_last). If no such element is found, last is returned.(Searches the range [first, last) for any of the elements in the range [s_first, s_last) ).
find_first_of_example.cpp
#include <iostream>
#include <vector>
#include <algorithm>
int main () {
std::vector<int> v{0, 2, 3, 25, 5};
std::vector<int> t{3, 19, 10, 2};
auto result = std::find_first_of(v.begin(), v.end(), t.begin(), t.end());
if (result == v.end()) {
std::cout << "no elements of v were equal to 3, 19, 10 or 2\n";
} else {
std::cout << "found a match at "
<< std::distance(v.begin(), result) << "\n";
}
return 0;
}
find_if
Description : Returns the first element in the range [first, last) that satisfies specific criteria(searches for an element for which predicate/condition p returns true).
find_if_example.cpp
#include <iostream>
#include <vector>
#include <algorithm>
bool IsOdd (int i) {
return ((i%2)==1);
}
int main(){
std::vector<int> v{ 1, 2, 3, 4, 4, 3, 7, 8, 9, 10 };
if(std::find_if(std::begin(v), std::end(v), IsOdd) != std::end(v)){
std::cout <<"\n Odd Value Found";
}
else
std::cout<<"No match !!";
return 0;
}
find_if_not
Description : Returns the first element in the range [first, last) that satisfies specific criteria(searches for an element for which predicate q returns false).
find_if_not_example.cpp
#include <iostream>
#include <vector>
#include <algorithm>
bool IsOdd (int i) {
return ((i%2)==1);
}
int main(){
std::vector<int> v{ 1, 2, 3, 4, 4, 3, 7, 8, 9, 10 };
if(std::find_if_not(std::begin(v), std::end(v), IsOdd) != std::end(v)){
std::cout <<"\n First Even Value";
}
else
std::cout<<"No match !!";
return 0;
}
for_each
Description : Applies the given Function Object f to each element of the container in range [first, last)
for_each_example.cpp
#include <iostream>
#include <vector>
#include <algorithm>
int main () {
std::vector<int> v{ 1, 2, 3, 4 };
std::for_each(v.begin(), v.end(), [](int& i){
i *= 2;
});
std::for_each(v.begin(), v.end(), [](int& i){
std::cout << i << " "; // 2 4 6 8
});
return 0;
}
for_each_n
Description : Applies the given function object f to the result of dereferencing every iterator in the range [first, first + n), in order.
for_each_n_example.cpp
#include <algorithm>
#include <iostream>
#include <vector>
int main()
{
std::vector<int> ns{1, 2, 3, 4, 5};
for (auto n: ns) std::cout << n << ", "; // 1, 2, 3, 4, 5,
std::cout << '\n';
std::for_each_n(ns.begin(), 3, [](auto& n){ n *= 2; });
for (auto n: ns) std::cout << n << ", "; // 2, 4, 6, 4, 5,
std::cout << '\n';
return 0;
}
generate
Description : Used to generate numbers based upon a generator function, and then, it assigns those values to the elements in the container in the range [first, last). The generator function has to be defined by the user, and it is called successively for assigning the numbers.
generate_example.cpp
#include <algorithm>
#include <iostream>
#include <vector>
int f(){
static int i;
return ++i;
}
int main(){
std::vector<int> v(5);
auto print = [&] {
for (std::cout << "v: "; auto iv: v)
std::cout << iv << " ";
std::cout << "\n";
};
std::generate(v.begin(), v.end(), f);
print();
return 0;
}
includes
Description : Test whether sorted range [first1, last1) contains (includes) all elements from another sorted range [first2, last2).
includes_example.cpp
#include <algorithm>
#include <iostream>
#include <vector>
int main()
{
std::vector<int> v1 {8, 2, 0, 4};
std::vector<int> v2 {2, 0};
std::vector<int> v3 {1, 0};
// includes requires sorted ranges
std::sort(v1.begin(), v1.end());
std::sort(v2.begin(), v2.end());
std::sort(v3.begin(), v3.end());
auto v1ContainsV2 = std::includes(v1.begin(), v1.end(), // first range
v2.begin(), v2.end()); // second range
// prints 1/true
std::cout << " v1 contains v2? " << v1ContainsV2 << std::endl;
auto v1ContainsV3 = std::includes(v1.begin(), v1.end(), // first range
v3.begin(), v3.end()); // second range
// prints 0/false
std::cout << " v1 contains v3? " << v1ContainsV3 << std::endl;
return 0;
}
iota
Description : This function operates on a range [first, last) of array elements and assigns the elements with successive values of val, as if incremented with ++val after each element is written. Also, the header file is required to access the function.
iota_example.cpp
#include <algorithm>
#include <iostream>
#include <numeric>
int main()
{
int arr[10];
//Initialising the starting value as 500
int num = 500;
//Applying the function iota to each element
std::iota(arr, arr + 10, num);
// Printing the final output
for(int i = 0; i<10; i++)
std::cout<<arr[i]<<" "; // 500 501 502 503 504 505 506 507 508 509
return 0;
}
is_heap
Description : The C++ function std::is_heap returns true if the elements in the range [first, last) form a max heap, such as is constructed by make_heap, and false otherwise.
is_heap_example.cpp
#include <algorithm>
#include <iostream>
#include <vector>
int main()
{
std::vector<int> v { 8, 6, 7, 5, 3, 0, 9 };
std::cout << "Intial value for v: ";
for (auto i : v) std::cout << i << ' ';
std::cout << '\n';
if (!std::is_heap(v.begin(), v.end())) {
std::cout << "Creating heap:\n";
std::make_heap(v.begin(), v.end());
}
std::cout << "After call to make_heap, v: ";
for (auto i : v) std::cout << i << ' ';
std::cout << '\n';
return 0;
}
Wrapping up
It's not the end, there are bunch of things which I will cover it the future, So consider to follow. And If you learned something new then don't forget to share it ❤️.