On 17 May 2017 at 17:10, Nicol Bolas <jmckesson@gmail.com> wrote:
>> 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`

Perhaps you should read the subject. This is about the algorithm in
Library Fundamentals v2.

--
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/CAFk2RUbHp%2B%3Dm1cR-jH8SOsmiz6MNHkgprKdtBkx8Dy3H-OpsUA%40mail.gmail.com.

.

------=_Part_3059_833352560.1495037250414
Content-Type: multipart/alternative;
 boundary="----=_Part_3060_2084202567.1495037250414"

------=_Part_3060_2084202567.1495037250414
Content-Type: text/plain; charset="UTF-8"



On Wednesday, May 17, 2017 at 10:16:16 AM UTC-4, Ville Voutilainen wrote:
>
> On 17 May 2017 at 17:10, Nicol Bolas <jmck...@gmail.com <javascript:>>
> wrote:
> >> 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`
>
> Perhaps you should read the subject. This is about the algorithm in
> Library Fundamentals v2.
>

OH! That's what "LFv2" meant.

In that case, I would say that this is not a good idea for a change. To do
what is being suggested would violate one of the basic elements of STL
container design: that containers contain a single value. This is why
containers have `value_type`, after all; it is the type returned by
dereferencing a container's iterator (well, more generally `reference`, but
that should be a `value_type&` in non-proxy cases. And until Ranges TS, we
can't really handle proxy iterators).

Yes, this means that users have to follow the standard library conventions
for these sorts of things, that they have to implement their map-style
types in such a way. But that's how we work.

Furthermore, I don't think the proposed solution really provides the kind
of general-purpose tools that users would need in order to be able to
separate keys from values. After all, this implementation requires that the
`reference` returned by the iterator's `operator*` is a `pair` or has a
`pair`-like interface. It would make more sense to invoke structured
binding on the `reference`; this would allow users to use more efficient
proxies (again, we don't really allow that, but Ranges TS ought to fix
that):

if constexpr (__is_binary_predicate(p))
{
  auto &&[first, second] = *it;
  if (p(first, second))
    it = c.erase(it);
  else
    ++it;
}

That also brings up a different question: in light of Ranges TS, do we even
*want* these container algorithms?

--
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/14e303f2-fca5-4654-8f1c-736da532e40a%40isocpp.org.

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

<div dir=3D"ltr"><br><br>On Wednesday, May 17, 2017 at 10:16:16 AM UTC-4, V=
ille Voutilainen wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0=
;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">On 17 M=
ay 2017 at 17:10, Nicol Bolas &lt;<a href=3D"javascript:" target=3D"_blank"=
 gdf-obfuscated-mailto=3D"0DcSn9s2AgAJ" rel=3D"nofollow" onmousedown=3D"thi=
s.href=3D&#39;javascript:&#39;;return true;" onclick=3D"this.href=3D&#39;ja=
vascript:&#39;;return true;">jmck...@gmail.com</a>&gt; wrote:
<br>&gt;&gt; The second is about passing std::pair as the argument of the p=
redicate for
<br>&gt;&gt; erase_if for maps. Yes, from a theoretical POV, passing the va=
lue_type is
<br>&gt;&gt; consistent. Still, IMO, the algorithm should pass the key and =
value
<br>&gt;&gt; separately, as that allows easier extension to associative dat=
a structures
<br>&gt;&gt; that do not store keys and values together,
<br>&gt;
<br>&gt;
<br>&gt; There is no &quot;erase_if&quot; function anywhere in the standard=
.. And `remove_if`
<br>
<br>Perhaps you should read the subject. This is about the algorithm in
<br>Library Fundamentals v2.
<br></blockquote><div><br>OH! That&#39;s what &quot;LFv2&quot; meant.<br><b=
r>In that case, I would say that this is not a good idea for a change. To d=
o what is being suggested would violate one of the basic elements of STL co=
ntainer design: that containers contain a single value. This is why contain=
ers have `value_type`, after all; it is the type returned by dereferencing =
a container&#39;s iterator (well, more generally `reference`, but that shou=
ld be a `value_type&amp;` in non-proxy cases. And until Ranges TS, we can&#=
39;t really handle proxy iterators).<br><br>Yes, this means that users have=
 to follow the standard library conventions for these sorts of things, that=
 they have to implement their map-style types in such a way. But that&#39;s=
 how we work.<br><br>Furthermore, I don&#39;t think the proposed solution r=
