WHAT (SHORT VERSION)


A new modifying sequence operation in <algorithms> that combines the behavior of std::unique with std::reduce/std::accumulate.


Consecutive equivalent elements are replaced by a single element that is a reduction of the original ones. The new element is equivalent to the original ones.


MOTIVATION


Suppose we have got a list of names and payments made to those names:

Alice, 100$

Bob, 50$

Charlie, 110$

Dania, 70$

Eve, 40$

Charlie, 60$

Alice, 30$

Eve, 90$

Alice, 110$

.... (and more elements)....


We would like to know the total amount of payment for each name. The first thing we can do is to sort (std::sort) the list:

Alice, 100$

Alice, 30$

Alice, 110$

Bob, 50$

Bob, 140$

Charlie, 110$

Charlie, 60$

Dania, 70$

Dania, 170$

Eve, 40$

Eve, 90$

Eve, 50$

.... (and more elements)....


The consecutive elements are equivalent with respect to the name, but we would to have a summary as follows:

Alice, 240$

Bob, 190$

Charlie, 170$

Dania, 240$

Eve, 180$

Faythe, 230$

.....


This operation is somewhat similar to removing consecutive equivalent elements, namely ones that are equivalent by name, and replacing by a single element, as in std::unique. The difference is that we want to reduce/accumulate equivalent elements into a single element.


To achieve this, we can can use a modification of std::unique that only takes an binary predicate for "testing equivalence" but also takes a binary operation for "reduction".


EXAMPLE CODE


The following code shows a possible implementation and is based on the second version of std::unique as described in:

https://en.cppreference.com/w/cpp/algorithm/unique


#include <iostream>
#include <vector>
#include <string>
#include <algorithm>


template<class ForwardIt, class BinaryPredicate, class BinaryOp>
ForwardIt accumulate_equivalents(ForwardIt first, ForwardIt last, BinaryPredicate p, BinaryOp op)

{
    if (first == last)
        return last;

    ForwardIt dest = first;
    ForwardIt src = first;
    while (++src != last) {
        if ( p( *dest, *src ) ) {
            *dest = op( std::move( *dest ), *src );
        } else {
            ++dest;
            *dest = std::move( *src );
   }
    }
    return ++dest;
}


struct Payment{
    std::string name;
    int amount;
};

int main()
{

    std::vector<Payment> ps = {
        { "Alice", 100 },
        { "Bob", 50 },
        { "Charlie", 110 },
        { "Dania", 70 },
        { "Eve", 40 },
        { "Charlie", 60 },
        { "Alice", 30 },
        { "Eve", 90 },
        { "Alice", 110 },
        { "Dania", 170 },
        { "Bob", 140 },
        { "Faythe", 230 },
        { "Eve", 50 }
    };

    for( auto& p : ps ) std::cout << p.name << ":" << p.amount << std::endl;
    std::cout << std::endl;

    std::sort( ps.begin(), ps.end(),
        []( Payment a, Payment b ) -> bool{ return a.name < b.name; }
    );

    for( auto& p : ps ) std::cout << p.name << ":" << p.amount << std::endl;
    std::cout << std::endl;

    auto last = accumulate_equivalents( ps.begin(), ps.end(),
        []( const Payment& a, const Payment& b ) -> bool{
            return a.name == b.name;
        },
        []( const Payment& a, const Payment& b ) -> Payment{
            std::cout << "Combine "
                      << a.name << ":" << a.amount << " | "
                      << b.name << ":" << b.amount << std::endl;
            return { a.name, a.amount + b.amount };
        }
    );

    std::cout << std::endl;

    for( auto& p : ps ) std::cout << p.name << ":" << p.amount << std::endl;
    std::cout << std::endl;

    ps.erase( last, ps.end() );

    for( auto& p : ps ) std::cout << p.name << ":" << p.amount << std::endl;
    std::cout << std::endl;

    return 0;
}



THOUGHTS & ISSUES:


This a pure extension to the standard library. The algorithm itself addresses a fundamental problem that may arise in a variety of contexts when dealing with containers.


The algorithm is similar to std::unique because it replaces consecutive equivalent elements by a single equivalent element. It is similar to std::reduce because it reduces a range of elements to a single element.


The specific design should resemble std::unique, std::reduce, and std::accumulate. I believe most specific issues in the design of the new algorithm can be taken from those existing methods. In particular, the aforementioned three methods should (in principle) be implementable in terms of the new method.


Thank you for your feedback.


Best,

Martin


http://www.math.ucsd.edu/~mlicht/