Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

for_each that gives two (or n) adjacent elements

Is there a standard implementation of a for_each that does call with the element and the next one in the range?

For example take the range {0, 1, 2, 3, 4, 5}, I would like to call a function f with each element and its successor: {f(0, 1), f(1, 2), f(2, 3), f(3, 4), f(4, 5)} Note how the last element is left out because it has no successor.

It would also be nice if there was a generalization of this to n successors that get passed with the element itself.

Up to now I have always solved this in terms of a handwritten loop with iterators. However, I would like to go much more along the lines of C++11 range based for or std::for_each to avoid boiler plate code.

Examples

// today: handwritten loop
for(Range::iterator current = range.begin(); current != range.end(); ++current) 
   f(*current, *std::next(current));

// near future: wrapped version
for_each_pair(range.begin(), range.end(), f);

// slightly further future: generalized version
for_each_tuple<n>(range.begin(), range.end(), f);

Additional Question

The name of the function could be improved. To me for_each_pair/tuple sounds like all subsets of size n of the range should be returned (which is in itself another problem I would like to solve). So I'd like some suggestions on better names like:

for_each_adjacent<n>

Temporary Solution

I have posted my own solution over at CR. I won't duplicate it here because this is about a standard solution and there are already enough roll-your-own answers.

like image 220
Nobody moving away from SE Avatar asked Nov 12 '13 11:11

Nobody moving away from SE


3 Answers

You could actually abuse std::unique or std::adjacent_find for this: the predicate is called with each consecutive pair in the iterator range, and as long as the predicate always returns false, it won't modify anything or return early.

Disregarding that particular hack, I would implement this as an iterator adapter, not an algorithm. That is, I'd implement a consecutive_tuple_iterator<N> which would return all tuples of N consecutive items. Then you could use it for things like count_if and includes, not just for_each. (It wouldn't be appropriate for most modifying algorithms, though.)

like image 179
Sneftel Avatar answered Oct 31 '22 08:10

Sneftel


The simplest thing would be to write it as a generic algorithm, then apply it many times.

 template< typename FwdIter, typename Func >
 Func for_each_pair( FwdIter iterStart, FwdIter iterEnd, Func func )
 {
     if( iterStart == iterEnd )
        return func;

     FwdIter iterNext = iterStart;
     ++iterNext;

     for( ; iterNext != iterEnd; ++iterStart, ++iterNext )
     {
          func( *iterStart, *iterNext );
     }
     return func;
}

As I was asked why it returns func (rather than void), this is typical of a for_each because of the fact that

  1. func could be an object
  2. It is passed by value.

func may "accumulate" some kind of state, but it is the copy we have made into this algorithm that is accumulating it, not the user's original object. We therefore pass them back the modified "func" object.

like image 41
CashCow Avatar answered Oct 31 '22 07:10

CashCow


With C++ 11 and the new iterator helper functions std::next and std::prev for iterators, the second variant of the standard algorithm std::transform can be used to iterate over adjacent elements.

Here is an example that generates a list of adjacent pairs from a list:

std::vector<int> nums{3, 4, 2, 9, 15, 267};
std::vector<std::pair<int,int>> num_pairs;
if (!nums.empty()) {
    std::transform(
        std::begin(nums), std::prev(std::end(nums)),
        std::next(std::begin(nums)),
        std::back_inserter(num_pairs),
        std::make_pair<
            decltype(nums)::const_reference,
            decltype(nums)::const_reference
        >
    );
}
like image 4
sakra Avatar answered Oct 31 '22 08:10

sakra