C++ Logo

STD-PROPOSALS

Advanced search

Subject: Re: [std-proposals] Proposal Idea: algorithm that combines unique and reduce/accumulate
From: Barry Revzin (barry.revzin_at_[hidden])
Date: 2019-09-06 09:48:25


On Fri, Sep 6, 2019, 9:12 AM Licht, Martin via Std-Proposals <
std-proposals_at_[hidden]> wrote:

> 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".
>

Rather that adding a new algorithm for each specific thing we might want to
do, I'd rather we add all the separate pieces and work on making it easier
to put those pieces together.

This example is something like:

ps
| actions::sort
| views::group(&Payment::name)
| views::transform([](auto&& range){
auto name = ranges::front(range).name;
auto total = ranges::accumulate(range | views::transform(&Payment::amount));
return Payment{.name=name, .amount=total};
});

Except range-v3's group is actually called group_by and takes a binary
predicate rather than a unary function. Otherwise. I think this is more or
less valid?

In other words, instead of accumulate_equivalents(), make it easier to do
the equivalents part and the accumulate part separately.

Barry

>



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

Standard Proposals Archives on Google Groups