Simple examples of parallel and serialized algorithms in C++

ppa.h

#ifndef PPA_H
#define PPA_H

#include "ppa_impl.h"

namespace ppa {

template<
    typename RandomIt,
    typename value_type = typename std::iterator_traits<RandomIt>::value_type
>
value_type average(RandomIt first, RandomIt last, exec_policy policy = exec_policy::sequenced){
    if(policy == exec_policy::parallel)
        return parallel_average(first, last);
    else
        return sequenced_average(first, last);
}

template<
    typename RandomIt,
    typename Function
>
void for_each(RandomIt first, RandomIt last, Function func,
              exec_policy policy = exec_policy::sequenced){
    if(policy == exec_policy::parallel)
        parallel_for_each(first, last, func);
    else
        sequenced_for_each(first, last, func);                
}

}

#endif

ppa_impl.h

#ifndef PPA_IMPL_H
#define PPA_IMPL_H

#include <algorithm>
#include <list>
#include <iterator>
#include <future>
#include <atomic>

namespace ppa {

static const size_t CHUNK_SIZE = 100000;
static const size_t num_threads = std::thread::hardware_concurrency();

enum class exec_policy {
    parallel,
    sequenced
};

template<
    typename RandomIt,
    typename value_type = typename std::iterator_traits<RandomIt>::value_type
>
value_type sequenced_average(RandomIt first, RandomIt last){
    value_type sum = 0;
    value_type num_elements = std::distance(first, last);
    while(first != last)
        sum += *first++;
    return num_elements == 0 ? 0 : sum / num_elements;
}

template<
    typename RandomIt,
    typename value_type = typename std::iterator_traits<RandomIt>::value_type
>
value_type parallel_average(RandomIt first, RandomIt last){
    size_t chunk_size = std::distance(first, last)/(num_threads);
    chunk_size = chunk_size == 0 ? std::distance(first, last) : chunk_size;
    std::list<std::future<value_type> > tasks;
    for(size_t i = 0; i < num_threads-1; i++){
        RandomIt next = first;
        std::advance(next, chunk_size);
        tasks.push_back(async(sequenced_average<RandomIt, value_type>, first, next));
        first = next;
    }
    value_type result = sequenced_average(first, last);
    for(std::future<value_type>& f : tasks)
        result += f.get();
    return result / num_threads;
}

/*
    TO-DO:
    For all bellow algorithms change them to iterative versions(more cache effecient)
    like the average algorithm and add execution polity
*/

class Finder {
public:
    Finder() : done(false) {}
    template<typename RandomIt, typename T>
    RandomIt parallel_find(RandomIt first, RandomIt last, T value){
        done = false;
        RandomIt res = parallel_find_impl(first, last, value);
        done = true;
        return res;
    }
private:
    std::atomic<bool> done;

    template<typename RandomIt, typename T>
    RandomIt parallel_find_impl(RandomIt first, RandomIt last, T value){
        if(std::distance(first, last) <= CHUNK_SIZE)
            return parallel_find_with_flag(first, last, value);
        RandomIt mid = first;
        std::advance(mid, std::distance(first, last)/2);
        std::future<RandomIt> right(
            std::async(&parallel_find_impl<RandomIt, T>, this, mid, last, value)
        );
        RandomIt res = parallel_find_impl(first, mid, value);
        return (res == mid ? right.get() : res);
    }