eally provides the kind of general-purpose tools that users would need in o=
rder to be able to separate keys from values. After all, this implementatio=
n requires that the `reference` returned by the iterator&#39;s `operator*` =
is a `pair` or has a `pair`-like interface. It would make more sense to inv=
oke structured binding on the `reference`; this would allow users to use mo=
re efficient proxies (again, we don&#39;t really allow that, but Ranges TS =
ought to fix that):<br><br><div style=3D"background-color: rgb(250, 250, 25=
0); border-color: rgb(187, 187, 187); border-style: solid; border-width: 1p=
x; overflow-wrap: break-word;" class=3D"prettyprint"><code class=3D"prettyp=
rint"><div class=3D"subprettyprint"><span style=3D"color: #008;" class=3D"s=
tyled-by-prettify">if</span><span style=3D"color: #000;" class=3D"styled-by=
-prettify"> </span><span style=3D"color: #008;" class=3D"styled-by-prettify=
">constexpr</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">__is_binary_predi=
cate</span><span style=3D"color: #660;" class=3D"styled-by-prettify">(</spa=
n><span style=3D"color: #000;" class=3D"styled-by-prettify">p</span><span s=
tyle=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;" c=
lass=3D"styled-by-prettify"><br>=C2=A0 </span><span style=3D"color: #008;" =
class=3D"styled-by-prettify">auto</span><span style=3D"color: #000;" class=
=3D"styled-by-prettify"> </span><span style=3D"color: #660;" class=3D"style=
d-by-prettify">&amp;&amp;[</span><span style=3D"color: #000;" class=3D"styl=
ed-by-prettify">first</span><span style=3D"color: #660;" class=3D"styled-by=
-prettify">,</span><span style=3D"color: #000;" class=3D"styled-by-prettify=
"> second</span><span style=3D"color: #660;" class=3D"styled-by-prettify">]=
</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> </span><s=
pan style=3D"color: #660;" class=3D"styled-by-prettify">=3D</span><span sty=
le=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=3D"col=
or: #660;" class=3D"styled-by-prettify">*</span><span style=3D"color: #000;=
" class=3D"styled-by-prettify">it</span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">;</span><span style=3D"color: #000;" class=3D"style=
d-by-prettify"><br>=C2=A0 </span><span style=3D"color: #008;" class=3D"styl=
ed-by-prettify">if</span><span style=3D"color: #000;" class=3D"styled-by-pr=
ettify"> </span><span style=3D"color: #660;" class=3D"styled-by-prettify">(=
</span><span style=3D"color: #000;" class=3D"styled-by-prettify">p</span><s=
pan style=3D"color: #660;" class=3D"styled-by-prettify">(</span><span style=
=3D"color: #000;" class=3D"styled-by-prettify">first</span><span style=3D"c=
olor: #660;" class=3D"styled-by-prettify">,</span><span style=3D"color: #00=
0;" class=3D"styled-by-prettify"> second</span><span style=3D"color: #660;"=
 class=3D"styled-by-prettify">))</span><span style=3D"color: #000;" class=
