Как выбрать случайный элемент в std :: set менее чем за O (n) раз?

Этот вопрос с дополнительным ограничением.

Я согласен допустить неоднородный выбор, если он не будет однобоким.

Учитывая, что « наборы обычно реализуются как деревья двоичного поиска », и я ожидаю, что они будут содержать какую-то информацию о глубине или размере для балансировки, я бы ожидал, что вы можете выполнить какое-то взвешенное случайное блуждание дерево. Однако я не знаю какого-либо удаленно переносимого способа сделать это.

Изменить: ограничение НЕ для амортизированного времени.