Skip to content

Implement ranges::starts_with and ranges::ends_with #1997

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
Stephan T. Lavavej (StephanTLavavej) merged 27 commits into from
Oct 20, 2021
Merged

Implement ranges::starts_with and ranges::ends_with #1997

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
27 commits
Select commit Hold shift + click to select a range
ed0af15
Implement ranges::starts_with and ranges::ends_with
miscco Jun 10, 2021
a4d81a2
Address review feedback
miscco Jun 11, 2021
08ac0ed
Accept any integral for _Equal_count
miscco Jun 11, 2021
c884756
Merge branch 'main' into P1659-ranges-starts_with
miscco Jun 12, 2021
75b4380
Add feature test macro
miscco Jun 12, 2021
39bd70d
Apply optimizations for infinite ranges
miscco Jun 22, 2021
51c859d
Merge branch 'main' into P1659-ranges-starts_with
StephanTLavavej Jun 30, 2021
3817faf
Fix failing tests
miscco Jul 1, 2021
e2ac556
Rework so that we pass unwrapped iterators around
miscco Jul 1, 2021
e0a9b89
Merge branch 'main' into P1659-ranges-starts_with
miscco Aug 4, 2021
063f583
Fix formatting
miscco Aug 4, 2021
81e49e5
Merge branch 'main' into P1659-ranges-starts_with
miscco Aug 6, 2021
1e26004
Merge branch 'main' into P1659-ranges-starts_with
miscco Aug 24, 2021
b929362
Merge branch 'main' into P1659-ranges-starts_with
StephanTLavavej Aug 31, 2021
37a18ba
Sort `tests/std/test.lst`.
StephanTLavavej Aug 31, 2021
69141f7
Merge branch 'main' into P1659-ranges-starts_with
miscco Sep 16, 2021
5849ddb
Address review comments
miscco Sep 16, 2021
624f273
Fix incorret feature test macro placement
miscco Sep 17, 2021
5f22bb6
Fix infinite ranges and prepare LWG issue
miscco Sep 17, 2021
9164868
Begone infinite ranges
miscco Oct 14, 2021
2bf6d93
Merge branch 'main' into P1659-ranges-starts_with
miscco Oct 14, 2021
8c9bf6a
We cannot handle infinite input ranges at all in starts_with, as `_Eq…
miscco Oct 14, 2021
507f85b
Reenable infinite sizes optimization
miscco Oct 15, 2021
58da2b3
optimize ends_with; fix borked tests
CaseyCarter Oct 18, 2021
cd7733d
Factor out large middle section of _Ends_with_impl
CaseyCarter Oct 18, 2021
2df4fa1
Review comments
CaseyCarter Oct 19, 2021
42c9471
[[nonodiscard]]
CaseyCarter Oct 19, 2021
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
Address review feedback
  • Loading branch information
@miscco
miscco committed Jun 11, 2021
commit a4d81a23a67a3c416c3c73b11f374a99c30abc97
52 changes: 25 additions & 27 deletions stl/inc/algorithm
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -714,27 +714,29 @@ _NODISCARD pair<_FwdIt1, _FwdIt2> mismatch(
#ifdef __cpp_lib_concepts
namespace ranges {
// VARIABLE ranges::equal
class _Equal_fn : private _Not_quite_object {
private:
template <class _It1, class _It2, class _Size, class _Pr, class _Pj1, class _Pj2>
_NODISCARD static constexpr bool _Equal_count(
_It1 _First1, _It2 _First2, _Size _Count, _Pr _Pred, _Pj1 _Proj1, _Pj2 _Proj2) {
if constexpr (_Equal_memcmp_is_safe<_It1, _It2,
_Pr> && same_as<_Pj1, identity> && same_as<_Pj2, identity>) {
if (!_STD is_constant_evaluated()) {
return _Memcmp_count(_First1, _First2, static_cast<size_t>(_Count)) == 0;
}
// clang-format off
template <input_iterator _It1, input_iterator _It2, class _Pr, class _Pj1, class _Pj2>
requires indirectly_comparable<_It1, _It2, _Pr, _Pj1, _Pj2>
_NODISCARD static constexpr bool _Equal_count(
Comment thread
CaseyCarter marked this conversation as resolved.
Resolved
_It1 _First1, _It2 _First2, iter_difference_t<_It1> _Count, _Pr _Pred, _Pj1 _Proj1, _Pj2 _Proj2) {
// clang-format on
Comment thread
miscco marked this conversation as resolved.
Resolved
if constexpr (_Equal_memcmp_is_safe<_It1, _It2, _Pr> && same_as<_Pj1, identity> && same_as<_Pj2, identity>) {
if (!_STD is_constant_evaluated()) {
return _Memcmp_count(_First1, _First2, static_cast<size_t>(_Count)) == 0;
}
}

for (; _Count != 0; ++_First1, (void) ++_First2, --_Count) {
if (!_STD invoke(_Pred, _STD invoke(_Proj1, *_First1), _STD invoke(_Proj2, *_First2))) {
return false;
}
for (; _Count != 0; ++_First1, (void) ++_First2, --_Count) {
if (!_STD invoke(_Pred, _STD invoke(_Proj1, *_First1), _STD invoke(_Proj2, *_First2))) {
return false;
}

return true;
}

return true;
}

class _Equal_fn : private _Not_quite_object {
private:
template <class _It1, class _Se1, class _It2, class _Se2, class _Pr, class _Pj1, class _Pj2>
_NODISCARD static constexpr bool _Equal_4(
_It1 _First1, _Se1 _Last1, _It2 _First2, _Se2 _Last2, _Pr _Pred, _Pj1 _Proj1, _Pj2 _Proj2) {
Expand Down Expand Up @@ -2446,11 +2448,10 @@ namespace ranges {
return false;
}

const auto _Result = _Mismatch_n(_STD move(_First1), _STD move(_First2),
return _RANGES _Equal_count(_STD move(_First1), _STD move(_First2),
static_cast<iter_difference_t<_It1>>(_Count2), _Pass_fn(_Pred), _Pass_fn(_Proj1), _Pass_fn(_Proj2));
return _Result.in2 == _Last2;
} else {
const auto _Result = _Mismatch_4(_STD move(_First1), _STD move(_Last1), _STD move(_First2),
const auto _Result = _RANGES _Mismatch_4(_STD move(_First1), _STD move(_Last1), _STD move(_First2),
_STD move(_Last2), _Pass_fn(_Pred), _Pass_fn(_Proj1), _Pass_fn(_Proj2));
return _Result.in2 == _Last2;
}
Expand All @@ -2470,13 +2471,12 @@ namespace ranges {
return false;
}

const auto _Result = _Mismatch_n(_RANGES begin(_Range1), _RANGES begin(_Range2),
return _RANGES _Equal_count(_RANGES begin(_Range1), _RANGES begin(_Range2),
static_cast<range_difference_t<_Rng1>>(_Count2), _Pass_fn(_Pred), _Pass_fn(_Proj1),
_Pass_fn(_Proj2));
return _Result.in2 == _RANGES end(_Range2);
} else {
const auto _Result = _Mismatch_4(_RANGES begin(_Range1), _RANGES end(_Range1), _RANGES begin(_Range2),
_RANGES end(_Range2), _Pass_fn(_Pred), _Pass_fn(_Proj1), _Pass_fn(_Proj2));
const auto _Result = _RANGES _Mismatch_4(_RANGES begin(_Range1), _RANGES end(_Range1),
_RANGES begin(_Range2), _RANGES end(_Range2), _Pass_fn(_Pred), _Pass_fn(_Proj1), _Pass_fn(_Proj2));
return _Result.in2 == _RANGES end(_Range2);
}
}
Expand Down Expand Up @@ -2520,9 +2520,8 @@ namespace ranges {
}

_RANGES advance(_First1, (_Count1 - _Count2));
const auto _Result = _Mismatch_n(_STD move(_First1), _STD move(_First2),
return _RANGES _Equal_count(_STD move(_First1), _STD move(_First2),
static_cast<iter_difference_t<_It1>>(_Count2), _Pass_fn(_Pred), _Pass_fn(_Proj1), _Pass_fn(_Proj2));
return _Result.in2 == _Last2;
}

// clang-format off
Expand All @@ -2541,9 +2540,8 @@ namespace ranges {

auto _First1 = _RANGES begin(_Range1);
_RANGES advance(_First1, (_Count1 - _Count2));
const auto _Result = _Mismatch_n(_STD move(_First1), _RANGES begin(_Range2),
return _RANGES _Equal_count(_STD move(_First1), _RANGES begin(_Range2),
static_cast<range_difference_t<_Rng1>>(_Count2), _Pass_fn(_Pred), _Pass_fn(_Proj1), _Pass_fn(_Proj2));
return _Result.in2 == _RANGES end(_Range2);
}
};

Expand Down
34 changes: 21 additions & 13 deletions stl/inc/xutility
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -4933,9 +4933,12 @@ namespace ranges {
using mismatch_result = in_in_result<_In1, _In2>;

// VARIABLE ranges::mismatch
Comment thread
miscco marked this conversation as resolved.
Resolved
template <class _It1, class _It2, class _Pr, class _Pj1, class _Pj2>
// clang-format off
template <input_iterator _It1, input_iterator _It2, class _Pr, class _Pj1, class _Pj2>
requires indirectly_comparable<_It1, _It2, _Pr, _Pj1, _Pj2>
_NODISCARD constexpr mismatch_result<_It1, _It2> _Mismatch_n(
_It1 _First1, _It2 _First2, iter_difference_t<_It1> _Count, _Pr _Pred, _Pj1 _Proj1, _Pj2 _Proj2) {
// clang-format on
Comment thread
miscco marked this conversation as resolved.
Resolved
auto _UFirst1 = _Get_unwrapped(_STD move(_First1));
auto _UFirst2 = _Get_unwrapped(_STD move(_First2));

Expand All @@ -4950,9 +4953,13 @@ namespace ranges {
return {_STD move(_First1), _STD move(_First2)};
}

template <class _It1, class _Se1, class _It2, class _Se2, class _Pr, class _Pj1, class _Pj2>
// clang-format off
template <input_iterator _It1, sentinel_for<_It1> _Se1, input_iterator _It2, sentinel_for<_It2> _Se2, class _Pr,
class _Pj1, class _Pj2>
requires indirectly_comparable<_It1, _It2, _Pr, _Pj1, _Pj2>
_NODISCARD constexpr mismatch_result<_It1, _It2> _Mismatch_4(
_It1 _First1, _Se1 _Last1, _It2 _First2, _Se2 _Last2, _Pr _Pred, _Pj1 _Proj1, _Pj2 _Proj2) {
// clang-format on
auto _UFirst1 = _Get_unwrapped(_STD move(_First1));
const auto _ULast1 = _Get_unwrapped(_STD move(_Last1));
auto _UFirst2 = _Get_unwrapped(_STD move(_First2));
Expand All @@ -4979,45 +4986,46 @@ namespace ranges {
requires indirectly_comparable<_It1, _It2, _Pr, _Pj1, _Pj2>
_NODISCARD constexpr mismatch_result<_It1, _It2> operator()(_It1 _First1, _Se1 _Last1,
_It2 _First2, _Se2 _Last2, _Pr _Pred = {}, _Pj1 _Proj1 = {}, _Pj2 _Proj2 = {}) const {
// clang-format on
_Adl_verify_range(_First1, _Last1);
_Adl_verify_range(_First2, _Last2);

if constexpr (sized_sentinel_for<_Se1, _It1> && sized_sentinel_for<_Se2, _It2>) {
iter_difference_t<_It1> _Count1 = _Last1 - _First1;
iter_difference_t<_It1> _Count1 = _Last1 - _First1;
const iter_difference_t<_It2> _Count2 = _Last2 - _First2;
if (_Count1 > _Count2) {
_Count1 = static_cast<decltype(_Count1)>(_Count2);
}

return _Mismatch_n(_STD move(_First1), _STD move(_First2), _Count1,
_Pass_fn(_Pred), _Pass_fn(_Proj1), _Pass_fn(_Proj2));
return _RANGES _Mismatch_n(_STD move(_First1), _STD move(_First2), _Count1, _Pass_fn(_Pred),
_Pass_fn(_Proj1), _Pass_fn(_Proj2));
} else {
return _Mismatch_4(_STD move(_First1), _STD move(_Last1), _STD move(_First2), _STD move(_Last2),
return _RANGES _Mismatch_4(_STD move(_First1), _STD move(_Last1), _STD move(_First2), _STD move(_Last2),
_Pass_fn(_Pred), _Pass_fn(_Proj1), _Pass_fn(_Proj2));
}
}

// clang-format off
template <input_range _Rng1, input_range _Rng2, class _Pr = ranges::equal_to, class _Pj1 = identity,
class _Pj2 = identity>
requires indirectly_comparable<iterator_t<_Rng1>, iterator_t<_Rng2>, _Pr, _Pj1, _Pj2>
_NODISCARD constexpr mismatch_result<borrowed_iterator_t<_Rng1>, borrowed_iterator_t<_Rng2>> operator()(
_Rng1&& _Range1, _Rng2&& _Range2, _Pr _Pred = {}, _Pj1 _Proj1 = {}, _Pj2 _Proj2 = {}) const {
// clang-format on
if constexpr (sized_range<_Rng1> && sized_range<_Rng2>) {
range_difference_t<_Rng1> _Count1 = _RANGES distance(_Range1);
range_difference_t<_Rng1> _Count1 = _RANGES distance(_Range1);
const range_difference_t<_Rng2> _Count2 = _RANGES distance(_Range2);
if (_Count1 > _Count2) {
_Count1 = static_cast<range_difference_t<_Rng1>>(_Count2);
}

return _Mismatch_n(_RANGES begin(_Range1), _RANGES begin(_Range2), _Count1,
_Pass_fn(_Pred), _Pass_fn(_Proj1), _Pass_fn(_Proj2));
return _RANGES _Mismatch_n(_RANGES begin(_Range1), _RANGES begin(_Range2), _Count1, _Pass_fn(_Pred),
_Pass_fn(_Proj1), _Pass_fn(_Proj2));
} else {
return _Mismatch_4(_RANGES begin(_Range1), _RANGES end(_Range1),
_RANGES begin(_Range2), _RANGES end(_Range2),
_Pass_fn(_Pred), _Pass_fn(_Proj1), _Pass_fn(_Proj2));
return _RANGES _Mismatch_4(_RANGES begin(_Range1), _RANGES end(_Range1), _RANGES begin(_Range2),
_RANGES end(_Range2), _Pass_fn(_Pred), _Pass_fn(_Proj1), _Pass_fn(_Proj2));
}
}
// clang-format on
};

inline constexpr _Mismatch_fn mismatch{_Not_quite_object::_Construct_tag{}};
Expand Down