Самый быстрый способ для случайного уникального подмножества C ++ tr1 unordered_set

Этот вопрос связан с этот , а точнее этот ответ на него.

Вот и: у меня есть unordered_set C ++ / TR1 U целых чисел без знака (приблизительная мощность 100-50000, приблизительный диапазон значений от 0 до 10 ^ 6). Учитывая мощность N , я хочу как можно быстрее перебрать N случайным образом, но уникальные члены U . Типичного значения для N нет, но оно должно работают быстро для малых N .

Более подробно, понятие "случайность" здесь что два вызова должны давать несколько разные подмножества - тем более разные, тем лучше, но это не так уж важно. Я, например, был бы доволен непрерывным (или непрерывно с обертыванием) блок из N членов U , пока начальный индекс блока является случайным. Лучше прерывание по той же цене, но главное беспокойство - скорость. U изменения мягко, но постоянно между вызовами (примерно 0-10 элементов вставляются / стираются между вызовами).

Как далеко я зашел:

1. Тривиальный подход:
   Выбрать случайный индекс i такой что (i + N-1) . Получите итератор it в U.begin () , продвиньте его i раз, используя it ++ , а затем запустите фактический цикл по подмножеству. Преимущество: легко. Недостаток: трата ++.

2. Подход ведра (и это я "недавно" извлек из приведенной выше ссылки):
   Выберите i , как указано выше, найдите сегмент b , в котором находится i -й элемент, получите local_iterator горит до U.begin (b) , продвижение горит через горит ++ , пока мы не достигнем i -го элемента U , и с этого момента продолжайте увеличивать , горит N раз. Если мы дойдем до конца ведра, мы продолжаем с горит с начала следующего ведра. Если я хочу это сделать более случайный. Я могу выбрать и полностью случайным образом и обернуть его по корзинам.

Мои открытые вопросы:

1. По пункту 2 выше, действительно ли я не могу каким-то образом получить итератор в U , как только я найду i -й элемент? Это пощадит меня контроль границ ковша и т. д. Для меня как новичку кажется непостижимым, что стандартный итератор вперед должен знать, как продолжить обход U , когда на i -й элемент, но когда я сам нашел i -й элемент, не должно быть возможности пройти U , кроме как через пункт 2.
2. Что еще я могу сделать? Вы знаете что-нибудь еще более умное / случайное? Если есть возможность, не хочу ввязываться в ручную контроль размеров ведер, хэш-функций и т. д., так как это немного мне не по зубам.