Introduction

With the standard std::set and std::map, you cannot obtain a uniformly random element in guaranteed O(log n) time using only the public container interface. The reason is simple: these containers support logarithmic lookup by key, but they do not support order statistics or indexing by position.

Why the Standard Containers Fall Short

std::set and std::map are usually tree-based ordered containers. They give you:

• 'O(log n) lookup by key'
• 'O(log n) insertion and erase'
• bidirectional iteration in sorted order

They do not give you:

• random-access iterators
• subtree-size queries
• an operation like "return the k-th element"

That missing indexed access is the core obstacle. If you pick a random offset and advance an iterator to it, the walk is linear in the offset.

1#include <set>
2#include <iterator>
3#include <random>
4
5std::set<int> s{1, 3, 5, 7, 9};
6std::mt19937 rng(std::random_device{}());
7std::uniform_int_distribution<std::size_t> dist(0, s.size() - 1);
8
9auto it = s.begin();
10std::advance(it, dist(rng));

This works functionally, but std::advance on a bidirectional iterator is O(n), not O(log n).

What You Need for O(log n) Random Selection

To support random selection in logarithmic time, the tree must know subtree sizes. Then you can:

1. choose a random rank k
2. walk the tree using left-subtree sizes
3. find the k-th element in O(log n) time

That is an order-statistics tree, not a plain standard set or map.

The standard containers do not expose the internals needed for this.

Practical Options

There are three common solutions.

1. Use a Secondary Random-Access Structure

Keep the ordered container for lookup and a vector for random selection.

1#include <vector>
2#include <unordered_map>
3#include <random>
4#include <iostream>
5
6std::vector<int> values{10, 20, 30, 40};
7std::mt19937 rng(std::random_device{}());
8std::uniform_int_distribution<std::size_t> dist(0, values.size() - 1);
9
10std::cout << values[dist(rng)] << '\n';

This gives O(1) random selection, but now you must keep the vector and ordered structure in sync on insert and erase.

2. Use an Order-Statistics Tree

Some non-standard containers support rank queries directly. In GCC-based environments, policy-based data structures can help.

1#include <ext/pb_ds/assoc_container.hpp>
2#include <ext/pb_ds/tree_policy.hpp>
3using namespace __gnu_pbds;
4
5using ordered_set = tree<
6    int,
7    null_type,
8    std::less<int>,
9    rb_tree_tag,
10    tree_order_statistics_node_update>;

Then find_by_order(k) returns the element with rank k, which gives the right primitive for logarithmic random selection.

This is powerful, but it is not standard STL.

3. Build a Custom Augmented Tree

If you control the data structure, you can store subtree sizes at each node and implement insertion, erase, and random rank selection yourself.

That is the most flexible option, but it is also the most work and is only worth it when the performance requirement is real and persistent.

Uniform Randomness Still Matters

Even if you solve the time-complexity problem, the selection must still be uniform. A naive randomized tree walk that chooses left or right with equal probability is not uniform unless the subtree sizes are equal.

Uniform random element selection requires choosing by rank, not by arbitrary branch coin flips.

That is another reason subtree sizes are the right abstraction.

The Honest Answer for Standard STL

If the question is strictly about std::set and std::map, the honest answer is:

• exact uniform random element selection in guaranteed O(log n) is not available from the standard interface alone
• you need either a secondary indexable structure or a different tree implementation

That is a more useful answer than trying to force a linear iterator walk into a logarithmic story.

Common Pitfalls

• Using std::advance from begin() with a random offset is not O(log n) on set or map; it is linear.
• Confusing lookup-by-key complexity with lookup-by-rank complexity leads to the wrong conclusion about what the container can do.
• A random left-right walk through the tree is not uniformly random unless it is weighted by subtree sizes.
• Requiring both ordering and fast random selection often means one container is not enough.
• Assuming policy-based data structures are standard STL can create portability issues across compilers and platforms.

Summary

• Plain std::set and std::map do not support uniformly random element selection in guaranteed O(log n) time.
• The missing capability is rank-based access such as "give me the k-th element."
• A vector side structure gives fast random access but requires synchronization with the ordered container.
• Order-statistics trees solve the problem cleanly, but they are not part of standard STL.
• If you need this operation often, choose the data structure around the requirement instead of fighting the standard container interface.