Functional programming favors functions whose results depend only on their inputs. A pure function also avoids changing external state, so calling it again with the same inputs gives the same result. section 4.4.1
For concurrent work, give each task the data it needs and pass its result to other tasks through futures rather than sharing data directly. With no shared-data modifications, there are no races on that data and no need to protect it with mutexes. section 4.4 section 4.4.1
Future-based Quicksort
The parallel version partitions a list around a pivot, starts sorting the lower partition asynchronously, and sorts the higher partition in the current task. It then retrieves the lower partition through its future and combines the results. The sequential version uses the same partition-and-recurse approach without asynchronous work. section 4.4.1
Listing 4.13. Parallel Quicksort using futures
template<typename T>
std::list<T> parallel_quick_sort(std::list<T> input)
{
if(input.empty())
{
return input;
}
std::list<T> result;
result.splice(result.begin(),input,input.begin());
T const& pivot=*result.begin();
auto divide_point=std::partition(input.begin(),input.end(),
[&](T const& t){return t<pivot;});
std::list<T> lower_part;
lower_part.splice(lower_part.end(),input,input.begin(),
divide_point);
std::future<std::list<T> > new_lower( #1
std::async(¶llel_quick_sort<T>,std::move(lower_part)));
auto new_higher(
parallel_quick_sort(std::move(input))); #2
result.splice(result.end(),new_higher); #3
result.splice(result.begin(),new_lower.get()); #4
return result;
}
!@%STYLE%@!
{"css":"{\"css\": \"font-weight: bold;\"}","target":"[[{\"line\":15,\"ch\":68},{\"line\":15,\"ch\":70}],[{\"line\":18,\"ch\":68},{\"line\":18,\"ch\":70}],[{\"line\":19,\"ch\":68},{\"line\":19,\"ch\":70}],[{\"line\":20,\"ch\":68},{\"line\":20,\"ch\":70}]]"}
!@%STYLE%@!
Inspect the C++ implementation that launches recursive sorting with std::async and combines the result through a future. section 4.4.1
