[gcc(refs/users/ppalka/heads/libstdcxx-constrained-algos)] Add ranges::equal
Patrick Palka
ppalka@gcc.gnu.org
Fri Jan 17 21:44:00 GMT 2020
https://gcc.gnu.org/g:13cda575b9be6d91b4276d16b7db41c9fab8d30e
commit 13cda575b9be6d91b4276d16b7db41c9fab8d30e
Author: Patrick Palka <ppalka@gcc.gnu.org>
Date: Fri Jan 17 16:26:28 2020 -0500
Add ranges::equal
Not all specializations of std::equal are reimplemented yet.
Diff:
---
libstdc++-v3/include/bits/ranges_algo.h | 74 ++++++++++++++++++++
.../testsuite/25_algorithms/equal/constrained.cc | 79 ++++++++++++++++++++++
2 files changed, 153 insertions(+)
diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
index b41f7d7..1cfa399 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -617,6 +617,80 @@ namespace ranges
std::move(__proj1), std::move(__proj2));
}
+ template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
+ input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
+ class _Pred = ranges::equal_to,
+ class _Proj1 = identity, class _Proj2 = identity>
+ requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
+ constexpr bool
+ equal(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2,
+ _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
+ {
+ // TODO: implement more specializations to at least have parity with
+ // std::equal.
+ constexpr bool __sized_iters
+ = (std::sized_sentinel_for<_Sent1, _Iter1>
+ && std::sized_sentinel_for<_Sent2, _Iter2>);
+ if constexpr (__sized_iters)
+ {
+ auto __d1 = std::distance(__first1, __last1);
+ auto __d2 = std::distance(__first2, __last2);
+ if (__d1 != __d2)
+ return false;
+
+ using _ValueType1 = iterator_traits<_Iter1>::value_type;
+ using _ValueType2 = iterator_traits<_Iter2>::value_type;
+ constexpr bool __simple
+ = ((is_integral_v<_ValueType1> || is_pointer_v<_ValueType1>)
+ && is_same_v<_ValueType1, _ValueType2>
+ && is_pointer_v<_Iter1>
+ && is_pointer_v<_Iter2>
+ && is_same_v<_Pred, ranges::equal_to>
+ && is_same_v<_Proj1, identity>
+ && is_same_v<_Proj2, identity>);
+ if constexpr (__simple)
+ {
+ if (const size_t __len = (__last1 - __first1))
+ return !std::__memcmp(__first1, __first2, __len);
+ return true;
+ }
+ else
+ {
+ for (; __first1 != __last1; ++__first1, (void)++__first2)
+ if (!std::__invoke(__pred,
+ std::__invoke(__proj1, *__first1),
+ std::__invoke(__proj2, *__first2)))
+ return false;
+ return true;
+ }
+ }
+ else
+ {
+ for (; __first1 != __last1 && __first2 != __last2;
+ ++__first1, (void)++__first2)
+ if (!std::__invoke(__pred,
+ std::__invoke(__proj1, *__first1),
+ std::__invoke(__proj2, *__first2)))
+ return false;
+ return __first1 == __last1 && __first2 == __last2;
+ }
+ }
+
+ template<input_range _Range1, input_range _Range2,
+ class _Pred = ranges::equal_to,
+ class _Proj1 = identity, class _Proj2 = identity>
+ requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
+ _Pred, _Proj1, _Proj2>
+ constexpr bool
+ equal(_Range1&& __r1, _Range2&& __r2,
+ _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
+ {
+ return ranges::equal(ranges::begin(__r1), ranges::end(__r1),
+ ranges::begin(__r2), ranges::end(__r2),
+ std::move(__pred),
+ std::move(__proj1), std::move(__proj2));
+ }
+
} // namespace ranges
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std
diff --git a/libstdc++-v3/testsuite/25_algorithms/equal/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/equal/constrained.cc
new file mode 100644
index 0000000..cb8f34d
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/equal/constrained.cc
@@ -0,0 +1,79 @@
+// Copyright (C) 2020 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++2a" }
+// { dg-do run { target c++2a } }
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::test_range;
+using __gnu_test::input_iterator_wrapper;
+using __gnu_test::forward_iterator_wrapper;
+using __gnu_test::bidirectional_iterator_wrapper;
+
+namespace ranges = std::ranges;
+
+struct X { int i; };
+
+void
+test01()
+{
+ int x[] = { {2}, {2}, {6}, {8}, {10}, {11}, {11} };
+ int y[] = { {2}, {2}, {6}, {8}, {10}, {11}, {11} };
+ X z[] = { {2}, {6}, {8}, {10}, {2}, {2} };
+ int w[] = { {1}, {1}, {1}, {1}, {1} };
+
+ VERIFY( ranges::equal(w, w+4, w+1, w+5) );
+ VERIFY( ranges::equal(w, w+5, w, w+5, std::greater<int>(),
+ [] (int a) { return a+1; }) );
+
+ test_container<int, forward_iterator_wrapper> cx(x), cy(y);
+ test_container<X, forward_iterator_wrapper> cz(z);
+ VERIFY( ranges::equal(cx, cy) );
+ VERIFY( !ranges::equal(cx, cy, {}, [] (int a) { return a+1; }) );
+ VERIFY( !ranges::equal(cx, cz, {}, {}, &X::i) );
+
+ test_range<int, input_iterator_wrapper> rx(x), ry(y);
+ test_range<X, input_iterator_wrapper> rz(z);
+ VERIFY( ranges::equal(rx, ry) );
+ VERIFY( !ranges::equal(rx, ry, {}, {}, [] (int a) { return a+1; }) );
+ VERIFY( !ranges::equal(rx, rz, {}, {}, &X::i) );
+}
+
+void
+test02()
+{
+ static constexpr X x[] = { {2}, {2}, {6}, {8}, {10}, {11} };
+ static constexpr X y[] = { {2}, {6}, {8}, {10}, {11}, {2} };
+ static constexpr int z[] = { {2}, {6}, {8}, {10}, {2}, {2} };
+ static constexpr int w[] = { {2}, {6}, {8}, {10}, {2}, {2} };
+
+ static_assert(ranges::equal(z, w));
+ static_assert(!ranges::equal(z, z+5, w+1, w+6));
+ static_assert(!ranges::equal(z, z, {}, {}, [] (int a) { return a+1; }));
+ static_assert(!ranges::equal(x, y, {}, &X::i, &X::i));
+}
+
+int
+main()
+{
+ test01();
+ test02();
+}
More information about the Libstdc++-cvs
mailing list