|
// FUNCTION TEMPLATE _Trim_matching_suffixes
|
|
template <class _FwdIt1, class _FwdIt2, class _Pr>
|
|
void _Trim_matching_suffixes(_FwdIt1&, _FwdIt2&, _Pr, forward_iterator_tag, forward_iterator_tag) {
|
|
// trim matching suffixes, forward iterators (do nothing)
|
|
}
|
|
|
|
template <class _FwdIt1, class _FwdIt2, class _Pr>
|
|
void _Trim_matching_suffixes(
|
|
_FwdIt1& _Last1, _FwdIt2& _Last2, _Pr _Pred, bidirectional_iterator_tag, bidirectional_iterator_tag) {
|
|
// trim matching suffixes, bidirectional iterators
|
|
// assumptions: same lengths, non-empty, !_Pred(*_First1, *_First2)
|
|
do { // find last inequality
|
|
--_Last1;
|
|
--_Last2;
|
|
} while (_Pred(*_Last1, *_Last2));
|
|
++_Last1;
|
|
++_Last2;
|
|
}
|
|
|
|
// FUNCTION TEMPLATE _Check_match_counts
|
|
template <class _FwdIt1, class _FwdIt2, class _Pr>
|
|
bool _Check_match_counts(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2, _FwdIt2 _Last2, _Pr _Pred) {
|
|
// test if [_First1, _Last1) == permuted [_First2, _Last2), using _Pred, same lengths
|
|
_Trim_matching_suffixes(_Last1, _Last2, _Pred, _Iter_cat_t<_FwdIt1>(), _Iter_cat_t<_FwdIt2>());
|
|
for (_FwdIt1 _Next1 = _First1; _Next1 != _Last1; ++_Next1) {
|
|
if (_Next1 == _Find_pr(_First1, _Next1, *_Next1, _Pred)) { // new value, compare match counts
|
|
_Iter_diff_t<_FwdIt2> _Count2 = _Count_pr(_First2, _Last2, *_Next1, _Pred);
|
|
if (_Count2 == 0) {
|
|
return false; // second range lacks value, fail
|
|
}
|
|
|
|
_FwdIt1 _Skip1 = _Next_iter(_Next1);
|
|
_Iter_diff_t<_FwdIt1> _Count1 = _Count_pr(_Skip1, _Last1, *_Next1, _Pred) + 1;
|
|
if (_Count2 != _Count1) {
|
|
return false; // match counts differ, fail
|
|
}
|
|
}
|
|
}
|
|
|
|
return true;
|
|
}
|
|
|
|
// FUNCTION TEMPLATE is_permutation
|
|
template <class _FwdIt1, class _FwdIt2, class _Pr>
|
|
bool _Is_permutation_unchecked(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2, _Pr _Pred) {
|
|
// test if [_First1, _Last1) == permuted [_First2, ...), using _Pred
|
|
for (; _First1 != _Last1; ++_First1, (void) ++_First2) {
|
|
if (!_Pred(*_First1, *_First2)) {
|
|
// found first inequality, check match counts in suffix narrowing _Iter_diff_t<_FwdIt1> to
|
|
// _Iter_diff_t<_FwdIt2> is OK because if the 2nd range is shorter than the 1st, the user already
|
|
// triggered UB
|
|
auto _Last2 = _STD next(_First2, static_cast<_Iter_diff_t<_FwdIt2>>(_STD distance(_First1, _Last1)));
|
|
return _Check_match_counts(_First1, _Last1, _First2, _Last2, _Pred);
|
|
}
|
|
}
|
|
|
|
return true;
|
|
}
|
|
|
|
template <class _FwdIt1, class _FwdIt2, class _Pr>
|
|
_NODISCARD bool is_permutation(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2, _Pr _Pred) {
|
We currently follow a convention of introducing structs, classes, functions, etc. with "SHOUTY COMMENT BANNERS". A few examples:
STL/stl/inc/vector
Lines 410 to 412 in 580e61a
STL/stl/inc/algorithm
Lines 29 to 41 in 580e61a
STL/stl/inc/type_traits
Lines 536 to 541 in 580e61a
We've been thinking about changing this convention. It hasn't been applied rigorously, even for publicly-documented components (e.g. we have
// STRUCT TEMPLATE is_emptybut not// VARIABLE TEMPLATE is_empty_v). It might have helped file navigation many years ago, but IDE/editor support for Go To Definition and Find In Files (e.g. VSCode Ctrl+Shift+F) makes it easy to find where components are defined.In theory, the banners could be most useful when publicly-documented components are preceded by internal support machinery, but in practice, we haven't always used them like that. For example, some but not all of the helpers for
is_permutation()are introduced with// FUNCTION TEMPLATE is_permutation:STL/stl/inc/xutility
Lines 4395 to 4455 in 580e61a
As these comments seem to provide minimal value today, are commonly overlooked by new contributors, and consume valuable lines, we should decide whether to keep or discard them.