Hi,

I have two suggestions on how to improve the API of the erase() and erase_if()
algorithms.

The first concerns the return type. Alex Stepanov teaches us to not throw away
useful information, but that is exactly what the functions currently do: the
implementation knows how many elements were removed, but that information is
lost upon return from the function. For most containers, this is not a
problem, because you can easily (and in constant time) compare the size() of
the container before and after the application of the algorithm, but that is
notably not the case for std::forward_list.

I therefore propose to change the return type from void to size_t, returning
the number of elements removed.

The second is about passing std::pair as the argument of the predicate for
erase_if for maps. Yes, from a theoretical POV, passing the value_type is
consistent. Still, IMO, the algorithm should pass the key and value
separately, as that allows easier extension to associative data structures
that do not store keys and values together, or not as a std::pair (like e.g.
http://doc.qt.io/qt-5/qhash.html). It would also make for easier predicates,
as they wouldn't need to decompose the pair first (no pun intended). Finally,
it would allow to isolate such predicates from the unfortunate 'first' and
'second' names (decomposition declarations solve that, too, but at the cost of
another line of code).

As I _do_ see the value in accepting value_type for generic code, how about
the algorithm checks to see whether it can pass key and value separately, and,
if so, does it, otherwise passes as a pair? Pseudocode:

   if constexpr (__is_binary_predicate(p)) {
      if (p(it->first, it->second))
          it = c.erase(it);
      else
          ++it;
   } else {
      if (p(*it))
          it = c.erase(it);
      else
          ++it;
   }

Thanks,
Marc

--
Marc Mutz <marc.mutz@kdab.com> | Senior Software Engineer
KDAB (Deutschland) GmbH & Co.KG, a KDAB Group Company
Tel: +49-30-521325470
KDAB - The Qt, C++ and OpenGL Experts

--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/201705171111.22639.marc.mutz%40kdab.com.

.

------=_Part_2914_627604846.1495030245380
Content-Type: multipart/alternative;
 boundary="----=_Part_2915_292519804.1495030245381"

------=_Part_2915_292519804.1495030245381
Content-Type: text/plain; charset="UTF-8"

On Wednesday, May 17, 2017 at 5:12:28 AM UTC-4, Marc Mutz wrote:
>
> Hi,
>
> I have two suggestions on how to improve the API of the erase() and
> erase_if()
> algorithms.
>
> The first concerns the return type. Alex Stepanov teaches us to not throw
> away
> useful information, but that is exactly what the functions currently do:
> the
> implementation knows how many elements were removed, but that information
> is
> lost upon return from the function. For most containers, this is not a
> problem, because you can easily (and in constant time) compare the size()
> of
> the container before and after the application of the algorithm, but that
> is
> notably not the case for std::forward_list.
>

`forward_list` has a constant-time `size`, just like every other container.
This is why the ranged `splice_after` functions aren't all O(1).

I therefore propose to change the return type from void to size_t,
> returning
> the number of elements removed.
>

None of the `erase` functions are `void` functions; they all return
iterators. Except for `erase` functions that act on containers with key
types; they return the number of elements erased.


> The second is about passing std::pair as the argument of the predicate for
> erase_if for maps. Yes, from a theoretical POV, passing the value_type is
> consistent. Still, IMO, the algorithm should pass the key and value
> separately, as that allows easier extension to associative data structures
> that do not store keys and values together,


There is no "erase_if" function anywhere in the standard. And `remove_if`
makes no sense because you *cannot* use `remove_if` on maps. It requires
iterators into a sequence container. Or more specifically, it requires that
the iterators are assignable, and associative/unordered containers don't
let you do that.

So I have no idea what you're talking about.

--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/18f39ac6-3b51-4b67-af14-754628f852b3%40isocpp.org.

------=_Part_2915_292519804.1495030245381
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">On Wednesday, May 17, 2017 at 5:12:28 AM UTC-4, Marc Mutz =
wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8=
ex;border-left: 1px #ccc solid;padding-left: 1ex;">Hi,
<br>
<br>I have two suggestions on how to improve the API of the erase() and era=
se_if()=20
<br>algorithms.
<br>
<br>The first concerns the return type. Alex Stepanov teaches us to not thr=
ow away=20
<br>useful information, but that is exactly what the functions currently do=
: the=20
<br>implementation knows how many elements were removed, but that informati=
on is=20
<br>lost upon return from the function. For most containers, this is not a=
=20
<br>problem, because you can easily (and in constant time) compare the size=
() of=20
<br>the container before and after the application of the algorithm, but th=
at is=20
<br>notably not the case for std::forward_list.<br></blockquote><div><br>`f=
orward_list` has a constant-time `size`, just like every other container. T=
his is why the ranged `splice_after` functions aren&#39;t all O(1).<br><br>=
</div><blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8=
ex;border-left: 1px #ccc solid;padding-left: 1ex;">
I therefore propose to change the return type from void to size_t, returnin=
g=20
<br>the number of elements removed.<br></blockquote><div><br>None of the `e=
rase` functions are `void` functions; they all return iterators. Except for=
 `erase` functions that act on containers with key types; they return the n=
umber of elements erased.<br>=C2=A0</div><blockquote class=3D"gmail_quote" =
style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-l=
eft: 1ex;">
The second is about passing std::pair as the argument of the predicate for=
=20
<br>erase_if for maps. Yes, from a theoretical POV, passing the value_type =
is=20
<br>consistent. Still, IMO, the algorithm should pass the key and value=20
<br>separately, as that allows easier extension to associative data structu=
res=20
<br>that do not store keys and values together,</blockquote><div><br>There =
is no &quot;erase_if&quot; function anywhere in the standard. And `remove_i=
f` makes no sense because you <i>cannot</i> use `remove_if` on maps. It req=
uires iterators into a sequence container. Or more specifically, it require=
s that the iterators are assignable, and associative/unordered containers d=
on&#39;t let you do that.<br><br>So I have no idea what you&#39;re talking =
about.</div></div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/18f39ac6-3b51-4b67-af14-754628f852b3%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/18f39ac6-3b51-4b67-af14-754628f852b3=
%40isocpp.org</a>.<br />

------=_Part_2915_292519804.1495030245381--

------=_Part_2914_627604846.1495030245380--

.

------=_Part_2862_1926942229.1495037018989
Content-Type: multipart/alternative;
 boundary="----=_Part_2863_769498025.1495037018989"

------=_Part_2863_769498025.1495037018989
Content-Type: text/plain; charset="UTF-8"

On Wednesday, May 17, 2017 at 7:10:45 AM UTC-7, Nicol Bolas wrote:
>
> On Wednesday, May 17, 2017 at 5:12:28 AM UTC-4, Marc Mutz wrote:
>>
>> Hi,
>>
>> I have two suggestions on how to improve the API of the erase() and
>> erase_if()
>> algorithms.
>>
>> The first concerns the return type. Alex Stepanov teaches us to not throw
>> away
>> useful information, but that is exactly what the functions currently do:
>> the
>> implementation knows how many elements were removed, but that information
>> is
>> lost upon return from the function. For most containers, this is not a
>> problem, because you can easily (and in constant time) compare the size()
>> of
>> the container before and after the application of the algorithm, but that
>> is
>> notably not the case for std::forward_list.
>>
>
> `forward_list` has a constant-time `size`, just like every other
> container. This is why the ranged `splice_after` functions aren't all O(1).
>


forward_list does not have *any* size, let alone constant time size. The
splice functions are not O(1) due to the need to find the end of the "new"
sequence of nodes to attach the old tail.

--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/7e67bec9-1855-40ba-a0bb-cb455f0b71fa%40isocpp.org.

------=_Part_2863_769498025.1495037018989
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">On Wednesday, May 17, 2017 at 7:10:45 AM UTC-7, Nicol Bola=
s wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0=
..8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr">On We=
dnesday, May 17, 2017 at 5:12:28 AM UTC-4, Marc Mutz wrote:<blockquote clas=
s=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc =
solid;padding-left:1ex">Hi,
<br>
<br>I have two suggestions on how to improve the API of the erase() and era=
se_if()=20
<br>algorithms.
<br>
<br>The first concerns the return type. Alex Stepanov teaches us to not thr=
ow away=20
<br>useful information, but that is exactly what the functions currently do=
: the=20
<br>implementation knows how many elements were removed, but that informati=
on is=20
<br>lost upon return from the function. For most containers, this is not a=
=20
<br>problem, because you can easily (and in constant time) compare the size=
() of=20
<br>the container before and after the application of the algorithm, but th=
at is=20
<br>notably not the case for std::forward_list.<br></blockquote><div><br>`f=
orward_list` has a constant-time `size`, just like every other container. T=
his is why the ranged `splice_after` functions aren&#39;t all O(1).</div></=
div></blockquote><div><br></div><div><br></div><h4 style=3D"line-height: 1;=
 color: rgb(0, 0, 0); font-family: serif; font-size: medium; text-align: ju=
stify;">forward_list does not have *any* size, let alone constant time size=
.. The splice functions are not O(1) due to the need to find the end of the =
&quot;new&quot; sequence of nodes to attach the old tail.</h4></div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/7e67bec9-1855-40ba-a0bb-cb455f0b71fa%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/7e67bec9-1855-40ba-a0bb-cb455f0b71fa=
%40isocpp.org</a>.<br />

------=_Part_2863_769498025.1495037018989--

------=_Part_2862_1926942229.1495037018989--

.

------=_Part_140_1634515155.1495061994741
Content-Type: multipart/alternative;
 boundary="----=_Part_141_2133372762.1495061994741"

------=_Part_141_2133372762.1495061994741
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

On Wednesday, May 17, 2017 at 3:12:28 AM UTC-6, Marc Mutz wrote:
> I have two suggestions on how to improve the API of the erase()
> and erase_if() algorithms.=20
>
> The first concerns the return type. Alex Stepanov teaches us to not throw=
=20
away=20
> useful information, but that is exactly what the functions currently do:=
=20
the=20
> implementation knows how many elements were removed, but that information=
=20
is=20
> lost upon return from the function. [...]
> I therefore propose to change the return type from void to size_t,=20
returning=20
> the number of elements removed.=20

I'm "weakly against" this idea out of general conservativity, but I don't=
=20
see anything fundamentally wrong with it.
You might equally well propose that the function should return "the last=20
removed element" as std::optional<value_type>, or some such; isn't that=20
also information that's "thrown away" by the current algorithm?  Sure, it'd=
=20
cost some performance to do that, but it'd also cost performance to count=
=20
the number of removed elements, which otherwise wouldn't need to be tracked=
=20
by the algorithm.
=20
> [...] For most containers, this is not a=20
> problem, because you can easily (and in constant time) compare the size()=
=20
of=20
> the container before and after the application of the algorithm, but that=
=20
is=20
> notably not the case for std::forward_list. [...]

Surely that's a problem only for the poor misguided users of=20
std::forward_list. :P

> The second is about passing std::pair as the argument of the predicate=20
for=20
> erase_if for maps. Yes, from a theoretical POV, passing the value_type is=
=20
> consistent. Still, IMO, the algorithm should pass the key and value=20
> separately, as that allows easier extension to associative data=20
structures=20
> that do not store keys and values together, or not as a std::pair (like=
=20
e.g.=20
> http://doc.qt.io/qt-5/qhash.html). It would also make for easier=20
predicates,=20
> as they wouldn't need to decompose the pair first (no pun intended).=20
Finally,=20
> it would allow to isolate such predicates from the unfortunate 'first'=20
and=20
> 'second' names (decomposition declarations solve that, too, but at the=20
cost of=20
> another line of code).=20

Agreed that std::pair has a pretty terrible API, but for better or worse,=
=20
it *is* the value_type of the container.

> As I _do_ see the value in accepting value_type for generic code, how=20
about=20
> the algorithm checks to see whether it can pass key and value separately,=
=20
and,=20
> if so, does it, otherwise passes as a pair? Pseudocode:=20
>
> if constexpr (__is_binary_predicate(p)) {=20
>     if (p(it->first, it->second))=20
>         it =3D c.erase(it);=20
>     else=20
>         ++it;=20
> } else {
>     if (p(*it))=20
>         it =3D c.erase(it);=20
>     else=20
>         ++it;=20
> }

Surely the check should be reversed, since breaking down the pair into=20
separate arguments is "doing more" than just passing a reference to the=20
pair itself?
Also, what if 'p' is a generic lambda or something like that, which is=20
callable in several *different* ways? Letting the algorithm choose the=20
signature with which it'll call 'p' seems like a recipe for confusion.=20
Every other algorithm is really explicit about the exact way it's going to=
=20
call all its predicate arguments.

=E2=80=93Arthur

--=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp=
..org/d/msgid/std-proposals/e584f516-f714-4175-a4bf-d89cc242cce6%40isocpp.or=
g.

------=_Part_141_2133372762.1495061994741
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">On Wednesday, May 17, 2017 at 3:12:28 AM UTC-6, Marc Mutz =
wrote:<br>&gt; I have two suggestions on how to improve the API of the eras=
e()<div>&gt; and erase_if() algorithms. <br> &gt;<br>&gt; The first concern=
s the return type. Alex Stepanov teaches us to not throw away <br>&gt; usef=
ul information, but that is exactly what the functions currently do: the <b=
r>&gt; implementation knows how many elements were removed, but that inform=
ation is <br>&gt; lost upon return from the function. [...]<br>&gt; I there=
fore propose to change the return type from void to size_t, returning=C2=A0=
<br>&gt; the number of elements removed.=C2=A0<br><br>I&#39;m &quot;weakly =
against&quot; this idea out of general conservativity, but I don&#39;t see =
anything fundamentally wrong with it.<br> You might equally well propose th=
at the function should return &quot;the last removed element&quot; as std::=
optional&lt;value_type&gt;, or some such; isn&#39;t that also information t=
hat&#39;s &quot;thrown away&quot; by the current algorithm? =C2=A0Sure, it&=
#39;d cost some performance to do that, but it&#39;d also cost performance =
to count the number of removed elements, which otherwise wouldn&#39;t need =
to be tracked by the algorithm.</div><div>=C2=A0<br>&gt; [...] For most con=
tainers, this is not a <br>&gt; problem, because you can easily (and in con=
stant time) compare the size() of <br>&gt; the container before and after t=
he application of the algorithm, but that is <br>&gt; notably not the case =
for std::forward_list. [...]<br> <br></div><div>Surely that&#39;s a problem=
 only for the poor misguided users of std::forward_list. :P</div><div><br>&=
gt;=C2=A0The second is about passing std::pair as the argument of the predi=
cate for <br>&gt; erase_if for maps. Yes, from a theoretical POV, passing t=
he value_type is <br>&gt; consistent. Still, IMO, the algorithm should pass=
 the key and value <br>&gt; separately, as that allows easier extension to =
associative data structures <br>&gt; that do not store keys and values toge=
ther, or not as a std::pair (like e.g. <br>&gt;=C2=A0<a href=3D"http://doc.=
qt.io/qt-5/qhash.html">http://doc.qt.io/qt-5/qhash.html</a>). It would also=
 make for easier predicates, <br>&gt; as they wouldn&#39;t need to decompos=
e the pair first (no pun intended). Finally, <br>&gt; it would allow to iso=
late such predicates from the unfortunate &#39;first&#39; and <br>&gt; &#39=
;second&#39; names (decomposition declarations solve that, too, but at the =
cost of <br>&gt; another line of code). <br> <br>Agreed that std::pair has =
a pretty terrible API, but for better or worse, it *is* the value_type of t=
he container.<br><br>&gt; As I _do_ see the value in accepting value_type f=
or generic code, how about <br>&gt; the algorithm checks to see whether it =
can pass key and value separately, and, <br>&gt; if so, does it, otherwise =
passes as a pair? Pseudocode:=C2=A0</div><div> &gt;<br>&gt; if constexpr (_=
_is_binary_predicate(p)) { <br>&gt; =C2=A0 =C2=A0 if (p(it-&gt;first, it-&g=
t;second)) <br>&gt; =C2=A0 =C2=A0 =C2=A0 =C2=A0 it =3D c.erase(it); <br>&gt=
; =C2=A0 =C2=A0 else <br>&gt; =C2=A0 =C2=A0 =C2=A0 =C2=A0 ++it; <br>&gt; } =
else {</div><div>&gt; =C2=A0 =C2=A0=C2=A0if (p(*it)) <br>&gt; =C2=A0 =C2=A0=
 =C2=A0 =C2=A0 it =3D c.erase(it); <br>&gt; =C2=A0 =C2=A0 else <br>&gt; =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 ++it; <br>&gt; }</div><div><br></div><div>Surely t=
he check should be reversed, since breaking down the pair into separate arg=
uments is &quot;doing more&quot; than just passing a reference to the pair =
itself?</div><div>Also, what if &#39;p&#39; is a generic lambda or somethin=
g like that, which is callable in several <i>different</i> ways? Letting th=
e algorithm choose the signature with which it&#39;ll call &#39;p&#39; seem=
s like a recipe for confusion. Every other algorithm is really explicit abo=
ut the exact way it&#39;s going to call all its predicate arguments.</div><=
div><br></div><div>=E2=80=93Arthur</div></div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/e584f516-f714-4175-a4bf-d89cc242cce6%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/e584f516-f714-4175-a4bf-d89cc242cce6=
%40isocpp.org</a>.<br />

------=_Part_141_2133372762.1495061994741--

------=_Part_140_1634515155.1495061994741--

.

On Wednesday 17 May 2017 11:11:22 Marc Mutz wrote:
> The first concerns the return type. Alex Stepanov teaches us to not throw
> away  useful information, but that is exactly what the functions currently
> do: the implementation knows how many elements were removed, but that
> information is lost upon return from the function. For most containers,
> this is not a problem, because you can easily (and in constant time)
> compare the size() of the container before and after the application of
> the algorithm, but that is notably not the case for std::forward_list.
>
> I therefore propose to change the return type from void to size_t,
> returning  the number of elements removed.

I've also found *list::remove{,_if} and *list::unique() with the same "problem".

https://github.com/marc-kdab/std-
proposals/raw/master/algorithms/lf2_erase_if/D000R0.pdf

has the details.

Thanks,
Marc


--
Marc Mutz <marc.mutz@kdab.com> | Senior Software Engineer
KDAB (Deutschland) GmbH & Co.KG, a KDAB Group Company
Tel: +49-30-521325470
KDAB - The Qt, C++ and OpenGL Experts

.

On Thursday 18 May 2017 11:23:32 Marc Mutz wrote:
> On Wednesday 17 May 2017 11:11:22 Marc Mutz wrote:
> > The first concerns the return type. Alex Stepanov teaches us to not throw
> > away  useful information, but that is exactly what the functions
> > currently do: the implementation knows how many elements were removed,
> > but that information is lost upon return from the function. For most
> > containers, this is not a problem, because you can easily (and in
> > constant time) compare the size() of the container before and after the
> > application of the algorithm, but that is notably not the case for
> > std::forward_list.
> >
> > I therefore propose to change the return type from void to size_t,
> > returning  the number of elements removed.
>
> I've also found *list::remove{,_if} and *list::unique() with the same
> "problem".
>
> https://github.com/marc-kdab/std-
> proposals/raw/master/algorithms/lf2_erase_if/D000R0.pdf
>
> has the details.

Today's version has assembler comparisons for Clang 4.0 and GCC 7.1, an
expanded test programme, and argues that returning the number of removed
elements is consistent with pre-exisiting practice, namely
map::erase(key_type).

I think I now have a strong case, so I requested a P number for it.

I can't make it to the July meeting, though, so I need a champion to present
it...

Thanks,
Marc

--
Marc Mutz <marc.mutz@kdab.com> | Senior Software Engineer
KDAB (Deutschland) GmbH & Co.KG, a KDAB Group Company
Tel: +49-30-521325470
KDAB - The Qt, C++ and OpenGL Experts

.