# # Standard Library Algorithms

## # std::next_permutation

``````template< class Iterator >
bool next_permutation( Iterator first, Iterator last );
template< class Iterator, class Compare >
bool next_permutation( Iterator first, Iterator last, Compare cmpFun );

``````

Effects:
Sift the data sequence of the range [first, last) into the next lexicographically higher permutation. If `cmpFun` is provided, the permutation rule is customized.

Parameters:
`first`- the beginning of the range to be permutated, inclusive
`last` - the end of the range to be permutated, exclusive

Return Value:
Returns true if such permutation exists.
Otherwise the range is swaped to the lexicographically smallest permutation and return false.

Complexity:
O(n), n is the distance from `first` to `last`.

Example:

``````std::vector< int > v { 1, 2, 3 };
do
{
for( int i = 0; i < v.size(); i += 1 )
{
std::cout << v[i];
}
std::cout << std::endl;
}while( std::next_permutation( v.begin(), v.end() ) );

``````

print all the permutation cases of 1,2,3 in lexicographically-increasing order.
output:

``````123
132
213
231
312
321

``````

## # std::for_each

``````template<class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator last, Function f);

``````

Effects:

Applies `f` to the result of dereferencing every iterator in the range `[first, last)` starting from `first` and proceeding to `last - 1`.

Parameters:

`first, last` - the range to apply `f` to.

`f` - callable object which is applied to the result of dereferencing every iterator in the range `[first, last)`.

Return value:

`f` (until C++11) and `std::move(f)` (since C++11).

Complexity:

Applies `f` exactly `last - first` times.

Example:

``````std::vector<int> v { 1, 2, 4, 8, 16 };
std::for_each(v.begin(), v.end(), [](int elem) { std::cout << elem << " "; });

``````

Applies the given function for every element of the vector `v` printing this element to `stdout`.

## # std::accumulate

Defined in header `<numeric>`

``````template<class InputIterator, class T>
T accumulate(InputIterator first, InputIterator last, T init); // (1)

template<class InputIterator, class T, class BinaryOperation>
T accumulate(InputIterator first, InputIterator last, T init, BinaryOperation f); // (2)

``````

Effects:

std::accumulate performs fold operation using `f` function on range `[first, last)` starting with `init` as accumulator value.

Effectively it's equivalent of:

``````T acc = init;
for (auto it = first; first != last; ++it)
acc = f(acc, *it);
return acc;

``````

In version (1) `operator+` is used in place of `f`, so accumulate over container is equivalent of sum of container elements.

Parameters:

`first, last` - the range to apply `f` to.
`init` - initial value of accumulator.
`f` - binary folding function.

Return value:

Accumulated value of `f` applications.

Complexity:

O(n×k), where n is the distance from `first` to `last`, O(k) is complexity of `f` function.

Example:

Simple sum example:

``````std::vector<int> v { 2, 3, 4 };
auto sum = std::accumulate(v.begin(), v.end(), 1);
std::cout << sum << std::endl;

``````

Output:

``````10

``````

Convert digits to number:

``````class Converter {
public:
int operator()(int a, int d) const { return a * 10 + d; }
};

``````

and later

``````const int ds = {1, 2, 3};
int n = std::accumulate(ds, ds + 3, 0, Converter());
std::cout << n << std::endl;

``````
``````const std::vector<int> ds = {1, 2, 3};
int n = std::accumulate(ds.begin(), ds.end(),
0,
[](int a, int d) { return a * 10 + d; });
std::cout << n << std::endl;

``````

Output:

``````123

``````

## # std::find

``````template <class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& val);

``````

Effects

Finds the first occurrence of val within the range [first, last)

Parameters

`first` => iterator pointing to the beginning of the range `last` => iterator pointing to the end of the range `val` => The value to find within the range

Return

An iterator that points to the first element within the range that is equal(==) to val, the iterator points to last if val is not found.

Example

``````#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int main(int argc, const char * argv[]) {

//create a vector
vector<int> intVec {4, 6, 8, 9, 10, 30, 55,100, 45, 2, 4, 7, 9, 43, 48};

//define iterators
vector<int>::iterator  itr_9;
vector<int>::iterator  itr_43;
vector<int>::iterator  itr_50;

//calling find
itr_9 = find(intVec.begin(), intVec.end(), 9); //occurs twice
itr_43 = find(intVec.begin(), intVec.end(), 43); //occurs once

