cilk_for for STL iterators

cilk_for for STL iterators


I have a loop in the form

// map transactions;

cilk_for (map::iterator transactions_it=transactions.begin(); transactions_it != transactions.end(); transactions_it++)

I get the following error:

In member function ?void cilk Item_Support_Generator::create_pairs()?:
125: error: no match for ?operator-? in ?loop bound - transactions_it?
125: error: No operator-(const std::_Rb_tree_iterator, std::allocator >, int> >, std::_Rb_tree_iterator, std::allocator >, int> >) for Cilk for loop control variable

I know the problem is due to the fact that maps do not support random access iterators,
and the cilk programming guide asks us to define a method for operator-.

I am not sure what exactly that means.
Has it got something to do with custom iterators?

Any pointersabouthow to define this operatorwould be helpful. Thanks.

6 posts / 0 new
Last post
For more complete information about compiler optimizations, see our Optimization Notice.

For now, I have worked around by declaring a

struct Row
string st;
int cnt;


and then a vector , as vector has random access iterators...
If anyone has a better solution, kindly reply.

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

Thanks for the reply.

The only problem I have is that, cilk does not have built in reducer object for vector.
I would like to use vector as a reducer object so that I can parallely push_back Rows into it.
I did find some material indicating I can build my own reducer objects, but it seemed a bit complex.

Are there any plans for providing vector reducers (like list reducers, which unfortunately have bi directional iterators) in future?
If not, if you could provide some links or guidelines to build reducer objectof vector, it would be helpful as it would be quite powerful to have a reducer with random access iterator, as it would then provide both

1. Capability to push items parallely
2. Process items parallely

Thanks again

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.

Thanks a lot, Pablo. It surely helped.

Leave a Comment

Please sign in to add a comment. Not a member? Join today