[PATCH, libstdc++] Uniform container erasure for c++20.

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

[PATCH, libstdc++] Uniform container erasure for c++20.

Ed Smith-Rowland
All,

I's very late but uniform container erasure is, I think, the last little
tidbit to graduate from fundamentals/v2 to std at the last meeting.  I
think it would be a shame not to nudge this into gcc-9.  The routines
are very short so I just copied them. Ditto the testcases (with
adjustments).  The node erasure tool was moved from experimental to
std/bits and adjustments made to affected *set/*map headers.

The experimental code has been in our tree since 2015.

This builds and tests clean on x86_64-linux.

Ed



patch_erasure (46K) Download Attachment
CL_erasure (1K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH, libstdc++] Uniform container erasure for c++20.

Ed Smith-Rowland

> Holy crap.  i just noticed that *set/*map don't have plain erase()
> only erase_if()!
>
> I need to implement final:
> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p1209r0.html 
> before I do anything.  Both for experimental and std.
>
> Ed
>
Never mind, This last paper *doesn't* have erase(value_type) for these
containers.  They were stricken from n4161.htm UCE R1.  I guess KeyTp ==
ValTp could be confusing.  I guess erase_key could be a thing later. 
It's too late for erase() -> erase_value().

False alarm.


Reply | Threaded
Open this post in threaded view
|

Re: [PATCH, libstdc++] Uniform container erasure for c++20.

Ed Smith-Rowland
In reply to this post by Ed Smith-Rowland
On 11/29/18 9:09 AM, Jonathan Wakely wrote:

> On 29/11/18 08:47 -0500, Ed Smith-Rowland wrote:
>> Fixed with 266616.
>
> Thanks!
>
>> Index: include/std/deque
>> ===================================================================
>> --- include/std/deque    (revision 266567)
>> +++ include/std/deque    (working copy)
>> @@ -58,6 +58,7 @@
>> #pragma GCC system_header
>>
>> #include <bits/stl_algobase.h>
>> +#include <bits/stl_algo.h> // For remove and remove_if
>
> Please only include <bits/stl_algo.h> when __cplusplus > 201703L
> otherwise we include hundreds of kilobytes of code just for these tiny
> functions that aren't even defined in the default C++14 dialect.
Done with 266624.

Ed

> At some point I'll split std::remove and std::remove_if into their own
> header, and we can just include that instead



CL_erasure_incs (306 bytes) Download Attachment
patch_erasure_incs (2K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH, libstdc++] Uniform container erasure for c++20.

Jonathan Wakely-3
On 29/11/18 10:18 -0500, Ed Smith-Rowland wrote:

>On 11/29/18 9:09 AM, Jonathan Wakely wrote:
>>On 29/11/18 08:47 -0500, Ed Smith-Rowland wrote:
>>>Fixed with 266616.
>>
>>Thanks!
>>
>>>Index: include/std/deque
>>>===================================================================
>>>--- include/std/deque    (revision 266567)
>>>+++ include/std/deque    (working copy)
>>>@@ -58,6 +58,7 @@
>>>#pragma GCC system_header
>>>
>>>#include <bits/stl_algobase.h>
>>>+#include <bits/stl_algo.h> // For remove and remove_if
>>
>>Please only include <bits/stl_algo.h> when __cplusplus > 201703L
>>otherwise we include hundreds of kilobytes of code just for these tiny
>>functions that aren't even defined in the default C++14 dialect.
>
>Done with 266624.

Thanks for the quick turnaround.


Reply | Threaded
Open this post in threaded view
|

Re: [PATCH, libstdc++] Uniform container erasure for c++20.

Jonathan Wakely-3
In reply to this post by Ed Smith-Rowland
On 29/11/18 12:05 -0500, Ed Smith-Rowland wrote:

>On 11/26/18 6:18 AM, Jonathan Wakely wrote:
>>On 24/11/18 13:54 -0500, Ed Smith-Rowland wrote:
>>>All,
>>>
>>>I's very late but uniform container erasure is, I think, the last
>>>little tidbit to graduate from fundamentals/v2 to std at the last
>>>meeting.  I think it would be a shame not to nudge this into
>>>gcc-9.  The routines are very short so I just copied them. Ditto
>>>the testcases (with adjustments).  The node erasure tool was moved
>>>from experimental to std/bits and adjustments made to affected
>>>*set/*map headers.
>>>
>>>The experimental code has been in our tree since 2015.
>>>
>>>This builds and tests clean on x86_64-linux.
>>
>>OK for trunk as it only touches experimental C++2a and TS material.
>>Thanks.
>>
>>I pointed out to the committee that the erase_if functions added to
>>C++20 completely overlook P0646R1 "Improving the Return Value of
>>Erase-Like Algorithms" and so fail to preserve the useful information
>>returned by the members of the linked list containers.
>Is *this* what you has in mind for this?  I basically return the
>number of erased items for all the things.

Yes, that's exactly what I had in mind (and what I expect to get
proposed for C++20 in the near future).

What does everyone else think, should we go ahead and do this?

The point is that C++20 changed forward_list (and list, for
consistency) to return the number of removed elements. The reason for
that is you can't easily find out the size before and after removing
elements, because forward_list doesn't have a size() member!

So IMHO the non-member erase should also return the size, and so that
it's uniform it should do that for all containers not just the lists.


>Index: include/std/forward_list
>===================================================================
>--- include/std/forward_list (revision 266623)
>+++ include/std/forward_list (working copy)
>@@ -66,16 +66,17 @@
> {
> _GLIBCXX_BEGIN_NAMESPACE_VERSION
>   template<typename _Tp, typename _Alloc, typename _Predicate>
>-    inline void
>+    inline typename forward_list<_Tp, _Alloc>::size_type
>     erase_if(forward_list<_Tp, _Alloc>& __cont, _Predicate __pred)
>-    { __cont.remove_if(__pred); }
>+    { return __cont.remove_if(__pred); }
>
>   template<typename _Tp, typename _Alloc, typename _Up>
>-    inline void
>+    inline typename forward_list<_Tp, _Alloc>::size_type
>     erase(forward_list<_Tp, _Alloc>& __cont, const _Up& __value)
>     {
>       using __elem_type = typename forward_list<_Tp, _Alloc>::value_type;
>-      erase_if(__cont, [&](__elem_type& __elem) { return __elem == __value; });
>+      return erase_if(__cont,
>+      [&](__elem_type& __elem) { return __elem == __value; });
>     }

I realised this can be a polymorphic lambda (here and in the TS
version) because it's only defined for C++14 and later. Also, the
erase overload that calls erase_if needs to qualify it as std::erase_if
to prevent ADL:

      return std::erase_if(__cont,
                           [&](auto& __elem) { return __elem == __value; });

Same comment for the erase(std::list) case.


Reply | Threaded
Open this post in threaded view
|

Re: [PATCH, libstdc++] Uniform container erasure for c++20.

Ville Voutilainen
On Fri, 30 Nov 2018 at 12:25, Jonathan Wakely <[hidden email]> wrote:
> Yes, that's exactly what I had in mind (and what I expect to get
> proposed for C++20 in the near future).
>
> What does everyone else think, should we go ahead and do this?

Yes, if we are confident that's what will be in C++20.

> The point is that C++20 changed forward_list (and list, for
> consistency) to return the number of removed elements. The reason for
> that is you can't easily find out the size before and after removing
> elements, because forward_list doesn't have a size() member!
> So IMHO the non-member erase should also return the size, and so that
> it's uniform it should do that for all containers not just the lists.

I don't mind forward_list being an exception. Returning the size from
other containers
is a bit pointless; presumably it would need to return a pair, and
handling that is clunky
even with structured bindings.