Page MenuHomePhabricator

[libc++][P1115][C++20] Improving the Return Value of Erase-Like Algorithms II: Free erase/erase if.
Needs ReviewPublic

Authored by curdeius on Tue, Mar 10, 4:20 AM.

Details

Reviewers
EricWF
mclow.lists
ldionne
Group Reviewers
Restricted Project
Summary

This patch adds return type to std::erase and std::erase_if functions.

Also:

  • Update __cpp_lib_erase_if to 202002L.
  • Fix synopsis in unordered_map.
  • Fix generate_feature_test_macro_components.py script.

Diff Detail

Event Timeline

curdeius created this revision.Tue, Mar 10, 4:20 AM
Herald added a project: Restricted Project. · View Herald Transcript
curdeius edited the summary of this revision. (Show Details)Tue, Mar 10, 4:22 AM
curdeius added reviewers: mclow.lists, ldionne.
curdeius marked an inline comment as done.Tue, Mar 10, 4:29 AM
curdeius added inline comments.
libcxx/include/deque
3028–3032

For deque, string and vector, it might be nice to refactor this repetitive code (e.g. to a __libcpp_erase_container function, analogue to __libcpp_erase_if_container).
However, I don't know in which header it should be put as these 3 headers have no good candidate being a common include.
Note that __libcpp_erase_if_container is in <functional> and that doesn't pose any problems for maps/sets as they already include it.
Vector and string already include <__functional_base> but deque doesn't, so I'm not sure what should be the best solution. Creating a new helper header? Leaving it unrefactored?

Possible implementation of the helper:

template <class _Container>
inline typename _Container::size_type
__libcpp_erase_container(_Container& __c,
                         typename _Container::iterator __new_end) {
  typename _Container::size_type __erased_count =
      std::distance(__new_end, __c.end());
  __c.erase(__new_end, __c.end());
  return __erased_count;
}
curdeius updated this revision to Diff 249323.Tue, Mar 10, 5:07 AM

Fixed forgotten return type tests.

curdeius updated this revision to Diff 249324.Tue, Mar 10, 5:10 AM

Fix string.

curdeius marked an inline comment as not done.Tue, Mar 10, 5:12 AM
curdeius updated this revision to Diff 249338.Tue, Mar 10, 5:51 AM

Fix tests with custom allocators. Fix assert in map test.

curdeius updated this revision to Diff 249344.Tue, Mar 10, 5:58 AM

Fix __cpp_lib_erase_if value.

The pre-merge build results show this build as failed because of failing clang-format linter tests (https://reviews.llvm.org/harbormaster/build/52549/, https://results.llvm-merge-guard.org/amd64_debian_testing_clang8-4604/summary.html).
However, these "failures" are all misindentations of preprocessor directives in generated files in libcxx/test/std/language.support/support.limits/support.limits.general/.
That's out of scope of this patch, but isn't the real fix modifying .clang-format config file to indent PP directives (or having a local copy of .clang-format in tests)?

EricWF requested changes to this revision.Wed, Mar 11, 8:23 PM

I think there is a bug in the paper, but I think the return type should be difference_type not size_type.
The paper says the return value is equivalent to:

auto r = distance(a, b);
return r;

And std::distance returns difference_type.

What do you think?

libcxx/include/functional
3087

We need to avoid calling an overloaded comma operator here.

This revision now requires changes to proceed.Wed, Mar 11, 8:23 PM
Herald added a reviewer: Restricted Project. · View Herald TranscriptWed, Mar 11, 8:23 PM

It would be nice if we could remove the calls to std::difference and replace them with a count variable so that we only have to iterate once. It may require adding a __libcpp_ erase function, though.

curdeius updated this revision to Diff 249862.Thu, Mar 12, 2:23 AM

Avoid using overloaded comma operator.

curdeius updated this revision to Diff 249863.Thu, Mar 12, 2:25 AM
curdeius marked 2 inline comments as done.

Fix typo.

It would be nice if we could remove the calls to std::difference and replace them with a count variable so that we only have to iterate once. It may require adding a __libcpp_ erase function, though.

Where do you see that the iteration takes place twice? std::distance on LegacyRandomAccessIterators is an O(1) operation. And all of basic_string, deque and vector iterators belong to this category.
What do you mean by adding a count variable? remove and remove_if functions do not provide us with a count.

I think there is a bug in the paper, but I think the return type should be difference_type not size_type.

I'm not sure if it's a bug. I think that a coherence with other APIs was intended. Apart the additions in P0646, there is already pre-C++11 size_type map::erase(key_type) as well as size_type set::erase(key_type).

Otherwise, to be coherent with __libcpp_erase_if_container and avoid casting difference_type to size_type, I'd suggest returning old_size - size() instead of using distance.

libcxx/include/functional
3087

Done.

curdeius updated this revision to Diff 249883.Thu, Mar 12, 3:40 AM

Avoid using std::distance.

curdeius marked an inline comment as done.Thu, Mar 12, 3:44 AM