CODEWITHSUNDEEP
c++c++11stlfunctional-programming
nnrales
nnrales

Reputation: 1519

How to replicate map, filter and reduce behaviors in C++ using STL?

I suppose we can use std::transform to replicate the map behavior in C++ like this :

std::vector<int> in = { 1 , 2 , 3 ,4 }; 
std::vector<int> out(in.size()); 

std::transform(in.begin() , in.end() , out.begin() , [](const int & val)
{
    return val+1;
});

I guess a better way would be to use the back inserter.'

std::vector<int> out2;

std::transform(in.begin() , in.end() , std::back_inserter(out2) , [](const int & val){
      return val + 1;
});

// out will be { 2 , 3 ,4 ,5 }

Am I right ? How do I do the filter and reduce operations in C++ using STL ?

Upvotes: 40

Views: 33304

Answers (3)

happy_sisyphus
happy_sisyphus

Reputation: 1835

You can use std::transform to do mapping, and std::copy_if for filtering.

You have two options for reduce depending on your input and if you want to use a specific type of execution model. I've written some simple examples below to demonstrate common use cases. Note that there are multiple overloads for all these algorithms that you should use depending on your needs.

  1. std::transform

Squaring a vector of integers in place:

std::vector<int> nums{1,2,3,4};
auto unary_op = [](int num) {return std::pow(num, 2);};
std::transform(nums.begin(), nums.end(), nums.begin(), unary_op);
// nums: 1, 4, 9, 16
  1. std::copy_if

Filtering odd numbers only from a vector of integers:

std::vector<int> nums{1,2,3,4};
std::vector<int> odd_nums;
auto pred = [](int num) {return num & 1;};
std::copy_if(nums.begin(), nums.end(), std::back_inserter(odd_nums), pred);
// odd_nums: 1, 3
  1. std::reduce

Sum of integers in the vector starting from 0 using parallel execution model. This is really useful if, for example, you are doing a reduce operation on a really big list. Reckon that the binary operator in this case ("+") is associate and commutative, otherwise the behavior would've been non-deterministic. This is really important. The reduce operation is out-of-order if the execution model is not sequential. Only available since C++17.

std::vector<int> nums{1,2,3,4};
auto binary_op = [](int num1, int num2){return num1 + num2;};
int result = std::reduce(
  std::execution::par, 
  nums.begin(), nums.end(), 
  0, binary_op
);
// result: 10
  1. std::accumulate

Same as reduce except it doesn't support execution model and the reduce operation is done in-order.

std::vector<int> nums{1,2,3,4};
auto binary_op = [](int num1, int num2){return num1 + num2;};
int result = std::accumulate(nums.begin(), nums.end(), 0, binary_op);
// result: 10

Upvotes: 61

Frank Kusters
Frank Kusters

Reputation: 2634

I generalized the transform example from happy_sisyphus's answer into a function:

#include <algorithm>

// avoid calling this function 'map', it will clash with 'using std::map;'
template<typename I, typename F>
void apply_to_all(I& iterable, const F& functor)
{
    std::transform(iterable.begin(), iterable.end(), iterable.begin(), functor);
}

Example use:

std::vector<int> nums{1,2,3,4};
auto unary_op = [](int num) {return std::pow(num, 2);};

apply_to_all(nums, unary_op);
// nums: 1, 4, 9, 16

Upvotes: 1

Daksh Gupta
Daksh Gupta

Reputation: 7804

Depends which container you use.

std::back_inserter will work only if the container has a push_back function.

For example back_insterter can't be used with forward_list.

In that case we need to have the memory allocated before we call std::transform on the same and first approach is better.

Upvotes: 3

Related Questions