[PATCH] Define std::sample for C++17
Jonathan Wakely
jwakely@redhat.com
Wed Oct 12 15:26:00 GMT 2016
I forgot that std::sample() was added to C++17, so it wasn't in our
status table. It is now.
I changed the testcase to use our iterator wrappers instead of
containers, which found some bugs. I intend to go through other tests
where I've used std::forward_list to get forward iterators, or stream
iterators for input/output iterators, and make them use the wrappers
too.
* doc/xml/manual/status_cxx2017.xml: Add std::sample status.
* doc/html/*: Regenerate.
* include/experimental/algorithm (__sample): Move to bits/stl_algo.h
and into namespace std.
* include/bits/stl_algo.h (__sample): Define here. Fix invalid use
of input iterator. Defend against overloaded comma operator.
(sample): Define for C++17.
* testsuite/25_algorithms/sample/1.cc: New test.
Tested powerpc64le-linux, committed to trunk.
-------------- next part --------------
commit d727fe4bd81e5c79d4f37df66fad53503e01ccec
Author: Jonathan Wakely <jwakely@redhat.com>
Date: Wed Oct 12 15:02:59 2016 +0100
Define std::sample for C++17
* doc/xml/manual/status_cxx2017.xml: Add std::sample status.
* doc/html/*: Regenerate.
* include/experimental/algorithm (__sample): Move to bits/stl_algo.h
and into namespace std.
* include/bits/stl_algo.h (__sample): Define here. Fix invalid use
of input iterator. Defend against overloaded comma operator.
(sample): Define for C++17.
* testsuite/25_algorithms/sample/1.cc: New test.
diff --git a/libstdc++-v3/doc/xml/manual/status_cxx2017.xml b/libstdc++-v3/doc/xml/manual/status_cxx2017.xml
index c6b8440..ae8dfa9 100644
--- a/libstdc++-v3/doc/xml/manual/status_cxx2017.xml
+++ b/libstdc++-v3/doc/xml/manual/status_cxx2017.xml
@@ -182,6 +182,17 @@ Feature-testing recommendations for C++</link>.
</row>
<row>
+ <entry> Library Fundamentals V1 TS Components: Sampling </entry>
+ <entry>
+ <link xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0220r1.html">
+ P0220R1
+ </link>
+ </entry>
+ <entry align="center"> 7 </entry>
+ <entry> <code>__cpp_lib_sample >= 201603</code> </entry>
+ </row>
+
+ <row>
<entry> Constant View: A proposal for a <code>std::as_const</code> helper function template </entry>
<entry>
<link xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="">
diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index ea0b56c..0538a79 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -5615,6 +5615,86 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
__gnu_cxx::__ops::__iter_comp_iter(__comp));
}
+#if __cplusplus >= 201402L
+ /// Reservoir sampling algorithm.
+ template<typename _InputIterator, typename _RandomAccessIterator,
+ typename _Size, typename _UniformRandomBitGenerator>
+ _RandomAccessIterator
+ __sample(_InputIterator __first, _InputIterator __last, input_iterator_tag,
+ _RandomAccessIterator __out, random_access_iterator_tag,
+ _Size __n, _UniformRandomBitGenerator&& __g)
+ {
+ using __distrib_type = uniform_int_distribution<_Size>;
+ using __param_type = typename __distrib_type::param_type;
+ __distrib_type __d{};
+ _Size __sample_sz = 0;
+ while (__first != __last && __sample_sz != __n)
+ {
+ __out[__sample_sz++] = *__first;
+ ++__first;
+ }
+ for (auto __pop_sz = __sample_sz; __first != __last;
+ ++__first, (void) ++__pop_sz)
+ {
+ const auto __k = __d(__g, __param_type{0, __pop_sz});
+ if (__k < __n)
+ __out[__k] = *__first;
+ }
+ return __out + __sample_sz;
+ }
+
+ /// Selection sampling algorithm.
+ template<typename _ForwardIterator, typename _OutputIterator, typename _Cat,
+ typename _Size, typename _UniformRandomBitGenerator>
+ _OutputIterator
+ __sample(_ForwardIterator __first, _ForwardIterator __last,
+ forward_iterator_tag,
+ _OutputIterator __out, _Cat,
+ _Size __n, _UniformRandomBitGenerator&& __g)
+ {
+ using __distrib_type = uniform_int_distribution<_Size>;
+ using __param_type = typename __distrib_type::param_type;
+ __distrib_type __d{};
+ _Size __unsampled_sz = std::distance(__first, __last);
+ for (__n = std::min(__n, __unsampled_sz); __n != 0; ++__first)
+ if (__d(__g, __param_type{0, --__unsampled_sz}) < __n)
+ {
+ *__out++ = *__first;
+ --__n;
+ }
+ return __out;
+ }
+
+#if __cplusplus > 201402L
+#define __cpp_lib_sample 201603
+ /// Take a random sample from a population.
+ template<typename _PopulationIterator, typename _SampleIterator,
+ typename _Distance, typename _UniformRandomBitGenerator>
+ _SampleIterator
+ sample(_PopulationIterator __first, _PopulationIterator __last,
+ _SampleIterator __out, _Distance __n,
+ _UniformRandomBitGenerator&& __g)
+ {
+ using __pop_cat = typename
+ std::iterator_traits<_PopulationIterator>::iterator_category;
+ using __samp_cat = typename
+ std::iterator_traits<_SampleIterator>::iterator_category;
+
+ static_assert(
+ __or_<is_convertible<__pop_cat, forward_iterator_tag>,
+ is_convertible<__samp_cat, random_access_iterator_tag>>::value,
+ "output range must use a RandomAccessIterator when input range"
+ " does not meet the ForwardIterator requirements");
+
+ static_assert(is_integral<_Distance>::value,
+ "sample size must be an integer type");
+
+ return std::__sample(__first, __last, __pop_cat{}, __out, __samp_cat{},
+ __n, std::forward<_UniformRandomBitGenerator>(__g));
+ }
+#endif // C++17
+#endif // C++14
+
_GLIBCXX_END_NAMESPACE_ALGO
} // namespace std
diff --git a/libstdc++-v3/include/experimental/algorithm b/libstdc++-v3/include/experimental/algorithm
index 0ba6311..eb18dde 100644
--- a/libstdc++-v3/include/experimental/algorithm
+++ b/libstdc++-v3/include/experimental/algorithm
@@ -36,7 +36,6 @@
#else
#include <algorithm>
-#include <random>
#include <experimental/bits/lfts_config.h>
namespace std _GLIBCXX_VISIBILITY(default)
@@ -55,52 +54,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
#define __cpp_lib_experimental_sample 201402
- /// Reservoir sampling algorithm.
- template<typename _InputIterator, typename _RandomAccessIterator,
- typename _Size, typename _UniformRandomNumberGenerator>
- _RandomAccessIterator
- __sample(_InputIterator __first, _InputIterator __last, input_iterator_tag,
- _RandomAccessIterator __out, random_access_iterator_tag,
- _Size __n, _UniformRandomNumberGenerator&& __g)
- {
- using __distrib_type = std::uniform_int_distribution<_Size>;
- using __param_type = typename __distrib_type::param_type;
- __distrib_type __d{};
- _Size __sample_sz = 0;
- while (__first != __last && __sample_sz != __n)
- __out[__sample_sz++] = *__first++;
- for (auto __pop_sz = __sample_sz; __first != __last;
- ++__first, ++__pop_sz)
- {
- const auto __k = __d(__g, __param_type{0, __pop_sz});
- if (__k < __n)
- __out[__k] = *__first;
- }
- return __out + __sample_sz;
- }
-
- /// Selection sampling algorithm.
- template<typename _ForwardIterator, typename _OutputIterator, typename _Cat,
- typename _Size, typename _UniformRandomNumberGenerator>
- _OutputIterator
- __sample(_ForwardIterator __first, _ForwardIterator __last,
- forward_iterator_tag,
- _OutputIterator __out, _Cat,
- _Size __n, _UniformRandomNumberGenerator&& __g)
- {
- using __distrib_type = std::uniform_int_distribution<_Size>;
- using __param_type = typename __distrib_type::param_type;
- __distrib_type __d{};
- _Size __unsampled_sz = std::distance(__first, __last);
- for (__n = std::min(__n, __unsampled_sz); __n != 0; ++__first)
- if (__d(__g, __param_type{0, --__unsampled_sz}) < __n)
- {
- *__out++ = *__first;
- --__n;
- }
- return __out;
- }
-
/// Take a random sample from a population.
template<typename _PopulationIterator, typename _SampleIterator,
typename _Distance, typename _UniformRandomNumberGenerator>
@@ -123,9 +76,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
static_assert(is_integral<_Distance>::value,
"sample size must be an integer type");
- return std::experimental::__sample(
- __first, __last, __pop_cat{}, __out, __samp_cat{},
- __n, std::forward<_UniformRandomNumberGenerator>(__g));
+ return std::__sample(__first, __last, __pop_cat{}, __out, __samp_cat{},
+ __n,
+ std::forward<_UniformRandomNumberGenerator>(__g));
}
_GLIBCXX_END_NAMESPACE_VERSION
diff --git a/libstdc++-v3/testsuite/25_algorithms/sample/1.cc b/libstdc++-v3/testsuite/25_algorithms/sample/1.cc
new file mode 100644
index 0000000..10376e2
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/sample/1.cc
@@ -0,0 +1,110 @@
+// Copyright (C) 2014-2016 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++17" }
+// { dg-do run { target c++1z } }
+
+#include <algorithm>
+#include <random>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+std::mt19937 rng;
+
+using std::sample;
+using __gnu_test::test_container;
+using __gnu_test::input_iterator_wrapper;
+using __gnu_test::output_iterator_wrapper;
+using __gnu_test::forward_iterator_wrapper;
+using __gnu_test::random_access_iterator_wrapper;
+
+void
+test01()
+{
+ const int in[] = { 1, 2 };
+ test_container<const int, random_access_iterator_wrapper> pop(in);
+ const int sample_size = 10;
+ int samp[sample_size] = { };
+
+ // population smaller than desired sample size
+ auto it = sample(pop.begin(), pop.end(), samp, sample_size, rng);
+ VERIFY( it == samp + std::distance(pop.begin(), pop.end()) );
+ const auto sum = std::accumulate(pop.begin(), pop.end(), 0);
+ VERIFY( std::accumulate(samp, samp + sample_size, 0) == sum );
+}
+
+void
+test02()
+{
+ const int in[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };
+ test_container<const int, random_access_iterator_wrapper> pop(in);
+ const int sample_size = 10;
+ int samp[sample_size] = { };
+
+ auto it = sample(pop.begin(), pop.end(), samp, sample_size, rng);
+ VERIFY( it == samp + sample_size );
+
+ // verify no duplicates
+ std::sort(samp, it);
+ auto it2 = std::unique(samp, it);
+ VERIFY( it2 == it );
+}
+
+void
+test03()
+{
+ const int in[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
+ test_container<const int, input_iterator_wrapper> pop(in);
+ const int sample_size = 5;
+ int samp[sample_size] = { };
+
+ // input iterator for population
+ auto it = sample(pop.begin(), pop.end(), samp, sample_size, rng);
+ VERIFY( it == samp + sample_size );
+
+ // verify no duplicates
+ std::sort(samp, it);
+ auto it2 = std::unique(samp, it);
+ VERIFY( it2 == it );
+}
+
+void
+test04()
+{
+ const int in[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+ test_container<const int, forward_iterator_wrapper> pop(in);
+ const int sample_size = 5;
+ int out[sample_size];
+ test_container<int, output_iterator_wrapper> samp(out);
+
+ // forward iterator for population and output iterator for result
+ auto res = sample(pop.begin(), pop.end(), samp.begin(), sample_size, rng);
+
+ // verify no duplicates
+ std::sort(std::begin(out), std::end(out));
+ auto it = std::unique(std::begin(out), std::end(out));
+ VERIFY( it == std::end(out) );
+}
+
+int
+main()
+{
+ test01();
+ test02();
+ test03();
+ test04();
+}
More information about the Gcc-patches
mailing list