Code It Yourself: Merging Consecutive Elements in a C++ Collection

After seeing how to extract words among spaces in C++, we are going to see another algorithm that, seen from the outside, does something very different, but has a similar implementation: merging identical consecutive elements in a collection.

We will use STL algorithms to implement this, and strive for writing code as expressive as possible.

You’ll have a chance to code it up right on this page, which is good STL exercise! And in the next post on Fluent C++, you will see a possible solution.

Aggregating flows together

Our motivating case is the following: our 24/7 grocery store makes sales all day long and every day of the week. Each sale has a date and a amount.

class Sale
{
public:
    Sale(Date date, double amount);
    Date getDate() const;
    double getAmount() const;
private:
    // ...
};

At the end of the month, the store manager has the list of all sales of the month:

std::vector<Sale> salesOfMonth = // ...

And she would like to know how much revenue the store made each day.

So we’d like to produce a collection of aggregated sales, that contains one sale for each day, being the sum of all the sales that day:

std::vector<Sale> dailySales = aggregateByDay(salesOfMonth );

The interface

The concept of adding consecutive things together is quite generic, and goes far beyond the example of daily sales. For this reason, let’s build a algorithm.

In the general case, it makes sense to produce the output of a function via its return type, but when we output a collection from an generic algorithm, this poses a problem. Indeed, what type of collection should we return? A std::vector? A std::set? Something else?

To remedy to that, the STL has the convention of using an output iterator, so we’ll stick to the conventions of the STL.

Here is a first attempt for our interface:

template <typename ForwardIterator, typename OutputIterator>
void merge_adjacent(ForwardIterator first, ForwardIterator last, OutputIterator out)

But the algorithm doesn’t have enough info as is. Indeed, it needs to be able to compare two elements together, and determine whether two consecutive ones are identical (in our case, have the same date). And it also needs to know how to add two elements together (in our case, generate a sale that has the sum of amounts).

To pass those two functions to merge_adjacent, its interface becomes:

template <typename ForwardIterator, typename OutputIterator, typename Equal, typename Merge>
void merge_adjacent(ForwardIterator first, ForwardIterator last, OutputIterator out, Equal equal, Merge merge)

And the implementations of those two functions for our Sale class are:

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 "Error: cannot add sales with different dates";
    
    return Sale(sale1.getDate(), sale1.getAmount() + sale2.getAmount());
}

Try it first

Practice makes perfect, they say. So why wouldn’t you give it a go before reading a solution? Try to use STL algorithms to make your code more expressive!

Here is a playground with some basic test cases to provide you with a quick feedback on whether your code is correct:

Alternatively, you can use this coliru that contains the same code, if you’d like to keep your trials for later reference.

Stay tuned in a few days for an article on Fluent C++ showing a possible solution, using STL algorithms. In the meantime, if you code it up, I’d love to see your code! You can share a coliru or godbolt link in a comment.

Happy coding!

Don't want to miss out ? Follow:   
Share this post!