You have correctly identified the problem -- std::map does not support random-access iterators and, therefore, you cannot use std::map::iterator as the control variable ina cilk_for loop. In answer to your question about operator-: part of what it means to have a random-access iterator is that you can find thedistance between two iterators in constant time (using operatator-). It also means that you can add an integer N to an iterator in order to increment the iterator N times, again in constant time. Random access iterators have operator+ and operator- defined for them. You should not attempt to define these operators yourself for any iterator that does not already have them.

A cilk_for loop does not execute the iterations in order -- it hops around, executing the first and middle iterations concurrently, and (depending on the number of workers), the iterations 1/4 and 3/4 of the way through. In order to make these jumps, it needs to be able to do arithmetic on the control variable. Hence the need for random-access iterators. If the vector data structure meets your needs, then it is a fine solution to this problem.

- Pablo

Yes, you can build your own vector-based reducer. There are several possible strategies, with different tradeoffs:

1. Use a reducer_list_append. At the end, copy all of the elements to a vector:

const std::list &lst = my_reducer.get_value();
std::vector my_vector(lst.begin(), list.end());

2. Make a copy of reducer_list.h. Eliminate the definition and code for reducer_list_prepend. Change list to vector. Change the reduce function to append the right-hand vector the the left-hand one:

void reduce(std::vector* left, std::vector* right) { left->insert(left->end(), right->begin(), right->end()); }

3. Make a copy of redicer_string.h. Modify it to work on vectors instead of strings.

1 is the simplest. 3 is the most complex, but probably the most efficient. It is hard to say which of 1 or 2 is most efficient. 1 has more memory overhead, but less copying. If the values you are storing (Rows) are cheap to copy (and it appears that they are), then 2 might be more efficient, but definately more work. 2 can probably be made more efficient by using a deque instead of a vector.

I hope this helps.
-Pablo