//a value not in the vector
itr_50 = find(intVec.begin(), intVec.end(), 50); //does not occur

cout << "first occurence of: " << *itr_9 << endl;
cout << "only occurence of: " << *itr_43 << Lendl;

/*
let's prove that itr_9 is pointing to the first occurence
of 9 by looking at the element after 9, which should be 10
not 43
*/
cout << "element after first 9: " << *(itr_9 + 1) << ends;

/*
to avoid dereferencing intVec.end(), lets look at the
element right before the end
*/
cout << "last element: " << *(itr_50 - 1) << endl;

return 0;
}

``````

Output

``````first occurence of: 9
only occurence of: 43
element after first 9: 10
last element: 48

``````

## # std::count

``````template <class InputIterator, class T>
typename iterator_traits<InputIterator>::difference_type
count (InputIterator first, InputIterator last, const T& val);

``````

Effects

Counts the number of elements that are equal to val

Parameters

`first` => iterator pointing to the beginning of the range
`last` => iterator pointing to the end of the range
`val` => The occurrence of this value in the range will be counted

Return

The number of elements in the range that are equal(==) to val.

Example

``````#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int main(int argc, const char * argv[]) {

//create vector
vector<int> intVec{4,6,8,9,10,30,55,100,45,2,4,7,9,43,48};

//count occurences of 9, 55, and 101
size_t count_9 = count(intVec.begin(), intVec.end(), 9); //occurs twice
size_t count_55 = count(intVec.begin(), intVec.end(), 55); //occurs once
size_t count_101 = count(intVec.begin(), intVec.end(), 101); //occurs once

//print result
cout << "There are " << count_9  << " 9s"<< endl;
cout << "There is " << count_55  << " 55"<< endl;
cout << "There is " << count_101  << " 101"<< ends;

//find the first element == 4 in the vector
vector<int>::iterator itr_4 = find(intVec.begin(), intVec.end(), 4);

//count its occurences in the vector starting from the first one
size_t count_4 = count(itr_4, intVec.end(), *itr_4); // should be 2

cout << "There are " << count_4  << " " << *itr_4 << endl;

return 0;
}

``````

Output

``````There are 2 9s
There is 1 55
There is 0 101
There are 2 4

``````

## # std::count_if

``````template <class InputIterator, class UnaryPredicate>
typename iterator_traits<InputIterator>::difference_type
count_if (InputIterator first, InputIterator last, UnaryPredicate red);

``````

Effects

Counts the number of elements in a range for which a specified predicate function is true

Parameters

`first` => iterator pointing to the beginning of the range `last` => iterator pointing to the end of the range `red` => predicate function(returns true or false)

Return

The number of elements within the specified range for which the predicate function returned true.

Example

``````#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/*
Define a few functions to use as predicates
*/

//return true if number is odd
bool isOdd(int i){
return i%2 == 1;
}

//functor that returns true if number is greater than the value of the constructor parameter provided
class Greater {
int _than;
public:
Greater(int th): _than(th){}
bool operator()(int i){
return i > _than;
}
};

int main(int argc, const char * argv[]) {

//create a vector
vector<int> myvec = {1,5,8,0,7,6,4,5,2,1,5,0,6,9,7};

//using a lambda function to count even numbers
size_t evenCount = count_if(myvec.begin(), myvec.end(), [](int i){return i % 2 == 0;}); // >= C++11

//using function pointer to count odd number in the first half of the vector
size_t oddCount = count_if(myvec.begin(), myvec.end()- myvec.size()/2, isOdd);

//using a functor to count numbers greater than 5
size_t greaterCount = count_if(myvec.begin(), myvec.end(), Greater(5));

cout << "vector size: " << myvec.size() << endl;
cout << "even numbers: " << evenCount << " found" << endl;
cout << "odd numbers: " << oddCount << " found" << endl;
cout << "numbers > 5: " << greaterCount << " found"<< endl;

return 0;
}

``````

Output

``````vector size: 15
even numbers: 7 found
odd numbers: 4 found
numbers > 5: 6 found

``````

## # std::find_if

``````template <class InputIterator, class UnaryPredicate>
InputIterator find_if (InputIterator first, InputIterator last, UnaryPredicate pred);

``````

Effects

Finds the first element in a range for which the predicate function `pred` returns true.

Parameters

