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

В моем приложении у меня есть следующие требования:

Структура данных будет заполняться только один раз с некоторыми значениями (не пары ключ/значение). Значения могут повторяться, но я хочу, чтобы структура данных сохраняла их только один раз.
Я буду повторять 100-е годы через все элементы структуры данных, созданные выше. Порядок, в котором элементы появляются на итерации, несуществен.

Ограничение 1 предполагает, что мне придется либо использовать set, либо unordered_set, поскольку данные не находятся в форме пар значений ключа.

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

Я считаю, что решающим фактором будет то, как быстро я могу выполнять итерацию по всем элементам структуры данных. Я не уверен, что для этой цели будет быстрее или неупорядочено. Я считаю, что стандарт не упоминает об этом факте, поскольку эта операция будет O (n) для любой структуры данных. Но мне интересно, для какой структуры данных iterator.next() будет быстрее.

Ответ 1

Существует несколько подходов.

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

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

Boost.Container flat_ [multi] map/set контейнеры упорядочены-вектор основанные ассоциативные контейнеры на основе Austern и Alexandrescu's методические рекомендации. Эти упорядоченные векторные контейнеры также выиграли недавно с добавлением семантики перемещения к С++, ускорение время вставки и стирания значительно. Плоские ассоциативные контейнеры имеют следующие атрибуты:

Более быстрый поиск, чем стандартные ассоциативные контейнеры.

Гораздо быстрее итерации, чем стандартные ассоциативные контейнеры

Меньшее потребление памяти для небольших объектов (и для больших объектов, если используется shrink_to_fit)

Улучшена производительность кеша (данные хранятся в непрерывной памяти)

Нестабильные итераторы (итераторы недействительны при вставке и стирании элементов)

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

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

Более медленная вставка и стирание, чем стандартные ассоциативные контейнеры (специально для непередвижных типов)

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

Ответ 2

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

Ответ 3

Если построение структуры данных не влияет на проблемы с производительностью (или, по крайней мере, незначительно), подумайте о сохранении ваших данных в 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);

Ответ 4

Я настоятельно рекомендую вам не использовать в этом случае. 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.

Ответ 5

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

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

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

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