从容器中获取随机元素
从STL范围获得[伪]随机元素的好方法是什么？
我可以想出最好的做法是做std::random_shuffle(c.begin(), c.end()) ，然后从c.begin()取出我的随机元素。
不过，我可能需要一个来自const容器的随机元素，或者我可能不想要一个完整的shuffle的成本。
有没有更好的办法？
所有在这里使用%的答案是不正确的，因为rand() % n会产生有偏见的结果：想象RAND_MAX == 5 ，元素的数量是4.然后，你会比数字2或2多两倍数字0和1 3。
正确的做法是：
template <typename I> I random_element(I begin, I end) { const unsigned long n = std::distance(begin, end); const unsigned long divisor = (RAND_MAX + 1) / n; unsigned long k; do { k = std::rand() / divisor; } while (k >= n); std::advance(begin, k); return begin; }
另一个问题是， std::rand只被假定为有15个随机位，但我们会在这里忘记这个。
我将这个解决scheme发布在Google+文章上，其他人也参考了这篇文章。 在这里发布，因为这个比其他的稍好，因为它通过使用std :: uniform_int_distribution避免偏见：
#include <random> #include <iterator> template<typename Iter, typename RandomGenerator> Iter select_randomly(Iter start, Iter end, RandomGenerator& g) { std::uniform_int_distribution<> dis(0, std::distance(start, end) - 1); std::advance(start, dis(g)); return start; } template<typename Iter> Iter select_randomly(Iter start, Iter end) { static std::random_device rd; static std::mt19937 gen(rd()); return select_randomly(start, end, gen); }
示例使用是：
#include <vector> using namespace std; vector<int> foo; /* .... */ int r = *select_randomly(foo.begin(), foo.end());
我用类似的方法最终创造了一个更好的devise 。
vector<int>::iterator randIt = myvector.begin(); std::advance(randIt, std::rand() % myvector.size());
如果你不能访问的大小，我想你会想要做到以下几点。 它将迭代器返回给随机元素。
#include <algorithm> #include <iterator> template <class InputIterator> InputIterator random_n(InputIterator first, InputIterator last) { typename std::iterator_traits<InputIterator>::difference_type distance = std::distance(first, last); InputIterator result = first; if (distance > 1) { // Uses std::rand() naively. Should replace with more uniform solution. std::advance( result, std::rand() % distance ); } return result; } // Added in case you want to specify the RNG. RNG uses same // definition as std::random_shuffle template <class InputIterator, class RandomGenerator> InputIterator random_n(InputIterator first, InputIterator last, RandomGenerator& rand) { typename std::iterator_traits<InputIterator>::difference_type distance = std::distance(first, last); InputIterator result = first; if (distance > 1) { std::advance( result, rand(distance) ); } return result; }
C ++ 17 std::sample
这将是一个方便的方法：
#include <algorithm> #include <iostream> #include <random> #include <vector> int main() { std::vector<int> in{1, 2, 3, 5, 7}, out; std::sample(in.begin(), in.end(), std::back_inserter(out), 3, std::mt19937{std::random_device{}()}); for (auto i : out) std::cout << i << std::endl; }
为了效率，由于ForwardIterator是使用的API，所以只保证O(n) ，但是我认为stdlib的实现将在可能的情况下专门用于O(1) （例如vector ）。
取元素数c.size() ，然后得到0到c.size()之间的c.size() ，并使用：
auto it = c.begin(); std::advance(it, random_number)
您可以尝试获取0到容器元素数之间的随机数。 然后您可以访问容器的相应元素。 例如，你可以这样做：
#include <cstdlib> #include <ctime> // ... std::srand(std::time(0)); // must be called once at the start of the program int r = std::rand() % c.size() + 1; container_type::iterator it = c.begin(); std::advance(it, r);
您可以使用0〜1的随机函数为容器中的每个元素生成一个浮点数作为其分数。 然后select分数最高的那个。
