How to get a random element from a C++ container?
algorithm, c++, stl
Solution
C++17 `std::sample`
This is a convenient method to get several random elements without repetition.
main.cpp
#include <algorithm>
#include <iostream>
#include <random>
#include <vector>
int main() {
const std::vector<int> in{1, 2, 3, 5, 7};
std::vector<int> out;
size_t nelems = 3;
std::sample(
in.begin(),
in.end(),
std::back_inserter(out),
nelems,
std::mt19937{std::random_device{}()}
);
for (auto i : out)
std::cout << i << std::endl;
}
Compile and run:
g++-7 -o main -std=c++17 -Wall -Wextra -pedantic main.cpp
./main
Output: 3 random numbers are picked from `1, 2, 3, 5, 7` without repetition.
For efficiency, only `O(n)` is guaranteed since `ForwardIterator` is the used API, but I think stdlib implementations will specialize to `O(1)` where possible (e.g. `vector`).
Tested in GCC 7.2, Ubuntu 17.10. How to obtain GCC 7 in 16.04.
Problem
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?