如何从 C++ 容器中获取随机元素？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/6942273/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to get a random element from a C++ container?
提问by paperjam
What is a good way to get a [pseudo-]random element from an STL range?
从 STL 范围中获取 [伪] 随机元素的好方法是什么？
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().
我能想到的最好的方法是先做std::random_shuffle(c.begin(), c.end())，然后从c.begin().
However, I might want a random element from a constcontainer, or I might not want the cost of a full shuffle.
但是，我可能想要const容器中的随机元素，或者我可能不想要完全洗牌的成本。
Is there a better way?
有没有更好的办法？
采纳答案by Christopher Smith
I posted this solution on a Google+ article where someone else referenced this. Posting it here, as this one is slightly better than others because it avoids bias by using std::uniform_int_distribution:
我在 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);
}
Sample use is:
示例用途是：
#include <vector>
using namespace std;
vector<int> foo;
/* .... */
int r = *select_randomly(foo.begin(), foo.end());
I ended up creating a gist with a better design following a similar approach.
回答by Alexandre C.
All the answers using %here are incorrect, since rand() % nwill produce biased results: imagine RAND_MAX == 5and the number of elements is 4. Then you'll get twice more the number 0 and 1 than the numbers 2 or 3.
%这里使用的所有答案都是不正确的，因为rand() % n会产生有偏差的结果：想象一下RAND_MAX == 5，元素的数量是 4。那么你得到的数字 0 和 1 是数字 2 或 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::randis only assumed to have 15 random bits, but we'll forget about this here.
另一个问题是std::rand假设只有 15 个随机位，但我们会在这里忘记这一点。
回答by cprogrammer
This works fine as long as RAND_MAXis much greater than the container size, otherwise it suffers from the bias problem cited by Alexandre:
只要RAND_MAX远大于容器大小，这就可以正常工作，否则它会受到 Alexandre 引用的偏差问题的影响：
vector<int>::iterator randIt = myvector.begin();
std::advance(randIt, std::rand() % myvector.size());
回答by Dave S
If you can't access the size, I think you would want to do the following. It returns the iterator to the random element.
如果您无法访问大小，我想您会想要执行以下操作。它将迭代器返回到随机元素。
#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;
}
回答by ypnos
Take the number of elements, c.size(), then get a random_numberbetween 0 and c.size(), and use:
取元素数c.size()，然后得到一个random_number介于 0 和 之间的值c.size()，然后使用：
auto it = c.begin();
std::advance(it, random_number)
Have a look at http://www.cplusplus.com/reference/clibrary/cstdlib/rand/
回答by Cedekasme
You can try to get a random number between 0 and the number of elements of the container. You could then access to the corresponding element of the container. For example, you can do this:
您可以尝试获取一个介于 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);
回答by zcc
You can use 0~1 random function to generate a float number for every element in the container as its score. And then select the one with highest score.
您可以使用 0~1 随机函数为容器中的每个元素生成一个浮点数作为其分数。然后选择得分最高的那个。
