I am trying to implement an algorithm that merges elements in an ordered container, if they satisfy a BinaryPredicate.

template <typename ForwardIt, 
          typename OutputIt, 
          typename BinaryPredicate, 
          typename Merge>
void merge_adjacent(ForwardIt first, 
                    ForwardIt last, 
                    OutputIt out, 
                    BinaryPredicate pred, 
                    Merge merge)
{
    if(first != last)
        *out = *(first  );
    while(first != last)
    {
        if(pred(*first, *out))
            *out = merge(*out, *(first  ));
        else
            *(  out) = *(first  );
    }
}

When I pass an empty container to put the result in (via OutputIterator), I get an segmentation fault - I also understand why, because the container does not have any space reserved... When I reserve enough space before passing the OutputIterator, the container stays empty...

I am a lil puzzled because I was following an example implementation of the std::transform function on cppreference:

template< class InputIt,
          class OutputIt,
          class UnaryOperation >
OutputIt transform( InputIt first1,
                    InputIt last1,
                    OutputIt d_first, 
                    UnaryOperation unary_op )
{
    while (first1 != last1) {
        *d_first   = unary_op(*first1  );
    }
    return d_first;
}

What am I doing wrong?

My main.cpp for completeness:

#include "merge_adjacent.hpp"
#include <vector>
#include <iostream>
#include <stdexcept>

class Sale
{
public:
    Sale(int date, double amount)
     : date(date),
       amount(amount)
    {}
    Sale()
     : date(0),
       amount(0)
    {}
    int getDate() const
    {
        return date;
    }
    double getAmount() const
    {
        return amount;
    }
private:
    int date;
    double amount;
};

bool sameDate(Sale const& sale1, Sale const& sale2)
{
    return sale1.getDate() == sale2.getDate();
}

Sale mergeSales(Sale const& sale1, Sale const& sale2)
{
    if (sale1.getDate() != sale2.getDate()) throw ;
    
    return Sale(sale1.getDate(), sale1.getAmount()   sale2.getAmount());
}

int main()
{
    std::vector<Sale> sales = {Sale{1,2.9}, Sale(1,2.2),Sale(1,4.7),Sale(2,1.9),Sale(3,3.8),Sale(3,1.1),Sale(5,2.9),Sale(6,2.9),Sale(6,2.9)};
    std::vector<Sale> merged;
    merged.reserve(20);
    merge_adjacent(sales.begin(), sales.end(), merged.begin()/*std::back_inserter(merged)*/, sameDate, mergeSales);
    std::cout << "size of merged must be 5: " << merged.size() << std::endl;
    return 0;
}

CodePudding user response：

You may be looking for something like this:

template <typename InputIt, 
          typename OutputIt, 
          typename BinaryPredicate, 
          typename Merge>
void merge_adjacent(InputIt first, 
                    InputIt last, 
                    OutputIt out, 
                    BinaryPredicate pred, 
                    Merge merge)
{
    if (first == last) return;
    auto accum = *first  ;
    while (first != last) {
        auto cur = *first  ;
        if (pred(cur, accum)) {
            accum = merge(accum, cur);
        } else {
            *out   = accum;
            accum = cur;
        }
    }
    *out   = accum;
}

Demo. Not tested very thoroughly, I only confirmed it worked on your example. I think I'm staying within the capabilities of InputIterator and OutputIterator, but I haven't tested that either.