C++ - , Functions

Introduction

In this article, we will explore two important STL libraries, <algorithm>, <numeric>.

In <algorithm>, we have:

• Partitioning algorithms:
  • Placing the nth element at the nth position using nth_element(first, nth, last, comp)
  • Moving all elements that satisfies pred=true to the left of it, and leaving the rest to its left, using it = std::partition(first, last, pred)
• Finding the minimum and maximum using it = std::minmax_element(begin_itr, end_itr, lambda), it = std::min_element, or std::min(value1, value2)
• Transforms
  • Perform an unary operation on an input sequence, then save the result in an output sequencestd::transform(input_beg, input_end, output_beg, unary_op).
  • Perform an accumulative operation on a sequence, and get a single value out
    • C++ 11, if the operation is sequential: std::accumulate(beg, end, begin_val, lambda_retuning_val).
    • C++ 17, we can parallelize if the operation is not associative (i.e., order of evaluation doesn’t matter, a+b=b+a)std::reduce(beg, end, begin_val, lambda_retuning_val)

In <numeric>, we have:

• Datatype std::NaN

<algorithm>

Nth Element

nth_element(first, nth, last, comp) makes sure:

1. At nth place of the container, the element is actually the nth as if the container were sorted.
2. Elements before the nth element has comp(i, n) = False, or without comp, they are smaller than the nth element

1
2
3
4
5
6
7
// elements before the returned iterator has a value less than or equal to the value
std::nth_element(keypoints.begin(),keypoints.begin() + desired_features_num - 1, keypoints.end(),
    [](const KeyPoint& k1, const KeyPoint& k2){
        //descending 
        return k1.response > k2.response;
    }
);

Partition

std::partition(first, last, pred) moves all elements that makes pred(item) true to first iterator, and returns an iterator that points to the first item that makes pred(item) false. In combination wtih std::nth_element, we can partition and find the iterator that makes sure all elements smaller than or equal to the nth elements are before a returned iterator, new_end.

1
2
3
// we might still have elements equal to the nth element. So, we use partition to find them
// std::partion moves items that satisfies the pred to before the iterator
auto new_end = std::partition(keypoints.begin() + desired_features_num, keypoints.end(), [&keypoints](const KeyPoint& k){k.response == (keypoints.begin() + desired_features_num - 1)->response});

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(begin_itr, end_itr, lambda): returns the min element based on the defintion of “smaller”

std::min(v1, v2)

std::transform(input_beg, input_end, output_beg, unary_op)

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::accumulate(beg, end, begin_val, lambda_retuning_val)

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::reduce(beg, end, begin_val, lambda_retuning_val) (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::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.

• Previous
  C++ - Sizing and Type Conversion
• Next
  C++ - Numeric