Practice Now
C++
random element
container
programming
coding tutorial

How to get a random element from a C++ container?

System Design practice on Codemia

Work through 120+ system design problems with detailed solutions, from rate limiters to multi-region storage.

Practice system design
Docker & ContainersC & C++

Introduction

Getting a random element from a C++ container depends on whether the container supports random access. For std::vector and std::array, generate a random index and access directly. For std::set, std::list, and other non-random-access containers, use std::advance with an iterator or std::sample. C++17's std::sample provides a clean, generic approach that works with any container.

Random Element from std::vector (Direct Index)

cpp
1#include <iostream>
2#include <vector>
3#include <random>
4
5int main() {
6    std::vector<std::string> items = {"apple", "banana", "cherry", "date", "elderberry"};
7
8    // Modern C++ random number generation
9    std::random_device rd;
10    std::mt19937 gen(rd());
11    std::uniform_int_distribution<size_t> dist(0, items.size() - 1);
12
13    std::string random_item = items[dist(gen)];
14    std::cout << random_item << std::endl;  // e.g., "cherry"
15
16    return 0;
17}

This is O(1) — std::vector supports constant-time random access by index.

Why Not rand() % size?

cpp
1// BAD — biased and non-uniform
2#include <cstdlib>
3#include <ctime>
4
5srand(time(nullptr));
6int idx = rand() % items.size();  // Modulo bias, low-quality randomness
7
8// GOOD — uniform distribution, high-quality randomness
9std::random_device rd;
10std::mt19937 gen(rd());
11std::uniform_int_distribution<size_t> dist(0, items.size() - 1);
12size_t idx = dist(gen);

rand() % n produces biased results when RAND_MAX + 1 is not evenly divisible by n. std::uniform_int_distribution guarantees uniform distribution.

Random Element from std::array

cpp
1#include <array>
2#include <random>
3#include <iostream>
4
5int main() {
6    std::array<int, 5> arr = {10, 20, 30, 40, 50};
7
8    std::random_device rd;
9    std::mt19937 gen(rd());
10    std::uniform_int_distribution<size_t> dist(0, arr.size() - 1);
11
12    int value = arr[dist(gen)];
13    std::cout << value << std::endl;  // e.g., 30
14
15    return 0;
16}

Same approach as std::vector — both support O(1) random access.

Random Element from std::set or std::list (No Random Access)

Containers like std::set, std::multiset, std::list, and std::map use bidirectional iterators. You cannot index into them directly, so you advance an iterator to a random position.

cpp
1#include <set>
2#include <random>
3#include <iostream>
4#include <iterator>
5
6int main() {
7    std::set<int> s = {10, 20, 30, 40, 50, 60, 70};
8
9    std::random_device rd;
10    std::mt19937 gen(rd());
11    std::uniform_int_distribution<size_t> dist(0, s.size() - 1);
12
13    auto it = s.begin();
14    std::advance(it, dist(gen));  // O(n) — must walk the tree
15
16    std::cout << *it << std::endl;  // e.g., 40
17
18    return 0;
19}

std::advance is O(n) for bidirectional iterators because it steps through nodes one by one.

Generic Function for Any Container

cpp
1#include <random>
2#include <iterator>
3
4template <typename Container, typename Gen>
5auto random_element(const Container& c, Gen& gen) ->
6    typename Container::const_reference
7{
8    auto it = c.begin();
9    std::uniform_int_distribution<size_t> dist(0, c.size() - 1);
10    std::advance(it, dist(gen));
11    return *it;
12}
13
14// Usage
15std::vector<int> vec = {1, 2, 3, 4, 5};
16std::set<std::string> names = {"Alice", "Bob", "Charlie"};
17std::list<double> values = {1.1, 2.2, 3.3};
18
19std::mt19937 gen(std::random_device{}());
20
21std::cout << random_element(vec, gen) << std::endl;
22std::cout << random_element(names, gen) << std::endl;
23std::cout << random_element(values, gen) << std::endl;

