Random tree pick

[helios]

Is it possible to pick a random element from an std::set/std::map in O(log n)? It's acceptable if some elements have a slightly higher chance of being picked.

[JayhawkZombie]

§23.2.4 associative container requirements
b.find(k); Complexity: Logarithmic

§23.2.5 Unordered associative container requirements
b.find(k); Complexity: Average case O(1), worst case O(b.size())

I reference the C++14 draft here.

Ignore that, I misunderstood the question.
But not from what I can find without having to use another container outside of std::set/set::map. You can use std::advance to move beyond b.begin() a random number of elements, but is linear in complexity.

[helios]

std::advance() actually takes O(n log n) when passed an iterator into an std::map or std::set.

[gunnerfunner]

boost::flat_set provides random access iterators but its insert/remove are slower (O(N)) than std::set

[helios]

No, a random pick returns an iterator into the container without modifying its contents. This question in particular is about std::set and std::map, since they're typically implemented using binary trees.