    template<typename RandomIt, typename T>
    RandomIt parallel_find_with_flag(RandomIt first, RandomIt last, T value){
        while(first != last && !done.load()){
            if(*first == value){
                done = true;
                return first;
            }
            first++;
        }
        return last;
    }
};

template<typename RandomIt, typename T>
RandomIt parallel_find(RandomIt first, RandomIt last, T value){
    Finder f;
    return f.parallel_find(first, last, value);
}

template<
    typename RandomIt,
    typename Function
>
void sequenced_for_each(RandomIt first, RandomIt last, Function func){
    std::for_each(first, last, func);
}

// Function func needs to be void
template<
    typename RandomIt,
    typename Function
>
void parallel_for_each(RandomIt first, RandomIt last, Function func){
    size_t chunk_size = std::distance(first, last)/(num_threads);
    chunk_size = chunk_size == 0 ? std::distance(first, last) : chunk_size;
    std::list<std::future<void> > tasks;
    for(size_t i = 0; i < num_threads-1; i++){
        RandomIt next = first;
        std::advance(next, chunk_size);
        tasks.push_back(std::async(
            sequenced_for_each<RandomIt, Function>, first, next, func)
        );
        first = next;
    }
    sequenced_for_each(first, last, func);
    for(std::future<void>& f : tasks)
        f.get();
}

/*
ppa::parallel_copy does not accept 
std::back_insert_iterators because it needs
to have enough space for the vector 
(can't use std::advance with back_insert_iterator)
*/
template<
    typename InputIt,
    typename OutputIt
>
void parallel_copy(InputIt first, InputIt last, OutputIt d_iter){
    if(std::distance(first, last) <= CHUNK_SIZE){
        std::copy(first, last, d_iter);
        return;
    }
    InputIt mid = first;
    OutputIt mid_d_iter = d_iter;
    std::advance(mid, std::distance(first, last)/2);
    std::advance(mid_d_iter, std::distance(first, last)/2);
    std::future<void> right(
        std::async(&parallel_copy<InputIt, OutputIt>, mid, last, mid_d_iter)
    );
    parallel_copy(first, mid, d_iter);
    right.get();
}

class Sorter {
public:
    template<
        typename RandomIt,
        typename Compare = std::less<typename std::iterator_traits<RandomIt>::value_type>
    >
    static void parallel_quicksort(RandomIt first, RandomIt last, Compare comp = {}){
        if(std::distance(first, last) <= CHUNK_SIZE){
            quicksort(first, last, comp);
            return;
        }
        RandomIt pivot = partition(first, last, comp);
        std::future<void> left(
            std::async(&parallel_quicksort<RandomIt, Compare>, first, pivot, comp)
        );
        pivot++;
        parallel_quicksort(pivot, last, comp);
        left.get();
    }

    template<
        typename RandomIt,
        typename Compare = std::less<typename std::iterator_traits<RandomIt>::value_type>
    >
    static void quicksort(RandomIt first, RandomIt last, Compare comp = {}){
        if(distance(first, last) <= 1)
            return;
        // partition
        RandomIt pivot = partition(first, last, comp);
        quicksort(first, pivot, comp);
        pivot++;
        quicksort(pivot, last, comp);
    }
    
    template<
        typename RandomIt,
        typename Compare = std::less<typename std::iterator_traits<RandomIt>::value_type>
    >
    static void parallel_merge_sort(RandomIt first, RandomIt last, Compare comp = {}){
        if(std::distance(first, last) <= CHUNK_SIZE){
            merge_sort(first, last, comp);
            return;
        }
        RandomIt mid = first;
        std::advance(mid, std::distance(first, last)/2);
        std::future<void> left(std::async(&parallel_merge_sort<RandomIt, Compare>, first, mid, comp));
        parallel_merge_sort(mid, last, comp);
        left.get();
        merge(first, mid, last, comp);
    }
    
    template<
        typename RandomIt,
        typename Compare = std::less<typename std::iterator_traits<RandomIt>::value_type>
    >
    static void merge_sort(RandomIt first, RandomIt last, Compare comp = {}){
        if(std::distance(first, last) <= 1)
            return;
        RandomIt mid = first;
        std::advance(mid, std::distance(first, last)/2);
        merge_sort(first, mid, comp);
        merge_sort(mid, last, comp);
        merge(first, mid, last, comp);
    }
private:
    template<
        typename RandomIt,
        typename Compare = std::less<typename std::iterator_traits<RandomIt>::value_type>
    >
    static RandomIt partition(RandomIt first, RandomIt last, Compare comp = {}){
        RandomIt front = first+1;
        RandomIt back = first+1;
        for(front; front != last; front++){
            if(comp(*front, *first)){
                std::swap(*back, *front);
                back++;
            }
        }
        back--;
        std::swap(*first, *back);
        return back;
    }

    
    template<
        typename RandomIt,
        typename Compare = std::less<typename std::iterator_traits<RandomIt>::value_type>,
        typename Container = std::list<typename std::iterator_traits<RandomIt>::value_type>
    >
    static void merge(RandomIt first, RandomIt mid, RandomIt last, Compare comp = {}){
        RandomIt i = first;
        RandomIt j = mid;
        Container res;
        std::back_insert_iterator<Container> it(res);
        while(i != mid && j != last){
            if(comp(*i, *j))
                *it++ = *i++;
            else
                *it++ = *j++;
        }
        while(i != mid)
            *it++ = *i++;
        while(j != last)
            *it++ = *j++;
        std::copy(std::begin(res), std::end(res), first);
    }
};

template<typename RandomIt>
void sort(RandomIt first, RandomIt last){
    Sorter::merge_sort(first, last);
}

template<typename RandomIt>
void parallel_sort(RandomIt first, RandomIt last){
    Sorter::parallel_merge_sort(first, last);
}

template<typename RandomIt>
void quicksort(RandomIt first, RandomIt last){
    Sorter::quicksort(first, last);
}

template<typename RandomIt>
void parallel_quicksort(RandomIt first, RandomIt last){
    Sorter::parallel_quicksort(first, last);
}

}

#endif