CODEWITHSUNDEEP
c++functional-programmingiterator
TamaMcGlinn
TamaMcGlinn

Reputation: 3248

How can I modify std::adjacent_difference to only give the diffs?

The documentation for std::adjacent_difference says that the first element written to the output is the first element of the input, unchanged. For my use case, I want to remove this first element. My question is, what is the most readable way to do this that is also maximally efficient?

For example, given [1, 3, 7], std::adjacent_difference will give [1, 2, 4] but that first element isn't actually a difference, it is just the first 1 we already had.

Currently, I have copied the reference implementation and modified it to not write the first element, and to perform the write in the loop before incrementing the output iterator instead of after:

template<class InputIt, class OutputIt>
constexpr
OutputIt adjacent_difference(InputIt first, InputIt last, 
                             OutputIt d_first)
{
    if (first == last) return d_first;
 
    typedef typename std::iterator_traits<InputIt>::value_type value_t;
    value_t acc = *first;
    while (++first != last) {
        value_t val = *first;
        *d_first++ = val - std::move(acc); // <-- previously *++d_first = ...
        acc = std::move(val);
    }
    return d_first;
}

This works, but of course isn't very satisfying since it copies over code from an existing algorithm. Is it possible to make an inserter that ignores the first write and increment? What performance cost would that incur?

Upvotes: 4

Views: 614

Answers (1)

eerorika
eerorika

Reputation: 238411

Is it possible to make an inserter that ignores the first write and increment?

Yes.

What performance cost would that incur?

In the most trivial implementation: A check for each write in the worst case. The check can be avoided using indirection, but I wouldn't assume indirection to be more efficient.

Regarding your custom algorithm, I believe that the return should not increment: return d_first;

Upvotes: 2

Related Questions