Topic: Standard proposal: adding a new modification of std::accumulate.
Author: Vlad from Moscow <vlad.moscow@mail.ru>
Date: Thu, 10 Jan 2013 14:29:18 -0800 (PST)
Raw View
------=_Part_128_25723057.1357856958098
Content-Type: text/plain; charset=ISO-8859-1
At first let consider a simple assignment: calculate sum of all elements of
a integer array after the last negative element.
It seems that the assignment should be done in two phases. Firstly the last
negative element should be found for example with std::find_if by supplying
reverse iterators. Secondly standard algorithm std::accumulate will be used.
This approach has a serious shortage. Nothing prevents that the last
negative element of the array will be at the same time the first element of
the array. So the array will be traversed twice. It is obvious that this
approach is ineffective.
But how to do the task in more effective way and preserve the symantic of
std::accumulate?
I suggest a new modification of std::accumulate that resolves this problem.
This modifications includes two forms of the algorithm
template <class InputIterator, class T, class UnaryPredicate, class
BinaryOperation>
T accumulate_first_if( InputIterator first,
InputIterator last,
T init,
UnaryPredicate unary_predicate,
BinaryOperation binary_operation )
{
for ( ; first != last && unary_predicate( *first ) ; ++first )
{
init = binary_operation( init, *first );
}
return ( init );
}
template <class InputIterator, class T, class UnaryPredicate>
T accumulate_first_if( InputIterator first,
InputIterator last,
T init,
UnaryPredicate unary_predicate )
{
for ( ; first != last && unary_predicate( *first ) ; ++first )
{
init = ( T )( init + *first );
}
return ( init );
}
Now the assignment can be done simply
int a[] = { 1, 2, -3, 4, 5, -6, 7, 8, 9};
int sum = accumulate_first_if( std::reverse_iterator<int *>( std::end( a )
),
std::reverse_iterator<int *>( std::begin(
a ) ), 0,
std::bind2nd( std::greater_equal<int>(), 0 ) );
std::cout << "sum = " << sum << std::endl;
--
------=_Part_128_25723057.1357856958098
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
<div>At first let consider a simple assignment: calculate sum of all elemen=
ts of a integer array after the last negative element.</div><div=
>It seems that the assignment should be done in two phases. Firstly the las=
t negative element should be found for example with std::find_if by supplyi=
ng reverse iterators. Secondly standard algorithm std::accumulate will be u=
sed.</div><div> </div><div>This approach has a serious shortage. Nothi=
ng prevents that the last negative element of the array will be at th=
e same time the first element of the array. So the array will be traversed =
twice. It is obvious that this approach is ineffective.</div><div>&nb=
sp;</div><div>But how to do the task in more effective way and preserve the=
symantic of std::accumulate?</div><div> </div><div> </div><div>I=
suggest a new modification of std::accumulate that resolves this problem.<=
/div><div> </div><div> </div><div>This modifications includes two=
forms of the algorithm</div><div> </div><div> </div><div>templat=
e <class InputIterator, class T, class UnaryPredicate, class BinaryOpera=
tion><br>T accumulate_first_if( InputIterator first, <br> &nb=
sp; =
InputIterator last,<br> &nb=
sp; T init,<br> Unary=
Predicate unary_predicate,<br> Bi=
naryOperation binary_operation )<br>{<br> for ( ; first !=3D last &=
;& unary_predicate( *first ) ; ++first )<br> {<br> init=
=3D binary_operation( init, *first );<br> }</div><div> return ( =
init );<br>}</div><div>template <class InputIterator, class T, class Una=
ryPredicate><br>T accumulate_first_if( InputIterator first, <br> &n=
bsp;  =
; InputIterator last,<br> &n=
bsp; T init,<br>  =
; UnaryPredicate unary_predicate )<br>{<br> for ( ; first !=3D last &a=
mp;& unary_predicate( *first ) ; ++first )<br> {<br> in=
it =3D ( T )( init + *first );<br> }</div><div> return ( init );<=
br>}<br></div><div> </div><div>Now the assignment can be done simply</=
div><div> </div><div>int a[] =3D { 1, 2, -3, 4, 5, -6, 7, 8, 9};</div>=
<div>int sum =3D accumulate_first_if( std::reverse_iterator<int *>( s=
td::end( a ) ), <br> &=
nbsp; &nbs=
p; std::r=
everse_iterator<int *>( std::begin( a ) ), 0,<br> &n=
bsp; std::bind2nd( std::greater_e=
qual<int>(), 0 ) );</div><div>std::cout << "sum =3D " << =
sum << std::endl;<br></div><div> </div><div> </div>
<p></p>
-- <br />
<br />
<br />
<br />
------=_Part_128_25723057.1357856958098--
.
Author: Fernando Cacciola <fernando.cacciola@gmail.com>
Date: Thu, 10 Jan 2013 19:46:11 -0300
Raw View
On Thu, Jan 10, 2013 at 8:29 PM, Vlad from Moscow <vlad.moscow@mail.ru> wrote:
> At first let consider a simple assignment: calculate sum of all elements of
> a integer array after the last negative element.
> It seems that the assignment should be done in two phases. Firstly the last
> negative element should be found for example with std::find_if by supplying
> reverse iterators. Secondly standard algorithm std::accumulate will be used.
>
> This approach has a serious shortage. Nothing prevents that the last
> negative element of the array will be at the same time the first element of
> the array. So the array will be traversed twice. It is obvious that this
> approach is ineffective.
>
> But how to do the task in more effective way and preserve the symantic of
> std::accumulate?
>
>
> I suggest a new modification of std::accumulate that resolves this problem.
>
>
> This modifications includes two forms of the algorithm
>
>
> template <class InputIterator, class T, class UnaryPredicate, class
> BinaryOperation>
> T accumulate_first_if( InputIterator first,
> InputIterator last,
> T init,
> UnaryPredicate unary_predicate,
> BinaryOperation binary_operation )
> {
> for ( ; first != last && unary_predicate( *first ) ; ++first )
> {
> init = binary_operation( init, *first );
> }
> return ( init );
> }
Actually, I'd like to see a more generalized approach.
What you've shown is the case where a standard algorithm should be
applied to a subset of a sequence, and you noticed that it is wasteful
to determine the sub-sequence in a separate pass.
For this case, you are of course correct, and the solution would
indeed be a loop of the form you just proposed.
However, I'm not sure if providing flavors of the algorithm that
combine with this particular sub-sequence selection is the best
approach. It's evident that you'll have to propose the same for pretty
much all other algorithms. And I wonder if there couldn't be other
forms of sub-sequencing as well (I'm thinking direct filtering but
that can be handled by specialized iterators).
So, what I would like is a composable approach, where an utility
generates the desired range, in this case from begin to the first
element failing a predicate, which is them transparently combined with
whatever algorithm, in this case the existing accumulate.
Best
--
Fernando Cacciola
SciSoft Consulting, Founder
http://www.scisoft-consulting.com
--
.
Author: Fernando Cacciola <fernando.cacciola@gmail.com>
Date: Thu, 10 Jan 2013 19:57:08 -0300
Raw View
On Thu, Jan 10, 2013 at 8:46 PM, Fernando Cacciola
<fernando.cacciola@gmail.com> wrote:
>
> So, what I would like is a composable approach, where an utility
> generates the desired range, in this case from begin to the first
> element failing a predicate, which is them transparently combined with
> whatever algorithm, in this case the existing accumulate.
>
Just to be clear, I'd like that composition to have the same
complexity as the proposed hand-made loop, of course, which is O(n) in
this case.
Otherwise we can just do that right away finding a new last element as
Vlad mentioned.
The driving idea would be similar to passing a filtering iterator as
opposed to creating a new filtered sequence, except that we can't do
that with iterators so what we need is a more flexible definition of
range.
That also means that we would have to come up with a new version of
std::accumulate. I said otherwise, but I meant that we don't need a
new version with it's own hard-coded redefinition of the input range
IOW, I believe that it is the definition of range and its related
utilities what is really needed here rather than a modification of the
algorithms.
Best
--
Fernando Cacciola
SciSoft Consulting, Founder
http://www.scisoft-consulting.com
--
.
Author: Jeremiah Willcock <jewillco@osl.iu.edu>
Date: Thu, 10 Jan 2013 17:58:28 -0500 (EST)
Raw View
On Thu, 10 Jan 2013, Fernando Cacciola wrote:
> On Thu, Jan 10, 2013 at 8:29 PM, Vlad from Moscow <vlad.moscow@mail.ru> wrote:
>> At first let consider a simple assignment: calculate sum of all elements of
>> a integer array after the last negative element.
>> It seems that the assignment should be done in two phases. Firstly the last
>> negative element should be found for example with std::find_if by supplying
>> reverse iterators. Secondly standard algorithm std::accumulate will be used.
>>
>> This approach has a serious shortage. Nothing prevents that the last
>> negative element of the array will be at the same time the first element of
>> the array. So the array will be traversed twice. It is obvious that this
>> approach is ineffective.
>>
>> But how to do the task in more effective way and preserve the symantic of
>> std::accumulate?
>>
>>
>> I suggest a new modification of std::accumulate that resolves this problem.
>>
>>
>> This modifications includes two forms of the algorithm
>>
>>
>> template <class InputIterator, class T, class UnaryPredicate, class
>> BinaryOperation>
>> T accumulate_first_if( InputIterator first,
>> InputIterator last,
>> T init,
>> UnaryPredicate unary_predicate,
>> BinaryOperation binary_operation )
>> {
>> for ( ; first != last && unary_predicate( *first ) ; ++first )
>> {
>> init = binary_operation( init, *first );
>> }
>> return ( init );
>> }
>
> Actually, I'd like to see a more generalized approach.
>
> What you've shown is the case where a standard algorithm should be
> applied to a subset of a sequence, and you noticed that it is wasteful
> to determine the sub-sequence in a separate pass.
> For this case, you are of course correct, and the solution would
> indeed be a loop of the form you just proposed.
>
> However, I'm not sure if providing flavors of the algorithm that
> combine with this particular sub-sequence selection is the best
> approach. It's evident that you'll have to propose the same for pretty
> much all other algorithms. And I wonder if there couldn't be other
> forms of sub-sequencing as well (I'm thinking direct filtering but
> that can be handled by specialized iterators).
This operation can also be handled using the normal std::accumulate; for
your example, you would use:
accumulate(first, last, 0,
[](int a, int b) {if (b < 0) return 0; else return a + b;});
That gives a single pass over the sequence. For accumulating up to the
first negative number, you would want a separate algorithm to allow the
iteration to stop early (you can use std::accumulate if you can afford to
iterate the entire sequence) or the approach Fernando is proposing with a
way to make a range of "all elements up to the first negative one."
-- Jeremiah Willcock
--
.
Author: Vlad from Moscow <vlad.moscow@mail.ru>
Date: Thu, 10 Jan 2013 15:05:36 -0800 (PST)
Raw View
------=_Part_164_13234938.1357859136533
Content-Type: text/plain; charset=KOI8-R
Content-Transfer-Encoding: quoted-printable
=D0=D1=D4=CE=C9=C3=C1, 11 =D1=CE=D7=C1=D2=D1 2013 =C7., 2:46:11 UTC+4 =D0=
=CF=CC=D8=DA=CF=D7=C1=D4=C5=CC=D8 Fernando Cacciola=20
=CE=C1=D0=C9=D3=C1=CC:
>
> On Thu, Jan 10, 2013 at 8:29 PM, Vlad from Moscow <vlad....@mail.ru<javas=
cript:>>=20
> wrote:=20
> > At first let consider a simple assignment: calculate sum of all element=
s=20
> of=20
> > a integer array after the last negative element.=20
> > It seems that the assignment should be done in two phases. Firstly the=
=20
> last=20
> > negative element should be found for example with std::find_if by=20
> supplying=20
> > reverse iterators. Secondly standard algorithm std::accumulate will be=
=20
> used.=20
> >=20
> > This approach has a serious shortage. Nothing prevents that the last=
=20
> > negative element of the array will be at the same time the first elemen=
t=20
> of=20
> > the array. So the array will be traversed twice. It is obvious that=20
> this=20
> > approach is ineffective.=20
> >=20
> > But how to do the task in more effective way and preserve the symantic=
=20
> of=20
> > std::accumulate?=20
> >=20
> >=20
> > I suggest a new modification of std::accumulate that resolves this=20
> problem.=20
> >=20
> >=20
> > This modifications includes two forms of the algorithm=20
> >=20
> >=20
> > template <class InputIterator, class T, class UnaryPredicate, class=20
> > BinaryOperation>=20
> > T accumulate_first_if( InputIterator first,=20
> > InputIterator last,=20
> > T init,=20
> > UnaryPredicate unary_predicate,=20
> > BinaryOperation binary_operation )=20
> > {=20
> > for ( ; first !=3D last && unary_predicate( *first ) ; ++first )=20
> > {=20
> > init =3D binary_operation( init, *first );=20
> > }=20
> > return ( init );=20
> > }=20
>
> Actually, I'd like to see a more generalized approach.=20
>
> What you've shown is the case where a standard algorithm should be=20
> applied to a subset of a sequence, and you noticed that it is wasteful=20
> to determine the sub-sequence in a separate pass.=20
> For this case, you are of course correct, and the solution would=20
> indeed be a loop of the form you just proposed.=20
>
> However, I'm not sure if providing flavors of the algorithm that=20
> combine with this particular sub-sequence selection is the best=20
> approach. It's evident that you'll have to propose the same for pretty=20
> much all other algorithms. And I wonder if there couldn't be other=20
> forms of sub-sequencing as well (I'm thinking direct filtering but=20
> that can be handled by specialized iterators).=20
>
> So, what I would like is a composable approach, where an utility=20
> generates the desired range, in this case from begin to the first=20
> element failing a predicate, which is them transparently combined with=20
> whatever algorithm, in this case the existing accumulate.=20
>
> Best=20
>
> --=20
> Fernando Cacciola=20
> SciSoft Consulting, Founder=20
> http://www.scisoft-consulting.com=20
>
=20
=20
You are right saying that I'll have to propose the same for pretty much=20
all other algorithms. For example the same idiom has to be realized in for=
=20
example std::for_each.
=20
I already wrote about this that I have a whole system of algorithms to=20
suggest. But till now I do not see that my proposals are being adopted. =20
=20
As for std::accumulate this proposal is self-sufficient due to presence of=
=20
the binary operation which enlages its possibility.=20
=20
The only thing that I would append to std::accumulate is=20
std::accumulate_n. But I have some disagreements in what iterator category=
=20
has to be specified.
--=20
------=_Part_164_13234938.1357859136533
Content-Type: text/html; charset=KOI8-R
Content-Transfer-Encoding: quoted-printable
<br>=D0=D1=D4=CE=C9=C3=C1, 11 =D1=CE=D7=C1=D2=D1 2013 =C7., 2:46:11 UT=
C+4 =D0=CF=CC=D8=DA=CF=D7=C1=D4=C5=CC=D8 Fernando Cacciola =CE=C1=D0=C9=D3=
=C1=CC:<blockquote style=3D"margin: 0px 0px 0px 0.8ex; padding-left: 1ex; b=
order-left-color: rgb(204, 204, 204); border-left-width: 1px; border-left-s=
tyle: solid;" class=3D"gmail_quote">On Thu, Jan 10, 2013 at 8:29 PM, Vlad f=
rom Moscow <<a href=3D"javascript:" target=3D"_blank" gdf-obfuscated-mai=
lto=3D"0kiuermoOwsJ">vlad....@mail.ru</a>> wrote:
<br>> At first let consider a simple assignment: calculate sum of all el=
ements of
<br>> a integer array after the last negative element.
<br>> It seems that the assignment should be done in two phases. Firstly=
the last
<br>> negative element should be found for example with std::find_if by =
supplying
<br>> reverse iterators. Secondly standard algorithm std::accumulate wil=
l be used.
<br>>
<br>> This approach has a serious shortage. Nothing prevents that =
the last
<br>> negative element of the array will be at the same time the first e=
lement of
<br>> the array. So the array will be traversed twice. It is obvio=
us that this
<br>> approach is ineffective.
<br>>
<br>> But how to do the task in more effective way and preserve the syma=
ntic of
<br>> std::accumulate?
<br>>
<br>>
<br>> I suggest a new modification of std::accumulate that resolves this=
problem.
<br>>
<br>>
<br>> This modifications includes two forms of the algorithm
<br>>
<br>>
<br>> template <class InputIterator, class T, class UnaryPredicate, c=
lass
<br>> BinaryOperation>
<br>> T accumulate_first_if( InputIterator first,
<br>> &nb=
sp; InputIterator last,
<br>> T init,
<br>> UnaryPredicate unary_predicate,
<br>> BinaryOperation binary_operation )
<br>> {
<br>> for ( ; first !=3D last && unary_predicate( *first )=
; ++first )
<br>> {
<br>> init =3D binary_operation( init, *first );
<br>> }
<br>> return ( init );
<br>> }
<br>
<br>Actually, I'd like to see a more generalized approach.
<br>
<br>What you've shown is the case where a standard algorithm should be
<br>applied to a subset of a sequence, and you noticed that it is wasteful
<br>to determine the sub-sequence in a separate pass.
<br>For this case, you are of course correct, and the solution would
<br>indeed be a loop of the form you just proposed.
<br>
<br>However, I'm not sure if providing flavors of the algorithm that
<br>combine with this particular sub-sequence selection is the best
<br>approach. It's evident that you'll have to propose the same for pretty
<br>much all other algorithms. And I wonder if there couldn't be other
<br>forms of sub-sequencing as well (I'm thinking direct filtering but
<br>that can be handled by specialized iterators).
<br>
<br>So, what I would like is a composable approach, where an utility
<br>generates the desired range, in this case from begin to the first
<br>element failing a predicate, which is them transparently combined with
<br>whatever algorithm, in this case the existing accumulate.
<br>
<br>Best
<br>
<br>--
<br>Fernando Cacciola
<br>SciSoft Consulting, Founder
<br><a href=3D"http://www.scisoft-consulting.com" target=3D"_blank">http://=
www.scisoft-consulting.<wbr>com</a>
<br></blockquote><div> </div><div> </div><div>You are right sayin=
g that I'll have to propose the same for pretty much all other a=
lgorithms. For example the same idiom has to be realized in for =
example std::for_each.</div><div> </div><div>I already wrote about thi=
s that I have a whole system of algorithms to suggest. But till now I do no=
t see that my proposals are being adopted. </div><div> </div><di=
v>As for std::accumulate this proposal is self-sufficient du=
e to presence of the binary operation which enlages its possibility. <=
/div><div> </div><div>The only thing that I would append to std:=
:accumulate is std::accumulate_n. But I have some disagreements in what ite=
rator category has to be specified.</div>
<p></p>
-- <br />
<br />
<br />
<br />
------=_Part_164_13234938.1357859136533--
.
Author: Fernando Cacciola <fernando.cacciola@gmail.com>
Date: Thu, 10 Jan 2013 20:19:17 -0300
Raw View
On Thu, Jan 10, 2013 at 9:05 PM, Vlad from Moscow <vlad.moscow@mail.ru> wro=
te:
>
> =D0=D1=D4=CE=C9=C3=C1, 11 =D1=CE=D7=C1=D2=D1 2013 =C7., 2:46:11 UTC+4 =D0=
=CF=CC=D8=DA=CF=D7=C1=D4=C5=CC=D8 Fernando Cacciola
> =CE=C1=D0=C9=D3=C1=CC:
>>
>> On Thu, Jan 10, 2013 at 8:29 PM, Vlad from Moscow <vlad....@mail.ru>
>> wrote:
>> > At first let consider a simple assignment: calculate sum of all elemen=
ts
>> > of
>> > a integer array after the last negative element.
>> > It seems that the assignment should be done in two phases. Firstly the
>> > last
>> > negative element should be found for example with std::find_if by
>> > supplying
>> > reverse iterators. Secondly standard algorithm std::accumulate will be
>> > used.
>> >
>> > This approach has a serious shortage. Nothing prevents that the last
>> > negative element of the array will be at the same time the first eleme=
nt
>> > of
>> > the array. So the array will be traversed twice. It is obvious that
>> > this
>> > approach is ineffective.
>> >
>> > But how to do the task in more effective way and preserve the symantic
>> > of
>> > std::accumulate?
>> >
>> >
>> > I suggest a new modification of std::accumulate that resolves this
>> > problem.
>> >
>> >
>> > This modifications includes two forms of the algorithm
>> >
>> >
>> > template <class InputIterator, class T, class UnaryPredicate, class
>> > BinaryOperation>
>> > T accumulate_first_if( InputIterator first,
>> > InputIterator last,
>> > T init,
>> > UnaryPredicate unary_predicate,
>> > BinaryOperation binary_operation )
>> > {
>> > for ( ; first !=3D last && unary_predicate( *first ) ; ++first )
>> > {
>> > init =3D binary_operation( init, *first );
>> > }
>> > return ( init );
>> > }
>>
>> Actually, I'd like to see a more generalized approach.
>>
>> What you've shown is the case where a standard algorithm should be
>> applied to a subset of a sequence, and you noticed that it is wasteful
>> to determine the sub-sequence in a separate pass.
>> For this case, you are of course correct, and the solution would
>> indeed be a loop of the form you just proposed.
>>
>> However, I'm not sure if providing flavors of the algorithm that
>> combine with this particular sub-sequence selection is the best
>> approach. It's evident that you'll have to propose the same for pretty
>> much all other algorithms. And I wonder if there couldn't be other
>> forms of sub-sequencing as well (I'm thinking direct filtering but
>> that can be handled by specialized iterators).
>>
>> So, what I would like is a composable approach, where an utility
>> generates the desired range, in this case from begin to the first
>> element failing a predicate, which is them transparently combined with
>> whatever algorithm, in this case the existing accumulate.
>>
>> Best
>>
>> --
>> Fernando Cacciola
>> SciSoft Consulting, Founder
>> http://www.scisoft-consulting.com
>
>
>
> You are right saying that I'll have to propose the same for pretty much =
all
> other algorithms. For example the same idiom has to be realized in for
> example std::for_each.
>
> I already wrote about this that I have a whole system of algorithms to
> suggest. But till now I do not see that my proposals are being adopted.
>
> As for std::accumulate this proposal is self-sufficient due to presence o=
f
> the binary operation which enlages its possibility.
>
> The only thing that I would append to std::accumulate is std::accumulate=
_n.
In there, as well, the difference is in the definition of the input
range. Hence it would be another candidate for the type of composition
I'm advocating.
This is off-topic but FWIW using iteration over a range allows for
other loop forms that are just not possible with an iterator pair,
such as circulating a cycle, so I would prefer to see the work put on
that instead.
Now... are the other algorithms you mentioned also just variations of
the existing ones but operating over different ranges, or there are
effectively new algorithms?
Best
--
Fernando Cacciola
SciSoft Consulting, Founder
http://www.scisoft-consulting.com
--=20
.
Author: Vlad from Moscow <vlad.moscow@mail.ru>
Date: Thu, 10 Jan 2013 16:24:44 -0800 (PST)
Raw View
------=_Part_185_6065896.1357863884630
Content-Type: text/plain; charset=KOI8-R
Content-Transfer-Encoding: quoted-printable
=D0=D1=D4=CE=C9=C3=C1, 11 =D1=CE=D7=C1=D2=D1 2013 =C7., 3:19:17 UTC+4 =D0=
=CF=CC=D8=DA=CF=D7=C1=D4=C5=CC=D8 Fernando Cacciola=20
=CE=C1=D0=C9=D3=C1=CC:
>
> On Thu, Jan 10, 2013 at 9:05 PM, Vlad from Moscow <vlad....@mail.ru<javas=
cript:>>=20
> wrote:=20
> >=20
> > =D0=D1=D4=CE=C9=C3=C1, 11 =D1=CE=D7=C1=D2=D1 2013 =C7., 2:46:11 UTC+4 =
=D0=CF=CC=D8=DA=CF=D7=C1=D4=C5=CC=D8 Fernando Cacciola=20
> > =CE=C1=D0=C9=D3=C1=CC:=20
> >>=20
> >> On Thu, Jan 10, 2013 at 8:29 PM, Vlad from Moscow <vlad....@mail.ru>=
=20
> >> wrote:=20
> >> > At first let consider a simple assignment: calculate sum of all=20
> elements=20
> >> > of=20
> >> > a integer array after the last negative element.=20
> >> > It seems that the assignment should be done in two phases. Firstly=
=20
> the=20
> >> > last=20
> >> > negative element should be found for example with std::find_if by=20
> >> > supplying=20
> >> > reverse iterators. Secondly standard algorithm std::accumulate will=
=20
> be=20
> >> > used.=20
> >> >=20
> >> > This approach has a serious shortage. Nothing prevents that the las=
t=20
> >> > negative element of the array will be at the same time the first=20
> element=20
> >> > of=20
> >> > the array. So the array will be traversed twice. It is obvious that=
=20
> >> > this=20
> >> > approach is ineffective.=20
> >> >=20
> >> > But how to do the task in more effective way and preserve the=20
> symantic=20
> >> > of=20
> >> > std::accumulate?=20
> >> >=20
> >> >=20
> >> > I suggest a new modification of std::accumulate that resolves this=
=20
> >> > problem.=20
> >> >=20
> >> >=20
> >> > This modifications includes two forms of the algorithm=20
> >> >=20
> >> >=20
> >> > template <class InputIterator, class T, class UnaryPredicate, class=
=20
> >> > BinaryOperation>=20
> >> > T accumulate_first_if( InputIterator first,=20
> >> > InputIterator last,=20
> >> > T init,=20
> >> > UnaryPredicate unary_predicate,=20
> >> > BinaryOperation binary_operation )=20
> >> > {=20
> >> > for ( ; first !=3D last && unary_predicate( *first ) ; ++first )=20
> >> > {=20
> >> > init =3D binary_operation( init, *first );=20
> >> > }=20
> >> > return ( init );=20
> >> > }=20
> >>=20
> >> Actually, I'd like to see a more generalized approach.=20
> >>=20
> >> What you've shown is the case where a standard algorithm should be=20
> >> applied to a subset of a sequence, and you noticed that it is wasteful=
=20
> >> to determine the sub-sequence in a separate pass.=20
> >> For this case, you are of course correct, and the solution would=20
> >> indeed be a loop of the form you just proposed.=20
> >>=20
> >> However, I'm not sure if providing flavors of the algorithm that=20
> >> combine with this particular sub-sequence selection is the best=20
> >> approach. It's evident that you'll have to propose the same for pretty=
=20
> >> much all other algorithms. And I wonder if there couldn't be other=20
> >> forms of sub-sequencing as well (I'm thinking direct filtering but=20
> >> that can be handled by specialized iterators).=20
> >>=20
> >> So, what I would like is a composable approach, where an utility=20
> >> generates the desired range, in this case from begin to the first=20
> >> element failing a predicate, which is them transparently combined with=
=20
> >> whatever algorithm, in this case the existing accumulate.=20
> >>=20
> >> Best=20
> >>=20
> >> --=20
> >> Fernando Cacciola=20
> >> SciSoft Consulting, Founder=20
> >> http://www.scisoft-consulting.com=20
> >=20
> >=20
> >=20
> > You are right saying that I'll have to propose the same for pretty muc=
h=20
> all=20
> > other algorithms. For example the same idiom has to be realized in for=
=20
> > example std::for_each.=20
> >=20
> > I already wrote about this that I have a whole system of algorithms to=
=20
> > suggest. But till now I do not see that my proposals are being adopted.=
=20
> >=20
> > As for std::accumulate this proposal is self-sufficient due to presence=
=20
> of=20
> > the binary operation which enlages its possibility.=20
> >=20
> > The only thing that I would append to std::accumulate is=20
> std::accumulate_n.=20
>
> In there, as well, the difference is in the definition of the input=20
> range. Hence it would be another candidate for the type of composition=20
> I'm advocating.=20
>
> This is off-topic but FWIW using iteration over a range allows for=20
> other loop forms that are just not possible with an iterator pair,=20
> such as circulating a cycle, so I would prefer to see the work put on=20
> that instead.=20
>
> Now... are the other algorithms you mentioned also just variations of=20
> the existing ones but operating over different ranges, or there are=20
> effectively new algorithms?=20
>
> Best=20
>
> --=20
> Fernando Cacciola=20
> SciSoft Consulting, Founder=20
> http://www.scisoft-consulting.com=20
>
=20
=20
Yes, they are variants of existing ones that makes the family of algorithm=
=20
complete and logically consustent=20
--=20
------=_Part_185_6065896.1357863884630
Content-Type: text/html; charset=KOI8-R
Content-Transfer-Encoding: quoted-printable
<br>=D0=D1=D4=CE=C9=C3=C1, 11 =D1=CE=D7=C1=D2=D1 2013 =C7., 3:19:17 UT=
C+4 =D0=CF=CC=D8=DA=CF=D7=C1=D4=C5=CC=D8 Fernando Cacciola =CE=C1=D0=C9=D3=
=C1=CC:<blockquote style=3D"margin: 0px 0px 0px 0.8ex; padding-left: 1ex; b=
order-left-color: rgb(204, 204, 204); border-left-width: 1px; border-left-s=
tyle: solid;" class=3D"gmail_quote">On Thu, Jan 10, 2013 at 9:05 PM, Vlad f=
rom Moscow <<a href=3D"javascript:" target=3D"_blank" gdf-obfuscated-mai=
lto=3D"uwbu7MZjdC8J">vlad....@mail.ru</a>> wrote:
<br>>
<br>> =D0=D1=D4=CE=C9=C3=C1, 11 =D1=CE=D7=C1=D2=D1 2013 =C7., 2:46:11 UT=
C+4 =D0=CF=CC=D8=DA=CF=D7=C1=D4=C5=CC=D8 Fernando Cacciola
<br>> =CE=C1=D0=C9=D3=C1=CC:
<br>>>
<br>>> On Thu, Jan 10, 2013 at 8:29 PM, Vlad from Moscow <<a>vlad.=
....@mail.ru</a>>
<br>>> wrote:
<br>>> > At first let consider a simple assignment: calculate sum =
of all elements
<br>>> > of
<br>>> > a integer array after the last negative element.
<br>>> > It seems that the assignment should be done in two phases=
.. Firstly the
<br>>> > last
<br>>> > negative element should be found for example with std::fi=
nd_if by
<br>>> > supplying
<br>>> > reverse iterators. Secondly standard algorithm std::accum=
ulate will be
<br>>> > used.
<br>>> >
<br>>> > This approach has a serious shortage. Nothing preve=
nts that the last
<br>>> > negative element of the array will be at the same time th=
e first element
<br>>> > of
<br>>> > the array. So the array will be traversed twice. It=
is obvious that
<br>>> > this
<br>>> > approach is ineffective.
<br>>> >
<br>>> > But how to do the task in more effective way and preserve=
the symantic
<br>>> > of
<br>>> > std::accumulate?
<br>>> >
<br>>> >
<br>>> > I suggest a new modification of std::accumulate that reso=
lves this
<br>>> > problem.
<br>>> >
<br>>> >
<br>>> > This modifications includes two forms of the algorithm
<br>>> >
<br>>> >
<br>>> > template <class InputIterator, class T, class UnaryPre=
dicate, class
<br>>> > BinaryOperation>
<br>>> > T accumulate_first_if( InputIterator first,
<br>>> > &=
nbsp; InputIterator last,
<br>>> > T init,
<br>>> > UnaryPredicate unary_predicat=
e,
<br>>> > BinaryOperation binary_operat=
ion )
<br>>> > {
<br>>> > for ( ; first !=3D last && unary_predicate(=
*first ) ; ++first )
<br>>> > {
<br>>> > init =3D binary_operation( init, *first );
<br>>> > }
<br>>> > return ( init );
<br>>> > }
<br>>>
<br>>> Actually, I'd like to see a more generalized approach.
<br>>>
<br>>> What you've shown is the case where a standard algorithm shoul=
d be
<br>>> applied to a subset of a sequence, and you noticed that it is =
wasteful
<br>>> to determine the sub-sequence in a separate pass.
<br>>> For this case, you are of course correct, and the solution wou=
ld
<br>>> indeed be a loop of the form you just proposed.
<br>>>
<br>>> However, I'm not sure if providing flavors of the algorithm th=
at
<br>>> combine with this particular sub-sequence selection is the bes=
t
<br>>> approach. It's evident that you'll have to propose the same fo=
r pretty
<br>>> much all other algorithms. And I wonder if there couldn't be o=
ther
<br>>> forms of sub-sequencing as well (I'm thinking direct filtering=
but
<br>>> that can be handled by specialized iterators).
<br>>>
<br>>> So, what I would like is a composable approach, where an utili=
ty
<br>>> generates the desired range, in this case from begin to the fi=
rst
<br>>> element failing a predicate, which is them transparently combi=
ned with
<br>>> whatever algorithm, in this case the existing accumulate.
<br>>>
<br>>> Best
<br>>>
<br>>> --
<br>>> Fernando Cacciola
<br>>> SciSoft Consulting, Founder
<br>>> <a href=3D"http://www.scisoft-consulting.com" target=3D"_blank=
">http://www.scisoft-consulting.<wbr>com</a>
<br>>
<br>>
<br>>
<br>> You are right saying that I'll have to propose the same for =
pretty much all
<br>> other algorithms. For example the same idiom has to be realized in=
for
<br>> example std::for_each.
<br>>
<br>> I already wrote about this that I have a whole system of algorithm=
s to
<br>> suggest. But till now I do not see that my proposals are being ado=
pted.
<br>>
<br>> As for std::accumulate this proposal is self-sufficient due to pre=
sence of
<br>> the binary operation which enlages its possibility.
<br>>
<br>> The only thing that I would append to std::accumulate is std=
::accumulate_n.
<br>
<br>In there, as well, the difference is in the definition of the input
<br>range. Hence it would be another candidate for the type of composition
<br>I'm advocating.
<br>
<br>This is off-topic but FWIW using iteration over a range allows for
<br>other loop forms that are just not possible with an iterator pair,
<br>such as circulating a cycle, so I would prefer to see the work put on
<br>that instead.
<br>
<br>Now... are the other algorithms you mentioned also just variations of
<br>the existing ones but operating over different ranges, or there are
<br>effectively new algorithms?
<br>
<br>Best
<br>
<br>--
<br>Fernando Cacciola
<br>SciSoft Consulting, Founder
<br><a href=3D"http://www.scisoft-consulting.com" target=3D"_blank">http://=
www.scisoft-consulting.<wbr>com</a>
<br></blockquote><div> </div><div> </div><div>Yes, they are varia=
nts of existing ones that makes the family of algorithm complete and logica=
lly consustent </div>
<p></p>
-- <br />
<br />
<br />
<br />
------=_Part_185_6065896.1357863884630--
.
Author: Vlad from Moscow <vlad.moscow@mail.ru>
Date: Thu, 10 Jan 2013 17:38:25 -0800 (PST)
Raw View
------=_Part_210_17579543.1357868305320
Content-Type: text/plain; charset=KOI8-R
Content-Transfer-Encoding: quoted-printable
=D0=D1=D4=CE=C9=C3=C1, 11 =D1=CE=D7=C1=D2=D1 2013 =C7., 2:58:28 UTC+4 =D0=
=CF=CC=D8=DA=CF=D7=C1=D4=C5=CC=D8 jewillco =CE=C1=D0=C9=D3=C1=CC:
>
> On Thu, 10 Jan 2013, Fernando Cacciola wrote:=20
>
> > On Thu, Jan 10, 2013 at 8:29 PM, Vlad from Moscow <vlad....@mail.ru<jav=
ascript:>>=20
> wrote:=20
> >> At first let consider a simple assignment: calculate sum of all=20
> elements of=20
> >> a integer array after the last negative element.=20
> >> It seems that the assignment should be done in two phases. Firstly the=
=20
> last=20
> >> negative element should be found for example with std::find_if by=20
> supplying=20
> >> reverse iterators. Secondly standard algorithm std::accumulate will be=
=20
> used.=20
> >>=20
> >> This approach has a serious shortage. Nothing prevents that the last=
=20
> >> negative element of the array will be at the same time the first=20
> element of=20
> >> the array. So the array will be traversed twice. It is obvious that=
=20
> this=20
> >> approach is ineffective.=20
> >>=20
> >> But how to do the task in more effective way and preserve the symantic=
=20
> of=20
> >> std::accumulate?=20
> >>=20
> >>=20
> >> I suggest a new modification of std::accumulate that resolves this=20
> problem.=20
> >>=20
> >>=20
> >> This modifications includes two forms of the algorithm=20
> >>=20
> >>=20
> >> template <class InputIterator, class T, class UnaryPredicate, class=20
> >> BinaryOperation>=20
> >> T accumulate_first_if( InputIterator first,=20
> >> InputIterator last,=20
> >> T init,=20
> >> UnaryPredicate unary_predicate,=20
> >> BinaryOperation binary_operation )=20
> >> {=20
> >> for ( ; first !=3D last && unary_predicate( *first ) ; ++first )=20
> >> {=20
> >> init =3D binary_operation( init, *first );=20
> >> }=20
> >> return ( init );=20
> >> }=20
> >=20
> > Actually, I'd like to see a more generalized approach.=20
> >=20
> > What you've shown is the case where a standard algorithm should be=20
> > applied to a subset of a sequence, and you noticed that it is wasteful=
=20
> > to determine the sub-sequence in a separate pass.=20
> > For this case, you are of course correct, and the solution would=20
> > indeed be a loop of the form you just proposed.=20
> >=20
> > However, I'm not sure if providing flavors of the algorithm that=20
> > combine with this particular sub-sequence selection is the best=20
> > approach. It's evident that you'll have to propose the same for pretty=
=20
> > much all other algorithms. And I wonder if there couldn't be other=20
> > forms of sub-sequencing as well (I'm thinking direct filtering but=20
> > that can be handled by specialized iterators).=20
>
> This operation can also be handled using the normal std::accumulate; for=
=20
> your example, you would use:=20
>
> accumulate(first, last, 0,=20
> [](int a, int b) {if (b < 0) return 0; else return a + b;});=
=20
>
> That gives a single pass over the sequence. For accumulating up to the=
=20
> first negative number, you would want a separate algorithm to allow the=
=20
> iteration to stop early (you can use std::accumulate if you can afford to=
=20
> iterate the entire sequence) or the approach Fernando is proposing with a=
=20
> way to make a range of "all elements up to the first negative one."=20
>
> -- Jeremiah Willcock=20
>
=20
It is a remarkable idea but it is what I wanted to escape suggesting the=20
new algorithm. =20
--=20
------=_Part_210_17579543.1357868305320
Content-Type: text/html; charset=KOI8-R
Content-Transfer-Encoding: quoted-printable
<br>=D0=D1=D4=CE=C9=C3=C1, 11 =D1=CE=D7=C1=D2=D1 2013 =C7., 2:58:28 UT=
C+4 =D0=CF=CC=D8=DA=CF=D7=C1=D4=C5=CC=D8 jewillco =CE=C1=D0=C9=D3=C1=CC:<bl=
ockquote style=3D"margin: 0px 0px 0px 0.8ex; padding-left: 1ex; border-left=
-color: rgb(204, 204, 204); border-left-width: 1px; border-left-style: soli=
d;" class=3D"gmail_quote">On Thu, 10 Jan 2013, Fernando Cacciola wrote:
<br>
<br>> On Thu, Jan 10, 2013 at 8:29 PM, Vlad from Moscow <<a href=3D"j=
avascript:" target=3D"_blank" gdf-obfuscated-mailto=3D"wZBwp3VnzpQJ">vlad..=
...@mail.ru</a>> wrote:
<br>>> At first let consider a simple assignment: calculate sum of al=
l elements of
<br>>> a integer array after the last negative element.
<br>>> It seems that the assignment should be done in two phases. Fir=
stly the last
<br>>> negative element should be found for example with std::find_if=
by supplying
<br>>> reverse iterators. Secondly standard algorithm std::accumulate=
will be used.
<br>>>
<br>>> This approach has a serious shortage. Nothing prevents t=
hat the last
<br>>> negative element of the array will be at the same time the fir=
st element of
<br>>> the array. So the array will be traversed twice. It is o=
bvious that this
<br>>> approach is ineffective.
<br>>>
<br>>> But how to do the task in more effective way and preserve the =
symantic of
<br>>> std::accumulate?
<br>>>
<br>>>
<br>>> I suggest a new modification of std::accumulate that resolves =
this problem.
<br>>>
<br>>>
<br>>> This modifications includes two forms of the algorithm
<br>>>
<br>>>
<br>>> template <class InputIterator, class T, class UnaryPredicat=
e, class
<br>>> BinaryOperation>
<br>>> T accumulate_first_if( InputIterator first,
<br>>> =
InputIterator last,
<br>>> T init,
<br>>> UnaryPredicate unary_predicate,
<br>>> BinaryOperation binary_operation )
<br>>> {
<br>>> for ( ; first !=3D last && unary_predicate( *fir=
st ) ; ++first )
<br>>> {
<br>>> init =3D binary_operation( init, *first );
<br>>> }
<br>>> return ( init );
<br>>> }
<br>>
<br>> Actually, I'd like to see a more generalized approach.
<br>>
<br>> What you've shown is the case where a standard algorithm should be
<br>> applied to a subset of a sequence, and you noticed that it is wast=
eful
<br>> to determine the sub-sequence in a separate pass.
<br>> For this case, you are of course correct, and the solution would
<br>> indeed be a loop of the form you just proposed.
<br>>
<br>> However, I'm not sure if providing flavors of the algorithm that
<br>> combine with this particular sub-sequence selection is the best
<br>> approach. It's evident that you'll have to propose the same for pr=
etty
<br>> much all other algorithms. And I wonder if there couldn't be other
<br>> forms of sub-sequencing as well (I'm thinking direct filtering but
<br>> that can be handled by specialized iterators).
<br>
<br>This operation can also be handled using the normal std::accumulate; fo=
r=20
<br>your example, you would use:
<br>
<br>accumulate(first, last, 0,
<br> [](int a, int b) {if (b < =
0) return 0; else return a + b;});
<br>
<br>That gives a single pass over the sequence. For accumulating up t=
o the=20
<br>first negative number, you would want a separate algorithm to allow the=
=20
<br>iteration to stop early (you can use std::accumulate if you can afford =
to=20
<br>iterate the entire sequence) or the approach Fernando is proposing with=
a=20
<br>way to make a range of "all elements up to the first negative one."
<br>
<br>-- Jeremiah Willcock
<br></blockquote><div> </div><div>It is a remarkable idea but it =
is what I wanted to escape suggesting the new algorithm. </=
div>
<p></p>
-- <br />
<br />
<br />
<br />
------=_Part_210_17579543.1357868305320--
.
Author: Nicol Bolas <jmckesson@gmail.com>
Date: Thu, 10 Jan 2013 17:57:40 -0800 (PST)
Raw View
------=_Part_324_2273437.1357869460441
Content-Type: text/plain; charset=KOI8-R
Content-Transfer-Encoding: quoted-printable
On Thursday, January 10, 2013 5:38:25 PM UTC-8, Vlad from Moscow wrote:
>
>
> =D0=D1=D4=CE=C9=C3=C1, 11 =D1=CE=D7=C1=D2=D1 2013 =C7., 2:58:28 UTC+4 =D0=
=CF=CC=D8=DA=CF=D7=C1=D4=C5=CC=D8 jewillco =CE=C1=D0=C9=D3=C1=CC:
>>
>> On Thu, 10 Jan 2013, Fernando Cacciola wrote:=20
>>
>> > On Thu, Jan 10, 2013 at 8:29 PM, Vlad from Moscow <vlad....@mail.ru>=
=20
>> wrote:=20
>> >> At first let consider a simple assignment: calculate sum of all=20
>> elements of=20
>> >> a integer array after the last negative element.=20
>> >> It seems that the assignment should be done in two phases. Firstly th=
e=20
>> last=20
>> >> negative element should be found for example with std::find_if by=20
>> supplying=20
>> >> reverse iterators. Secondly standard algorithm std::accumulate will b=
e=20
>> used.=20
>> >>=20
>> >> This approach has a serious shortage. Nothing prevents that the last=
=20
>> >> negative element of the array will be at the same time the first=20
>> element of=20
>> >> the array. So the array will be traversed twice. It is obvious that=
=20
>> this=20
>> >> approach is ineffective.=20
>> >>=20
>> >> But how to do the task in more effective way and preserve the symanti=
c=20
>> of=20
>> >> std::accumulate?=20
>> >>=20
>> >>=20
>> >> I suggest a new modification of std::accumulate that resolves this=20
>> problem.=20
>> >>=20
>> >>=20
>> >> This modifications includes two forms of the algorithm=20
>> >>=20
>> >>=20
>> >> template <class InputIterator, class T, class UnaryPredicate, class=
=20
>> >> BinaryOperation>=20
>> >> T accumulate_first_if( InputIterator first,=20
>> >> InputIterator last,=20
>> >> T init,=20
>> >> UnaryPredicate unary_predicate,=20
>> >> BinaryOperation binary_operation )=20
>> >> {=20
>> >> for ( ; first !=3D last && unary_predicate( *first ) ; ++first )=20
>> >> {=20
>> >> init =3D binary_operation( init, *first );=20
>> >> }=20
>> >> return ( init );=20
>> >> }=20
>> >=20
>> > Actually, I'd like to see a more generalized approach.=20
>> >=20
>> > What you've shown is the case where a standard algorithm should be=20
>> > applied to a subset of a sequence, and you noticed that it is wasteful=
=20
>> > to determine the sub-sequence in a separate pass.=20
>> > For this case, you are of course correct, and the solution would=20
>> > indeed be a loop of the form you just proposed.=20
>> >=20
>> > However, I'm not sure if providing flavors of the algorithm that=20
>> > combine with this particular sub-sequence selection is the best=20
>> > approach. It's evident that you'll have to propose the same for pretty=
=20
>> > much all other algorithms. And I wonder if there couldn't be other=20
>> > forms of sub-sequencing as well (I'm thinking direct filtering but=20
>> > that can be handled by specialized iterators).=20
>>
>> This operation can also be handled using the normal std::accumulate; for=
=20
>> your example, you would use:=20
>>
>> accumulate(first, last, 0,=20
>> [](int a, int b) {if (b < 0) return 0; else return a + b;});=
=20
>>
>> That gives a single pass over the sequence. For accumulating up to the=
=20
>> first negative number, you would want a separate algorithm to allow the=
=20
>> iteration to stop early (you can use std::accumulate if you can afford t=
o=20
>> iterate the entire sequence) or the approach Fernando is proposing with =
a=20
>> way to make a range of "all elements up to the first negative one."=20
>>
>> -- Jeremiah Willcock=20
>>
> =20
> It is a remarkable idea but it is what I wanted to escape suggesting the=
=20
> new algorithm. =20
>
That's part of the point, and it's the reason why we have lambdas: so that=
=20
we don't have to have a new algorithm for every corner case imaginable.
Code-wise, his std::accumulate+lambda is in every way equivalent to what=20
you proposed. It's not particularly long, and it's very clear as to what it=
=20
does. Odds are good that they'll even compile to the same code.
So why do we need a whole new function for something that we can trivially=
=20
do ourselves?
While this algorithm would certainly see use, I don't see the *need* to=20
have it as an algorithm in the standard library. It's not used frequently=
=20
enough to need such canonization, and we can achieve the same effect with a=
=20
simple lambda.
--=20
------=_Part_324_2273437.1357869460441
Content-Type: text/html; charset=KOI8-R
Content-Transfer-Encoding: quoted-printable
On Thursday, January 10, 2013 5:38:25 PM UTC-8, Vlad from Moscow wrote:<blo=
ckquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-=
left: 1px #ccc solid;padding-left: 1ex;"><br>=D0=D1=D4=CE=C9=C3=C1, 11 =D1=
=CE=D7=C1=D2=D1 2013 =C7., 2:58:28 UTC+4 =D0=CF=CC=D8=DA=CF=D7=C1=D4=
=C5=CC=D8 jewillco =CE=C1=D0=C9=D3=C1=CC:<blockquote style=3D"margin:0px 0p=
x 0px 0.8ex;padding-left:1ex;border-left-color:rgb(204,204,204);border-left=
-width:1px;border-left-style:solid" class=3D"gmail_quote">On Thu, 10 Jan 20=
13, Fernando Cacciola wrote:
<br>
<br>> On Thu, Jan 10, 2013 at 8:29 PM, Vlad from Moscow <<a>vlad....@=
mail.ru</a>> wrote:
<br>>> At first let consider a simple assignment: calculate sum of al=
l elements of
<br>>> a integer array after the last negative element.
<br>>> It seems that the assignment should be done in two phases. Fir=
stly the last
<br>>> negative element should be found for example with std::find_if=
by supplying
<br>>> reverse iterators. Secondly standard algorithm std::accumulate=
will be used.
<br>>>
<br>>> This approach has a serious shortage. Nothing prevents t=
hat the last
<br>>> negative element of the array will be at the same time the fir=
st element of
<br>>> the array. So the array will be traversed twice. It is o=
bvious that this
<br>>> approach is ineffective.
<br>>>
<br>>> But how to do the task in more effective way and preserve the =
symantic of
<br>>> std::accumulate?
<br>>>
<br>>>
<br>>> I suggest a new modification of std::accumulate that resolves =
this problem.
<br>>>
<br>>>
<br>>> This modifications includes two forms of the algorithm
<br>>>
<br>>>
<br>>> template <class InputIterator, class T, class UnaryPredicat=
e, class
<br>>> BinaryOperation>
<br>>> T accumulate_first_if( InputIterator first,
<br>>> =
InputIterator last,
<br>>> T init,
<br>>> UnaryPredicate unary_predicate,
<br>>> BinaryOperation binary_operation )
<br>>> {
<br>>> for ( ; first !=3D last && unary_predicate( *fir=
st ) ; ++first )
<br>>> {
<br>>> init =3D binary_operation( init, *first );
<br>>> }
<br>>> return ( init );
<br>>> }
<br>>
<br>> Actually, I'd like to see a more generalized approach.
<br>>
<br>> What you've shown is the case where a standard algorithm should be
<br>> applied to a subset of a sequence, and you noticed that it is wast=
eful
<br>> to determine the sub-sequence in a separate pass.
<br>> For this case, you are of course correct, and the solution would
<br>> indeed be a loop of the form you just proposed.
<br>>
<br>> However, I'm not sure if providing flavors of the algorithm that
<br>> combine with this particular sub-sequence selection is the best
<br>> approach. It's evident that you'll have to propose the same for pr=
etty
<br>> much all other algorithms. And I wonder if there couldn't be other
<br>> forms of sub-sequencing as well (I'm thinking direct filtering but
<br>> that can be handled by specialized iterators).
<br>
<br>This operation can also be handled using the normal std::accumulate; fo=
r=20
<br>your example, you would use:
<br>
<br>accumulate(first, last, 0,
<br> [](int a, int b) {if (b < =
0) return 0; else return a + b;});
<br>
<br>That gives a single pass over the sequence. For accumulating up t=
o the=20
<br>first negative number, you would want a separate algorithm to allow the=
=20
<br>iteration to stop early (you can use std::accumulate if you can afford =
to=20
<br>iterate the entire sequence) or the approach Fernando is proposing with=
a=20
<br>way to make a range of "all elements up to the first negative one."
<br>
<br>-- Jeremiah Willcock
<br></blockquote><div> </div><div>It is a remarkable idea but it =
is what I wanted to escape suggesting the new algorithm. </=
div></blockquote><div><br>That's part of the point, and it's the reason why=
we have lambdas: so that we don't have to have a new algorithm for every c=
orner case imaginable.<br><br>Code-wise, his std::accumulate+lambda is in e=
very way equivalent to what you proposed. It's not particularly long, and i=
t's very clear as to what it does. Odds are good that they'll even compile =
to the same code.<br><br>So why do we need a whole new function for somethi=
ng that we can trivially do ourselves?<br><br>While this algorithm would ce=
rtainly see use, I don't see the <i>need</i> to have it as an algorithm in =
the standard library. It's not used frequently enough to need such canoniza=
tion, and we can achieve the same effect with a simple lambda.<br></div>
<p></p>
-- <br />
<br />
<br />
<br />
------=_Part_324_2273437.1357869460441--
.
Author: Vlad from Moscow <vlad.moscow@mail.ru>
Date: Thu, 10 Jan 2013 18:31:42 -0800 (PST)
Raw View
------=_Part_231_3368335.1357871502220
Content-Type: text/plain; charset=KOI8-R
Content-Transfer-Encoding: quoted-printable
=D0=D1=D4=CE=C9=C3=C1, 11 =D1=CE=D7=C1=D2=D1 2013 =C7., 5:57:40 UTC+4 =D0=
=CF=CC=D8=DA=CF=D7=C1=D4=C5=CC=D8 Nicol Bolas =CE=C1=D0=C9=D3=C1=CC:
>
> On Thursday, January 10, 2013 5:38:25 PM UTC-8, Vlad from Moscow wrote:
>>
>>
>> =D0=D1=D4=CE=C9=C3=C1, 11 =D1=CE=D7=C1=D2=D1 2013 =C7., 2:58:28 UTC+4 =
=D0=CF=CC=D8=DA=CF=D7=C1=D4=C5=CC=D8 jewillco =CE=C1=D0=C9=D3=C1=CC:
>>>
>>> On Thu, 10 Jan 2013, Fernando Cacciola wrote:=20
>>>
>>> > On Thu, Jan 10, 2013 at 8:29 PM, Vlad from Moscow <vlad....@mail.ru>=
=20
>>> wrote:=20
>>> >> At first let consider a simple assignment: calculate sum of all=20
>>> elements of=20
>>> >> a integer array after the last negative element.=20
>>> >> It seems that the assignment should be done in two phases. Firstly=
=20
>>> the last=20
>>> >> negative element should be found for example with std::find_if by=20
>>> supplying=20
>>> >> reverse iterators. Secondly standard algorithm std::accumulate will=
=20
>>> be used.=20
>>> >>=20
>>> >> This approach has a serious shortage. Nothing prevents that the las=
t=20
>>> >> negative element of the array will be at the same time the first=20
>>> element of=20
>>> >> the array. So the array will be traversed twice. It is obvious that=
=20
>>> this=20
>>> >> approach is ineffective.=20
>>> >>=20
>>> >> But how to do the task in more effective way and preserve the=20
>>> symantic of=20
>>> >> std::accumulate?=20
>>> >>=20
>>> >>=20
>>> >> I suggest a new modification of std::accumulate that resolves this=
=20
>>> problem.=20
>>> >>=20
>>> >>=20
>>> >> This modifications includes two forms of the algorithm=20
>>> >>=20
>>> >>=20
>>> >> template <class InputIterator, class T, class UnaryPredicate, class=
=20
>>> >> BinaryOperation>=20
>>> >> T accumulate_first_if( InputIterator first,=20
>>> >> InputIterator last,=20
>>> >> T init,=20
>>> >> UnaryPredicate unary_predicate,=20
>>> >> BinaryOperation binary_operation )=20
>>> >> {=20
>>> >> for ( ; first !=3D last && unary_predicate( *first ) ; ++first )=20
>>> >> {=20
>>> >> init =3D binary_operation( init, *first );=20
>>> >> }=20
>>> >> return ( init );=20
>>> >> }=20
>>> >=20
>>> > Actually, I'd like to see a more generalized approach.=20
>>> >=20
>>> > What you've shown is the case where a standard algorithm should be=20
>>> > applied to a subset of a sequence, and you noticed that it is wastefu=
l=20
>>> > to determine the sub-sequence in a separate pass.=20
>>> > For this case, you are of course correct, and the solution would=20
>>> > indeed be a loop of the form you just proposed.=20
>>> >=20
>>> > However, I'm not sure if providing flavors of the algorithm that=20
>>> > combine with this particular sub-sequence selection is the best=20
>>> > approach. It's evident that you'll have to propose the same for prett=
y=20
>>> > much all other algorithms. And I wonder if there couldn't be other=20
>>> > forms of sub-sequencing as well (I'm thinking direct filtering but=20
>>> > that can be handled by specialized iterators).=20
>>>
>>> This operation can also be handled using the normal std::accumulate; fo=
r=20
>>> your example, you would use:=20
>>>
>>> accumulate(first, last, 0,=20
>>> [](int a, int b) {if (b < 0) return 0; else return a + b;})=
;=20
>>>
>>> That gives a single pass over the sequence. For accumulating up to the=
=20
>>> first negative number, you would want a separate algorithm to allow the=
=20
>>> iteration to stop early (you can use std::accumulate if you can afford=
=20
>>> to=20
>>> iterate the entire sequence) or the approach Fernando is proposing with=
=20
>>> a=20
>>> way to make a range of "all elements up to the first negative one."=20
>>>
>>> -- Jeremiah Willcock=20
>>>
>> =20
>> It is a remarkable idea but it is what I wanted to escape suggesting the=
=20
>> new algorithm. =20
>>
>
> That's part of the point, and it's the reason why we have lambdas: so tha=
t=20
> we don't have to have a new algorithm for every corner case imaginable.
>
> Code-wise, his std::accumulate+lambda is in every way equivalent to what=
=20
> you proposed. It's not particularly long, and it's very clear as to what =
it=20
> does. Odds are good that they'll even compile to the same code.
>
> So why do we need a whole new function for something that we can triviall=
y=20
> do ourselves?
>
> While this algorithm would certainly see use, I don't see the *need* to=
=20
> have it as an algorithm in the standard library. It's not used frequently=
=20
> enough to need such canonization, and we can achieve the same effect with=
a=20
> simple lambda.
>
=20
=20
The example of Jeremiah can be considered as an interesting trick in a=20
stident auditotium but in can not be used in a professional code.=20
--=20
------=_Part_231_3368335.1357871502220
Content-Type: text/html; charset=KOI8-R
Content-Transfer-Encoding: quoted-printable
<br>=D0=D1=D4=CE=C9=C3=C1, 11 =D1=CE=D7=C1=D2=D1 2013 =C7., 5:57:40 UT=
C+4 =D0=CF=CC=D8=DA=CF=D7=C1=D4=C5=CC=D8 Nicol Bolas =CE=C1=D0=C9=D3=C1=CC:=
<blockquote style=3D"margin: 0px 0px 0px 0.8ex; padding-left: 1ex; border-l=
eft-color: rgb(204, 204, 204); border-left-width: 1px; border-left-style: s=
olid;" class=3D"gmail_quote">On Thursday, January 10, 2013 5:38:25 PM UTC-8=
, Vlad from Moscow wrote:<blockquote style=3D"margin: 0px 0px 0px 0.8ex; pa=
dding-left: 1ex; border-left-color: rgb(204, 204, 204); border-left-width: =
1px; border-left-style: solid;" class=3D"gmail_quote"><br>=D0=D1=D4=CE=C9=
=C3=C1, 11 =D1=CE=D7=C1=D2=D1 2013 =C7., 2:58:28 UTC+4 =D0=CF=CC=D8=DA=
=CF=D7=C1=D4=C5=CC=D8 jewillco =CE=C1=D0=C9=D3=C1=CC:<blockquote style=3D"m=
argin: 0px 0px 0px 0.8ex; padding-left: 1ex; border-left-color: rgb(204, 20=
4, 204); border-left-width: 1px; border-left-style: solid;" class=3D"gmail_=
quote">On Thu, 10 Jan 2013, Fernando Cacciola wrote:
<br>
<br>> On Thu, Jan 10, 2013 at 8:29 PM, Vlad from Moscow <<a>vlad....@=
mail.ru</a>> wrote:
<br>>> At first let consider a simple assignment: calculate sum of al=
l elements of
<br>>> a integer array after the last negative element.
<br>>> It seems that the assignment should be done in two phases. Fir=
stly the last
<br>>> negative element should be found for example with std::find_if=
by supplying
<br>>> reverse iterators. Secondly standard algorithm std::accumulate=
will be used.
<br>>>
<br>>> This approach has a serious shortage. Nothing prevents t=
hat the last
<br>>> negative element of the array will be at the same time the fir=
st element of
<br>>> the array. So the array will be traversed twice. It is o=
bvious that this
<br>>> approach is ineffective.
<br>>>
<br>>> But how to do the task in more effective way and preserve the =
symantic of
<br>>> std::accumulate?
<br>>>
<br>>>
<br>>> I suggest a new modification of std::accumulate that resolves =
this problem.
<br>>>
<br>>>
<br>>> This modifications includes two forms of the algorithm
<br>>>
<br>>>
<br>>> template <class InputIterator, class T, class UnaryPredicat=
e, class
<br>>> BinaryOperation>
<br>>> T accumulate_first_if( InputIterator first,
<br>>> =
InputIterator last,
<br>>> T init,
<br>>> UnaryPredicate unary_predicate,
<br>>> BinaryOperation binary_operation )
<br>>> {
<br>>> for ( ; first !=3D last && unary_predicate( *fir=
st ) ; ++first )
<br>>> {
<br>>> init =3D binary_operation( init, *first );
<br>>> }
<br>>> return ( init );
<br>>> }
<br>>
<br>> Actually, I'd like to see a more generalized approach.
<br>>
<br>> What you've shown is the case where a standard algorithm should be
<br>> applied to a subset of a sequence, and you noticed that it is wast=
eful
<br>> to determine the sub-sequence in a separate pass.
<br>> For this case, you are of course correct, and the solution would
<br>> indeed be a loop of the form you just proposed.
<br>>
<br>> However, I'm not sure if providing flavors of the algorithm that
<br>> combine with this particular sub-sequence selection is the best
<br>> approach. It's evident that you'll have to propose the same for pr=
etty
<br>> much all other algorithms. And I wonder if there couldn't be other
<br>> forms of sub-sequencing as well (I'm thinking direct filtering but
<br>> that can be handled by specialized iterators).
<br>
<br>This operation can also be handled using the normal std::accumulate; fo=
r=20
<br>your example, you would use:
<br>
<br>accumulate(first, last, 0,
<br> [](int a, int b) {if (b < =
0) return 0; else return a + b;});
<br>
<br>That gives a single pass over the sequence. For accumulating up t=
o the=20
<br>first negative number, you would want a separate algorithm to allow the=
=20
<br>iteration to stop early (you can use std::accumulate if you can afford =
to=20
<br>iterate the entire sequence) or the approach Fernando is proposing with=
a=20
<br>way to make a range of "all elements up to the first negative one."
<br>
<br>-- Jeremiah Willcock
<br></blockquote><div> </div><div>It is a remarkable idea but it =
is what I wanted to escape suggesting the new algorithm. </=
div></blockquote><div><br>That's part of the point, and it's the reason why=
we have lambdas: so that we don't have to have a new algorithm for every c=
orner case imaginable.<br><br>Code-wise, his std::accumulate+lambda is in e=
very way equivalent to what you proposed. It's not particularly long, and i=
t's very clear as to what it does. Odds are good that they'll even compile =
to the same code.<br><br>So why do we need a whole new function for somethi=
ng that we can trivially do ourselves?<br><br>While this algorithm would ce=
rtainly see use, I don't see the <i>need</i> to have it as an algorithm in =
the standard library. It's not used frequently enough to need such canoniza=
tion, and we can achieve the same effect with a simple lambda.<br></div></b=
lockquote><div> </div><div> </div><div>The example of Jeremi=
ah can be considered as an interesting trick in a stident audito=
tium but in can not be used in a professional code. </div>
<p></p>
-- <br />
<br />
<br />
<br />
------=_Part_231_3368335.1357871502220--
.
Author: Vlad from Moscow <vlad.moscow@mail.ru>
Date: Thu, 10 Jan 2013 18:41:22 -0800 (PST)
Raw View
------=_Part_217_1969514.1357872082865
Content-Type: text/plain; charset=KOI8-R
Content-Transfer-Encoding: quoted-printable
=D0=D1=D4=CE=C9=C3=C1, 11 =D1=CE=D7=C1=D2=D1 2013 =C7., 5:57:40 UTC+4 =D0=
=CF=CC=D8=DA=CF=D7=C1=D4=C5=CC=D8 Nicol Bolas =CE=C1=D0=C9=D3=C1=CC:
>
> On Thursday, January 10, 2013 5:38:25 PM UTC-8, Vlad from Moscow wrote:
>>
>>
>> =D0=D1=D4=CE=C9=C3=C1, 11 =D1=CE=D7=C1=D2=D1 2013 =C7., 2:58:28 UTC+4 =
=D0=CF=CC=D8=DA=CF=D7=C1=D4=C5=CC=D8 jewillco =CE=C1=D0=C9=D3=C1=CC:
>>>
>>> On Thu, 10 Jan 2013, Fernando Cacciola wrote:=20
>>>
>>> > On Thu, Jan 10, 2013 at 8:29 PM, Vlad from Moscow <vlad....@mail.ru>=
=20
>>> wrote:=20
>>> >> At first let consider a simple assignment: calculate sum of all=20
>>> elements of=20
>>> >> a integer array after the last negative element.=20
>>> >> It seems that the assignment should be done in two phases. Firstly=
=20
>>> the last=20
>>> >> negative element should be found for example with std::find_if by=20
>>> supplying=20
>>> >> reverse iterators. Secondly standard algorithm std::accumulate will=
=20
>>> be used.=20
>>> >>=20
>>> >> This approach has a serious shortage. Nothing prevents that the las=
t=20
>>> >> negative element of the array will be at the same time the first=20
>>> element of=20
>>> >> the array. So the array will be traversed twice. It is obvious that=
=20
>>> this=20
>>> >> approach is ineffective.=20
>>> >>=20
>>> >> But how to do the task in more effective way and preserve the=20
>>> symantic of=20
>>> >> std::accumulate?=20
>>> >>=20
>>> >>=20
>>> >> I suggest a new modification of std::accumulate that resolves this=
=20
>>> problem.=20
>>> >>=20
>>> >>=20
>>> >> This modifications includes two forms of the algorithm=20
>>> >>=20
>>> >>=20
>>> >> template <class InputIterator, class T, class UnaryPredicate, class=
=20
>>> >> BinaryOperation>=20
>>> >> T accumulate_first_if( InputIterator first,=20
>>> >> InputIterator last,=20
>>> >> T init,=20
>>> >> UnaryPredicate unary_predicate,=20
>>> >> BinaryOperation binary_operation )=20
>>> >> {=20
>>> >> for ( ; first !=3D last && unary_predicate( *first ) ; ++first )=20
>>> >> {=20
>>> >> init =3D binary_operation( init, *first );=20
>>> >> }=20
>>> >> return ( init );=20
>>> >> }=20
>>> >=20
>>> > Actually, I'd like to see a more generalized approach.=20
>>> >=20
>>> > What you've shown is the case where a standard algorithm should be=20
>>> > applied to a subset of a sequence, and you noticed that it is wastefu=
l=20
>>> > to determine the sub-sequence in a separate pass.=20
>>> > For this case, you are of course correct, and the solution would=20
>>> > indeed be a loop of the form you just proposed.=20
>>> >=20
>>> > However, I'm not sure if providing flavors of the algorithm that=20
>>> > combine with this particular sub-sequence selection is the best=20
>>> > approach. It's evident that you'll have to propose the same for prett=
y=20
>>> > much all other algorithms. And I wonder if there couldn't be other=20
>>> > forms of sub-sequencing as well (I'm thinking direct filtering but=20
>>> > that can be handled by specialized iterators).=20
>>>
>>> This operation can also be handled using the normal std::accumulate; fo=
r=20
>>> your example, you would use:=20
>>>
>>> accumulate(first, last, 0,=20
>>> [](int a, int b) {if (b < 0) return 0; else return a + b;})=
;=20
>>>
>>> That gives a single pass over the sequence. For accumulating up to the=
=20
>>> first negative number, you would want a separate algorithm to allow the=
=20
>>> iteration to stop early (you can use std::accumulate if you can afford=
=20
>>> to=20
>>> iterate the entire sequence) or the approach Fernando is proposing with=
=20
>>> a=20
>>> way to make a range of "all elements up to the first negative one."=20
>>>
>>> -- Jeremiah Willcock=20
>>>
>> =20
>> It is a remarkable idea but it is what I wanted to escape suggesting the=
=20
>> new algorithm. =20
>>
>
> That's part of the point, and it's the reason why we have lambdas: so tha=
t=20
> we don't have to have a new algorithm for every corner case imaginable.
>
> Code-wise, his std::accumulate+lambda is in every way equivalent to what=
=20
> you proposed. It's not particularly long, and it's very clear as to what =
it=20
> does. Odds are good that they'll even compile to the same code.
>
> So why do we need a whole new function for something that we can triviall=
y=20
> do ourselves?
>
> While this algorithm would certainly see use, I don't see the *need* to=
=20
> have it as an algorithm in the standard library. It's not used frequently=
=20
> enough to need such canonization, and we can achieve the same effect with=
a=20
> simple lambda.
>
=20
=20
I even do not want to answer to such "argument" as "So why do we need a=20
whole new function for something that we can trivially do ourselves?". I=20
heard is thousand times. I hope that you can also yourself to write strlen=
=20
can not you?:) At least as far as I know all students write strlen while=20
are studing C/C++.
However I will do one remark. As the post of Jeremiah Willcock showed not=
=20
all can write this algorithm. There will be numerous realizations that in=
=20
most part will be ineffective and that can be difficult to understand and=
=20
to read what the author was going to do.
--=20
------=_Part_217_1969514.1357872082865
Content-Type: text/html; charset=KOI8-R
Content-Transfer-Encoding: quoted-printable
<br>=D0=D1=D4=CE=C9=C3=C1, 11 =D1=CE=D7=C1=D2=D1 2013 =C7., 5:57:40 UT=
C+4 =D0=CF=CC=D8=DA=CF=D7=C1=D4=C5=CC=D8 Nicol Bolas =CE=C1=D0=C9=D3=C1=CC:=
<blockquote style=3D"margin: 0px 0px 0px 0.8ex; padding-left: 1ex; border-l=
eft-color: rgb(204, 204, 204); border-left-width: 1px; border-left-style: s=
olid;" class=3D"gmail_quote">On Thursday, January 10, 2013 5:38:25 PM UTC-8=
, Vlad from Moscow wrote:<blockquote style=3D"margin: 0px 0px 0px 0.8ex; pa=
dding-left: 1ex; border-left-color: rgb(204, 204, 204); border-left-width: =
1px; border-left-style: solid;" class=3D"gmail_quote"><br>=D0=D1=D4=CE=C9=
=C3=C1, 11 =D1=CE=D7=C1=D2=D1 2013 =C7., 2:58:28 UTC+4 =D0=CF=CC=D8=DA=
=CF=D7=C1=D4=C5=CC=D8 jewillco =CE=C1=D0=C9=D3=C1=CC:<blockquote style=3D"m=
argin: 0px 0px 0px 0.8ex; padding-left: 1ex; border-left-color: rgb(204, 20=
4, 204); border-left-width: 1px; border-left-style: solid;" class=3D"gmail_=
quote">On Thu, 10 Jan 2013, Fernando Cacciola wrote:
<br>
<br>> On Thu, Jan 10, 2013 at 8:29 PM, Vlad from Moscow <<a>vlad....@=
mail.ru</a>> wrote:
<br>>> At first let consider a simple assignment: calculate sum of al=
l elements of
<br>>> a integer array after the last negative element.
<br>>> It seems that the assignment should be done in two phases. Fir=
stly the last
<br>>> negative element should be found for example with std::find_if=
by supplying
<br>>> reverse iterators. Secondly standard algorithm std::accumulate=
will be used.
<br>>>
<br>>> This approach has a serious shortage. Nothing prevents t=
hat the last
<br>>> negative element of the array will be at the same time the fir=
st element of
<br>>> the array. So the array will be traversed twice. It is o=
bvious that this
<br>>> approach is ineffective.
<br>>>
<br>>> But how to do the task in more effective way and preserve the =
symantic of
<br>>> std::accumulate?
<br>>>
<br>>>
<br>>> I suggest a new modification of std::accumulate that resolves =
this problem.
<br>>>
<br>>>
<br>>> This modifications includes two forms of the algorithm
<br>>>
<br>>>
<br>>> template <class InputIterator, class T, class UnaryPredicat=
e, class
<br>>> BinaryOperation>
<br>>> T accumulate_first_if( InputIterator first,
<br>>> =
InputIterator last,
<br>>> T init,
<br>>> UnaryPredicate unary_predicate,
<br>>> BinaryOperation binary_operation )
<br>>> {
<br>>> for ( ; first !=3D last && unary_predicate( *fir=
st ) ; ++first )
<br>>> {
<br>>> init =3D binary_operation( init, *first );
<br>>> }
<br>>> return ( init );
<br>>> }
<br>>
<br>> Actually, I'd like to see a more generalized approach.
<br>>
<br>> What you've shown is the case where a standard algorithm should be
<br>> applied to a subset of a sequence, and you noticed that it is wast=
eful
<br>> to determine the sub-sequence in a separate pass.
<br>> For this case, you are of course correct, and the solution would
<br>> indeed be a loop of the form you just proposed.
<br>>
<br>> However, I'm not sure if providing flavors of the algorithm that
<br>> combine with this particular sub-sequence selection is the best
<br>> approach. It's evident that you'll have to propose the same for pr=
etty
<br>> much all other algorithms. And I wonder if there couldn't be other
<br>> forms of sub-sequencing as well (I'm thinking direct filtering but
<br>> that can be handled by specialized iterators).
<br>
<br>This operation can also be handled using the normal std::accumulate; fo=
r=20
<br>your example, you would use:
<br>
<br>accumulate(first, last, 0,
<br> [](int a, int b) {if (b < =
0) return 0; else return a + b;});
<br>
<br>That gives a single pass over the sequence. For accumulating up t=
o the=20
<br>first negative number, you would want a separate algorithm to allow the=
=20
<br>iteration to stop early (you can use std::accumulate if you can afford =
to=20
<br>iterate the entire sequence) or the approach Fernando is proposing with=
a=20
<br>way to make a range of "all elements up to the first negative one."
<br>
<br>-- Jeremiah Willcock
<br></blockquote><div> </div><div>It is a remarkable idea but it =
is what I wanted to escape suggesting the new algorithm. </=
div></blockquote><div><br>That's part of the point, and it's the reason why=
we have lambdas: so that we don't have to have a new algorithm for every c=
orner case imaginable.<br><br>Code-wise, his std::accumulate+lambda is in e=
very way equivalent to what you proposed. It's not particularly long, and i=
t's very clear as to what it does. Odds are good that they'll even compile =
to the same code.<br><br>So why do we need a whole new function for somethi=
ng that we can trivially do ourselves?<br><br>While this algorithm would ce=
rtainly see use, I don't see the <i>need</i> to have it as an algorithm in =
the standard library. It's not used frequently enough to need such canoniza=
tion, and we can achieve the same effect with a simple lambda.<br></div></b=
lockquote><div> </div><div> </div><div>I even do not want to answ=
er to such "argument" as "So why do we need a whole new function for =
something that we can trivially do ourselves?". I heard is thousand times. =
I hope that you can also yourself to write strlen can not you?:) At least a=
s far as I know all students write strlen while are studing C/C++.</d=
iv><div>However I will do one remark. As the post of Jeremiah Willcoc=
k showed not all can write this algorithm. There will be numerous realizati=
ons that in most part will be ineffective and that can be difficult to unde=
rstand and to read what the author was going to do.</div>
<p></p>
-- <br />
<br />
<br />
<br />
------=_Part_217_1969514.1357872082865--
.
Author: Nicol Bolas <jmckesson@gmail.com>
Date: Thu, 10 Jan 2013 20:15:11 -0800 (PST)
Raw View
------=_Part_370_9847527.1357877711996
Content-Type: text/plain; charset=KOI8-R
Content-Transfer-Encoding: quoted-printable
On Thursday, January 10, 2013 6:41:22 PM UTC-8, Vlad from Moscow wrote:
>
>
> =D0=D1=D4=CE=C9=C3=C1, 11 =D1=CE=D7=C1=D2=D1 2013 =C7., 5:57:40 UTC+4 =D0=
=CF=CC=D8=DA=CF=D7=C1=D4=C5=CC=D8 Nicol Bolas =CE=C1=D0=C9=D3=C1=CC:
>>
>> On Thursday, January 10, 2013 5:38:25 PM UTC-8, Vlad from Moscow wrote:
>>>
>>>
>>> =D0=D1=D4=CE=C9=C3=C1, 11 =D1=CE=D7=C1=D2=D1 2013 =C7., 2:58:28 UTC+4 =
=D0=CF=CC=D8=DA=CF=D7=C1=D4=C5=CC=D8 jewillco =CE=C1=D0=C9=D3=C1=CC:
>>>>
>>>> On Thu, 10 Jan 2013, Fernando Cacciola wrote:=20
>>>>
>>>> > On Thu, Jan 10, 2013 at 8:29 PM, Vlad from Moscow <vlad....@mail.ru>=
=20
>>>> wrote:=20
>>>> >> At first let consider a simple assignment: calculate sum of all=20
>>>> elements of=20
>>>> >> a integer array after the last negative element.=20
>>>> >> It seems that the assignment should be done in two phases. Firstly=
=20
>>>> the last=20
>>>> >> negative element should be found for example with std::find_if by=
=20
>>>> supplying=20
>>>> >> reverse iterators. Secondly standard algorithm std::accumulate will=
=20
>>>> be used.=20
>>>> >>=20
>>>> >> This approach has a serious shortage. Nothing prevents that the=20
>>>> last=20
>>>> >> negative element of the array will be at the same time the first=20
>>>> element of=20
>>>> >> the array. So the array will be traversed twice. It is obvious tha=
t=20
>>>> this=20
>>>> >> approach is ineffective.=20
>>>> >>=20
>>>> >> But how to do the task in more effective way and preserve the=20
>>>> symantic of=20
>>>> >> std::accumulate?=20
>>>> >>=20
>>>> >>=20
>>>> >> I suggest a new modification of std::accumulate that resolves this=
=20
>>>> problem.=20
>>>> >>=20
>>>> >>=20
>>>> >> This modifications includes two forms of the algorithm=20
>>>> >>=20
>>>> >>=20
>>>> >> template <class InputIterator, class T, class UnaryPredicate, class=
=20
>>>> >> BinaryOperation>=20
>>>> >> T accumulate_first_if( InputIterator first,=20
>>>> >> InputIterator last,=20
>>>> >> T init,=20
>>>> >> UnaryPredicate unary_predicate,=20
>>>> >> BinaryOperation binary_operation )=20
>>>> >> {=20
>>>> >> for ( ; first !=3D last && unary_predicate( *first ) ; ++first )=
=20
>>>> >> {=20
>>>> >> init =3D binary_operation( init, *first );=20
>>>> >> }=20
>>>> >> return ( init );=20
>>>> >> }=20
>>>> >=20
>>>> > Actually, I'd like to see a more generalized approach.=20
>>>> >=20
>>>> > What you've shown is the case where a standard algorithm should be=
=20
>>>> > applied to a subset of a sequence, and you noticed that it is=20
>>>> wasteful=20
>>>> > to determine the sub-sequence in a separate pass.=20
>>>> > For this case, you are of course correct, and the solution would=20
>>>> > indeed be a loop of the form you just proposed.=20
>>>> >=20
>>>> > However, I'm not sure if providing flavors of the algorithm that=20
>>>> > combine with this particular sub-sequence selection is the best=20
>>>> > approach. It's evident that you'll have to propose the same for=20
>>>> pretty=20
>>>> > much all other algorithms. And I wonder if there couldn't be other=
=20
>>>> > forms of sub-sequencing as well (I'm thinking direct filtering but=
=20
>>>> > that can be handled by specialized iterators).=20
>>>>
>>>> This operation can also be handled using the normal std::accumulate;=
=20
>>>> for=20
>>>> your example, you would use:=20
>>>>
>>>> accumulate(first, last, 0,=20
>>>> [](int a, int b) {if (b < 0) return 0; else return a +=20
>>>> b;});=20
>>>>
>>>> That gives a single pass over the sequence. For accumulating up to th=
e=20
>>>> first negative number, you would want a separate algorithm to allow th=
e=20
>>>> iteration to stop early (you can use std::accumulate if you can afford=
=20
>>>> to=20
>>>> iterate the entire sequence) or the approach Fernando is proposing wit=
h=20
>>>> a=20
>>>> way to make a range of "all elements up to the first negative one."=20
>>>>
>>>> -- Jeremiah Willcock=20
>>>>
>>> =20
>>> It is a remarkable idea but it is what I wanted to escape suggesting th=
e=20
>>> new algorithm. =20
>>>
>>
>> That's part of the point, and it's the reason why we have lambdas: so=20
>> that we don't have to have a new algorithm for every corner case imagina=
ble.
>>
>> Code-wise, his std::accumulate+lambda is in every way equivalent to what=
=20
>> you proposed. It's not particularly long, and it's very clear as to what=
it=20
>> does. Odds are good that they'll even compile to the same code.
>>
>> So why do we need a whole new function for something that we can=20
>> trivially do ourselves?
>>
>> While this algorithm would certainly see use, I don't see the *need* to=
=20
>> have it as an algorithm in the standard library. It's not used frequentl=
y=20
>> enough to need such canonization, and we can achieve the same effect wit=
h a=20
>> simple lambda.
>>
> =20
> =20
> I even do not want to answer to such "argument" as "So why do we need a=
=20
> whole new function for something that we can trivially do ourselves?". I=
=20
> heard is thousand times.
>
The reason you hear this argument "thousand times" is because it's a=20
reasonable argument. People can come up with innumerable patterns of range=
=20
iteration that could be represented by algorithms.
In general, things that become standard library algorithms fill one of=20
these criteria:
1: It's quite common. Taking the sum of all values in a list, calling a=20
function and storing the result in a list, searching for a value, etc are=
=20
simple tasks, but they're tasks that programmers often have to do.
2: It's hard to write efficiently. std::sort, std::binary_search, etc, are=
=20
all algorithms that are very easy to get wrong. Either you make it slow, or=
=20
you make it behave incorrectly. By having a simple algorithm,
In general, find first/last negative value followed by accumulate is=20
sufficient for most people's needs. Those people who actually need this=20
either know they need it through profiling, or are using InputIterators=20
that they can't traverse multiple times. I just don't see this as being a=
=20
compelling need for such a feature.
=20
> I hope that you can also yourself to write strlen can not you?:) At least=
=20
> as far as I know all students write strlen while are studing C/C++.
>
Are you honestly suggesting that this specific adaptation of accumulate is=
=20
anywhere near as generally useful as strlen?
However I will do one remark. As the post of Jeremiah Willcock showed not=
=20
> all can write this algorithm.
>
How did his post show that? It showed that he wrote the first variation=20
(everything from the last key value on). It explained how to write the=20
second one, but he didn't write it for you.
=20
> There will be numerous realizations that in most part will be ineffective=
=20
> and that can be difficult to understand and to read what the author was=
=20
> going to do.=20
>
And this is what you consider easier to understand:
accumulate_first_if( std::reverse_iterator<int *>( std::end( a ) ),
std::reverse_iterator<int *>( std::begin( a ) ),
0,
std::bind2nd( std::greater_equal<int>(), 0 ) );
The other one was much easier to digest.
--=20
------=_Part_370_9847527.1357877711996
Content-Type: text/html; charset=KOI8-R
Content-Transfer-Encoding: quoted-printable
<br><br>On Thursday, January 10, 2013 6:41:22 PM UTC-8, Vlad from Moscow wr=
ote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex=
;border-left: 1px #ccc solid;padding-left: 1ex;"><br>=D0=D1=D4=CE=C9=C3=C1,=
11 =D1=CE=D7=C1=D2=D1 2013 =C7., 5:57:40 UTC+4 =D0=CF=CC=D8=DA=CF=D7=
=C1=D4=C5=CC=D8 Nicol Bolas =CE=C1=D0=C9=D3=C1=CC:<blockquote style=3D"marg=
in:0px 0px 0px 0.8ex;padding-left:1ex;border-left-color:rgb(204,204,204);bo=
rder-left-width:1px;border-left-style:solid" class=3D"gmail_quote">On Thurs=
day, January 10, 2013 5:38:25 PM UTC-8, Vlad from Moscow wrote:<blockquote =
style=3D"margin:0px 0px 0px 0.8ex;padding-left:1ex;border-left-color:rgb(20=
4,204,204);border-left-width:1px;border-left-style:solid" class=3D"gmail_qu=
ote"><br>=D0=D1=D4=CE=C9=C3=C1, 11 =D1=CE=D7=C1=D2=D1 2013 =C7., 2:58:=
28 UTC+4 =D0=CF=CC=D8=DA=CF=D7=C1=D4=C5=CC=D8 jewillco =CE=C1=D0=C9=D3=C1=
=CC:<blockquote style=3D"margin:0px 0px 0px 0.8ex;padding-left:1ex;border-l=
eft-color:rgb(204,204,204);border-left-width:1px;border-left-style:solid" c=
lass=3D"gmail_quote">On Thu, 10 Jan 2013, Fernando Cacciola wrote:
<br>
<br>> On Thu, Jan 10, 2013 at 8:29 PM, Vlad from Moscow <<a>vlad....@=
mail.ru</a>> wrote:
<br>>> At first let consider a simple assignment: calculate sum of al=
l elements of
<br>>> a integer array after the last negative element.
<br>>> It seems that the assignment should be done in two phases. Fir=
stly the last
<br>>> negative element should be found for example with std::find_if=
by supplying
<br>>> reverse iterators. Secondly standard algorithm std::accumulate=
will be used.
<br>>>
<br>>> This approach has a serious shortage. Nothing prevents t=
hat the last
<br>>> negative element of the array will be at the same time the fir=
st element of
<br>>> the array. So the array will be traversed twice. It is o=
bvious that this
<br>>> approach is ineffective.
<br>>>
<br>>> But how to do the task in more effective way and preserve the =
symantic of
<br>>> std::accumulate?
<br>>>
<br>>>
<br>>> I suggest a new modification of std::accumulate that resolves =
this problem.
<br>>>
<br>>>
<br>>> This modifications includes two forms of the algorithm
<br>>>
<br>>>
<br>>> template <class InputIterator, class T, class UnaryPredicat=
e, class
<br>>> BinaryOperation>
<br>>> T accumulate_first_if( InputIterator first,
<br>>> =
InputIterator last,
<br>>> T init,
<br>>> UnaryPredicate unary_predicate,
<br>>> BinaryOperation binary_operation )
<br>>> {
<br>>> for ( ; first !=3D last && unary_predicate( *fir=
st ) ; ++first )
<br>>> {
<br>>> init =3D binary_operation( init, *first );
<br>>> }
<br>>> return ( init );
<br>>> }
<br>>
<br>> Actually, I'd like to see a more generalized approach.
<br>>
<br>> What you've shown is the case where a standard algorithm should be
<br>> applied to a subset of a sequence, and you noticed that it is wast=
eful
<br>> to determine the sub-sequence in a separate pass.
<br>> For this case, you are of course correct, and the solution would
<br>> indeed be a loop of the form you just proposed.
<br>>
<br>> However, I'm not sure if providing flavors of the algorithm that
<br>> combine with this particular sub-sequence selection is the best
<br>> approach. It's evident that you'll have to propose the same for pr=
etty
<br>> much all other algorithms. And I wonder if there couldn't be other
<br>> forms of sub-sequencing as well (I'm thinking direct filtering but
<br>> that can be handled by specialized iterators).
<br>
<br>This operation can also be handled using the normal std::accumulate; fo=
r=20
<br>your example, you would use:
<br>
<br>accumulate(first, last, 0,
<br> [](int a, int b) {if (b < =
0) return 0; else return a + b;});
<br>
<br>That gives a single pass over the sequence. For accumulating up t=
o the=20
<br>first negative number, you would want a separate algorithm to allow the=
=20
<br>iteration to stop early (you can use std::accumulate if you can afford =
to=20
<br>iterate the entire sequence) or the approach Fernando is proposing with=
a=20
<br>way to make a range of "all elements up to the first negative one."
<br>
<br>-- Jeremiah Willcock
<br></blockquote><div> </div><div>It is a remarkable idea but it =
is what I wanted to escape suggesting the new algorithm. </=
div></blockquote><div><br>That's part of the point, and it's the reason why=
we have lambdas: so that we don't have to have a new algorithm for every c=
orner case imaginable.<br><br>Code-wise, his std::accumulate+lambda is in e=
very way equivalent to what you proposed. It's not particularly long, and i=
t's very clear as to what it does. Odds are good that they'll even compile =
to the same code.<br><br>So why do we need a whole new function for somethi=
ng that we can trivially do ourselves?<br><br>While this algorithm would ce=
rtainly see use, I don't see the <i>need</i> to have it as an algorithm in =
the standard library. It's not used frequently enough to need such canoniza=
tion, and we can achieve the same effect with a simple lambda.<br></div></b=
lockquote><div> </div><div> </div><div>I even do not want to answ=
er to such "argument" as "So why do we need a whole new function for =
something that we can trivially do ourselves?". I heard is thousand times.<=
/div></blockquote><div><br>The reason you hear this argument "thousand time=
s" is because it's a reasonable argument. People can come up with innumerab=
le patterns of range iteration that could be represented by algorithms.<br>=
<br>In general, things that become standard library algorithms fill one of =
these criteria:<br><br>1: It's quite common. Taking the sum of all values i=
n a list, calling a function and storing the result in a list, searching fo=
r a value, etc are simple tasks, but they're tasks that programmers often h=
ave to do.<br><br>2: It's hard to write efficiently. std::sort, std::binary=
_search, etc, are all algorithms that are very easy to get wrong. Either yo=
u make it slow, or you make it behave incorrectly. By having a simple algor=
ithm,<br><br>In general, find first/last negative value followed by accumul=
ate is sufficient for most people's needs. Those people who actually need t=
his either know they need it through profiling, or are using InputIterators=
that they can't traverse multiple times. I just don't see this as being a =
compelling need for such a feature.<br> </div><blockquote class=3D"gma=
il_quote" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid=
;padding-left: 1ex;"><div>I hope that you can also yourself to write strlen=
can not you?:) At least as far as I know all students write strlen while a=
re studing C/C++.<br></div></blockquote><div><br>Are you honestly sug=
gesting that this specific adaptation of accumulate is anywhere near as gen=
erally useful as strlen?<br><br></div><blockquote class=3D"gmail_quote" sty=
le=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left=
: 1ex;"><div>However I will do one remark. As the post of Jeremiah Wi=
llcock showed not all can write this algorithm.</div></blockquote><div><br>=
How did his post show that? It showed that he wrote the first variation (ev=
erything from the last key value on). It explained how to write the second =
one, but he didn't write it for you.<br> </div><blockquote class=3D"gm=
ail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc soli=
d;padding-left: 1ex;"><div> There will be numerous realizations that in mos=
t part will be ineffective and that can be difficult to understand and to r=
ead what the author was going to do. <br></div></blockquote><div><br>And th=
is is what you consider easier to understand:<br><br><div class=3D"prettypr=
int" style=3D"background-color: rgb(250, 250, 250); border-color: rgb(187, =
187, 187); border-style: solid; border-width: 1px; word-wrap: break-word;">=
<code class=3D"prettyprint"><div class=3D"subprettyprint"><span style=3D"co=
lor: #000;" class=3D"styled-by-prettify">accumulate_first_if</span><span st=
yle=3D"color: #660;" class=3D"styled-by-prettify">(</span><span style=3D"co=
lor: #000;" class=3D"styled-by-prettify"> std</span><span style=3D"color: #=
660;" class=3D"styled-by-prettify">::</span><span style=3D"color: #000;" cl=
ass=3D"styled-by-prettify">reverse_iterator</span><span style=3D"color: #66=
0;" class=3D"styled-by-prettify"><</span><span style=3D"color: #008;" cl=
ass=3D"styled-by-prettify">int</span><span style=3D"color: #000;" class=3D"=
styled-by-prettify"> </span><span style=3D"color: #660;" class=3D"styled-by=
-prettify">*>(</span><span style=3D"color: #000;" class=3D"styled-by-pre=
ttify"> std</span><span style=3D"color: #660;" class=3D"styled-by-prettify"=
>::</span><span style=3D"color: #008;" class=3D"styled-by-prettify">end</sp=
an><span style=3D"color: #660;" class=3D"styled-by-prettify">(</span><span =
style=3D"color: #000;" class=3D"styled-by-prettify"> a </span><span style=
=3D"color: #660;" class=3D"styled-by-prettify">)</span><span style=3D"color=
: #000;" class=3D"styled-by-prettify"> </span><span style=3D"color: #660;" =
class=3D"styled-by-prettify">),</span><span style=3D"color: #000;" class=3D=
"styled-by-prettify"><br> &=
nbsp; std</span><span style=3D"color: #660;" class=3D"s=
tyled-by-prettify">::</span><span style=3D"color: #000;" class=3D"styled-by=
-prettify">reverse_iterator</span><span style=3D"color: #660;" class=3D"sty=
led-by-prettify"><</span><span style=3D"color: #008;" class=3D"styled-by=
-prettify">int</span><span style=3D"color: #000;" class=3D"styled-by-pretti=
fy"> </span><span style=3D"color: #660;" class=3D"styled-by-prettify">*>=
(</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> std</spa=
n><span style=3D"color: #660;" class=3D"styled-by-prettify">::</span><span =
style=3D"color: #008;" class=3D"styled-by-prettify">begin</span><span style=
=3D"color: #660;" class=3D"styled-by-prettify">(</span><span style=3D"color=
: #000;" class=3D"styled-by-prettify"> a </span><span style=3D"color: #660;=
" class=3D"styled-by-prettify">)</span><span style=3D"color: #000;" class=
=3D"styled-by-prettify"> </span><span style=3D"color: #660;" class=3D"style=
d-by-prettify">),</span><span style=3D"color: #000;" class=3D"styled-by-pre=
ttify"><br> &=
nbsp; </span><span style=3D"color: #066;" class=3D"styled-by-prettify=
">0</span><span style=3D"color: #660;" class=3D"styled-by-prettify">,</span=
><span style=3D"color: #000;" class=3D"styled-by-prettify"><br>  =
; std</span><=
span style=3D"color: #660;" class=3D"styled-by-prettify">::</span><span sty=
le=3D"color: #000;" class=3D"styled-by-prettify">bind2nd</span><span style=
=3D"color: #660;" class=3D"styled-by-prettify">(</span><span style=3D"color=
: #000;" class=3D"styled-by-prettify"> std</span><span style=3D"color: #660=
;" class=3D"styled-by-prettify">::</span><span style=3D"color: #000;" class=
=3D"styled-by-prettify">greater_equal</span><span style=3D"color: #080;" cl=
ass=3D"styled-by-prettify"><int></span><span style=3D"color: #660;" c=
lass=3D"styled-by-prettify">(),</span><span style=3D"color: #000;" class=3D=
"styled-by-prettify"> </span><span style=3D"color: #066;" class=3D"styled-b=
y-prettify">0</span><span style=3D"color: #000;" class=3D"styled-by-prettif=
y"> </span><span style=3D"color: #660;" class=3D"styled-by-prettify">)</spa=
n><span style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span s=
tyle=3D"color: #660;" class=3D"styled-by-prettify">);</span></div></code></=
div><div><br></div>The other one was much easier to digest.<br></div>
<p></p>
-- <br />
<br />
<br />
<br />
------=_Part_370_9847527.1357877711996--
.
Author: Vlad from Moscow <vlad.moscow@mail.ru>
Date: Thu, 10 Jan 2013 22:07:25 -0800 (PST)
Raw View
------=_Part_288_19106165.1357884445469
Content-Type: text/plain; charset=KOI8-R
Content-Transfer-Encoding: quoted-printable
=D0=D1=D4=CE=C9=C3=C1, 11 =D1=CE=D7=C1=D2=D1 2013 =C7., 8:15:11 UTC+4 =D0=
=CF=CC=D8=DA=CF=D7=C1=D4=C5=CC=D8 Nicol Bolas =CE=C1=D0=C9=D3=C1=CC:
>
>
>
> On Thursday, January 10, 2013 6:41:22 PM UTC-8, Vlad from Moscow wrote:
>>
>>
>> =D0=D1=D4=CE=C9=C3=C1, 11 =D1=CE=D7=C1=D2=D1 2013 =C7., 5:57:40 UTC+4 =
=D0=CF=CC=D8=DA=CF=D7=C1=D4=C5=CC=D8 Nicol Bolas=20
>> =CE=C1=D0=C9=D3=C1=CC:
>>>
>>> On Thursday, January 10, 2013 5:38:25 PM UTC-8, Vlad from Moscow wrote:
>>>>
>>>>
>>>> =D0=D1=D4=CE=C9=C3=C1, 11 =D1=CE=D7=C1=D2=D1 2013 =C7., 2:58:28 UTC+4 =
=D0=CF=CC=D8=DA=CF=D7=C1=D4=C5=CC=D8 jewillco =CE=C1=D0=C9=D3=C1=CC:
>>>>>
>>>>> On Thu, 10 Jan 2013, Fernando Cacciola wrote:=20
>>>>>
>>>>> > On Thu, Jan 10, 2013 at 8:29 PM, Vlad from Moscow <vlad....@mail.ru=
>=20
>>>>> wrote:=20
>>>>> >> At first let consider a simple assignment: calculate sum of all=20
>>>>> elements of=20
>>>>> >> a integer array after the last negative element.=20
>>>>> >> It seems that the assignment should be done in two phases. Firstly=
=20
>>>>> the last=20
>>>>> >> negative element should be found for example with std::find_if by=
=20
>>>>> supplying=20
>>>>> >> reverse iterators. Secondly standard algorithm std::accumulate wil=
l=20
>>>>> be used.=20
>>>>> >>=20
>>>>> >> This approach has a serious shortage. Nothing prevents that the=
=20
>>>>> last=20
>>>>> >> negative element of the array will be at the same time the first=
=20
>>>>> element of=20
>>>>> >> the array. So the array will be traversed twice. It is obvious=20
>>>>> that this=20
>>>>> >> approach is ineffective.=20
>>>>> >>=20
>>>>> >> But how to do the task in more effective way and preserve the=20
>>>>> symantic of=20
>>>>> >> std::accumulate?=20
>>>>> >>=20
>>>>> >>=20
>>>>> >> I suggest a new modification of std::accumulate that resolves this=
=20
>>>>> problem.=20
>>>>> >>=20
>>>>> >>=20
>>>>> >> This modifications includes two forms of the algorithm=20
>>>>> >>=20
>>>>> >>=20
>>>>> >> template <class InputIterator, class T, class UnaryPredicate, clas=
s=20
>>>>> >> BinaryOperation>=20
>>>>> >> T accumulate_first_if( InputIterator first,=20
>>>>> >> InputIterator last,=20
>>>>> >> T init,=20
>>>>> >> UnaryPredicate unary_predicate,=20
>>>>> >> BinaryOperation binary_operation )=20
>>>>> >> {=20
>>>>> >> for ( ; first !=3D last && unary_predicate( *first ) ; ++first )=
=20
>>>>> >> {=20
>>>>> >> init =3D binary_operation( init, *first );=20
>>>>> >> }=20
>>>>> >> return ( init );=20
>>>>> >> }=20
>>>>> >=20
>>>>> > Actually, I'd like to see a more generalized approach.=20
>>>>> >=20
>>>>> > What you've shown is the case where a standard algorithm should be=
=20
>>>>> > applied to a subset of a sequence, and you noticed that it is=20
>>>>> wasteful=20
>>>>> > to determine the sub-sequence in a separate pass.=20
>>>>> > For this case, you are of course correct, and the solution would=20
>>>>> > indeed be a loop of the form you just proposed.=20
>>>>> >=20
>>>>> > However, I'm not sure if providing flavors of the algorithm that=20
>>>>> > combine with this particular sub-sequence selection is the best=20
>>>>> > approach. It's evident that you'll have to propose the same for=20
>>>>> pretty=20
>>>>> > much all other algorithms. And I wonder if there couldn't be other=
=20
>>>>> > forms of sub-sequencing as well (I'm thinking direct filtering but=
=20
>>>>> > that can be handled by specialized iterators).=20
>>>>>
>>>>> This operation can also be handled using the normal std::accumulate;=
=20
>>>>> for=20
>>>>> your example, you would use:=20
>>>>>
>>>>> accumulate(first, last, 0,=20
>>>>> [](int a, int b) {if (b < 0) return 0; else return a +=20
>>>>> b;});=20
>>>>>
>>>>> That gives a single pass over the sequence. For accumulating up to=
=20
>>>>> the=20
>>>>> first negative number, you would want a separate algorithm to allow=
=20
>>>>> the=20
>>>>> iteration to stop early (you can use std::accumulate if you can affor=
d=20
>>>>> to=20
>>>>> iterate the entire sequence) or the approach Fernando is proposing=20
>>>>> with a=20
>>>>> way to make a range of "all elements up to the first negative one."=
=20
>>>>>
>>>>> -- Jeremiah Willcock=20
>>>>>
>>>> =20
>>>> It is a remarkable idea but it is what I wanted to escape suggesting=
=20
>>>> the new algorithm. =20
>>>>
>>>
>>> That's part of the point, and it's the reason why we have lambdas: so=
=20
>>> that we don't have to have a new algorithm for every corner case imagin=
able.
>>>
>>> Code-wise, his std::accumulate+lambda is in every way equivalent to wha=
t=20
>>> you proposed. It's not particularly long, and it's very clear as to wha=
t it=20
>>> does. Odds are good that they'll even compile to the same code.
>>>
>>> So why do we need a whole new function for something that we can=20
>>> trivially do ourselves?
>>>
>>> While this algorithm would certainly see use, I don't see the *need* to=
=20
>>> have it as an algorithm in the standard library. It's not used frequent=
ly=20
>>> enough to need such canonization, and we can achieve the same effect wi=
th a=20
>>> simple lambda.
>>>
>> =20
>> =20
>> I even do not want to answer to such "argument" as "So why do we need a=
=20
>> whole new function for something that we can trivially do ourselves?". I=
=20
>> heard is thousand times.
>>
>
> The reason you hear this argument "thousand times" is because it's a=20
> reasonable argument. People can come up with innumerable patterns of rang=
e=20
> iteration that could be represented by algorithms.
>
> In general, things that become standard library algorithms fill one of=20
> these criteria:
>
> 1: It's quite common. Taking the sum of all values in a list, calling a=
=20
> function and storing the result in a list, searching for a value, etc are=
=20
> simple tasks, but they're tasks that programmers often have to do.
>
> 2: It's hard to write efficiently. std::sort, std::binary_search, etc, ar=
e=20
> all algorithms that are very easy to get wrong. Either you make it slow, =
or=20
> you make it behave incorrectly. By having a simple algorithm,
>
> In general, find first/last negative value followed by accumulate is=20
> sufficient for most people's needs. Those people who actually need this=
=20
> either know they need it through profiling, or are using InputIterators=
=20
> that they can't traverse multiple times. I just don't see this as being a=
=20
> compelling need for such a feature.
> =20
>
>> I hope that you can also yourself to write strlen can not you?:) At leas=
t=20
>> as far as I know all students write strlen while are studing C/C++.
>>
>
> Are you honestly suggesting that this specific adaptation of accumulate i=
s=20
> anywhere near as generally useful as strlen?
>
> However I will do one remark. As the post of Jeremiah Willcock showed no=
t=20
>> all can write this algorithm.
>>
>
> How did his post show that? It showed that he wrote the first variation=
=20
> (everything from the last key value on). It explained how to write the=20
> second one, but he didn't write it for you.
> =20
>
>> There will be numerous realizations that in most part will be ineffectiv=
e=20
>> and that can be difficult to understand and to read what the author was=
=20
>> going to do.=20
>>
>
> And this is what you consider easier to understand:
>
> accumulate_first_if( std::reverse_iterator<int *>( std::end( a ) ),
> std::reverse_iterator<int *>( std::begin( a ) ),
> 0,
> std::bind2nd( std::greater_equal<int>(), 0 ) );
>
> The other one was much easier to digest.
>
=20
=20
I seriously think that this specific adaptation of accumulate is generally=
=20
useful. I will not compare it with strlen because it is obvious that some=
=20
algorithms are used more rarely than others. But this modification makes=
=20
algorithm std::accumulate of full value.
=20
I will not point out that the realization of the task suggested by Jeremiah=
=20
Willcock is ineffective. It is clear without my comments. I will say just=
=20
that it is invalid! Why? Because it has a side effect. It touches=20
elements that it shall not touch. You forgot that usage of std::accumulate=
=20
is very multiform. For example a pointer to character can be used as the=20
initial value. And this pointer can be incremented in the binary operation.=
=20
Moreover also objects that pointed by this pointer can be changed. So when=
=20
at last you will find the required subsequence you will be unable to=20
rollback your changes.
=20
I will not discuss your statement that "In general, find first/last=20
negative value followed by accumulate is sufficient for most people's=20
needs." Maybe you are speaking about students and their assignments. I=20
think that this statement is futile. I only would like to point out that=20
very often some algorithm is used rare because its possibility are=20
artificially restricted.
=20
Let assume that there is no such modification of std::accumulate that I=20
suggested. What do others do in this case? They put aside the algorithm and=
=20
try to invent something pwn. So we get a zoo of various realizations for a=
=20
simple task. And moreover very ofthen these realizations are incorrect as=
=20
I demonstrated relative to the realization of Jeremiah Willcock.=20
=20
This modification makes the algorithm of full value and essentially enlages=
=20
its usage.=20
=20
We have two idioms for the sequential access of a sequence. Either we go=20
through all elements of a sequence or we stop when required elements were=
=20
found. Now std::accumulate includes the both idioms. This makes its usage=
=20
very effective.
--=20
------=_Part_288_19106165.1357884445469
Content-Type: text/html; charset=KOI8-R
Content-Transfer-Encoding: quoted-printable
<br>=D0=D1=D4=CE=C9=C3=C1, 11 =D1=CE=D7=C1=D2=D1 2013 =C7., 8:15:11 UT=
C+4 =D0=CF=CC=D8=DA=CF=D7=C1=D4=C5=CC=D8 Nicol Bolas =CE=C1=D0=C9=D3=C1=CC:=
<blockquote style=3D"margin: 0px 0px 0px 0.8ex; padding-left: 1ex; border-l=
eft-color: rgb(204, 204, 204); border-left-width: 1px; border-left-style: s=
olid;" class=3D"gmail_quote"><br><br>On Thursday, January 10, 2013 6:41:22 =
PM UTC-8, Vlad from Moscow wrote:<blockquote style=3D"margin: 0px 0px 0px 0=
..8ex; padding-left: 1ex; border-left-color: rgb(204, 204, 204); border-left=
-width: 1px; border-left-style: solid;" class=3D"gmail_quote"><br>=D0=D1=D4=
=CE=C9=C3=C1, 11 =D1=CE=D7=C1=D2=D1 2013 =C7., 5:57:40 UTC+4 =D0=CF=CC=
=D8=DA=CF=D7=C1=D4=C5=CC=D8 Nicol Bolas =CE=C1=D0=C9=D3=C1=CC:<blockquote s=
tyle=3D"margin: 0px 0px 0px 0.8ex; padding-left: 1ex; border-left-color: rg=
b(204, 204, 204); border-left-width: 1px; border-left-style: solid;" class=
=3D"gmail_quote">On Thursday, January 10, 2013 5:38:25 PM UTC-8, Vlad from =
Moscow wrote:<blockquote style=3D"margin: 0px 0px 0px 0.8ex; padding-left: =
1ex; border-left-color: rgb(204, 204, 204); border-left-width: 1px; border-=
left-style: solid;" class=3D"gmail_quote"><br>=D0=D1=D4=CE=C9=C3=C1, 11 =D1=
=CE=D7=C1=D2=D1 2013 =C7., 2:58:28 UTC+4 =D0=CF=CC=D8=DA=CF=D7=C1=D4=
=C5=CC=D8 jewillco =CE=C1=D0=C9=D3=C1=CC:<blockquote style=3D"margin: 0px 0=
px 0px 0.8ex; padding-left: 1ex; border-left-color: rgb(204, 204, 204); bor=
der-left-width: 1px; border-left-style: solid;" class=3D"gmail_quote">On Th=
u, 10 Jan 2013, Fernando Cacciola wrote:
<br>
<br>> On Thu, Jan 10, 2013 at 8:29 PM, Vlad from Moscow <<a>vlad....@=
mail.ru</a>> wrote:
<br>>> At first let consider a simple assignment: calculate sum of al=
l elements of
<br>>> a integer array after the last negative element.
<br>>> It seems that the assignment should be done in two phases. Fir=
stly the last
<br>>> negative element should be found for example with std::find_if=
by supplying
<br>>> reverse iterators. Secondly standard algorithm std::accumulate=
will be used.
<br>>>
<br>>> This approach has a serious shortage. Nothing prevents t=
hat the last
<br>>> negative element of the array will be at the same time the fir=
st element of
<br>>> the array. So the array will be traversed twice. It is o=
bvious that this
<br>>> approach is ineffective.
<br>>>
<br>>> But how to do the task in more effective way and preserve the =
symantic of
<br>>> std::accumulate?
<br>>>
<br>>>
<br>>> I suggest a new modification of std::accumulate that resolves =
this problem.
<br>>>
<br>>>
<br>>> This modifications includes two forms of the algorithm
<br>>>
<br>>>
<br>>> template <class InputIterator, class T, class UnaryPredicat=
e, class
<br>>> BinaryOperation>
<br>>> T accumulate_first_if( InputIterator first,
<br>>> =
InputIterator last,
<br>>> T init,
<br>>> UnaryPredicate unary_predicate,
<br>>> BinaryOperation binary_operation )
<br>>> {
<br>>> for ( ; first !=3D last && unary_predicate( *fir=
st ) ; ++first )
<br>>> {
<br>>> init =3D binary_operation( init, *first );
<br>>> }
<br>>> return ( init );
<br>>> }
<br>>
<br>> Actually, I'd like to see a more generalized approach.
<br>>
<br>> What you've shown is the case where a standard algorithm should be
<br>> applied to a subset of a sequence, and you noticed that it is wast=
eful
<br>> to determine the sub-sequence in a separate pass.
<br>> For this case, you are of course correct, and the solution would
<br>> indeed be a loop of the form you just proposed.
<br>>
<br>> However, I'm not sure if providing flavors of the algorithm that
<br>> combine with this particular sub-sequence selection is the best
<br>> approach. It's evident that you'll have to propose the same for pr=
etty
<br>> much all other algorithms. And I wonder if there couldn't be other
<br>> forms of sub-sequencing as well (I'm thinking direct filtering but
<br>> that can be handled by specialized iterators).
<br>
<br>This operation can also be handled using the normal std::accumulate; fo=
r=20
<br>your example, you would use:
<br>
<br>accumulate(first, last, 0,
<br> [](int a, int b) {if (b < =
0) return 0; else return a + b;});
<br>
<br>That gives a single pass over the sequence. For accumulating up t=
o the=20
<br>first negative number, you would want a separate algorithm to allow the=
=20
<br>iteration to stop early (you can use std::accumulate if you can afford =
to=20
<br>iterate the entire sequence) or the approach Fernando is proposing with=
a=20
<br>way to make a range of "all elements up to the first negative one."
<br>
<br>-- Jeremiah Willcock
<br></blockquote><div> </div><div>It is a remarkable idea but it =
is what I wanted to escape suggesting the new algorithm. </=
div></blockquote><div><br>That's part of the point, and it's the reason why=
we have lambdas: so that we don't have to have a new algorithm for every c=
orner case imaginable.<br><br>Code-wise, his std::accumulate+lambda is in e=
very way equivalent to what you proposed. It's not particularly long, and i=
t's very clear as to what it does. Odds are good that they'll even compile =
to the same code.<br><br>So why do we need a whole new function for somethi=
ng that we can trivially do ourselves?<br><br>While this algorithm would ce=
rtainly see use, I don't see the <i>need</i> to have it as an algorithm in =
the standard library. It's not used frequently enough to need such canoniza=
tion, and we can achieve the same effect with a simple lambda.<br></div></b=
lockquote><div> </div><div> </div><div>I even do not want to answ=
er to such "argument" as "So why do we need a whole new function for =
something that we can trivially do ourselves?". I heard is thousand times.<=
/div></blockquote><div><br>The reason you hear this argument "thousand time=
s" is because it's a reasonable argument. People can come up with innumerab=
le patterns of range iteration that could be represented by algorithms.<br>=
<br>In general, things that become standard library algorithms fill one of =
these criteria:<br><br>1: It's quite common. Taking the sum of all values i=
n a list, calling a function and storing the result in a list, searching fo=
r a value, etc are simple tasks, but they're tasks that programmers often h=
ave to do.<br><br>2: It's hard to write efficiently. std::sort, std::binary=
_search, etc, are all algorithms that are very easy to get wrong. Either yo=
u make it slow, or you make it behave incorrectly. By having a simple algor=
ithm,<br><br>In general, find first/last negative value followed by accumul=
ate is sufficient for most people's needs. Those people who actually need t=
his either know they need it through profiling, or are using InputIterators=
that they can't traverse multiple times. I just don't see this as being a =
compelling need for such a feature.<br> </div><blockquote style=3D"mar=
gin: 0px 0px 0px 0.8ex; padding-left: 1ex; border-left-color: rgb(204, 204,=
204); border-left-width: 1px; border-left-style: solid;" class=3D"gmail_qu=
ote"><div>I hope that you can also yourself to write strlen can not you?:) =
At least as far as I know all students write strlen while are studing=
C/C++.<br></div></blockquote><div><br>Are you honestly suggesting that thi=
s specific adaptation of accumulate is anywhere near as generally useful as=
strlen?<br><br></div><blockquote style=3D"margin: 0px 0px 0px 0.8ex; paddi=
ng-left: 1ex; border-left-color: rgb(204, 204, 204); border-left-width: 1px=
; border-left-style: solid;" class=3D"gmail_quote"><div>However I will do o=
ne remark. As the post of Jeremiah Willcock showed not all can write =
this algorithm.</div></blockquote><div><br>How did his post show that? It s=
howed that he wrote the first variation (everything from the last key value=
on). It explained how to write the second one, but he didn't write it for =
you.<br> </div><blockquote style=3D"margin: 0px 0px 0px 0.8ex; padding=
-left: 1ex; border-left-color: rgb(204, 204, 204); border-left-width: 1px; =
border-left-style: solid;" class=3D"gmail_quote"><div> There will be numero=
us realizations that in most part will be ineffective and that can be diffi=
cult to understand and to read what the author was going to do. <br></div><=
/blockquote><div><br>And this is what you consider easier to understand:<br=
><br><div style=3D"border: 1px solid rgb(187, 187, 187); word-wrap: break-w=
ord; background-color: rgb(250, 250, 250);"><code><div><span style=3D"color=
: rgb(0, 0, 0);">accumulate_first_if</span><span style=3D"color: rgb(102, 1=
02, 0);">(</span><span style=3D"color: rgb(0, 0, 0);"> std</span><span styl=
e=3D"color: rgb(102, 102, 0);">::</span><span style=3D"color: rgb(0, 0, 0);=
">reverse_iterator</span><span style=3D"color: rgb(102, 102, 0);"><</spa=
n><span style=3D"color: rgb(0, 0, 136);">int</span><span style=3D"color: rg=
b(0, 0, 0);"> </span><span style=3D"color: rgb(102, 102, 0);">*>(</span>=
<span style=3D"color: rgb(0, 0, 0);"> std</span><span style=3D"color: rgb(1=
02, 102, 0);">::</span><span style=3D"color: rgb(0, 0, 136);">end</span><sp=
an style=3D"color: rgb(102, 102, 0);">(</span><span style=3D"color: rgb(0, =
0, 0);"> a </span><span style=3D"color: rgb(102, 102, 0);">)</span><span st=
yle=3D"color: rgb(0, 0, 0);"> </span><span style=3D"color: rgb(102, 102, 0)=
;">),</span><span style=3D"color: rgb(0, 0, 0);"><br> &=
nbsp; std</span><span style=
=3D"color: rgb(102, 102, 0);">::</span><span style=3D"color: rgb(0, 0, 0);"=
>reverse_iterator</span><span style=3D"color: rgb(102, 102, 0);"><</span=
><span style=3D"color: rgb(0, 0, 136);">int</span><span style=3D"color: rgb=
(0, 0, 0);"> </span><span style=3D"color: rgb(102, 102, 0);">*>(</span><=
span style=3D"color: rgb(0, 0, 0);"> std</span><span style=3D"color: rgb(10=
2, 102, 0);">::</span><span style=3D"color: rgb(0, 0, 136);">begin</span><s=
pan style=3D"color: rgb(102, 102, 0);">(</span><span style=3D"color: rgb(0,=
0, 0);"> a </span><span style=3D"color: rgb(102, 102, 0);">)</span><span s=
tyle=3D"color: rgb(0, 0, 0);"> </span><span style=3D"color: rgb(102, 102, 0=
);">),</span><span style=3D"color: rgb(0, 0, 0);"><br> =
</span><span style=
=3D"color: rgb(0, 102, 102);">0</span><span style=3D"color: rgb(102, 102, 0=
);">,</span><span style=3D"color: rgb(0, 0, 0);"><br> &=
nbsp; std</span><span style=
=3D"color: rgb(102, 102, 0);">::</span><span style=3D"color: rgb(0, 0, 0);"=
>bind2nd</span><span style=3D"color: rgb(102, 102, 0);">(</span><span style=
=3D"color: rgb(0, 0, 0);"> std</span><span style=3D"color: rgb(102, 102, 0)=
;">::</span><span style=3D"color: rgb(0, 0, 0);">greater_equal</span><span =
style=3D"color: rgb(0, 136, 0);"><int></span><span style=3D"color: rg=
b(102, 102, 0);">(),</span><span style=3D"color: rgb(0, 0, 0);"> </span><sp=
an style=3D"color: rgb(0, 102, 102);">0</span><span style=3D"color: rgb(0, =
0, 0);"> </span><span style=3D"color: rgb(102, 102, 0);">)</span><span styl=
e=3D"color: rgb(0, 0, 0);"> </span><span style=3D"color: rgb(102, 102, 0);"=
>);</span></div></code></div><div><br></div>The other one was much easier t=
o digest.<br></div></blockquote><div> </div><div> </div><div>I se=
riously think that this specific adaptation of accumulate is generally=
useful. I will not compare it with strlen because it is obvious that some =
algorithms are used more rarely than others. But this modificat=
ion makes algorithm std::accumulate of full value.</div><div> </div><d=
iv>I will not point out that the realization of the task suggested by Jerem=
iah Willcock is ineffective. It is clear without my comments. I =
will say just that it is invalid! Why? Because it has a side ef=
fect. It touches elements that it shall not touch. You forgot that&nbs=
p;usage of std::accumulate is very multiform. For example a pointer to char=
acter can be used as the initial value. And this pointer can be incremented=
in the binary operation. Moreover also objects that pointed by this p=
ointer can be changed. So when at last you will find the required subsequen=
ce you will be unable to rollback your changes.</div><div> </div><div>=
I will not discuss your statement that "In general, find first/last negativ=
e value followed by accumulate is sufficient for most people's needs." Mayb=
e you are speaking about students and their assignments. I think that this =
statement is futile. I only would like to point out that very often some al=
gorithm is used rare because its possibility are artificially restric=
ted.</div><div> </div><div>Let assume that there is no such modificati=
on of std::accumulate that I suggested. What do others do in this case=
? They put aside the algorithm and try to invent something pwn. So we =
get a zoo of various realizations for a simple task. And moreover very ofth=
en these realizations are incorrect as I demonstrated relative to the =
realization of Jeremiah Willcock. </div><div> </div><d=
iv>This modification makes the algorithm of full value and essentially enla=
ges its usage. </div><div> </div><div>We have two idioms for the =
sequential access of a sequence. Either we go through all elements of a seq=
uence or we stop when required elements were found. Now std::accumulate inc=
ludes the both idioms. This makes its usage very effective.</div>
<p></p>
-- <br />
<br />
<br />
<br />
------=_Part_288_19106165.1357884445469--
.
Author: Nicol Bolas <jmckesson@gmail.com>
Date: Thu, 10 Jan 2013 23:07:02 -0800 (PST)
Raw View
------=_Part_511_16260466.1357888022195
Content-Type: text/plain; charset=KOI8-R
Content-Transfer-Encoding: quoted-printable
On Thursday, January 10, 2013 10:07:25 PM UTC-8, Vlad from Moscow wrote:
>
>
> =D0=D1=D4=CE=C9=C3=C1, 11 =D1=CE=D7=C1=D2=D1 2013 =C7., 8:15:11 UTC+4 =D0=
=CF=CC=D8=DA=CF=D7=C1=D4=C5=CC=D8 Nicol Bolas =CE=C1=D0=C9=D3=C1=CC:
>>
>>
>>
>> On Thursday, January 10, 2013 6:41:22 PM UTC-8, Vlad from Moscow wrote:
>>>
>>>
>>> =D0=D1=D4=CE=C9=C3=C1, 11 =D1=CE=D7=C1=D2=D1 2013 =C7., 5:57:40 UTC+4 =
=D0=CF=CC=D8=DA=CF=D7=C1=D4=C5=CC=D8 Nicol Bolas=20
>>> =CE=C1=D0=C9=D3=C1=CC:
>>>>
>>>> On Thursday, January 10, 2013 5:38:25 PM UTC-8, Vlad from Moscow wrote=
:
>>>>>
>>>>>
>>>>> =D0=D1=D4=CE=C9=C3=C1, 11 =D1=CE=D7=C1=D2=D1 2013 =C7., 2:58:28 UTC+4=
=D0=CF=CC=D8=DA=CF=D7=C1=D4=C5=CC=D8 jewillco=20
>>>>> =CE=C1=D0=C9=D3=C1=CC:
>>>>>>
>>>>>> On Thu, 10 Jan 2013, Fernando Cacciola wrote:=20
>>>>>>
>>>>>> > On Thu, Jan 10, 2013 at 8:29 PM, Vlad from Moscow <vlad....@mail.r=
u>=20
>>>>>> wrote:=20
>>>>>> >> At first let consider a simple assignment: calculate sum of all=
=20
>>>>>> elements of=20
>>>>>> >> a integer array after the last negative element.=20
>>>>>> >> It seems that the assignment should be done in two phases. Firstl=
y=20
>>>>>> the last=20
>>>>>> >> negative element should be found for example with std::find_if by=
=20
>>>>>> supplying=20
>>>>>> >> reverse iterators. Secondly standard algorithm std::accumulate=20
>>>>>> will be used.=20
>>>>>> >>=20
>>>>>> >> This approach has a serious shortage. Nothing prevents that the=
=20
>>>>>> last=20
>>>>>> >> negative element of the array will be at the same time the first=
=20
>>>>>> element of=20
>>>>>> >> the array. So the array will be traversed twice. It is obvious=
=20
>>>>>> that this=20
>>>>>> >> approach is ineffective.=20
>>>>>> >>=20
>>>>>> >> But how to do the task in more effective way and preserve the=20
>>>>>> symantic of=20
>>>>>> >> std::accumulate?=20
>>>>>> >>=20
>>>>>> >>=20
>>>>>> >> I suggest a new modification of std::accumulate that resolves thi=
s=20
>>>>>> problem.=20
>>>>>> >>=20
>>>>>> >>=20
>>>>>> >> This modifications includes two forms of the algorithm=20
>>>>>> >>=20
>>>>>> >>=20
>>>>>> >> template <class InputIterator, class T, class UnaryPredicate,=20
>>>>>> class=20
>>>>>> >> BinaryOperation>=20
>>>>>> >> T accumulate_first_if( InputIterator first,=20
>>>>>> >> InputIterator last,=20
>>>>>> >> T init,=20
>>>>>> >> UnaryPredicate unary_predicate,=20
>>>>>> >> BinaryOperation binary_operation )=20
>>>>>> >> {=20
>>>>>> >> for ( ; first !=3D last && unary_predicate( *first ) ; ++first )=
=20
>>>>>> >> {=20
>>>>>> >> init =3D binary_operation( init, *first );=20
>>>>>> >> }=20
>>>>>> >> return ( init );=20
>>>>>> >> }=20
>>>>>> >=20
>>>>>> > Actually, I'd like to see a more generalized approach.=20
>>>>>> >=20
>>>>>> > What you've shown is the case where a standard algorithm should be=
=20
>>>>>> > applied to a subset of a sequence, and you noticed that it is=20
>>>>>> wasteful=20
>>>>>> > to determine the sub-sequence in a separate pass.=20
>>>>>> > For this case, you are of course correct, and the solution would=
=20
>>>>>> > indeed be a loop of the form you just proposed.=20
>>>>>> >=20
>>>>>> > However, I'm not sure if providing flavors of the algorithm that=
=20
>>>>>> > combine with this particular sub-sequence selection is the best=20
>>>>>> > approach. It's evident that you'll have to propose the same for=20
>>>>>> pretty=20
>>>>>> > much all other algorithms. And I wonder if there couldn't be other=
=20
>>>>>> > forms of sub-sequencing as well (I'm thinking direct filtering but=
=20
>>>>>> > that can be handled by specialized iterators).=20
>>>>>>
>>>>>> This operation can also be handled using the normal std::accumulate;=
=20
>>>>>> for=20
>>>>>> your example, you would use:=20
>>>>>>
>>>>>> accumulate(first, last, 0,=20
>>>>>> [](int a, int b) {if (b < 0) return 0; else return a +=
=20
>>>>>> b;});=20
>>>>>>
>>>>>> That gives a single pass over the sequence. For accumulating up to=
=20
>>>>>> the=20
>>>>>> first negative number, you would want a separate algorithm to allow=
=20
>>>>>> the=20
>>>>>> iteration to stop early (you can use std::accumulate if you can=20
>>>>>> afford to=20
>>>>>> iterate the entire sequence) or the approach Fernando is proposing=
=20
>>>>>> with a=20
>>>>>> way to make a range of "all elements up to the first negative one."=
=20
>>>>>>
>>>>>> -- Jeremiah Willcock=20
>>>>>>
>>>>> =20
>>>>> It is a remarkable idea but it is what I wanted to escape suggesting=
=20
>>>>> the new algorithm. =20
>>>>>
>>>>
>>>> That's part of the point, and it's the reason why we have lambdas: so=
=20
>>>> that we don't have to have a new algorithm for every corner case imagi=
nable.
>>>>
>>>> Code-wise, his std::accumulate+lambda is in every way equivalent to=20
>>>> what you proposed. It's not particularly long, and it's very clear as =
to=20
>>>> what it does. Odds are good that they'll even compile to the same code=
..
>>>>
>>>> So why do we need a whole new function for something that we can=20
>>>> trivially do ourselves?
>>>>
>>>> While this algorithm would certainly see use, I don't see the *need*to=
have it as an algorithm in the standard library. It's not used=20
>>>> frequently enough to need such canonization, and we can achieve the sa=
me=20
>>>> effect with a simple lambda.
>>>>
>>> =20
>>> =20
>>> I even do not want to answer to such "argument" as "So why do we need =
a=20
>>> whole new function for something that we can trivially do ourselves?". =
I=20
>>> heard is thousand times.
>>>
>>
>> The reason you hear this argument "thousand times" is because it's a=20
>> reasonable argument. People can come up with innumerable patterns of ran=
ge=20
>> iteration that could be represented by algorithms.
>>
>> In general, things that become standard library algorithms fill one of=
=20
>> these criteria:
>>
>> 1: It's quite common. Taking the sum of all values in a list, calling a=
=20
>> function and storing the result in a list, searching for a value, etc ar=
e=20
>> simple tasks, but they're tasks that programmers often have to do.
>>
>> 2: It's hard to write efficiently. std::sort, std::binary_search, etc,=
=20
>> are all algorithms that are very easy to get wrong. Either you make it=
=20
>> slow, or you make it behave incorrectly. By having a simple algorithm,
>>
>> In general, find first/last negative value followed by accumulate is=20
>> sufficient for most people's needs. Those people who actually need this=
=20
>> either know they need it through profiling, or are using InputIterators=
=20
>> that they can't traverse multiple times. I just don't see this as being =
a=20
>> compelling need for such a feature.
>> =20
>>
>>> I hope that you can also yourself to write strlen can not you?:) At=20
>>> least as far as I know all students write strlen while are studing C/C=
++.
>>>
>>
>> Are you honestly suggesting that this specific adaptation of accumulate=
=20
>> is anywhere near as generally useful as strlen?
>>
>> However I will do one remark. As the post of Jeremiah Willcock showed=
=20
>>> not all can write this algorithm.
>>>
>>
>> How did his post show that? It showed that he wrote the first variation=
=20
>> (everything from the last key value on). It explained how to write the=
=20
>> second one, but he didn't write it for you.
>> =20
>>
>>> There will be numerous realizations that in most part will be=20
>>> ineffective and that can be difficult to understand and to read what th=
e=20
>>> author was going to do.=20
>>>
>>
>> And this is what you consider easier to understand:
>>
>> accumulate_first_if( std::reverse_iterator<int *>( std::end( a ) ),
>> std::reverse_iterator<int *>( std::begin( a ) ),
>> 0,
>> std::bind2nd( std::greater_equal<int>(), 0 ) );
>>
>> The other one was much easier to digest.
>>
> =20
> =20
> I seriously think that this specific adaptation of accumulate is generall=
y=20
> useful. I will not compare it with strlen because it is obvious that some=
=20
> algorithms are used more rarely than others. But this modification make=
s=20
> algorithm std::accumulate of full value.
> =20
> I will not point out that the realization of the task suggested by=20
> Jeremiah Willcock is ineffective. It is clear without my comments.
>
If it were "clear without my comments," then I wouldn't have said that it=
=20
solved the problem.
I will say just that it is invalid! Why? Because it has a side effect. It=
=20
> touches elements that it shall not touch. You forgot that usage of=20
> std::accumulate is very multiform. For example a pointer to character can=
=20
> be used as the initial value. And this pointer can be incremented in=20
> the binary operation. Moreover also objects that pointed by this pointer=
=20
> can be changed. So when at last you will find the required subsequence yo=
u=20
> will be unable to rollback your changes.
>
If I see `std::accumulate` in someone's code, I would generally assume that=
=20
it's accumulating a value. And accumulating a value should not *modify the=
=20
input data*. That's not to say that you can't do it; it's certainly legal=
=20
C++ to do that. But it would be very confusing for the reader as to what=20
you're doing.
Let assume that there is no such modification of std::accumulate that I=20
> suggested. What do others do in this case? They put aside the algorithm a=
nd=20
> try to invent something pwn. So we get a zoo of various realizations for =
a=20
> simple task. And moreover very ofthen these realizations are incorrect as=
=20
> I demonstrated relative to the realization of Jeremiah Willcock.
>
All you get is this:
int accum =3D 0;
for(int val : range)
{
if(val < 0) break;
accum +=3D val;
}
This is what you're talking about saving someone from writing. This is far=
=20
from an onerous burden.
This modification makes the algorithm of full value and essentially enlages=
=20
> its usage.
> =20
> We have two idioms for the sequential access of a sequence. Either we go=
=20
> through all elements of a sequence or we stop when required elements were=
=20
> found. Now std::accumulate includes the both idioms. This makes its usage=
=20
> very effective.
>
Or, you could just do this:
int accum =3D std::accumulate(rng | range::break_if([](int t) {return t < 0
;}), 0);
And if you want to do it from the rear:
int accum =3D std::accumulate(rng | range::reversed() | range::break_if([](=
intt
) {return t < 0;}), 0);
This assumes range-based algorithms and adapters, ala Boost.Range.=20
`break_if` is not actually in Boost.Range, but it would treat an iterator=
=20
as the end iterator if the predicate returns true. It therefore effectively=
=20
cuts the range off.
It also expresses the intent better. You're not using a different=20
algorithm; you're accumulating just like before. So you use the=20
`accumulate` algorithm, just like before What you're really doing is=20
modifying the *range* you're accumulating over. So in this code, we *modify=
=20
the range* and use std::accumulate.
And because of that, you can now use this with pretty much any algorithm=20
(that accepts a forward range). If you want to do std::transform based for=
=20
the first or last numbers before the first negative, you can. You don't=20
need std::transform_first_if or whatever.
It can be applied to arbitrary algorithms (that use forward ranges). It's=
=20
much more versatile and flexible.
--=20
------=_Part_511_16260466.1357888022195
Content-Type: text/html; charset=KOI8-R
Content-Transfer-Encoding: quoted-printable
<br><br>On Thursday, January 10, 2013 10:07:25 PM UTC-8, Vlad from Moscow w=
rote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8e=
x;border-left: 1px #ccc solid;padding-left: 1ex;"><br>=D0=D1=D4=CE=C9=C3=C1=
, 11 =D1=CE=D7=C1=D2=D1 2013 =C7., 8:15:11 UTC+4 =D0=CF=CC=D8=DA=CF=D7=
=C1=D4=C5=CC=D8 Nicol Bolas =CE=C1=D0=C9=D3=C1=CC:<blockquote style=3D"marg=
in:0px 0px 0px 0.8ex;padding-left:1ex;border-left-color:rgb(204,204,204);bo=
rder-left-width:1px;border-left-style:solid" class=3D"gmail_quote"><br><br>=
On Thursday, January 10, 2013 6:41:22 PM UTC-8, Vlad from Moscow wrote:<blo=
ckquote style=3D"margin:0px 0px 0px 0.8ex;padding-left:1ex;border-left-colo=
r:rgb(204,204,204);border-left-width:1px;border-left-style:solid" class=3D"=
gmail_quote"><br>=D0=D1=D4=CE=C9=C3=C1, 11 =D1=CE=D7=C1=D2=D1 2013 =C7=
.., 5:57:40 UTC+4 =D0=CF=CC=D8=DA=CF=D7=C1=D4=C5=CC=D8 Nicol Bolas =CE=C1=D0=
=C9=D3=C1=CC:<blockquote style=3D"margin:0px 0px 0px 0.8ex;padding-left:1ex=
;border-left-color:rgb(204,204,204);border-left-width:1px;border-left-style=
:solid" class=3D"gmail_quote">On Thursday, January 10, 2013 5:38:25 PM UTC-=
8, Vlad from Moscow wrote:<blockquote style=3D"margin:0px 0px 0px 0.8ex;pad=
ding-left:1ex;border-left-color:rgb(204,204,204);border-left-width:1px;bord=
er-left-style:solid" class=3D"gmail_quote"><br>=D0=D1=D4=CE=C9=C3=C1, 11 =
=D1=CE=D7=C1=D2=D1 2013 =C7., 2:58:28 UTC+4 =D0=CF=CC=D8=DA=CF=D7=C1=
=D4=C5=CC=D8 jewillco =CE=C1=D0=C9=D3=C1=CC:<blockquote style=3D"margin:0px=
0px 0px 0.8ex;padding-left:1ex;border-left-color:rgb(204,204,204);border-l=
eft-width:1px;border-left-style:solid" class=3D"gmail_quote">On Thu, 10 Jan=
2013, Fernando Cacciola wrote:
<br>
<br>> On Thu, Jan 10, 2013 at 8:29 PM, Vlad from Moscow <<a>vlad....@=
mail.ru</a>> wrote:
<br>>> At first let consider a simple assignment: calculate sum of al=
l elements of
<br>>> a integer array after the last negative element.
<br>>> It seems that the assignment should be done in two phases. Fir=
stly the last
<br>>> negative element should be found for example with std::find_if=
by supplying
<br>>> reverse iterators. Secondly standard algorithm std::accumulate=
will be used.
<br>>>
<br>>> This approach has a serious shortage. Nothing prevents t=
hat the last
<br>>> negative element of the array will be at the same time the fir=
st element of
<br>>> the array. So the array will be traversed twice. It is o=
bvious that this
<br>>> approach is ineffective.
<br>>>
<br>>> But how to do the task in more effective way and preserve the =
symantic of
<br>>> std::accumulate?
<br>>>
<br>>>
<br>>> I suggest a new modification of std::accumulate that resolves =
this problem.
<br>>>
<br>>>
<br>>> This modifications includes two forms of the algorithm
<br>>>
<br>>>
<br>>> template <class InputIterator, class T, class UnaryPredicat=
e, class
<br>>> BinaryOperation>
<br>>> T accumulate_first_if( InputIterator first,
<br>>> =
InputIterator last,
<br>>> T init,
<br>>> UnaryPredicate unary_predicate,
<br>>> BinaryOperation binary_operation )
<br>>> {
<br>>> for ( ; first !=3D last && unary_predicate( *fir=
st ) ; ++first )
<br>>> {
<br>>> init =3D binary_operation( init, *first );
<br>>> }
<br>>> return ( init );
<br>>> }
<br>>
<br>> Actually, I'd like to see a more generalized approach.
<br>>
<br>> What you've shown is the case where a standard algorithm should be
<br>> applied to a subset of a sequence, and you noticed that it is wast=
eful
<br>> to determine the sub-sequence in a separate pass.
<br>> For this case, you are of course correct, and the solution would
<br>> indeed be a loop of the form you just proposed.
<br>>
<br>> However, I'm not sure if providing flavors of the algorithm that
<br>> combine with this particular sub-sequence selection is the best
<br>> approach. It's evident that you'll have to propose the same for pr=
etty
<br>> much all other algorithms. And I wonder if there couldn't be other
<br>> forms of sub-sequencing as well (I'm thinking direct filtering but
<br>> that can be handled by specialized iterators).
<br>
<br>This operation can also be handled using the normal std::accumulate; fo=
r=20
<br>your example, you would use:
<br>
<br>accumulate(first, last, 0,
<br> [](int a, int b) {if (b < =
0) return 0; else return a + b;});
<br>
<br>That gives a single pass over the sequence. For accumulating up t=
o the=20
<br>first negative number, you would want a separate algorithm to allow the=
=20
<br>iteration to stop early (you can use std::accumulate if you can afford =
to=20
<br>iterate the entire sequence) or the approach Fernando is proposing with=
a=20
<br>way to make a range of "all elements up to the first negative one."
<br>
<br>-- Jeremiah Willcock
<br></blockquote><div> </div><div>It is a remarkable idea but it =
is what I wanted to escape suggesting the new algorithm. </=
div></blockquote><div><br>That's part of the point, and it's the reason why=
we have lambdas: so that we don't have to have a new algorithm for every c=
orner case imaginable.<br><br>Code-wise, his std::accumulate+lambda is in e=
very way equivalent to what you proposed. It's not particularly long, and i=
t's very clear as to what it does. Odds are good that they'll even compile =
to the same code.<br><br>So why do we need a whole new function for somethi=
ng that we can trivially do ourselves?<br><br>While this algorithm would ce=
rtainly see use, I don't see the <i>need</i> to have it as an algorithm in =
the standard library. It's not used frequently enough to need such canoniza=
tion, and we can achieve the same effect with a simple lambda.<br></div></b=
lockquote><div> </div><div> </div><div>I even do not want to answ=
er to such "argument" as "So why do we need a whole new function for =
something that we can trivially do ourselves?". I heard is thousand times.<=
/div></blockquote><div><br>The reason you hear this argument "thousand time=
s" is because it's a reasonable argument. People can come up with innumerab=
le patterns of range iteration that could be represented by algorithms.<br>=
<br>In general, things that become standard library algorithms fill one of =
these criteria:<br><br>1: It's quite common. Taking the sum of all values i=
n a list, calling a function and storing the result in a list, searching fo=
r a value, etc are simple tasks, but they're tasks that programmers often h=
ave to do.<br><br>2: It's hard to write efficiently. std::sort, std::binary=
_search, etc, are all algorithms that are very easy to get wrong. Either yo=
u make it slow, or you make it behave incorrectly. By having a simple algor=
ithm,<br><br>In general, find first/last negative value followed by accumul=
ate is sufficient for most people's needs. Those people who actually need t=
his either know they need it through profiling, or are using InputIterators=
that they can't traverse multiple times. I just don't see this as being a =
compelling need for such a feature.<br> </div><blockquote style=3D"mar=
gin:0px 0px 0px 0.8ex;padding-left:1ex;border-left-color:rgb(204,204,204);b=
order-left-width:1px;border-left-style:solid" class=3D"gmail_quote"><div>I =
hope that you can also yourself to write strlen can not you?:) At least as =
far as I know all students write strlen while are studing C/C++.<br><=
/div></blockquote><div><br>Are you honestly suggesting that this specific a=
daptation of accumulate is anywhere near as generally useful as strlen?<br>=
<br></div><blockquote style=3D"margin:0px 0px 0px 0.8ex;padding-left:1ex;bo=
rder-left-color:rgb(204,204,204);border-left-width:1px;border-left-style:so=
lid" class=3D"gmail_quote"><div>However I will do one remark. As the post o=
f Jeremiah Willcock showed not all can write this algorithm.</div></b=
lockquote><div><br>How did his post show that? It showed that he wrote the =
first variation (everything from the last key value on). It explained how t=
o write the second one, but he didn't write it for you.<br> </div><blo=
ckquote style=3D"margin:0px 0px 0px 0.8ex;padding-left:1ex;border-left-colo=
r:rgb(204,204,204);border-left-width:1px;border-left-style:solid" class=3D"=
gmail_quote"><div> There will be numerous realizations that in most part wi=
ll be ineffective and that can be difficult to understand and to read what =
the author was going to do. <br></div></blockquote><div><br>And this is wha=
t you consider easier to understand:<br><br><div style=3D"border:1px solid =
rgb(187,187,187);word-wrap:break-word;background-color:rgb(250,250,250)"><c=
ode><div><span style=3D"color:rgb(0,0,0)">accumulate_first_if</span><span s=
tyle=3D"color:rgb(102,102,0)">(</span><span style=3D"color:rgb(0,0,0)"> std=
</span><span style=3D"color:rgb(102,102,0)">::</span><span style=3D"color:r=
gb(0,0,0)">reverse_iterator</span><span style=3D"color:rgb(102,102,0)"><=
</span><span style=3D"color:rgb(0,0,136)">int</span><span style=3D"color:rg=
b(0,0,0)"> </span><span style=3D"color:rgb(102,102,0)">*>(</span><span s=
tyle=3D"color:rgb(0,0,0)"> std</span><span style=3D"color:rgb(102,102,0)">:=
:</span><span style=3D"color:rgb(0,0,136)">end</span><span style=3D"color:r=
gb(102,102,0)">(</span><span style=3D"color:rgb(0,0,0)"> a </span><span sty=
le=3D"color:rgb(102,102,0)">)</span><span style=3D"color:rgb(0,0,0)"> </spa=
n><span style=3D"color:rgb(102,102,0)">),</span><span style=3D"color:rgb(0,=
0,0)"><br> &n=
bsp; std</span><span style=3D"color:rgb(102,102,0)">::</span><span st=
yle=3D"color:rgb(0,0,0)">reverse_iterator</span><span style=3D"color:rgb(10=
2,102,0)"><</span><span style=3D"color:rgb(0,0,136)">int</span><span sty=
le=3D"color:rgb(0,0,0)"> </span><span style=3D"color:rgb(102,102,0)">*>(=
</span><span style=3D"color:rgb(0,0,0)"> std</span><span style=3D"color:rgb=
(102,102,0)">::</span><span style=3D"color:rgb(0,0,136)">begin</span><span =
style=3D"color:rgb(102,102,0)">(</span><span style=3D"color:rgb(0,0,0)"> a =
</span><span style=3D"color:rgb(102,102,0)">)</span><span style=3D"color:rg=
b(0,0,0)"> </span><span style=3D"color:rgb(102,102,0)">),</span><span style=
=3D"color:rgb(0,0,0)"><br> =
</span><span style=3D"color:rgb(0,102,102)">0</s=
pan><span style=3D"color:rgb(102,102,0)">,</span><span style=3D"color:rgb(0=
,0,0)"><br> &=
nbsp; std</span><span style=3D"color:rgb(102,102,0)">::</span><span s=
tyle=3D"color:rgb(0,0,0)">bind2nd</span><span style=3D"color:rgb(102,102,0)=
">(</span><span style=3D"color:rgb(0,0,0)"> std</span><span style=3D"color:=
rgb(102,102,0)">::</span><span style=3D"color:rgb(0,0,0)">greater_equal</sp=
an><span style=3D"color:rgb(0,136,0)"><int></span><span style=3D"colo=
r:rgb(102,102,0)">(),</span><span style=3D"color:rgb(0,0,0)"> </span><span =
style=3D"color:rgb(0,102,102)">0</span><span style=3D"color:rgb(0,0,0)"> </=
span><span style=3D"color:rgb(102,102,0)">)</span><span style=3D"color:rgb(=
0,0,0)"> </span><span style=3D"color:rgb(102,102,0)">);</span></div></code>=
</div><div><br></div>The other one was much easier to digest.<br></div></bl=
ockquote><div> </div><div> </div><div>I seriously think that this=
specific adaptation of accumulate is generally useful. I will not com=
pare it with strlen because it is obvious that some algorithms =
are used more rarely than others. But this modification makes algorithm std=
::accumulate of full value.</div><div> </div><div>I will not point out=
that the realization of the task suggested by Jeremiah Willcock is ineffec=
tive. It is clear without my comments.</div></blockquote><div><br>If i=
t were "clear without my comments," then I wouldn't have said that it solve=
d the problem.<br><br></div><blockquote class=3D"gmail_quote" style=3D"marg=
in: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><d=
iv>I will say just that it is invalid! Why? Because it has a si=
de effect. It touches elements that it shall not touch. You forgot tha=
t usage of std::accumulate is very multiform. For example a pointer to=
character can be used as the initial value. And this pointer can be increm=
ented in the binary operation. Moreover also objects that pointed by t=
his pointer can be changed. So when at last you will find the required subs=
equence you will be unable to rollback your changes.</div></blockquote><div=
><br>If I see `std::accumulate` in someone's code, I would generally assume=
that it's accumulating a value. And accumulating a value should not <i>mod=
ify the input data</i>.
That's not to say that you can't do it; it's certainly legal C++ to do tha=
t. But it would be very confusing for the reader as to what you're doing.<b=
r><br></div><blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-lef=
t: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div></div><div>Le=
t assume that there is no such modification of std::accumulate that I sugge=
sted. What do others do in this case? They put aside the algorith=
m and try to invent something pwn. So we get a zoo of various realizations =
for a simple task. And moreover very ofthen these realizations are incorrec=
t as I demonstrated relative to the realization of Jeremiah=
Willcock.</div></blockquote><div><br>All you get is this:<br><br><div clas=
s=3D"prettyprint" style=3D"background-color: rgb(250, 250, 250); border-col=
or: rgb(187, 187, 187); border-style: solid; border-width: 1px; word-wrap: =
break-word;"><code class=3D"prettyprint"><div class=3D"subprettyprint"><spa=
n style=3D"color: #008;" class=3D"styled-by-prettify">int</span><span style=
=3D"color: #000;" class=3D"styled-by-prettify"> accum </span><span style=3D=
"color: #660;" class=3D"styled-by-prettify">=3D</span><span style=3D"color:=
#000;" class=3D"styled-by-prettify"> </span><span style=3D"color: #066;" c=
lass=3D"styled-by-prettify">0</span><span style=3D"color: #660;" class=3D"s=
tyled-by-prettify">;</span><span style=3D"color: #000;" class=3D"styled-by-=
prettify"><br></span><span style=3D"color: #008;" class=3D"styled-by-pretti=
fy">for</span><span style=3D"color: #660;" class=3D"styled-by-prettify">(</=
span><span style=3D"color: #008;" class=3D"styled-by-prettify">int</span><s=
pan style=3D"color: #000;" class=3D"styled-by-prettify"> val </span><span s=
tyle=3D"color: #660;" class=3D"styled-by-prettify">:</span><span style=3D"c=
olor: #000;" class=3D"styled-by-prettify"> range</span><span style=3D"color=
: #660;" class=3D"styled-by-prettify">)</span><span style=3D"color: #000;" =
class=3D"styled-by-prettify"><br></span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">{</span><span style=3D"color: #000;" class=3D"style=
d-by-prettify"><br> </span><span style=3D"color: #008;" class=3D"styl=
ed-by-prettify">if</span><span style=3D"color: #660;" class=3D"styled-by-pr=
ettify">(</span><span style=3D"color: #000;" class=3D"styled-by-prettify">v=
al </span><span style=3D"color: #660;" class=3D"styled-by-prettify"><</s=
pan><span style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span=
style=3D"color: #066;" class=3D"styled-by-prettify">0</span><span style=3D=
"color: #660;" class=3D"styled-by-prettify">)</span><span style=3D"color: #=
000;" class=3D"styled-by-prettify"> </span><span style=3D"color: #008;" cla=
ss=3D"styled-by-prettify">break</span><span style=3D"color: #660;" class=3D=
"styled-by-prettify">;</span><span style=3D"color: #000;" class=3D"styled-b=
y-prettify"><br> accum </span><span style=3D"color: #660;" class=3D"s=
tyled-by-prettify">+=3D</span><span style=3D"color: #000;" class=3D"styled-=
by-prettify"> val</span><span style=3D"color: #660;" class=3D"styled-by-pre=
ttify">;</span><span style=3D"color: #000;" class=3D"styled-by-prettify"><b=
r></span><span style=3D"color: #660;" class=3D"styled-by-prettify">}</span>=
</div></code></div><br>This is what you're talking about saving someone fro=
m writing. This is far from an onerous burden.<br><br></div><blockquote cla=
ss=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #=
ccc solid;padding-left: 1ex;"><div></div><div>This modification makes the a=
lgorithm of full value and essentially enlages its usage.</div><div> <=
/div><div>We have two idioms for the sequential access of a sequence. Eithe=
r we go through all elements of a sequence or we stop when required element=
s were found. Now std::accumulate includes the both idioms. This makes its =
usage very effective.</div></blockquote><div><br>Or, you could just do this=
:<br><br><div class=3D"prettyprint" style=3D"background-color: rgb(250, 250=
, 250); border-color: rgb(187, 187, 187); border-style: solid; border-width=
: 1px; word-wrap: break-word;"><code class=3D"prettyprint"><div class=3D"su=
bprettyprint"><span style=3D"color: #008;" class=3D"styled-by-prettify">int=
</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> accum </s=
pan><span style=3D"color: #660;" class=3D"styled-by-prettify">=3D</span><sp=
an style=3D"color: #000;" class=3D"styled-by-prettify"> std</span><span sty=
le=3D"color: #660;" class=3D"styled-by-prettify">::</span><span style=3D"co=
lor: #000;" class=3D"styled-by-prettify">accumulate</span><span style=3D"co=
lor: #660;" class=3D"styled-by-prettify">(</span><span style=3D"color: #000=
;" class=3D"styled-by-prettify">rng </span><span style=3D"color: #660;" cla=
ss=3D"styled-by-prettify">|</span><span style=3D"color: #000;" class=3D"sty=
led-by-prettify"> range</span><span style=3D"color: #660;" class=3D"styled-=
by-prettify">::</span><span style=3D"color: #000;" class=3D"styled-by-prett=
ify">break_if</span><span style=3D"color: #660;" class=3D"styled-by-prettif=
y">([](</span><span style=3D"color: #008;" class=3D"styled-by-prettify">int=
</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> t</span><=
span style=3D"color: #660;" class=3D"styled-by-prettify">)</span><span styl=
e=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=3D"colo=
r: #660;" class=3D"styled-by-prettify">{</span><span style=3D"color: #008;"=
class=3D"styled-by-prettify">return</span><span style=3D"color: #000;" cla=
ss=3D"styled-by-prettify"> t </span><span style=3D"color: #660;" class=3D"s=
tyled-by-prettify"><</span><span style=3D"color: #000;" class=3D"styled-=
by-prettify"> </span><span style=3D"color: #066;" class=3D"styled-by-pretti=
fy">0</span><span style=3D"color: #660;" class=3D"styled-by-prettify">;}),<=
/span><span style=3D"color: #000;" class=3D"styled-by-prettify"> </span><sp=
an style=3D"color: #066;" class=3D"styled-by-prettify">0</span><span style=
=3D"color: #660;" class=3D"styled-by-prettify">);</span><span style=3D"colo=
r: #000;" class=3D"styled-by-prettify"><br></span></div></code></div><br>An=
d if you want to do it from the rear:<br><br><div class=3D"prettyprint" sty=
le=3D"background-color: rgb(250, 250, 250); border-color: rgb(187, 187, 187=
); border-style: solid; border-width: 1px; word-wrap: break-word;"><code cl=
ass=3D"prettyprint"><div class=3D"subprettyprint"><span style=3D"color: #00=
8;" class=3D"styled-by-prettify">int</span><span style=3D"color: #000;" cla=
ss=3D"styled-by-prettify"> accum </span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">=3D</span><span style=3D"color: #000;" class=3D"sty=
led-by-prettify"> std</span><span style=3D"color: #660;" class=3D"styled-by=
-prettify">::</span><span style=3D"color: #000;" class=3D"styled-by-prettif=
y">accumulate</span><span style=3D"color: #660;" class=3D"styled-by-prettif=
y">(</span><span style=3D"color: #000;" class=3D"styled-by-prettify">rng </=
span><span style=3D"color: #660;" class=3D"styled-by-prettify">|</span><spa=
n style=3D"color: #000;" class=3D"styled-by-prettify"> range</span><span st=
yle=3D"color: #660;" class=3D"styled-by-prettify">::</span><span style=3D"c=
olor: #000;" class=3D"styled-by-prettify">reversed</span><span style=3D"col=
or: #660;" class=3D"styled-by-prettify">()</span><span style=3D"color: #000=
;" class=3D"styled-by-prettify"> </span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">|</span><span style=3D"color: #000;" class=3D"style=
d-by-prettify"> range</span><span style=3D"color: #660;" class=3D"styled-by=
-prettify">::</span><span style=3D"color: #000;" class=3D"styled-by-prettif=
y">break_if</span><span style=3D"color: #660;" class=3D"styled-by-prettify"=
>([](</span><span style=3D"color: #008;" class=3D"styled-by-prettify">int</=
span><span style=3D"color: #000;" class=3D"styled-by-prettify"> t</span><sp=
an style=3D"color: #660;" class=3D"styled-by-prettify">)</span><span style=
=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=3D"color=
: #660;" class=3D"styled-by-prettify">{</span><span style=3D"color: #008;" =
class=3D"styled-by-prettify">return</span><span style=3D"color: #000;" clas=
s=3D"styled-by-prettify"> t </span><span style=3D"color: #660;" class=3D"st=
yled-by-prettify"><</span><span style=3D"color: #000;" class=3D"styled-b=
y-prettify"> </span><span style=3D"color: #066;" class=3D"styled-by-prettif=
y">0</span><span style=3D"color: #660;" class=3D"styled-by-prettify">;}),</=
span><span style=3D"color: #000;" class=3D"styled-by-prettify"> </span><spa=
n style=3D"color: #066;" class=3D"styled-by-prettify">0</span><span style=
=3D"color: #660;" class=3D"styled-by-prettify">);</span></div></code></div>=
<br>This assumes range-based algorithms and adapters, ala Boost.Range. `bre=
ak_if` is not actually in Boost.Range, but it would treat an iterator as th=
e end iterator if the predicate returns true. It therefore effectively cuts=
the range off.<br><br>It also expresses the intent better. You're not usin=
g a different algorithm; you're accumulating just like before. So you use t=
he `accumulate` algorithm, just like before What you're really doing is mod=
ifying the <i>range</i> you're accumulating over. So in this code, we <i>mo=
dify the range</i> and use std::accumulate.<br><br>And because of that, you=
can now use this with pretty much any algorithm (that accepts a forward ra=
nge). If you want to do std::transform based for the first or last numbers =
before the first negative, you can. You don't need std::transform_first_if =
or whatever.<br><br>It can be applied to arbitrary algorithms (that use for=
ward ranges). It's much more versatile and flexible.<br></div>
<p></p>
-- <br />
<br />
<br />
<br />
------=_Part_511_16260466.1357888022195--
.
Author: Vlad from Moscow <vlad.moscow@mail.ru>
Date: Fri, 11 Jan 2013 04:33:31 -0800 (PST)
Raw View
------=_Part_141_961325.1357907611786
Content-Type: text/plain; charset=KOI8-R
Content-Transfer-Encoding: quoted-printable
=D0=D1=D4=CE=C9=C3=C1, 11 =D1=CE=D7=C1=D2=D1 2013 =C7., 11:07:02 UTC+4 =D0=
=CF=CC=D8=DA=CF=D7=C1=D4=C5=CC=D8 Nicol Bolas =CE=C1=D0=C9=D3=C1=CC:
>
>
>
> On Thursday, January 10, 2013 10:07:25 PM UTC-8, Vlad from Moscow wrote:
>>
>>
>> =D0=D1=D4=CE=C9=C3=C1, 11 =D1=CE=D7=C1=D2=D1 2013 =C7., 8:15:11 UTC+4 =
=D0=CF=CC=D8=DA=CF=D7=C1=D4=C5=CC=D8 Nicol Bolas=20
>> =CE=C1=D0=C9=D3=C1=CC:
>>>
>>>
>>>
>>> On Thursday, January 10, 2013 6:41:22 PM UTC-8, Vlad from Moscow wrote:
>>>>
>>>>
>>>> =D0=D1=D4=CE=C9=C3=C1, 11 =D1=CE=D7=C1=D2=D1 2013 =C7., 5:57:40 UTC+4 =
=D0=CF=CC=D8=DA=CF=D7=C1=D4=C5=CC=D8 Nicol Bolas=20
>>>> =CE=C1=D0=C9=D3=C1=CC:
>>>>>
>>>>> On Thursday, January 10, 2013 5:38:25 PM UTC-8, Vlad from Moscow wrot=
e:
>>>>>>
>>>>>>
>>>>>> =D0=D1=D4=CE=C9=C3=C1, 11 =D1=CE=D7=C1=D2=D1 2013 =C7., 2:58:28 UTC+=
4 =D0=CF=CC=D8=DA=CF=D7=C1=D4=C5=CC=D8 jewillco=20
>>>>>> =CE=C1=D0=C9=D3=C1=CC:
>>>>>>>
>>>>>>> On Thu, 10 Jan 2013, Fernando Cacciola wrote:=20
>>>>>>>
>>>>>>> > On Thu, Jan 10, 2013 at 8:29 PM, Vlad from Moscow <
>>>>>>> vlad....@mail.ru> wrote:=20
>>>>>>> >> At first let consider a simple assignment: calculate sum of all=
=20
>>>>>>> elements of=20
>>>>>>> >> a integer array after the last negative element.=20
>>>>>>> >> It seems that the assignment should be done in two phases.=20
>>>>>>> Firstly the last=20
>>>>>>> >> negative element should be found for example with std::find_if b=
y=20
>>>>>>> supplying=20
>>>>>>> >> reverse iterators. Secondly standard algorithm std::accumulate=
=20
>>>>>>> will be used.=20
>>>>>>> >>=20
>>>>>>> >> This approach has a serious shortage. Nothing prevents that the=
=20
>>>>>>> last=20
>>>>>>> >> negative element of the array will be at the same time the first=
=20
>>>>>>> element of=20
>>>>>>> >> the array. So the array will be traversed twice. It is obvious=
=20
>>>>>>> that this=20
>>>>>>> >> approach is ineffective.=20
>>>>>>> >>=20
>>>>>>> >> But how to do the task in more effective way and preserve the=20
>>>>>>> symantic of=20
>>>>>>> >> std::accumulate?=20
>>>>>>> >>=20
>>>>>>> >>=20
>>>>>>> >> I suggest a new modification of std::accumulate that resolves=20
>>>>>>> this problem.=20
>>>>>>> >>=20
>>>>>>> >>=20
>>>>>>> >> This modifications includes two forms of the algorithm=20
>>>>>>> >>=20
>>>>>>> >>=20
>>>>>>> >> template <class InputIterator, class T, class UnaryPredicate,=20
>>>>>>> class=20
>>>>>>> >> BinaryOperation>=20
>>>>>>> >> T accumulate_first_if( InputIterator first,=20
>>>>>>> >> InputIterator last,=20
>>>>>>> >> T init,=20
>>>>>>> >> UnaryPredicate unary_predicate,=20
>>>>>>> >> BinaryOperation binary_operation )=20
>>>>>>> >> {=20
>>>>>>> >> for ( ; first !=3D last && unary_predicate( *first ) ; ++first =
)=20
>>>>>>> >> {=20
>>>>>>> >> init =3D binary_operation( init, *first );=20
>>>>>>> >> }=20
>>>>>>> >> return ( init );=20
>>>>>>> >> }=20
>>>>>>> >=20
>>>>>>> > Actually, I'd like to see a more generalized approach.=20
>>>>>>> >=20
>>>>>>> > What you've shown is the case where a standard algorithm should b=
e=20
>>>>>>> > applied to a subset of a sequence, and you noticed that it is=20
>>>>>>> wasteful=20
>>>>>>> > to determine the sub-sequence in a separate pass.=20
>>>>>>> > For this case, you are of course correct, and the solution would=
=20
>>>>>>> > indeed be a loop of the form you just proposed.=20
>>>>>>> >=20
>>>>>>> > However, I'm not sure if providing flavors of the algorithm that=
=20
>>>>>>> > combine with this particular sub-sequence selection is the best=
=20
>>>>>>> > approach. It's evident that you'll have to propose the same for=
=20
>>>>>>> pretty=20
>>>>>>> > much all other algorithms. And I wonder if there couldn't be othe=
r=20
>>>>>>> > forms of sub-sequencing as well (I'm thinking direct filtering bu=
t=20
>>>>>>> > that can be handled by specialized iterators).=20
>>>>>>>
>>>>>>> This operation can also be handled using the normal std::accumulate=
;=20
>>>>>>> for=20
>>>>>>> your example, you would use:=20
>>>>>>>
>>>>>>> accumulate(first, last, 0,=20
>>>>>>> [](int a, int b) {if (b < 0) return 0; else return a +=
=20
>>>>>>> b;});=20
>>>>>>>
>>>>>>> That gives a single pass over the sequence. For accumulating up to=
=20
>>>>>>> the=20
>>>>>>> first negative number, you would want a separate algorithm to allow=
=20
>>>>>>> the=20
>>>>>>> iteration to stop early (you can use std::accumulate if you can=20
>>>>>>> afford to=20
>>>>>>> iterate the entire sequence) or the approach Fernando is proposing=
=20
>>>>>>> with a=20
>>>>>>> way to make a range of "all elements up to the first negative one."=
=20
>>>>>>>
>>>>>>> -- Jeremiah Willcock=20
>>>>>>>
>>>>>> =20
>>>>>> It is a remarkable idea but it is what I wanted to escape suggesting=
=20
>>>>>> the new algorithm. =20
>>>>>>
>>>>>
>>>>> That's part of the point, and it's the reason why we have lambdas: so=
=20
>>>>> that we don't have to have a new algorithm for every corner case imag=
inable.
>>>>>
>>>>> Code-wise, his std::accumulate+lambda is in every way equivalent to=
=20
>>>>> what you proposed. It's not particularly long, and it's very clear as=
to=20
>>>>> what it does. Odds are good that they'll even compile to the same cod=
e.
>>>>>
>>>>> So why do we need a whole new function for something that we can=20
>>>>> trivially do ourselves?
>>>>>
>>>>> While this algorithm would certainly see use, I don't see the *need*t=
o have it as an algorithm in the standard library. It's not used=20
>>>>> frequently enough to need such canonization, and we can achieve the s=
ame=20
>>>>> effect with a simple lambda.
>>>>>
>>>> =20
>>>> =20
>>>> I even do not want to answer to such "argument" as "So why do we need=
=20
>>>> a whole new function for something that we can trivially do ourselves?=
". I=20
>>>> heard is thousand times.
>>>>
>>>
>>> The reason you hear this argument "thousand times" is because it's a=20
>>> reasonable argument. People can come up with innumerable patterns of ra=
nge=20
>>> iteration that could be represented by algorithms.
>>>
>>> In general, things that become standard library algorithms fill one of=
=20
>>> these criteria:
>>>
>>> 1: It's quite common. Taking the sum of all values in a list, calling a=
=20
>>> function and storing the result in a list, searching for a value, etc a=
re=20
>>> simple tasks, but they're tasks that programmers often have to do.
>>>
>>> 2: It's hard to write efficiently. std::sort, std::binary_search, etc,=
=20
>>> are all algorithms that are very easy to get wrong. Either you make it=
=20
>>> slow, or you make it behave incorrectly. By having a simple algorithm,
>>>
>>> In general, find first/last negative value followed by accumulate is=20
>>> sufficient for most people's needs. Those people who actually need this=
=20
>>> either know they need it through profiling, or are using InputIterators=
=20
>>> that they can't traverse multiple times. I just don't see this as being=
a=20
>>> compelling need for such a feature.
>>> =20
>>>
>>>> I hope that you can also yourself to write strlen can not you?:) At=20
>>>> least as far as I know all students write strlen while are studing C/=
C++.
>>>>
>>>
>>> Are you honestly suggesting that this specific adaptation of accumulate=
=20
>>> is anywhere near as generally useful as strlen?
>>>
>>> However I will do one remark. As the post of Jeremiah Willcock showed=
=20
>>>> not all can write this algorithm.
>>>>
>>>
>>> How did his post show that? It showed that he wrote the first variation=
=20
>>> (everything from the last key value on). It explained how to write the=
=20
>>> second one, but he didn't write it for you.
>>> =20
>>>
>>>> There will be numerous realizations that in most part will be=20
>>>> ineffective and that can be difficult to understand and to read what t=
he=20
>>>> author was going to do.=20
>>>>
>>>
>>> And this is what you consider easier to understand:
>>>
>>> accumulate_first_if( std::reverse_iterator<int *>( std::end( a ) ),
>>> std::reverse_iterator<int *>( std::begin( a ) ),
>>> 0,
>>> std::bind2nd( std::greater_equal<int>(), 0 ) );
>>>
>>> The other one was much easier to digest.
>>>
>> =20
>> =20
>> I seriously think that this specific adaptation of accumulate=20
>> is generally useful. I will not compare it with strlen because it is=20
>> obvious that some algorithms are used more rarely than others. But thi=
s=20
>> modification makes algorithm std::accumulate of full value.
>> =20
>> I will not point out that the realization of the task suggested by=20
>> Jeremiah Willcock is ineffective. It is clear without my comments.
>>
>
> If it were "clear without my comments," then I wouldn't have said that it=
=20
> solved the problem.
>
> I will say just that it is invalid! Why? Because it has a side=20
>> effect. It touches elements that it shall not touch. You forgot that usa=
ge=20
>> of std::accumulate is very multiform. For example a pointer to character=
=20
>> can be used as the initial value. And this pointer can be incremented in=
=20
>> the binary operation. Moreover also objects that pointed by this pointer=
=20
>> can be changed. So when at last you will find the required subsequence y=
ou=20
>> will be unable to rollback your changes.
>>
>
> If I see `std::accumulate` in someone's code, I would generally assume=20
> that it's accumulating a value. And accumulating a value should not *modi=
fy=20
> the input data*. That's not to say that you can't do it; it's certainly=
=20
> legal C++ to do that. But it would be very confusing for the reader as to=
=20
> what you're doing.
>
> Let assume that there is no such modification of std::accumulate that I=
=20
>> suggested. What do others do in this case? They put aside the algorithm =
and=20
>> try to invent something pwn. So we get a zoo of various realizations for=
a=20
>> simple task. And moreover very ofthen these realizations are incorrect a=
s=20
>> I demonstrated relative to the realization of Jeremiah Willcock.
>>
>
> All you get is this:
>
> int accum =3D 0;
> for(int val : range)
> {
> if(val < 0) break;
> accum +=3D val;
> }
>
> This is what you're talking about saving someone from writing. This is fa=
r=20
> from an onerous burden.
>
> This modification makes the algorithm of full value and essentially=20
>> enlages its usage.
>> =20
>> We have two idioms for the sequential access of a sequence. Either we go=
=20
>> through all elements of a sequence or we stop when required elements wer=
e=20
>> found. Now std::accumulate includes the both idioms. This makes its usag=
e=20
>> very effective.
>>
>
> Or, you could just do this:
>
> int accum =3D std::accumulate(rng | range::break_if([](int t) {return t <=
0
> ;}), 0);
>
> And if you want to do it from the rear:
>
> int accum =3D std::accumulate(rng | range::reversed() | range::break_if([=
](
> int t) {return t < 0;}), 0);
>
> This assumes range-based algorithms and adapters, ala Boost.Range.=20
> `break_if` is not actually in Boost.Range, but it would treat an iterator=
=20
> as the end iterator if the predicate returns true. It therefore effective=
ly=20
> cuts the range off.
>
> It also expresses the intent better. You're not using a different=20
> algorithm; you're accumulating just like before. So you use the=20
> `accumulate` algorithm, just like before What you're really doing is=20
> modifying the *range* you're accumulating over. So in this code, we *modi=
fy=20
> the range* and use std::accumulate.
>
> And because of that, you can now use this with pretty much any algorithm=
=20
> (that accepts a forward range). If you want to do std::transform based fo=
r=20
> the first or last numbers before the first negative, you can. You don't=
=20
> need std::transform_first_if or whatever.
>
> It can be applied to arbitrary algorithms (that use forward ranges). It's=
=20
> much more versatile and flexible.
>
=20
=20
You are using non-standard features. Either they should be adopted or you=
=20
shoud not refer to them. But in any case even if ranges will be adopted I=
=20
prefer for example to have std::find and std::find_if instead of compound=
=20
construction of std::find that does the work of std::find_if. The name of=
=20
an algorithm gives more information for a reader of a code then compound=20
constructions.
--=20
------=_Part_141_961325.1357907611786
Content-Type: text/html; charset=KOI8-R
Content-Transfer-Encoding: quoted-printable
<br>=D0=D1=D4=CE=C9=C3=C1, 11 =D1=CE=D7=C1=D2=D1 2013 =C7., 11:07:02 U=
TC+4 =D0=CF=CC=D8=DA=CF=D7=C1=D4=C5=CC=D8 Nicol Bolas =CE=C1=D0=C9=D3=C1=CC=
:<blockquote style=3D"margin: 0px 0px 0px 0.8ex; padding-left: 1ex; border-=
left-color: rgb(204, 204, 204); border-left-width: 1px; border-left-style: =
solid;" class=3D"gmail_quote"><br><br>On Thursday, January 10, 2013 10:07:2=
5 PM UTC-8, Vlad from Moscow wrote:<blockquote style=3D"margin: 0px 0px 0px=
0.8ex; padding-left: 1ex; border-left-color: rgb(204, 204, 204); border-le=
ft-width: 1px; border-left-style: solid;" class=3D"gmail_quote"><br>=D0=D1=
=D4=CE=C9=C3=C1, 11 =D1=CE=D7=C1=D2=D1 2013 =C7., 8:15:11 UTC+4 =D0=CF=
=CC=D8=DA=CF=D7=C1=D4=C5=CC=D8 Nicol Bolas =CE=C1=D0=C9=D3=C1=CC:<blockquot=
e style=3D"margin: 0px 0px 0px 0.8ex; padding-left: 1ex; border-left-color:=
rgb(204, 204, 204); border-left-width: 1px; border-left-style: solid;" cla=
ss=3D"gmail_quote"><br><br>On Thursday, January 10, 2013 6:41:22 PM UTC-8, =
Vlad from Moscow wrote:<blockquote style=3D"margin: 0px 0px 0px 0.8ex; padd=
ing-left: 1ex; border-left-color: rgb(204, 204, 204); border-left-width: 1p=
x; border-left-style: solid;" class=3D"gmail_quote"><br>=D0=D1=D4=CE=C9=C3=
=C1, 11 =D1=CE=D7=C1=D2=D1 2013 =C7., 5:57:40 UTC+4 =D0=CF=CC=D8=DA=CF=
=D7=C1=D4=C5=CC=D8 Nicol Bolas =CE=C1=D0=C9=D3=C1=CC:<blockquote style=3D"m=
argin: 0px 0px 0px 0.8ex; padding-left: 1ex; border-left-color: rgb(204, 20=
4, 204); border-left-width: 1px; border-left-style: solid;" class=3D"gmail_=
quote">On Thursday, January 10, 2013 5:38:25 PM UTC-8, Vlad from Moscow wro=
te:<blockquote style=3D"margin: 0px 0px 0px 0.8ex; padding-left: 1ex; borde=
r-left-color: rgb(204, 204, 204); border-left-width: 1px; border-left-style=
: solid;" class=3D"gmail_quote"><br>=D0=D1=D4=CE=C9=C3=C1, 11 =D1=CE=D7=C1=
=D2=D1 2013 =C7., 2:58:28 UTC+4 =D0=CF=CC=D8=DA=CF=D7=C1=D4=C5=CC=D8 j=
ewillco =CE=C1=D0=C9=D3=C1=CC:<blockquote style=3D"margin: 0px 0px 0px 0.8e=
x; padding-left: 1ex; border-left-color: rgb(204, 204, 204); border-left-wi=
dth: 1px; border-left-style: solid;" class=3D"gmail_quote">On Thu, 10 Jan 2=
013, Fernando Cacciola wrote:
<br>
<br>> On Thu, Jan 10, 2013 at 8:29 PM, Vlad from Moscow <<a>vlad....@=
mail.ru</a>> wrote:
<br>>> At first let consider a simple assignment: calculate sum of al=
l elements of
<br>>> a integer array after the last negative element.
<br>>> It seems that the assignment should be done in two phases. Fir=
stly the last
<br>>> negative element should be found for example with std::find_if=
by supplying
<br>>> reverse iterators. Secondly standard algorithm std::accumulate=
will be used.
<br>>>
<br>>> This approach has a serious shortage. Nothing prevents t=
hat the last
<br>>> negative element of the array will be at the same time the fir=
st element of
<br>>> the array. So the array will be traversed twice. It is o=
bvious that this
<br>>> approach is ineffective.
<br>>>
<br>>> But how to do the task in more effective way and preserve the =
symantic of
<br>>> std::accumulate?
<br>>>
<br>>>
<br>>> I suggest a new modification of std::accumulate that resolves =
this problem.
<br>>>
<br>>>
<br>>> This modifications includes two forms of the algorithm
<br>>>
<br>>>
<br>>> template <class InputIterator, class T, class UnaryPredicat=
e, class
<br>>> BinaryOperation>
<br>>> T accumulate_first_if( InputIterator first,
<br>>> =
InputIterator last,
<br>>> T init,
<br>>> UnaryPredicate unary_predicate,
<br>>> BinaryOperation binary_operation )
<br>>> {
<br>>> for ( ; first !=3D last && unary_predicate( *fir=
st ) ; ++first )
<br>>> {
<br>>> init =3D binary_operation( init, *first );
<br>>> }
<br>>> return ( init );
<br>>> }
<br>>
<br>> Actually, I'd like to see a more generalized approach.
<br>>
<br>> What you've shown is the case where a standard algorithm should be
<br>> applied to a subset of a sequence, and you noticed that it is wast=
eful
<br>> to determine the sub-sequence in a separate pass.
<br>> For this case, you are of course correct, and the solution would
<br>> indeed be a loop of the form you just proposed.
<br>>
<br>> However, I'm not sure if providing flavors of the algorithm that
<br>> combine with this particular sub-sequence selection is the best
<br>> approach. It's evident that you'll have to propose the same for pr=
etty
<br>> much all other algorithms. And I wonder if there couldn't be other
<br>> forms of sub-sequencing as well (I'm thinking direct filtering but
<br>> that can be handled by specialized iterators).
<br>
<br>This operation can also be handled using the normal std::accumulate; fo=
r=20
<br>your example, you would use:
<br>
<br>accumulate(first, last, 0,
<br> [](int a, int b) {if (b < =
0) return 0; else return a + b;});
<br>
<br>That gives a single pass over the sequence. For accumulating up t=
o the=20
<br>first negative number, you would want a separate algorithm to allow the=
=20
<br>iteration to stop early (you can use std::accumulate if you can afford =
to=20
<br>iterate the entire sequence) or the approach Fernando is proposing with=
a=20
<br>way to make a range of "all elements up to the first negative one."
<br>
<br>-- Jeremiah Willcock
<br></blockquote><div> </div><div>It is a remarkable idea but it =
is what I wanted to escape suggesting the new algorithm. </=
div></blockquote><div><br>That's part of the point, and it's the reason why=
we have lambdas: so that we don't have to have a new algorithm for every c=
orner case imaginable.<br><br>Code-wise, his std::accumulate+lambda is in e=
very way equivalent to what you proposed. It's not particularly long, and i=
t's very clear as to what it does. Odds are good that they'll even compile =
to the same code.<br><br>So why do we need a whole new function for somethi=
ng that we can trivially do ourselves?<br><br>While this algorithm would ce=
rtainly see use, I don't see the <i>need</i> to have it as an algorithm in =
the standard library. It's not used frequently enough to need such canoniza=
tion, and we can achieve the same effect with a simple lambda.<br></div></b=
lockquote><div> </div><div> </div><div>I even do not want to answ=
er to such "argument" as "So why do we need a whole new function for =
something that we can trivially do ourselves?". I heard is thousand times.<=
/div></blockquote><div><br>The reason you hear this argument "thousand time=
s" is because it's a reasonable argument. People can come up with innumerab=
le patterns of range iteration that could be represented by algorithms.<br>=
<br>In general, things that become standard library algorithms fill one of =
these criteria:<br><br>1: It's quite common. Taking the sum of all values i=
n a list, calling a function and storing the result in a list, searching fo=
r a value, etc are simple tasks, but they're tasks that programmers often h=
ave to do.<br><br>2: It's hard to write efficiently. std::sort, std::binary=
_search, etc, are all algorithms that are very easy to get wrong. Either yo=
u make it slow, or you make it behave incorrectly. By having a simple algor=
ithm,<br><br>In general, find first/last negative value followed by accumul=
ate is sufficient for most people's needs. Those people who actually need t=
his either know they need it through profiling, or are using InputIterators=
that they can't traverse multiple times. I just don't see this as being a =
compelling need for such a feature.<br> </div><blockquote style=3D"mar=
gin: 0px 0px 0px 0.8ex; padding-left: 1ex; border-left-color: rgb(204, 204,=
204); border-left-width: 1px; border-left-style: solid;" class=3D"gmail_qu=
ote"><div>I hope that you can also yourself to write strlen can not you?:) =
At least as far as I know all students write strlen while are studing=
C/C++.<br></div></blockquote><div><br>Are you honestly suggesting that thi=
s specific adaptation of accumulate is anywhere near as generally useful as=
strlen?<br><br></div><blockquote style=3D"margin: 0px 0px 0px 0.8ex; paddi=
ng-left: 1ex; border-left-color: rgb(204, 204, 204); border-left-width: 1px=
; border-left-style: solid;" class=3D"gmail_quote"><div>However I will do o=
ne remark. As the post of Jeremiah Willcock showed not all can write =
this algorithm.</div></blockquote><div><br>How did his post show that? It s=
howed that he wrote the first variation (everything from the last key value=
on). It explained how to write the second one, but he didn't write it for =
you.<br> </div><blockquote style=3D"margin: 0px 0px 0px 0.8ex; padding=
-left: 1ex; border-left-color: rgb(204, 204, 204); border-left-width: 1px; =
border-left-style: solid;" class=3D"gmail_quote"><div> There will be numero=
us realizations that in most part will be ineffective and that can be diffi=
cult to understand and to read what the author was going to do. <br></div><=
/blockquote><div><br>And this is what you consider easier to understand:<br=
><br><div style=3D"border: 1px solid rgb(187, 187, 187); word-wrap: break-w=
ord; background-color: rgb(250, 250, 250);"><code><div><span style=3D"color=
: rgb(0, 0, 0);">accumulate_first_if</span><span style=3D"color: rgb(102, 1=
02, 0);">(</span><span style=3D"color: rgb(0, 0, 0);"> std</span><span styl=
e=3D"color: rgb(102, 102, 0);">::</span><span style=3D"color: rgb(0, 0, 0);=
">reverse_iterator</span><span style=3D"color: rgb(102, 102, 0);"><</spa=
n><span style=3D"color: rgb(0, 0, 136);">int</span><span style=3D"color: rg=
b(0, 0, 0);"> </span><span style=3D"color: rgb(102, 102, 0);">*>(</span>=
<span style=3D"color: rgb(0, 0, 0);"> std</span><span style=3D"color: rgb(1=
02, 102, 0);">::</span><span style=3D"color: rgb(0, 0, 136);">end</span><sp=
an style=3D"color: rgb(102, 102, 0);">(</span><span style=3D"color: rgb(0, =
0, 0);"> a </span><span style=3D"color: rgb(102, 102, 0);">)</span><span st=
yle=3D"color: rgb(0, 0, 0);"> </span><span style=3D"color: rgb(102, 102, 0)=
;">),</span><span style=3D"color: rgb(0, 0, 0);"><br> &=
nbsp; std</span><span style=
=3D"color: rgb(102, 102, 0);">::</span><span style=3D"color: rgb(0, 0, 0);"=
>reverse_iterator</span><span style=3D"color: rgb(102, 102, 0);"><</span=
><span style=3D"color: rgb(0, 0, 136);">int</span><span style=3D"color: rgb=
(0, 0, 0);"> </span><span style=3D"color: rgb(102, 102, 0);">*>(</span><=
span style=3D"color: rgb(0, 0, 0);"> std</span><span style=3D"color: rgb(10=
2, 102, 0);">::</span><span style=3D"color: rgb(0, 0, 136);">begin</span><s=
pan style=3D"color: rgb(102, 102, 0);">(</span><span style=3D"color: rgb(0,=
0, 0);"> a </span><span style=3D"color: rgb(102, 102, 0);">)</span><span s=
tyle=3D"color: rgb(0, 0, 0);"> </span><span style=3D"color: rgb(102, 102, 0=
);">),</span><span style=3D"color: rgb(0, 0, 0);"><br> =
</span><span style=
=3D"color: rgb(0, 102, 102);">0</span><span style=3D"color: rgb(102, 102, 0=
);">,</span><span style=3D"color: rgb(0, 0, 0);"><br> &=
nbsp; std</span><span style=
=3D"color: rgb(102, 102, 0);">::</span><span style=3D"color: rgb(0, 0, 0);"=
>bind2nd</span><span style=3D"color: rgb(102, 102, 0);">(</span><span style=
=3D"color: rgb(0, 0, 0);"> std</span><span style=3D"color: rgb(102, 102, 0)=
;">::</span><span style=3D"color: rgb(0, 0, 0);">greater_equal</span><span =
style=3D"color: rgb(0, 136, 0);"><int></span><span style=3D"color: rg=
b(102, 102, 0);">(),</span><span style=3D"color: rgb(0, 0, 0);"> </span><sp=
an style=3D"color: rgb(0, 102, 102);">0</span><span style=3D"color: rgb(0, =
0, 0);"> </span><span style=3D"color: rgb(102, 102, 0);">)</span><span styl=
e=3D"color: rgb(0, 0, 0);"> </span><span style=3D"color: rgb(102, 102, 0);"=
>);</span></div></code></div><div><br></div>The other one was much easier t=
o digest.<br></div></blockquote><div> </div><div> </div><div>I se=
riously think that this specific adaptation of accumulate is generally=
useful. I will not compare it with strlen because it is obvious that some =
algorithms are used more rarely than others. But this modificat=
ion makes algorithm std::accumulate of full value.</div><div> </div><d=
iv>I will not point out that the realization of the task suggested by Jerem=
iah Willcock is ineffective. It is clear without my comments.</div></b=
lockquote><div><br>If it were "clear without my comments," then I wouldn't =
have said that it solved the problem.<br><br></div><blockquote style=3D"mar=
gin: 0px 0px 0px 0.8ex; padding-left: 1ex; border-left-color: rgb(204, 204,=
204); border-left-width: 1px; border-left-style: solid;" class=3D"gmail_qu=
ote"><div>I will say just that it is invalid! Why? Because it h=
as a side effect. It touches elements that it shall not touch. You for=
got that usage of std::accumulate is very multiform. For example a poi=
nter to character can be used as the initial value. And this pointer can be=
incremented in the binary operation. Moreover also objects that point=
ed by this pointer can be changed. So when at last you will find the requir=
ed subsequence you will be unable to rollback your changes.</div></blockquo=
te><div><br>If I see `std::accumulate` in someone's code, I would generally=
assume that it's accumulating a value. And accumulating a value should not=
<i>modify the input data</i>.
That's not to say that you can't do it; it's certainly legal C++ to do tha=
t. But it would be very confusing for the reader as to what you're doing.<b=
r><br></div><blockquote style=3D"margin: 0px 0px 0px 0.8ex; padding-left: 1=
ex; border-left-color: rgb(204, 204, 204); border-left-width: 1px; border-l=
eft-style: solid;" class=3D"gmail_quote"><div></div><div>Let assume that th=
ere is no such modification of std::accumulate that I suggested. What =
do others do in this case? They put aside the algorithm and try to inv=
ent something pwn. So we get a zoo of various realizations for a simple tas=
k. And moreover very ofthen these realizations are incorrect as I demo=
nstrated relative to the realization of Jeremiah Willcock.</div>=
</blockquote><div><br>All you get is this:<br><br><div style=3D"border: 1px=
solid rgb(187, 187, 187); word-wrap: break-word; background-color: rgb(250=
, 250, 250);"><code><div><span style=3D"color: rgb(0, 0, 136);">int</span><=
span style=3D"color: rgb(0, 0, 0);"> accum </span><span style=3D"color: rgb=
(102, 102, 0);">=3D</span><span style=3D"color: rgb(0, 0, 0);"> </span><spa=
n style=3D"color: rgb(0, 102, 102);">0</span><span style=3D"color: rgb(102,=
102, 0);">;</span><span style=3D"color: rgb(0, 0, 0);"><br></span><span st=
yle=3D"color: rgb(0, 0, 136);">for</span><span style=3D"color: rgb(102, 102=
, 0);">(</span><span style=3D"color: rgb(0, 0, 136);">int</span><span style=
=3D"color: rgb(0, 0, 0);"> val </span><span style=3D"color: rgb(102, 102, 0=
);">:</span><span style=3D"color: rgb(0, 0, 0);"> range</span><span style=
=3D"color: rgb(102, 102, 0);">)</span><span style=3D"color: rgb(0, 0, 0);">=
<br></span><span style=3D"color: rgb(102, 102, 0);">{</span><span style=3D"=
color: rgb(0, 0, 0);"><br> </span><span style=3D"color: rgb(0, 0, 136=
);">if</span><span style=3D"color: rgb(102, 102, 0);">(</span><span style=
=3D"color: rgb(0, 0, 0);">val </span><span style=3D"color: rgb(102, 102, 0)=
;"><</span><span style=3D"color: rgb(0, 0, 0);"> </span><span style=3D"c=
olor: rgb(0, 102, 102);">0</span><span style=3D"color: rgb(102, 102, 0);">)=
</span><span style=3D"color: rgb(0, 0, 0);"> </span><span style=3D"color: r=
gb(0, 0, 136);">break</span><span style=3D"color: rgb(102, 102, 0);">;</spa=
n><span style=3D"color: rgb(0, 0, 0);"><br> accum </span><span style=
=3D"color: rgb(102, 102, 0);">+=3D</span><span style=3D"color: rgb(0, 0, 0)=
;"> val</span><span style=3D"color: rgb(102, 102, 0);">;</span><span style=
=3D"color: rgb(0, 0, 0);"><br></span><span style=3D"color: rgb(102, 102, 0)=
;">}</span></div></code></div><br>This is what you're talking about saving =
someone from writing. This is far from an onerous burden.<br><br></div><blo=
ckquote style=3D"margin: 0px 0px 0px 0.8ex; padding-left: 1ex; border-left-=
color: rgb(204, 204, 204); border-left-width: 1px; border-left-style: solid=
;" class=3D"gmail_quote"><div></div><div>This modification makes the algori=
thm of full value and essentially enlages its usage.</div><div> </div>=
<div>We have two idioms for the sequential access of a sequence. Either we =
go through all elements of a sequence or we stop when required elements wer=
e found. Now std::accumulate includes the both idioms. This makes its usage=
very effective.</div></blockquote><div><br>Or, you could just do this:<br>=
<br><div style=3D"border: 1px solid rgb(187, 187, 187); word-wrap: break-wo=
rd; background-color: rgb(250, 250, 250);"><code><div><span style=3D"color:=
rgb(0, 0, 136);">int</span><span style=3D"color: rgb(0, 0, 0);"> accum </s=
pan><span style=3D"color: rgb(102, 102, 0);">=3D</span><span style=3D"color=
: rgb(0, 0, 0);"> std</span><span style=3D"color: rgb(102, 102, 0);">::</sp=
an><span style=3D"color: rgb(0, 0, 0);">accumulate</span><span style=3D"col=
or: rgb(102, 102, 0);">(</span><span style=3D"color: rgb(0, 0, 0);">rng </s=
pan><span style=3D"color: rgb(102, 102, 0);">|</span><span style=3D"color: =
rgb(0, 0, 0);"> range</span><span style=3D"color: rgb(102, 102, 0);">::</sp=
an><span style=3D"color: rgb(0, 0, 0);">break_if</span><span style=3D"color=
: rgb(102, 102, 0);">([](</span><span style=3D"color: rgb(0, 0, 136);">int<=
/span><span style=3D"color: rgb(0, 0, 0);"> t</span><span style=3D"color: r=
gb(102, 102, 0);">)</span><span style=3D"color: rgb(0, 0, 0);"> </span><spa=
n style=3D"color: rgb(102, 102, 0);">{</span><span style=3D"color: rgb(0, 0=
, 136);">return</span><span style=3D"color: rgb(0, 0, 0);"> t </span><span =
style=3D"color: rgb(102, 102, 0);"><</span><span style=3D"color: rgb(0, =
0, 0);"> </span><span style=3D"color: rgb(0, 102, 102);">0</span><span styl=
e=3D"color: rgb(102, 102, 0);">;}),</span><span style=3D"color: rgb(0, 0, 0=
);"> </span><span style=3D"color: rgb(0, 102, 102);">0</span><span style=3D=
"color: rgb(102, 102, 0);">);</span><span style=3D"color: rgb(0, 0, 0);"><b=
r></span></div></code></div><br>And if you want to do it from the rear:<br>=
<br><div style=3D"border: 1px solid rgb(187, 187, 187); word-wrap: break-wo=
rd; background-color: rgb(250, 250, 250);"><code><div><span style=3D"color:=
rgb(0, 0, 136);">int</span><span style=3D"color: rgb(0, 0, 0);"> accum </s=
pan><span style=3D"color: rgb(102, 102, 0);">=3D</span><span style=3D"color=
: rgb(0, 0, 0);"> std</span><span style=3D"color: rgb(102, 102, 0);">::</sp=
an><span style=3D"color: rgb(0, 0, 0);">accumulate</span><span style=3D"col=
or: rgb(102, 102, 0);">(</span><span style=3D"color: rgb(0, 0, 0);">rng </s=
pan><span style=3D"color: rgb(102, 102, 0);">|</span><span style=3D"color: =
rgb(0, 0, 0);"> range</span><span style=3D"color: rgb(102, 102, 0);">::</sp=
an><span style=3D"color: rgb(0, 0, 0);">reversed</span><span style=3D"color=
: rgb(102, 102, 0);">()</span><span style=3D"color: rgb(0, 0, 0);"> </span>=
<span style=3D"color: rgb(102, 102, 0);">|</span><span style=3D"color: rgb(=
0, 0, 0);"> range</span><span style=3D"color: rgb(102, 102, 0);">::</span><=
span style=3D"color: rgb(0, 0, 0);">break_if</span><span style=3D"color: rg=
b(102, 102, 0);">([](</span><span style=3D"color: rgb(0, 0, 136);">int</spa=
n><span style=3D"color: rgb(0, 0, 0);"> t</span><span style=3D"color: rgb(1=
02, 102, 0);">)</span><span style=3D"color: rgb(0, 0, 0);"> </span><span st=
yle=3D"color: rgb(102, 102, 0);">{</span><span style=3D"color: rgb(0, 0, 13=
6);">return</span><span style=3D"color: rgb(0, 0, 0);"> t </span><span styl=
e=3D"color: rgb(102, 102, 0);"><</span><span style=3D"color: rgb(0, 0, 0=
);"> </span><span style=3D"color: rgb(0, 102, 102);">0</span><span style=3D=
"color: rgb(102, 102, 0);">;}),</span><span style=3D"color: rgb(0, 0, 0);">=
</span><span style=3D"color: rgb(0, 102, 102);">0</span><span style=3D"col=
or: rgb(102, 102, 0);">);</span></div></code></div><br>This assumes range-b=
ased algorithms and adapters, ala Boost.Range. `break_if` is not actually i=
n Boost.Range, but it would treat an iterator as the end iterator if the pr=
edicate returns true. It therefore effectively cuts the range off.<br><br>I=
t also expresses the intent better. You're not using a different algorithm;=
you're accumulating just like before. So you use the `accumulate` algorith=
m, just like before What you're really doing is modifying the <i>range</i> =
you're accumulating over. So in this code, we <i>modify the range</i> and u=
se std::accumulate.<br><br>And because of that, you can now use this with p=
retty much any algorithm (that accepts a forward range). If you want to do =
std::transform based for the first or last numbers before the first negativ=
e, you can. You don't need std::transform_first_if or whatever.<br><br>It c=
an be applied to arbitrary algorithms (that use forward ranges). It's much =
more versatile and flexible.<br></div></blockquote><div> </div><div>&n=
bsp;</div><div>You are using non-standard features. Either they should be a=
dopted or you shoud not refer to them. But in any case even if ra=
nges will be adopted I prefer for example to have std::find and std::find_i=
f instead of compound construction of std::find that does the work of std::=
find_if. The name of an algorithm gives more information for a reader of a =
code then compound constructions.</div>
<p></p>
-- <br />
<br />
<br />
<br />
------=_Part_141_961325.1357907611786--
.