[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

[Jonathan Wakely]

Post by 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.

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.

I expect that to get fixed as a defect. If you have time and
motivation, I think we should make that change proactively in
libstdc++. The Library Fundamentals versions can continue to return
void, but the ones in namespace std can return the number of elements
removed.

[Ed Smith-Rowland]

Post by Jonathan Wakely

Post by 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.

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.
I expect that to get fixed as a defect. If you have time and
motivation, I think we should make that change proactively in
libstdc++. The Library Fundamentals versions can continue to return
void, but the ones in namespace std can return the number of elements
removed.

I committed essentially what I started with (attached) as a baseline.

I would like to change the return as you suggest in another patch.

It seems to me that the intent of UCE is to have the same API for all
containers.

So all erase_if would have size_type returns, including vector, string,
deque.  Not a problem as those are const time.

It looks like the node erasure tool needs to maintain a count of erased
nodes.  (it can't use erase(KeyT k) that returns a count since it
involves a predicate rather than key compare.  Too bad there aren't
'size_t erase_if(Pred)' members.)  No biggie - the complexity isn't
changed by keeping count.

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

[Ed Smith-Rowland]

Holy crap.  i just noticed that *set/*map don't have plain erase()
only erase_if()!
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.

[Jonathan Wakely]

Index: testsuite/21_strings/basic_string/erasure.cc
===================================================================
--- testsuite/21_strings/basic_string/erasure.cc (nonexistent)
+++ testsuite/21_strings/basic_string/erasure.cc (working copy)
@@ -0,0 +1,53 @@
+// { dg-do run { target c++2a } }
+

None of these new tests actually run by default, because they are
gated to only run for C++2a and the default is gnu++14. That means
they're all skipped as UNSUPPORTED.

(When I add new tests I always try to remember to check the
testsuite/libstdc++.sum file to make sure they are actually running).

The tests need an explicit -std option added via dg-options, which has
to come before the dg-do directive, otherwise the target check still
uses the default options i.e.

// { dg-options "-std=gnu++2a" }
// { dg-do run { target c++2a } }

With that added, most of them start to FAIL:

FAIL: 23_containers/deque/erasure.cc (test for excess errors)
UNRESOLVED: 23_containers/deque/erasure.cc compilation failed to produce executable
FAIL: 23_containers/unordered_set/erasure.cc (test for excess errors)
UNRESOLVED: 23_containers/unordered_set/erasure.cc compilation failed to produce executable
FAIL: 23_containers/vector/erasure.cc (test for excess errors)
UNRESOLVED: 23_containers/vector/erasure.cc compilation failed to produce executable
FAIL: experimental/deque/erasure.cc (test for excess errors)
UNRESOLVED: experimental/deque/erasure.cc compilation failed to produce executable
FAIL: experimental/forward_list/erasure.cc (test for excess errors)
UNRESOLVED: experimental/forward_list/erasure.cc compilation failed to produce executable
FAIL: experimental/list/erasure.cc (test for excess errors)
UNRESOLVED: experimental/list/erasure.cc compilation failed to produce executable
FAIL: experimental/vector/erasure.cc (test for excess errors)
UNRESOLVED: experimental/vector/erasure.cc compilation failed to produce executable


The errors are all like:

In file included from /home/jwakely/src/gcc/gcc/libstdc++-v3/testsuite/23_containers/vector/erasure.cc:21:
/home/jwakely/src/gcc/build/x86_64-pc-linux-gnu/libstdc++-v3/include/vector: In function 'void std::erase_if(std::vector<_Tp, _Alloc>&, _Predicate)':
/home/jwakely/src/gcc/build/x86_64-pc-linux-gnu/libstdc++-v3/include/vector:101: error: 'remove_if' is not a member of 'std'; did you mean 'remove_cv'?
/home/jwakely/src/gcc/build/x86_64-pc-linux-gnu/libstdc++-v3/include/vector: In function 'void std::erase(std::vector<_Tp, _Alloc>&, const _Up&)':
/home/jwakely/src/gcc/build/x86_64-pc-linux-gnu/libstdc++-v3/include/vector:109: error: 'remove' is not a member of 'std'; did you mean 'move'?

This is because std::remove and std::remove_if are defined in
<bits/stl_algo.h> which is not included.

Could you please fix this ASAP?

[Ed Smith-Rowland]

Post by Jonathan Wakely

Index: testsuite/21_strings/basic_string/erasure.cc
===================================================================
--- testsuite/21_strings/basic_string/erasure.cc (nonexistent)
+++ testsuite/21_strings/basic_string/erasure.cc    (working copy)
@@ -0,0 +1,53 @@
+// { dg-do run { target c++2a } }
+

None of these new tests actually run by default, because they are
gated to only run for C++2a and the default is gnu++14. That means
they're all skipped as UNSUPPORTED.
(When I add new tests I always try to remember to check the
testsuite/libstdc++.sum file to make sure they are actually running).
The tests need an explicit -std option added via dg-options, which has
to come before the dg-do directive, otherwise the target check still
uses the default options i.e.
// { dg-options "-std=gnu++2a" }
// { dg-do run { target c++2a } }
FAIL: 23_containers/deque/erasure.cc (test for excess errors)
UNRESOLVED: 23_containers/deque/erasure.cc compilation failed to produce executable
FAIL: 23_containers/unordered_set/erasure.cc (test for excess errors)
UNRESOLVED: 23_containers/unordered_set/erasure.cc compilation failed to produce executable
FAIL: 23_containers/vector/erasure.cc (test for excess errors)
UNRESOLVED: 23_containers/vector/erasure.cc compilation failed to produce executable
FAIL: experimental/deque/erasure.cc (test for excess errors)
UNRESOLVED: experimental/deque/erasure.cc compilation failed to produce executable
FAIL: experimental/forward_list/erasure.cc (test for excess errors)
UNRESOLVED: experimental/forward_list/erasure.cc compilation failed to produce executable
FAIL: experimental/list/erasure.cc (test for excess errors)
UNRESOLVED: experimental/list/erasure.cc compilation failed to produce executable
FAIL: experimental/vector/erasure.cc (test for excess errors)
UNRESOLVED: experimental/vector/erasure.cc compilation failed to produce executable
In file included from
error: 'remove_if' is not a member of 'std'; did you mean 'remove_cv'?
error: 'remove' is not a member of 'std'; did you mean 'move'?
This is because std::remove and std::remove_if are defined in
<bits/stl_algo.h> which is not included.
Could you please fix this ASAP

Sorry about that.

Fixed with 266616.

Ed

[Jonathan Wakely]

Post by Ed Smith-Rowland
Fixed with 266616.

Thanks!

Post by Ed Smith-Rowland
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.

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

[Ed Smith-Rowland]

Post by Jonathan Wakely

Post by Ed Smith-Rowland
Fixed with 266616.

Thanks!

Post by Ed Smith-Rowland
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

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

[Jonathan Wakely]

Post by Ed Smith-Rowland

Post by Jonathan Wakely

Post by Ed Smith-Rowland
Fixed with 266616.

Thanks!

Post by Ed Smith-Rowland
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.

[Jakub Jelinek]

Post by Ed Smith-Rowland
--- 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

Isn't that too expensive, especially in non-C++20 modes?
stl_algo.h is larger than 200KB.

So, could these includes be either guarded with __cplusplus > 201703
if they are only needed for C++20, or better have bits/stl_remove.h
containing just those?

Jakub

[Ed Smith-Rowland]

Post by Jonathan Wakely

Post by 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.

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.

Post by Jonathan Wakely
I expect that to get fixed as a defect. If you have time and
motivation, I think we should make that change proactively in
libstdc++. The Library Fundamentals versions can continue to return
void, but the ones in namespace std can return the number of elements
removed

Ed

[Ed Smith-Rowland]

This version of erase_if/erase returning number erased actually build
and tests cleanly on x86_64-linux.

Is this what you has in mind for this?  I basically return the number of
erased items for all the things

Ed

[Jonathan Wakely]

Post by Jonathan Wakely

Post by 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.

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.

[Ville Voutilainen]

Post by Jonathan Wakely
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.

Post by Jonathan Wakely
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.

[Jonathan Wakely]

Post by Ville Voutilainen

Post by Jonathan Wakely
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.

We're not, but we don't need to be. Anything in the current draft
could get removed before the final standard.

Post by Ville Voutilainen

Post by Jonathan Wakely
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

Oops, I meant "should also return the number of removed elements", not
"the number of removed element and also the new size".

Post by Ville Voutilainen

Post by Jonathan Wakely
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.

No need for a pair, sorry for the confusing wording above.