[gcc(refs/users/ppalka/heads/libstdcxx-constrained-algos)] Add ranges::partial_sort_copy
Patrick Palka
ppalka@gcc.gnu.org
Mon Jan 27 15:25:00 GMT 2020
https://gcc.gnu.org/g:c74eba2af54b821c9761dbb12f9261f649b13dab
commit c74eba2af54b821c9761dbb12f9261f649b13dab
Author: Patrick Palka <ppalka@redhat.com>
Date: Sat Jan 25 23:45:58 2020 -0500
Add ranges::partial_sort_copy
Diff:
---
libstdc++-v3/include/bits/ranges_algo.h | 70 ++++++++++++++++
.../25_algorithms/partial_sort_copy/constrained.cc | 97 ++++++++++++++++++++++
2 files changed, 167 insertions(+)
diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
index 53f4c72..89e8214 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -2235,6 +2235,76 @@ namespace ranges
std::move(__comp), std::move(__proj));
}
+ template<class _Iter, class _Out>
+ using partial_sort_copy_result = copy_result<_Iter, _Out>;
+
+ template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
+ random_access_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
+ typename _Comp = ranges::less,
+ typename _Proj1 = identity, typename _Proj2 = identity>
+ requires indirectly_copyable<_Iter1, _Iter2>
+ && sortable<_Iter2, _Comp, _Proj2>
+ && indirect_strict_weak_order<_Comp,
+ projected<_Iter1, _Proj1>,
+ projected<_Iter2, _Proj2>>
+ constexpr partial_sort_copy_result<_Iter1, _Iter2>
+ partial_sort_copy(_Iter1 __first, _Sent1 __last,
+ _Iter2 __result_first, _Sent2 __result_last,
+ _Comp __comp = {},
+ _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
+ {
+ if (__result_first == __result_last)
+ {
+ // TODO: Eliminating the variable __lasti triggers an ICE.
+ auto __lasti = ranges::next(std::move(__first),
+ std::move(__last));
+ return {std::move(__lasti), std::move(__result_first)};
+ }
+
+ auto __result_real_last = __result_first;
+ while (__first != __last && __result_real_last != __result_last)
+ {
+ *__result_real_last = *__first;
+ ++__result_real_last;
+ ++__first;
+ }
+
+ ranges::make_heap(__result_first, __result_real_last, __comp, __proj2);
+ for (; __first != __last; ++__first)
+ if (std::__invoke(__comp,
+ std::__invoke(__proj1, *__first),
+ std::__invoke(__proj2, *__result_first)))
+ {
+ ranges::pop_heap(__result_first, __result_real_last,
+ __comp, __proj2);
+ *(__result_real_last-1) = *__first;
+ ranges::push_heap(__result_first, __result_real_last,
+ __comp, __proj2);
+ }
+ ranges::sort_heap(__result_first, __result_real_last, __comp, __proj2);
+
+ return {std::move(__first), std::move(__result_real_last)};
+ }
+
+ template<input_range _Range1, random_access_range _Range2,
+ typename _Comp = ranges::less,
+ typename _Proj1 = identity, typename _Proj2 = identity>
+ requires indirectly_copyable<iterator_t<_Range1>, iterator_t<_Range2>>
+ && sortable<iterator_t<_Range2>, _Comp, _Proj2>
+ && indirect_strict_weak_order<_Comp,
+ projected<iterator_t<_Range1>, _Proj1>,
+ projected<iterator_t<_Range2>, _Proj2>>
+ constexpr partial_sort_copy_result<safe_iterator_t<_Range1>,
+ safe_iterator_t<_Range2>>
+ partial_sort_copy(_Range1&& __r, _Range2&& __out, _Comp __comp = {},
+ _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
+ {
+ return ranges::partial_sort_copy(ranges::begin(__r), ranges::end(__r),
+ ranges::begin(__out), ranges::end(__out),
+ std::move(__comp),
+ std::move(__proj1), std::move(__proj2));
+ }
+
template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
typename _Proj = identity,
indirect_strict_weak_order<projected<_Iter, _Proj>> Comp
diff --git a/libstdc++-v3/testsuite/25_algorithms/partial_sort_copy/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/partial_sort_copy/constrained.cc
new file mode 100644
index 0000000..6b586f8
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/partial_sort_copy/constrained.cc
@@ -0,0 +1,97 @@
+// 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 } }
+// { dg-require-cstdint "" }
+
+#include <algorithm>
+#include <random>
+#include <vector>
+#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::random_access_iterator_wrapper;
+
+namespace ranges = std::ranges;
+
+void
+test01()
+{
+ for (unsigned size = 0; size < 50; ++size)
+ {
+ std::vector<int> vref(size);
+ std::iota(vref.begin(), vref.end(), 0);
+ std::vector<int> v1(vref), v2(vref);
+
+ std::ranlux48_base g1(size), g2(size + 1);
+ ranges::shuffle(v1, g1);
+ ranges::shuffle(v2, g2);
+
+ for (unsigned middle = 0; middle < 10; ++middle)
+ {
+ test_container<int, forward_iterator_wrapper> c
+ = {&v1[0], &v1[0] + size};
+ test_range<int, input_iterator_wrapper> r
+ = {&v2[0], &v2[0] + size};
+
+ std::vector<int> o1(middle), o2(middle);
+ test_range<int, random_access_iterator_wrapper> w1
+ = {&o1[0], &o1[0]+middle};
+ test_range<int, random_access_iterator_wrapper> w2
+ = {&o2[0], &o2[0]+middle};
+
+ auto [in1, out1] = ranges::partial_sort_copy(c.begin(), c.end(),
+ w1.begin(), w1.end(),
+ {},
+ std::negate<>{},
+ std::negate<>{});
+ VERIFY( in1 == c.end() );
+ VERIFY( out1 == w1.begin() + std::min(size, middle) );
+
+ auto [in2,out2] = ranges::partial_sort_copy(r, w2, ranges::greater{});
+ VERIFY( in2 == ranges::end(r) );
+ VERIFY( out2 == w2.begin() + std::min(size, middle) );
+
+ VERIFY( ranges::equal(w1.begin(), out1, w2.begin(), out2) );
+ VERIFY( ranges::equal(w1.begin(), out1,
+ vref.rbegin(),
+ vref.rbegin()+(out1-w1.begin())) );
+ }
+ }
+}
+
+constexpr bool
+test02()
+{
+ int x[] = { 5,4,1,3,2 };
+ int w[3];
+ const int y[] = { 1,2,3 };
+ ranges::partial_sort_copy(x, x+5, w, w+3);
+ return ranges::equal(w, y);
+}
+
+int
+main()
+{
+ test01();
+ static_assert(test02());
+}
More information about the Libstdc++-cvs
mailing list