This works for any container with begin(), size(), and bidirectional iterators. It is O(1) for random-access containers and O(n) for others.

std::sample (C++17) — Select Multiple Random Elements

cpp
1#include <algorithm>
2#include <random>
3#include <vector>
4#include <iostream>
5
6int main() {
7    std::vector<int> population = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
8    std::vector<int> sample;
9
10    std::random_device rd;
11    std::mt19937 gen(rd());
12
13    // Select 3 random elements (without replacement)
14    std::sample(population.begin(), population.end(),
15                std::back_inserter(sample), 3, gen);
16
17    for (int x : sample)
18        std::cout << x << " ";  // e.g., "2 5 8"
19
20    return 0;
21}

std::sample selects k elements without replacement using reservoir sampling. It works with forward iterators, so it handles std::set, std::list, etc.

Single Random Element with std::sample

cpp
1std::vector<int> result;
2std::sample(container.begin(), container.end(),
3            std::back_inserter(result), 1, gen);
4int random_item = result[0];

Random Element from std::map

cpp
1#include <map>
2#include <random>
3#include <iostream>
4
5int main() {
6    std::map<std::string, int> scores = {
7        {"Alice", 95}, {"Bob", 87}, {"Charlie", 92}, {"Diana", 88}
8    };
9
10    std::random_device rd;
11    std::mt19937 gen(rd());
12    std::uniform_int_distribution<size_t> dist(0, scores.size() - 1);
13
14    auto it = scores.begin();
15    std::advance(it, dist(gen));
16
17    std::cout << it->first << ": " << it->second << std::endl;
18    // e.g., "Charlie: 92"
19
20    return 0;
21}

Random Element from std::unordered_set / std::unordered_map

These containers have forward iterators, so std::advance works but is still O(n):

cpp
1#include <unordered_set>
2#include <random>
3#include <iostream>
4
5std::unordered_set<int> us = {10, 20, 30, 40, 50};
6
7std::mt19937 gen(std::random_device{}());
8std::uniform_int_distribution<size_t> dist(0, us.size() - 1);
9
10auto it = us.begin();
11std::advance(it, dist(gen));
12std::cout << *it << std::endl;

If you need frequent random access from a set, consider maintaining a parallel std::vector of elements.

Common Pitfalls

  • Using rand() instead of <random>: rand() has poor randomness quality and modulo bias. Always use std::mt19937 with std::uniform_int_distribution for correct uniform sampling.
  • Empty container: Calling dist(0, container.size() - 1) when the container is empty causes undefined behavior (underflow to SIZE_MAX). Always check !container.empty() first.
  • Assuming O(1) for all containers: std::advance is O(1) for random-access iterators (vector, array, deque) but O(n) for bidirectional (set, map, list) and forward (unordered_set) iterators. If you need frequent random selection from a non-random-access container, copy elements to a vector first.
  • Creating std::random_device in a loop: std::random_device may be expensive to construct and should be used once to seed the generator. Create std::mt19937 once and reuse it.
  • Thread safety: std::mt19937 is not thread-safe. Each thread should have its own generator instance, typically using thread_local std::mt19937 gen(std::random_device{}());.

Summary

  • std::vector/std::array: Generate random index with std::uniform_int_distribution — O(1)
  • std::set/std::list/std::map: Use std::advance with a random offset — O(n)
  • std::sample (C++17): Select one or more random elements from any container without replacement
  • Always use <random> (std::mt19937 + distributions) instead of rand() for quality and correctness
  • Check for empty containers before generating random indices
Related reading
Course
Beginner
27 lessons
10 hours
System Design Fundamentals

Build a strong foundation in designing scalable, reliable distributed systems.

View the course
Track what you have practised

A free account saves your progress, solutions and study plan across every problem on Codemia.

System Design practice on Codemia

Work through 120+ system design problems with detailed solutions, from rate limiters to multi-region storage.

Practice system design
Codemia
© 2026 Codemia
Resources
Legal
Social
All Rights Reserved.