Случайный элемент в наборе / сопоставлении STL в журнале n

Поскольку набор / карта C ++ STL реализованы как красно-черные деревья, должна быть возможность не только выполнять insert , delete , и найти за O (log n) времени, но также getMin , getMax , getRandom . Насколько я понимаю, у первых двух есть свои эквиваленты в begin () и end () (это правильно?). Как насчет последнего? Как я могу это сделать?

Единственная идея, которая у меня была до сих пор, заключалась в том, чтобы использовать advance со случайным аргументом, который, однако, требует линейного времени ...

EDIT: «random» должно относиться к равномерное распределение