2
\$\begingroup\$

There is a small programming exercise to merge adjacent identical elements in a collection.

Here are two solutions (passing the tests from the exercise). I am asking for review of the first version using standard algorithms. The second is just for reference of the expected behavior.

template <typename ForwardIterator, typename OutputIterator, typename Equal, typename Merge>
void merge_adjacent(ForwardIterator first, ForwardIterator last, OutputIterator out, Equal equal, Merge merge)
{
    while(first != last){
    auto start = first;
    auto stop = std::find_if_not(start,last,[&](auto const &t){return equal(*start,t);});
    if(start != stop){
        out = std::accumulate(start+1,stop,*start,merge);
    }
    else{
        out = *start;
    }
    first = stop;
    }

    /*    
    while(first != last)
    {
        auto next = *first;
        first++;
        while((first != last) && (equal(next,*first)))
        {
            next = merge(next,*first);
            first++;
        }
        out = next;
    }
    */
}
\$\endgroup\$
  • \$\begingroup\$ Are you sure the data is sorted? If yes, then you could just std::upper_bound your way to the end. \$\endgroup\$ – Incomputable Oct 11 at 6:51
  • \$\begingroup\$ I do not have an compare, only an equal. So the data is not sorted. \$\endgroup\$ – user9400869 Oct 11 at 7:00
  • \$\begingroup\$ If I understand correctly, this is std::unique_copy(), but instead of discarding duplicates, we have to use merge to combine them? \$\endgroup\$ – Toby Speight Oct 11 at 8:24
  • \$\begingroup\$ @Toby correct, but I want to clarify: We only merge adjacent duplicates and the element we push write to the output is the result of this merge. \$\endgroup\$ – user9400869 Oct 11 at 8:44
2
\$\begingroup\$

Generally looks okay (though I would prefer shorter line lengths, and the indentation needs cleaning up).

It seems that we've focused on using std::back_insert_iterator as the output iterator; this leads to a couple of problems that are visible when we switch to a different iterator, such as a collection iterator or raw pointer:

  • The caller doesn't know where the output finished; we should return the final value of out, just as std::unique_copy() does.
  • The assignment out = neither indirects nor advances the iterator; it should be *out++ =.

We don't need a separate start copied from first, and we can use std::adjacent_find to determine the range of equal elements:

#include <algorithm>
#include <functional>
#include <numeric>

template <typename ForwardIterator, typename OutputIterator,
          typename Equal, typename Merge>
OutputIterator merge_adjacent(ForwardIterator first, ForwardIterator last,
                              OutputIterator out,
                              Equal equal, Merge merge)
{
    while (first != last) {
        auto stop = std::adjacent_find(first, last, std::not_fn(equal));
        if (stop != last) {
            // advance to include the first of the pair
            ++stop;
        }
        *out++ = std::accumulate(first+1, stop, *first, merge);
        first = stop;
    }

    return out;
}

This version still performs two passes (one for the search, and one for the accumulate). The commented-out, lower-level version of the function should be able to accept input iterators, as a single-pass algorithm.

Looking at that version, there's only a little to improve. I'd probably post-increment the iterators while dereferencing, rather than as a separate statement, but that's just a style preference. One thing I would change would be to use std::move() when finishing with next, to minimise unnecessary copying:

#include <algorithm>
#include <numeric>
#include <utility>

template <typename InputIterator, typename OutputIterator,
          typename Equal, typename Merge>
OutputIterator merge_adjacent(InputIterator first, InputIterator last,
                              OutputIterator out,
                              Equal equal, Merge merge)
{
    while (first != last) {
        auto next = *first++;
        while (first != last && equal(next, *first)) {
            next = merge(std::move(next), *first++);
        }
        *out++ = std::move(next);
    }

    return out;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.