C++ Logo

STD-PROPOSALS

Advanced search

Subject: Re: [std-proposals] Proposal Idea: algorithm that combines unique and reduce/accumulate
From: Tony V E (tvaneerd_at_[hidden])
Date: 2019-09-06 09:34:16


I've written something similar, so I agree there are motivating use cases. 

In my version (IIRC), I passed the subrange of equal elements to the reduce function, instead of just element pairs. But, looking at your version, I'm not sure the added complexity of mine was worth it. ‎ (I would need to check the code, which is not at hand‎, to see if I'm overlooking any benefits to my version.)


Sent from my BlackBerry portable Babbage Device
From: Licht, Martin via Std-Proposals
Sent: Friday, September 6, 2019 10:12 AM
To: std-proposals@lists.isocpp.org
Reply To: std-proposals@lists.isocpp.org
Cc: Licht, Martin
Subject: [std-proposals] Proposal Idea: algorithm that combines unique and reduce/accumulate

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/


STD-PROPOSALS list run by herb.sutter at gmail.com

Standard Proposals Archives on Google Groups