Исправление KivApple, (текущая версия) :
Ну так фишка в том, что количество занимаемой памяти не зависит от количества элементов и вполне приемлемое. То есть 12 МБ будет занято, хоть в этом множестве 1 элемент, хоть миллион. Это не так уж и плохо.
При поиске элемента в таком векторе можно применить оптимизацию. Например, представить его данные как массив uint64_t (на 64-битной архитектуре) и искать в нём первый ненулевой элемент, а уже потом искать в этом элементе какой же битик не равен нулю. В итоге количество итераций сократится в 64 раза. Для 100 миллионов элементов это полтора миллиона итераций в худшем случае.
Исходная версия KivApple, :
Ну так фишка в том, что количество занимаемой памяти не зависит от количества элементов и вполне приемлемое. То есть 12 МБ будет занято, хоть в этом множестве 1 элемент, хоть миллион. Это не так уж и плохо.
При поиске элемента в таком векторе можно применить оптимизацию. Например, представить его данные как массив uint64_t (на 64-битной архитектуре) и искать в нём первый ненулевой элемент, а уже потом искать этом элементе какой же битик не равен нулю. В итоге количество итераций сократится в 64 раза. Для 100 миллионов элементов это полтора миллиона итераций в худшем случае.