<xutility>: is_permutation() could detect reversed sequences

[StephanTLavavej]

is_permutation() is, famously, a quadratic-time algorithm. It currently has a significant amount of logic attempting to avoid this worst case. It begins by trimming matching prefixes, and then trims matching suffixes, before running the quadratic-time algorithm on the presumably jumbled cores of the sequences.

There's a fairly simple improvement that could further improve performance. Note that if two sequences are the reverses of each other, then trimming matching prefixes and suffixes won't help (very much). But comparing opposite ends would help. Although that would spend more comparisons, I believe that the cost is inherently very limited, and worth it to reduce the quadratic part.

I haven't analyzed this in detail, but I initially believe that the right strategy would be to trim matching prefixes (as required by the Standard; this handles equal sequences in linear time, and works for forward-only iterators). Then we should repeatedly attempt up to 4 comparisons:

• Back of A == Back of B (matching suffix)
• Back of A == Front of B
• Front of A == Back of B
• Front of A == Front of B (matching prefix)

If any of these comparisons are equal, we should consume and repeat. (Although we initially drain matching prefixes, after we consume anything at the front, the prefixes might match again.) If none are equal, then we run the quadratic part.

STL/stl/inc/xutility

Lines 4461 to 4595 in f9b1dcc

	// 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) {
	// test if [_First1, _Last1) == permuted [_First2, ...), using _Pred
	_Adl_verify_range(_First1, _Last1);
	const auto _UFirst1 = _Get_unwrapped(_First1);
	const auto _ULast1 = _Get_unwrapped(_Last1);
	const auto _UFirst2 = _Get_unwrapped_n(_First2, _Idl_distance<_FwdIt1>(_UFirst1, _ULast1));
	return _Is_permutation_unchecked(_UFirst1, _ULast1, _UFirst2, _Pass_fn(_Pred));
	}
	#if _ITERATOR_DEBUG_ARRAY_OVERLOADS
	template <class _FwdIt1, class _RightTy, size_t _RightSize, class _Pr, enable_if_t<!is_same_v<_RightTy*, _Pr>, int> = 0>
	_NODISCARD bool is_permutation(_FwdIt1 _First1, _FwdIt1 _Last1, _RightTy (&_First2)[_RightSize], _Pr _Pred) {
	// test if [_First1, _Last1) == permuted [_First2, ...), using _Pred
	return _STD is_permutation(_First1, _Last1, _Array_iterator<_RightTy, _RightSize>(_First2), _Pass_fn(_Pred));
	}
	#endif // _ITERATOR_DEBUG_ARRAY_OVERLOADS
	template <class _FwdIt1, class _FwdIt2>
	bool is_permutation(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2) {
	// test if [_First1, _Last1) == permuted [_First2, ...)
	return _STD is_permutation(_First1, _Last1, _First2, equal_to<>());
	}
	#if _ITERATOR_DEBUG_ARRAY_OVERLOADS
	template <class _FwdIt1, class _RightTy, size_t _RightSize>
	_NODISCARD bool is_permutation(_FwdIt1 _First1, _FwdIt1 _Last1, _RightTy (&_First2)[_RightSize]) {
	// test if [_First1, _Last1) == permuted [_First2, ...)
	return _STD is_permutation(_First1, _Last1, _First2, equal_to<>());
	}
	#endif // _ITERATOR_DEBUG_ARRAY_OVERLOADS
	template <class _FwdIt1, class _FwdIt2, class _Pr>
	bool _Is_permutation_unchecked(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2, _FwdIt2 _Last2, _Pr _Pred,
	forward_iterator_tag, forward_iterator_tag) {
	// test if [_First1, _Last1) == permuted [_First2, _Last2), using _Pred, arbitrary iterators
	for (; _First1 != _Last1 && _First2 != _Last2; ++_First1, (void) ++_First2) {
	if (!_Pred(*_First1, *_First2)) { // found first inequality, check match counts in suffix
	if (_STD distance(_First1, _Last1) == _STD distance(_First2, _Last2)) {
	return _Check_match_counts(_First1, _Last1, _First2, _Last2, _Pred);
	} else {
	return false; // lengths differ, fail
	}
	}
	}
	return _First1 == _Last1 && _First2 == _Last2;
	}
	template <class _FwdIt1, class _FwdIt2, class _Pr>
	bool _Is_permutation_unchecked(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2, _FwdIt2 _Last2, _Pr _Pred,
	random_access_iterator_tag, random_access_iterator_tag) {
	// test if [_First1, _Last1) == permuted [_First2, _Last2), using _Pred, random-access iterators
	if (_Last1 - _First1 != _Last2 - _First2) {
	return false;
	}
	return _Is_permutation_unchecked(_First1, _Last1, _First2, _Pred);
	}
	template <class _FwdIt1, class _FwdIt2, class _Pr>
	_NODISCARD bool is_permutation(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2, _FwdIt2 _Last2, _Pr _Pred) {
	// test if [_First1, _Last1) == permuted [_First2, _Last2), using _Pred
	_Adl_verify_range(_First1, _Last1);
	_Adl_verify_range(_First2, _Last2);
	return _Is_permutation_unchecked(_Get_unwrapped(_First1), _Get_unwrapped(_Last1), _Get_unwrapped(_First2),
	_Get_unwrapped(_Last2), _Pass_fn(_Pred), _Iter_cat_t<_FwdIt1>(), _Iter_cat_t<_FwdIt2>());
	}
	// FUNCTION TEMPLATE is_permutation WITH TWO RANGES
	template <class _FwdIt1, class _FwdIt2>
	_NODISCARD bool is_permutation(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2, _FwdIt2 _Last2) {
	// test if [_First1, _Last1) == permuted [_First2, _Last2)
	return _STD is_permutation(_First1, _Last1, _First2, _Last2, equal_to<>());
	}