Генерация без повторений. Как ускорить проверку на дубликаты?

С помощью гпсп mt19937_64 генерирую 800 тысяч чисел в диапазоне от 0 до 30 миллионов. Каждое генерируемое число должно быть исключительным, то есть с каждой генерацией приходится сравнивать полученное число со всеми уже сгенерированными:
unsigned array[800 000];
for (int i = 0; i < 800 000; i++) {
generate_again:
buffer = uid(rng); // генерация в буфер
for (int j = 0; j < i; j++) // сравниваем с каждым сгенерированным числом { if (buffer == array[j]) { goto generate_again; // если такое число уже есть - переход к генерации } } array[i] = pepper; // если число исключительное - записываем в массив }
Этот процесс занимает 16 минут. Есть ли способ ускорить этот процесс? Спасибо.

Ответ

Можно хранить полученные данные в дереве(std::set) — получите O(lgn) на вставку и поиск или в hash таблице(std::unordered_set), где вставка тоже довольно дёшева(не помню сколько точно), а поиск O(1). Это гарантировано ускорит процесс.
Если же оставить массив, то можно к нему добавить std::bitset на 30 000 000 бит. Выставлять i-й бит, если i было сгенерировано, и, соответственно, проверять на каждой итерации, не было ли оно сгенерировано. Это тоже должно ускорить процесс.