=3D"styled-by-prettify"><br>=C2=A0 =C2=A0 it </span><span style=3D"color: #=
660;" class=3D"styled-by-prettify">=3D</span><span style=3D"color: #000;" c=
lass=3D"styled-by-prettify"> c</span><span style=3D"color: #660;" class=3D"=
styled-by-prettify">.</span><span style=3D"color: #000;" class=3D"styled-by=
-prettify">erase</span><span style=3D"color: #660;" class=3D"styled-by-pret=
tify">(</span><span style=3D"color: #000;" class=3D"styled-by-prettify">it<=
/span><span style=3D"color: #660;" class=3D"styled-by-prettify">);</span><s=
pan style=3D"color: #000;" class=3D"styled-by-prettify"><br>=C2=A0 </span><=
span style=3D"color: #008;" class=3D"styled-by-prettify">else</span><span s=
tyle=3D"color: #000;" class=3D"styled-by-prettify"><br>=C2=A0 =C2=A0 </span=
><span style=3D"color: #660;" class=3D"styled-by-prettify">++</span><span s=
tyle=3D"color: #000;" class=3D"styled-by-prettify">it</span><span style=3D"=
color: #660;" class=3D"styled-by-prettify">;</span><span style=3D"color: #0=
00;" class=3D"styled-by-prettify"><br></span><span style=3D"color: #660;" c=
lass=3D"styled-by-prettify">}</span></div></code></div><br>That also brings=
 up a different question: in light of Ranges TS, do we even <i>want</i> the=
se container algorithms?<br></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/14e303f2-fca5-4654-8f1c-736da532e40a%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/14e303f2-fca5-4654-8f1c-736da532e40a=
%40isocpp.org</a>.<br />

------=_Part_3060_2084202567.1495037250414--

------=_Part_3059_833352560.1495037250414--

.

On Thursday 18 May 2017 00:59:54 Arthur O'Dwyer wrote:
> 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.
> >
> > 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. [...]
> > I therefore propose to change the return type from void to size_t,
>
> returning
>
> > the number of elements removed.
>
> I'm "weakly against" this idea out of general conservativity, but I don't
> see anything fundamentally wrong with it.
> You might equally well propose that the function should return "the last
> removed element" as std::optional<value_type>, or some such; isn't that
> also information that's "thrown away" by the current algorithm?  Sure, it'd
> cost some performance to do that, but it'd also cost performance to count
> the number of removed elements, which otherwise wouldn't need to be tracked
> by the algorithm.

For erase(), you know which elements are returned (those which are equal to
the prototype value passed), but you have no way of knowing how many were
removed, except by counting before and after. I'm pretty sure that compilers
can remove the counting if they see that the return value is not used. It's
just a local unused counter, or a useless subtraction. For erase_if(), you
could theoretically count the number of predicate invocations, but ... ugh.

As for returning the last-removed value, sure, or a vector of all removed
elements. But that's another algorithm, roughly partition_copy. The point is
that if you erase elements, you might want to know how many, or at least
whether some were removed. And right now you can't.

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:32:28 Marc Mutz wrote:
> I'm pretty sure that compilers
> can remove the counting if they see that the return value is not used.
> It's  just a local unused counter, or a useless subtraction

So, I have implemented erase() and erase_if() over Qt's QList:

 #ifndef COUNTING

 template <typename T, typename U>
 void erase(QList<T> &c, const U &v)
 {
    const auto end = c.end();
    const auto it = std::remove(c.begin(), end, v);
    c.erase(it, end);
 }

 #else

 template <typename T, typename U>
 std::size_t erase(QList<T> &c, const U &v)
 {
    const auto end = c.end();
    const auto it = std::remove(c.begin(), end, v);
    const auto numRemoved = size_t(std::distance(it, end));
    c.erase(it, end);
    return numRemoved;
 }

 #endif

(erase_if skipped)

If I port some erase-remove idioms in QtCore to these functions, and compile
QtCore with COUNTING or without, I get these surprising results:

 $ size lib/lib*-lfv2-*
    text    data     bss     dec     hex filename
 5711683   52176   14136 5777995  582a4b lib/libQt5Core.so.5-lfv2-counting
 5711787   52176   14136 5778099  582ab3 lib/libQt5Core.so.5-lfv2-non-counting

iow: the non-counting version is smaller. Now, that's just one data point, and
it might well be due to the non-counting version being inlined while the other
is not.

But here's an example with std::vector, which shows identical assembly for the
two versions: https://godbolt.org/g/iWSbJu

And here's an example with a node-based container, showing identical assembly,
too: https://godbolt.org/g/CIZsU5

So, no, I don't think there's any overhead to counting when not used.

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

.