blocked_range<set<size_t>::const_iterator> template argument 1 is invalid

[khteh]

How to use blocked_range with set and map?

set<size_t> uset1;
size_t result = parallel_reduce(
		blocked_range<set<size_t>::const_iterator>(uset1.begin(), uset1.end()), 1 /* Identity for Multiplication */,
		[&](tbb::blocked_range<set<size_t>::const_iterator> const &r, size_t running_total)
		{
			for (set<size_t>::const_iterator it = r.begin(); it != r.end(); it++)
				running_total = ((running_total % modulo) * (*it % modulo)) % modulo;
			return running_total;
		},
		[&modulo](size_t x, size_t y) -> size_t
		{
			return ((x % modulo) * (y % modulo) % modulo);
		});

Errors:

Console.cpp:2175:41: error: template argument 1 is invalid
 2175 |                 blocked_range<set<size_t>::const_iterator>(uset1.begin(), uset1.end()), 1 /* Identity for Multiplication */,
      |                                         ^
Console.cpp:2176:50: error: template argument 1 is invalid
 2176 |                 [&](tbb::blocked_range<set<size_t>::const_iterator> const &r, size_t running_total)
      |                                                  ^
Console.cpp:2176:51: error: expected identifier before ‘::’ token
 2176 |                 [&](tbb::blocked_range<set<size_t>::const_iterator> const &r, size_t running_total)
      |                                                   ^~
Console.cpp:2176:67: error: expected unqualified-id before ‘>’ token
 2176 |                 [&](tbb::blocked_range<set<size_t>::const_iterator> const &r, size_t running_total)
      |                                                                   ^
Console.cpp:2176:67: error: expected ‘)’ before ‘>’ token
 2176 |                 [&](tbb::blocked_range<set<size_t>::const_iterator> const &r, size_t running_total)
      |                    ~                                              ^
      |                                                                   )

[kboyarinov]

Hi @khteh, thanks for your question.
Unfortunately, it is impossible to use std::map and std::set iterators directly as a value for blocked_range since these types does not model the BlockedRangeValue. Only the random access iterators can be used directly, i.e. std::vector or std::array ones.
tbb::blocked_range needs to be splittable into two parts during the run of parallel_reduce and non-random access iterators cannot provide this functionality with constant complexity.
If you are able to share with us more details about the behavior you are trying to achieve, we will be happy to help with finding the best alternative.

[khteh]

How can I use parallel_reduce on std::set and std::map for simple use cases of sum or multiplication reduction?

[kboyarinov]

The only way I see to use std::set and std::map containers for parallel reduction is to track a set of keys in another random-access container or regular blocked_range. But since it introduce duplications of the data in both set or map and other container, I don't think it makes much sense.

Another proposal is to consider using TBB associative containers instead - tbb::concurrent_set and tbb::concurent_map.
They provide a special method range() that returns an object that can be used as an input for parallel algorithms:

using set_type = tbb::concurrent_set<size_t>;
using range_type = typename set_type::range_type;

set_type uset1 = {/*data in the set*/};

tbb::parallel_reduce(uset1.range(), /*identity = */1,
    [&modulo](range_type const& r, size_t running_total) {
        for (auto it = r.begin(); it != r.end(); it++)
	    running_total = ((running_total % modulo) * (*it % modulo)) % modulo;
	return running_total;
    },
    [&modulo](size_t x, size_t y) -> size_t {
        return ((x % modulo) * (y % modulo) % modulo);
    });