Author: pcc Date: Fri Jan 26 13:23:27 2018 New Revision: 323563 URL: http://llvm.org/viewvc/llvm-project?rev=323563&view=rev Log: Fix the BinaryPredicate form of std::is_permutation to not rely on operator==
According to [1], forms 2 and 4 of std::is_permutation should use the passed in binary predicate to compare elements. operator== should only be used for forms 1 and 3 which do not take a binary predicate. This CL fixes forms 2 and 4 which relied on operator== for some comparisons. [1] http://en.cppreference.com/w/cpp/algorithm/is_permutation Patch by Thomas Anderson! Differential Revision: https://reviews.llvm.org/D42518 Modified: libcxx/trunk/include/algorithm libcxx/trunk/test/std/algorithms/alg.nonmodifying/alg.is_permutation/is_permutation_pred.pass.cpp Modified: libcxx/trunk/include/algorithm URL: http://llvm.org/viewvc/llvm-project/libcxx/trunk/include/algorithm?rev=323563&r1=323562&r2=323563&view=diff ============================================================================== --- libcxx/trunk/include/algorithm (original) +++ libcxx/trunk/include/algorithm Fri Jan 26 13:23:27 2018 @@ -1418,7 +1418,11 @@ is_permutation(_ForwardIterator1 __first for (_ForwardIterator1 __i = __first1; __i != __last1; ++__i) { // Have we already counted the number of *__i in [f1, l1)? - if (find(__first1, __i, *__i) == __i) { + _ForwardIterator1 __match = __first1; + for (; __match != __i; ++__match) + if (__pred(*__match, *__i)) + break; + if (__match == __i) { // Count number of *__i in [f2, l2) _D1 __c2 = 0; for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j) @@ -1479,7 +1483,11 @@ __is_permutation(_ForwardIterator1 __fir for (_ForwardIterator1 __i = __first1; __i != __last1; ++__i) { // Have we already counted the number of *__i in [f1, l1)? - if (find(__first1, __i, *__i) == __i) { + _ForwardIterator1 __match = __first1; + for (; __match != __i; ++__match) + if (__pred(*__match, *__i)) + break; + if (__match == __i) { // Count number of *__i in [f2, l2) _D1 __c2 = 0; for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j) Modified: libcxx/trunk/test/std/algorithms/alg.nonmodifying/alg.is_permutation/is_permutation_pred.pass.cpp URL: http://llvm.org/viewvc/llvm-project/libcxx/trunk/test/std/algorithms/alg.nonmodifying/alg.is_permutation/is_permutation_pred.pass.cpp?rev=323563&r1=323562&r2=323563&view=diff ============================================================================== --- libcxx/trunk/test/std/algorithms/alg.nonmodifying/alg.is_permutation/is_permutation_pred.pass.cpp (original) +++ libcxx/trunk/test/std/algorithms/alg.nonmodifying/alg.is_permutation/is_permutation_pred.pass.cpp Fri Jan 26 13:23:27 2018 @@ -738,6 +738,30 @@ int main() std::equal_to<const int>()) == false); #endif } + { + struct S { + S(int i) : i_(i) {} + bool operator==(const S& other) = delete; + int i_; + }; + struct eq { + bool operator()(const S& a, const S&b) { return a.i_ == b.i_; } + }; + const S a[] = {S(0), S(1)}; + const S b[] = {S(1), S(0)}; + const unsigned sa = sizeof(a)/sizeof(a[0]); + assert(std::is_permutation(forward_iterator<const S*>(a), + forward_iterator<const S*>(a + sa), + forward_iterator<const S*>(b), + eq())); +#if TEST_STD_VER >= 14 + assert(std::is_permutation(forward_iterator<const S*>(a), + forward_iterator<const S*>(a + sa), + forward_iterator<const S*>(b), + forward_iterator<const S*>(b + sa), + eq())); +#endif + } #if TEST_STD_VER > 17 static_assert(test_constexpr()); _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits