C++

C++ - Algorithm Functions

minmax_element, min_element, reduce, transform, numeric

Posted by Rico's Nerd Cluster on January 20, 2023

std::minmax_element(begin_itr, end_itr, lambda)

This function finds the [min, max] of a container based on the definition of “smaller”.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};

    auto minmax = std::minmax_element(vec.begin(), vec.end(), [](const int& i1, const int& i2){
        return i1 < i2;
        // return i1>i2; // the first element (min) is the one that satisfies this condition throughout the container
    });

    // See Min element: 1
    std::cout << "Min element: " << *minmax.first << std::endl;
    std::cout << "Max element: " << *minmax.second << std::endl;

    return 0;
}

std::min_element: returns the min element based on the defintion of “smaller”

std::min(v1, v2)

std::transform

std::transform is a funtion that allows us to apply a function (usually lambda) on one or two (zipped) containers, and puts the output into an output container.

  1. unary operations
1
2
3
4
5
6
7
// Definition
transform(Iterator inputBegin, Iterator inputEnd, 
        Iterator OutputBegin, unary_operation) 
// example: increment a number in an array
int arr[] = {1,2,3,4}; 
n = sizeof(arr)/sizeof(int); 
std::transform(arr, arr+n, arr, [](int x){return x+1;})
  1. binary operation
1
2
3
4
5
6
7
8
// Definition
transform(Iterator inputBegin1, Iterator inputEnd1, Iterator inputBegin2, 
        Iterator outputBegin, binary_operation)
// Example: arr_1 - arr 2 
int arr_1[] = {1,2,3,4}; 
int arr_2[] = {1,2,3,4}; 
int result[5]; 
std::transform(arr_1, arr_1+4, arr_2, result, [](int i1, i2){return i1 - i2; }); 
  • std::transform(It1 it1_begin, It1, it1_end, It2 it2_end, It3 out_begin, [](const Type1& a, const Type2&b){return something})

std::reduce (C++17)

std::reduce is an algorithm introduced in C++17 (and enhanced in C++20) that aggregates a range of elements using a binary operation and an initial value.

Unlike std::accumulate, std::reduce has no guaranteed order of evaluation, which allows it to be parallelized for improved performance. However, because it processes elements in an unspecified order, the binary operation should be both associative and commutative to guarantee correct results.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <optional>
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

void test_reduce(){
    std::vector<int> vec {1,2,3,4,5};
    // order of execution is unspecified
    double sum = std::reduce(
        std::execution::par_unseq,
        vec.begin(), vec.end(), 0.0, [](int a, double sum){return 0.25*a + sum;});
    cout<<"using reduce to find sum: "<<sum<<endl;
}

int main(){
    // test_optional();
    test_reduce();

}
  • std::execution::par_unseq parallelizes the above.
  • Pay attention to the initial value 0.0, otherwise, it will be an int and will be rounded.

std::accumulate

  1. simple summing
1
2
#include <numeric>
sum = std::accumulate(vec.begin(), vec.end(), 0.0); 
  • Note: in the below example, sum will be casted to int, even if std::vector<double> vec:
1
sum = std::accumulate(vec.begin(), vec.end(), 0); 
  1. Other accumulative tasks:
1
2
3
4
5
T accumulate(Iterator first, Iterator Last, T init, Binary_Operation op){
    for(; first != last; ++first){
    init = op(std::move(init), *first); 
    }
}
  • E.g,
1
std::accumulate(vec.begin(), vec.end(), 1, [](int product, int b){return product*b}); 

std::numeric

NaN: (C++11)

  • std::numeric_limits<float>::quiet_NaN(): propagates through arithmetic operations without triggering floating-point exceptions.
1
2
3
4
5
6
7
8
9
10
11
12
    float nan_value = std::numeric_limits<float>::quiet_NaN();

    std::cout << "NaN value: " << nan_value << std::endl;

    // Checking if a value is NaN
    if (std::isnan(nan_value)) {
        std::cout << "The value is NaN." << std::endl;
    }
    // Propagation example
    float result = nan_value + 5.0f;  // Still NaN
    std::cout << "Result of NaN + 5: " << result << std::endl;

  • std::numeric_limits<T>::signaling_NaN: signaling NaN (SNaN) raises an exception when used in computations.