Я думаю, что на самом деле вы можете сделать это с STL, но это немного сложнее.
Вам нужно поддерживать карту.Каждый с ключом от 1..N
(N - количество элементов).
Таким образом, каждый раз, когда вам нужно взять случайный элемент, генерируйте случайное число из 1..N
, затем найдите элемент на картес выбранным ключом.Это элемент, который вы выбираете.
После этого вам нужно поддерживать согласованность карты, находя самый большой элемент, и обновлять его ключ случайным числом, которое вы только что выбрали.
Поскольку каждый шаг является log(n)
операцией, общее время составляет log(n)
.