`first` => iterator pointing to the beginning of the range `last` => iterator pointing to the end of the range `pred` => predicate function(returns true or false)

Return

An iterator that points to the first element within the range the predicate function pred returns true for. The iterator points to last if val is not found

Example

``````#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/*
define some functions to use as predicates
*/

//Returns true if x is multiple of 10
bool multOf10(int x) {
return x % 10 == 0;
}

//returns true if item greater than passed in parameter
class Greater {
int _than;

public:
Greater(int th):_than(th){

}
bool operator()(int data) const
{
return data > _than;
}
};

int main()
{

vector<int> myvec {2, 5, 6, 10, 56, 7, 48, 89, 850, 7, 456};

//with a lambda function
vector<int>::iterator gt10 = find_if(myvec.begin(), myvec.end(), [](int x){return x>10;}); // >= C++11

//with a function pointer
vector<int>::iterator pow10 = find_if(myvec.begin(), myvec.end(), multOf10);

//with functor
vector<int>::iterator gt5 = find_if(myvec.begin(), myvec.end(), Greater(5));

vector<int>::iterator nf = find_if(myvec.begin(), myvec.end(), Greater(1000)); // nf points to myvec.end()

//check if pointer points to myvec.end()
if(nf != myvec.end()) {
cout << "nf points to: " << *nf << endl;
}
else {
}

cout << "First item >   10: " << *gt10  << endl;
cout << "First Item n * 10: " << *pow10 << endl;
cout << "First Item >    5: " << *gt5   << endl;

return 0;
}

``````

Output

``````item not found
First item >   10: 56
First Item n * 10: 10
First Item >    5: 6

``````

## # std::min_element

``````template <class ForwardIterator>
ForwardIterator min_element (ForwardIterator first, ForwardIterator last);

template <class ForwardIterator, class Compare>
ForwardIterator min_element (ForwardIterator first, ForwardIterator last,Compare comp);

``````

Effects

Finds the minimum element in a range

Parameters

`first` - iterator pointing to the beginning of the range
`last` - iterator pointing to the end of the range `comp` - a function pointer or function object that takes two arguments and returns true or false indicating whether argument is less than argument 2. This function should not modify inputs

Return

Iterator to the minimum element in the range

Complexity

Linear in one less than the number of elements compared.

Example

``````#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>  //to use make_pair

using namespace std;

//function compare two pairs
bool pairLessThanFunction(const pair<string, int> &p1, const pair<string, int> &p2)
{
return p1.second < p2.second;
}

int main(int argc, const char * argv[]) {

vector<int> intVec {30,200,167,56,75,94,10,73,52,6,39,43};

vector<pair<string, int>> pairVector = {make_pair("y", 25), make_pair("b", 2), make_pair("z", 26), make_pair("e", 5) };

// default using < operator
auto minInt = min_element(intVec.begin(), intVec.end());

//Using pairLessThanFunction
auto minPairFunction = min_element(pairVector.begin(), pairVector.end(), pairLessThanFunction);

//print minimum of intVector
cout << "min int from default: " << *minInt << endl;

//print minimum of pairVector
cout << "min pair from PairLessThanFunction: " << (*minPairFunction).second << endl;

return 0;
}

``````

Output

``````min int from default: 6
min pair from PairLessThanFunction: 2

``````

## # Using std::nth_element To Find The Median (Or Other Quantiles)

The `std::nth_element` algorithm takes three iterators: an iterator to the beginning, nth position, and end. Once the function returns, the nth element (by order) will be the nth smallest element. (The function has more elaborate overloads, e.g., some taking comparison functors; see the above link for all the variations.)

Note This function is very efficient - it has linear complexity.

For the sake of this example, let's define the median of a sequence of length n as the element that would be in position ⌈n / 2⌉. For example, the median of a sequence of length 5 is the 3rd smallest element, and so is the median of a sequence of length 6.

To use this function to find the median, we can use the following. Say we start with

``````std::vector<int> v{5, 1, 2, 3, 4};

std::vector<int>::iterator b = v.begin();
std::vector<int>::iterator e = v.end();

std::vector<int>::iterator med = b;

// This makes the 2nd position hold the median.
std::nth_element(b, med, e);

// The median is now at v.

``````

To find the pth quantile, we would change some of the lines above:

``````const std::size_t pos = p * std::distance(b, e);

and look for the quantile at position `pos`.