从容器获取随机元素

本文介绍了从容器获取随机元素的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

从STL范围中获得[伪]随机元素的好方法是什么？

最好的办法是做 std :: random_shuffle（c.begin（），c.end（））然后从 c.begin（）接受我的随机元素。

想从一个 const 容器中的随机元素，或者我可能不想要一个完整的shuffle的成本。

有更好的方法吗？

解决方案

％这里不正确，因为 rand（）％n 会产生有偏差的结果：imagine RAND_MAX == 5 ，元素数量为4.然后你会得到的数字0和1比数字2或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

What is a good way to get a [pseudo-]random element from an STL range?

The best I can come up with is to do std::random_shuffle(c.begin(), c.end()) and then take my random element from c.begin().

However, I might want a random element from a const container, or I might not want the cost of a full shuffle.

Is there a better way?

解决方案

All the answers using % here are incorrect, since rand() % n will produce biased results: imagine RAND_MAX == 5 and the number of elements is 4. Then you'll get twice more the number 0 and 1 than the numbers 2 or 3.

A correct way to do this is:

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; }

Another problem is that std::rand is only assumed to have 15 random bits, but we'll forget about this here.