Example of a Parallel Algorithm

STL provides a count algorithm for counting the number of elements in an iterator range first and last that have value = value, and adds the result to the argument n. The following piece of code shows a sequential implementation:

 template <class InputIterator, class T, class Size>

		void count(InputIterator first,

						 InputIterator last,

						const T& value,

						Size& n)

		{

				while (first != last)

				{

						if(*first++ == value)

								++n;

				}

		}

The following algorithm provides a parallel implementation of the same using strategy classes. This assumes that each thread participating in a data-parallel operation invokes this function and provides its own local copy of n. The implementation uses the sequential version of count where each thread computes the partial results.

 template <class Strategy, class InputIterator,

						class T, class Size>

		void count(Strategy& strategy,

						InputIterator first,

						InputIterator last,

						const T& value,

						Size& n)

		{

				//get the current data parallel object

				Rope& self_rope = Rope::SelfRope();

				//get the rope size

				int rope_size = self_rope.Size();

				//create a type-specific reduction object

				ReductionT<Size, plus<Size> >

						red(self_rope.ReductionObj());

				//create thread-specific iterators

				Strategy::thread_iterator my_first(first);

				Strategy::thread_iterator my_last(last);

				// position the iterators based on strategy

				strategy(rope_size, first, last, my_first, my_last);

				  Size my_n = 0;

				// per-thread sequential algorithm

				  ::count(my_first, my_last, value_pred, my_n);

				// combine the partial results

				  Size total = red(plus<Size>(), my_n);

				  n += total;

		}