[gcc(refs/users/ppalka/heads/libstdcxx-constrained-algos)] Add ranges::unique
Patrick Palka
ppalka@gcc.gnu.org
Tue Jan 21 16:53:00 GMT 2020
https://gcc.gnu.org/g:06518e50f696ee2189c6e935b6f61adaa5192baa
commit 06518e50f696ee2189c6e935b6f61adaa5192baa
Author: Patrick Palka <ppalka@gcc.gnu.org>
Date: Tue Jan 21 11:25:47 2020 -0500
Add ranges::unique
Diff:
---
libstdc++-v3/include/bits/ranges_algo.h | 32 +++++
.../testsuite/25_algorithms/unique/constrained.cc | 143 +++++++++++++++++++++
2 files changed, 175 insertions(+)
diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
index 6290846..4c9c54b 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -1407,6 +1407,38 @@ namespace ranges
}
+ template<permutable _Iter, sentinel_for<_Iter> _Sent, class _Proj = identity,
+ indirect_equivalence_relation<
+ projected<_Iter, _Proj>> _Comp = ranges::equal_to>
+ constexpr subrange<_Iter>
+ unique(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {})
+ {
+ __first = ranges::adjacent_find(__first, __last, __comp, __proj);
+ if (__first == __last)
+ return {__last, __last};
+
+ auto __dest = __first;
+ ++__first;
+ while (++__first != __last)
+ if (!std::__invoke(__comp,
+ std::__invoke(__proj, *__dest),
+ std::__invoke(__proj, *__first)))
+ *++__dest = std::move(*__first);
+ return {++__dest, __last};
+ }
+
+ template<forward_range _Range, class _Proj = identity,
+ indirect_equivalence_relation<
+ projected<iterator_t<_Range>, _Proj>> _Comp = ranges::equal_to>
+ requires permutable<iterator_t<_Range>>
+ constexpr safe_subrange_t<_Range>
+ unique(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
+ {
+ return ranges::unique(ranges::begin(__r), ranges::end(__r),
+ std::move(__comp), std::move(__proj));
+ }
+
+
} // namespace ranges
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std
diff --git a/libstdc++-v3/testsuite/25_algorithms/unique/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/unique/constrained.cc
new file mode 100644
index 0000000..e863a60
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/unique/constrained.cc
@@ -0,0 +1,143 @@
+// 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 <list>
+#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;
+
+
+namespace ranges = std::ranges;
+
+struct X
+{
+ int i;
+};
+
+void
+test01()
+{
+ {
+ X x[6] = { {2}, {2}, {6}, {8}, {2}, {11} };
+ const int y[5] = { {2}, {6}, {8}, {2}, {11} };
+ test_container<X, forward_iterator_wrapper> cx(x);
+ auto res = ranges::unique(cx, {}, &X::i);
+ VERIFY( res.end() == cx.end() );
+ VERIFY( ranges::equal(cx.begin(), res.begin(), y, y+5, {}, &X::i) );
+ }
+
+ {
+ X x[6] = { {2}, {2}, {6}, {8}, {2}, {11} };
+ const int y[5] = { {2}, {6}, {8}, {2}, {11} };
+ test_range<X, forward_iterator_wrapper> rx(x);
+ auto res = ranges::unique(rx, {}, &X::i);
+ VERIFY( res.end() == rx.end() );
+ VERIFY( ranges::equal(rx.begin(), res.begin(), y, y+5, {}, &X::i) );
+ }
+}
+
+constexpr bool
+test02()
+{
+ int x[2] = {2, 2};
+ const int y[1] = {2};
+ auto res = ranges::unique(x);
+ return ranges::equal(x, res.begin(), y, y+1, ranges::equal_to{});
+}
+
+/* The following is adapted from 25_algorithms/unique/2.cc. */
+
+namespace two_dot_cc
+{
+ const int T1[] = {1, 4, 4, 6, 1, 2, 2, 3, 1, 6, 6, 6, 5, 7, 5, 4, 4};
+ const int T2[] = {1, 1, 1, 2, 2, 1, 1, 7, 6, 6, 7, 8, 8, 8, 8, 9, 9};
+ const int N = sizeof(T1) / sizeof(int);
+
+ const int A1[] = {1, 4, 6, 1, 2, 3, 1, 6, 5, 7, 5, 4};
+ const int A2[] = {1, 4, 4, 6, 6, 6, 6, 7};
+ const int A3[] = {1, 1, 1};
+
+ const int B1[] = {1, 2, 1, 7, 6, 7, 8, 9};
+ const int B2[] = {1, 1, 1, 2, 2, 7, 7, 8, 8, 8, 8, 9, 9};
+ const int B3[] = {9, 9, 8, 8, 8, 8, 7, 6, 6, 1, 1, 1, 1, 1};
+
+ void test01()
+ {
+ using namespace std;
+
+ list<int>::iterator pos;
+
+ list<int> coll(T1, T1 + N);
+ pos = ranges::unique(coll.begin(), coll.end()).begin();
+ VERIFY( equal(coll.begin(), pos, A1) );
+
+ list<int> coll2(T2, T2 + N);
+ pos = ranges::unique(coll2.begin(), coll2.end()).begin();
+ VERIFY( equal(coll2.begin(), pos, B1) );
+ }
+
+ void test02()
+ {
+ using namespace std;
+
+ list<int>::iterator pos;
+
+ list<int> coll(T1, T1 + N);
+ pos = ranges::unique(coll.begin(), coll.end(), greater<int>()).begin();
+ VERIFY( equal(coll.begin(), pos, A2) );
+
+ list<int> coll2(T2, T2 + N);
+ pos = ranges::unique(coll2.begin(), coll2.end(), greater<int>()).begin();
+ VERIFY( equal(coll2.begin(), pos, B2) );
+ }
+
+ void test03()
+ {
+ using namespace std;
+
+ list<int>::iterator pos;
+
+ list<int> coll(T1, T1 + N);
+ pos = ranges::unique(coll.begin(), coll.end(), less<int>()).begin();
+ VERIFY( equal(coll.begin(), pos, A3) );
+
+ list<int> coll2(T2, T2 + N);
+ reverse(coll2.begin(), coll2.end());
+ pos = ranges::unique(coll2.begin(), coll2.end(), less<int>()).begin();
+ VERIFY( equal(coll2.begin(), pos, B3) );
+ }
+} // namespace two_dot_cc
+
+int main()
+{
+ test01();
+ static_assert(test02());
+
+ two_dot_cc::test01();
+ two_dot_cc::test02();
+ two_dot_cc::test03();
+
+ return 0;
+}
More information about the Libstdc++-cvs
mailing list