Как приблизительно определить количество различных значений в массиве за один проход через него

У меня есть несколько огромных массивов (миллионы ++ членов). Все это массивы чисел, и они не отсортированы (и я не могу этого сделать). Некоторые из них uint8_t , некоторые uint16_t / 32/64 . Я хотел бы приблизить количество различных значений в этих массивах. Условия следующие:

1. скорость ОЧЕНЬ важна, мне нужно сделать это за один проход через массив, и я должен пройти через это последовательно (не могу прыгать вперед и назад) (я делаю это на C ++, если это важно)
2. Мне не нужны ТОЧНЫЕ подсчеты. Я хочу знать, что если это массив uint32_t, есть ли 10 или 20 различных чисел или есть тысячи или миллионы.
3. У меня довольно много памяти, которую я могу использовать, но чем меньше используется, тем лучше
4. , чем меньше тип данных массива, тем точнее мне нужно быть
5. Я не возражаю против STL, но если я может обойтись без этого, это было бы здорово (хотя без BOOST, извините)
6. , если бы подход можно было легко распараллелить, это было бы здорово (но это не обязательное условие)

Примеры идеального вывода:

ArrayA [uint32_t, 3M members]: ~128 distinct values
ArrayB [uint32_t, 9M members]: 100000+ distinct values
ArrayC [uint8_t, 50K members]: 2-5 distinct values
ArrayD [uint8_t, 700K members]: 64+ distinct values

Я понимаю, что некоторые ограничения могут показаться нелогичными, но так оно и есть. В качестве примечания, мне также нужны верхние X (3 или 10) наиболее часто используемых и наименее используемых значений, но это намного проще сделать, и я могу сделать это самостоятельно. Однако, если у кого-то есть мысли по этому поводу, не стесняйтесь поделиться ими!

РЕДАКТИРОВАТЬ: небольшое разъяснение относительно STL. Если у вас есть решение, использующее его, опубликуйте его. Отказ от использования STL был бы для нас просто бонусом, нам это не особо нравится. Однако, если это хорошее решение, оно будет использовано!