set vs unordered_set для самой быстрой итерации

Есть несколько подходов.

1. В комментариях к вашему вопросу предлагается сохранить std::unordered_set, который имеет самый быстрый O(1) поиск/вставку и O(N) итерацию (как и каждый контейнер). Если у вас есть данные, которые сильно меняются или требуют много случайных поисков, это, вероятно, самый быстрый способ. Но проверить.
2. Если вам нужно повторить 100 раз без промежуточных вставок, вы можете сделать одну O(N) копию в std::vector и получить выгоду от непрерывной разметки памяти 100 раз. Проверьте, работает ли он быстрее обычного std::unordered_set.
3. Если у вас есть небольшое количество промежуточных вставок между итерациями, может быть полезно использовать выделенный вектор. Если вы можете использовать Boost.Container, попробуйте boost::flat_set, который предлагает интерфейс std::set с внутренним хранилищем std::vector (т. е. расположение непрерывной памяти, которое очень удобно для кэширования и предварительной выборки). Опять же, проверьте, дает ли это ускорение по сравнению с двумя другими решениями.

Для последнего решения см. документацию Boost для некоторых компромиссов (полезно знать обо всех других проблемах, таких как недействительность итератора, семантика перемещения и безопасность исключений):

Контейнеры Boost.Container flat_[multi]map/set — это ассоциативные контейнеры на основе упорядоченных векторов, основанные на рекомендациях Остерна и Александреску. Эти упорядоченные векторные контейнеры также недавно получили преимущества благодаря добавлению семантики перемещения в C++, что значительно ускорило время вставки и стирания. Плоские ассоциативные контейнеры имеют следующие атрибуты:

• Более быстрый поиск, чем стандартные ассоциативные контейнеры
• Гораздо более быстрая итерация, чем стандартные ассоциативные контейнеры.
• Меньшее потребление памяти для небольших объектов (и для больших объектов, если используется сжатие_в_подгонку)
• Улучшена производительность кеша (данные хранятся в непрерывной памяти)
• Нестабильные итераторы (итераторы становятся недействительными при вставке и удалении элементов)
• Не копируемые и неперемещаемые типы значений не могут быть сохранены
• Более слабая безопасность исключений, чем у стандартных ассоциативных контейнеров (конструкторы копирования/перемещения могут генерировать ошибки при смещении значений при стирании и вставке)
• Медленнее вставка и стирание, чем у стандартных ассоциативных контейнеров (особенно для неподвижных типов).

ПРИМЕЧАНИЕ: под более быстрым поиском подразумевается, что flat_set выполняет O(log N) в непрерывной памяти, а не O(log N) гоняется за указателем обычного std::set. Конечно, std::unordered_set выполняет поиск O(1), что будет быстрее для больших N.

Я предлагаю вам использовать set или unordered_set для «фильтрации», а когда вы закончите, переместите данные в вектор фиксированного размера.

Если создание структуры данных не влияет на проблемы с производительностью (или, по крайней мере, лишь незначительно), рассмотрите возможность сохранения ваших данных в std::vector: нет ничего лучше этого.

Для ускорения первоначального построения структуры данных вы можете сначала вставить в std::unordered_set или, по крайней мере, использовать его для проверки существования перед вставкой.

Во втором случае он не обязательно должен содержать элементы, но может содержать, например. индексы.

std::vector<T> v;
auto h = [&v](size_t i){return std::hash<T>()(v[i]);};
auto c = [&v](size_t a, size_t b){return v[a] == v[b];};
std::unordered_set<size_t, decltype(h), decltype(c)> tester(0, h, c);

Неупорядоченный набор использует хэш-таблицу для обеспечения поиска за время, близкое к O(1). Это делается с помощью хэша ключа для вычисления смещения искомого элемента (ключей) от начала набора данных. Если ваш набор данных не мал (например, chars), разные ключи могут иметь один и тот же хэш (коллизия).

Чтобы свести к минимуму коллизии, неупорядоченный набор должен поддерживать довольно редкое заполнение хранилища данных. Это означает, что поиск ключа в большинстве случаев займет O(1) раз (если нет коллизии).

Однако при переборе хеш-таблицы наш итератор столкнется с большим количеством неиспользуемого пространства в нашем хранилище данных, что замедлит поиск следующего элемента нашим итератором. Мы могли бы связать соседние элементы в хеш-таблице с помощью дополнительных указателей, но я не думаю, что неупорядоченный набор делает это.

В свете вышесказанного я предлагаю вам использовать отсортированный вектор для вашего «набора». Используя деление пополам, вы можете искать в хранилище за время O (log n), а итерация по списку тривиальна. Дополнительным преимуществом вектора является то, что память является непрерывной, поэтому у вас меньше шансов столкнуться с промахами кеша.

Я настоятельно рекомендую вам не использовать в таком случае. set — это двоичное дерево, а unordered_set — хэш-таблица, поэтому они используют много памяти, имеют медленную скорость итерации и плохую локальность ссылок. Если вам нужно часто вставлять/удалять/находить данные, set или unordered_set хороший выбор, но теперь вам нужно просто прочитать, сохранить, отсортировать данные один раз и только использовать данные много раз.

В этом случае отсортированный вектор может быть хорошим выбором. vector — это динамический массив, поэтому он не требует дополнительных затрат.

Просто непосредственно, см. код.

std::vector<int> data;

int input;
for (int i = 0; i < 10; i++)
{
    std::cin >> input;
    data.push_back(input); // store data
}

std::sort(data.begin(), data.end()); // sort data

Это все. Все ваши данные готовы.

Если вам нужно удалить дубликаты, такие как set, просто используйте unique - erase после сортировки.

data.erase(
    std::unique(data.begin(), data.end()),
    data.end()
    );

Обратите внимание, что вы должны использовать lower_bound, upper_bound и equal_range, а не find или find_if, чтобы использовать преимущества отсортированных данных.