Является ли std :: unordered_set смежным (например, std :: vector)?
Я храню указатели в std :: unordered_set, потому что я не хочу дубликатов (я удаляю указатели в коллекции, поэтому, если есть дубликат, я попытаюсь удалить уже удаленный указатель). Я интенсивно зацикливаюсь на этих наборах, и, поскольку я знаю, что std :: vector — самый быстрый контейнер для зацикливания (непрерывная память), я подумал, что std :: unordered_set делает то же самое.
Если это не так, будет ли быстрее использовать std :: vector и проверять, был ли удален указатель?
Решение
Является
std::unordered_setсмежный?
Точная реализация контейнеров не детализирована стандартом … тем не мение Стандарт действительно предписывает ряд поведений, которые ограничивают фактическое представление.
Например, std::unordered_set должен быть стабильным в памяти: ссылка на / address элемента действительна даже при добавлении / удалении Другой элементы.
Единственный способ добиться этого — распределить элементы более или менее независимо. Это не может быть достигнуто при непрерывном выделении памяти, поскольку такое выделение обязательно будет ограниченным, и, следовательно, может быть переросшим без возможности перераспределения элементов в большей части.
Другие решения
Нет, это не непрерывная память, но она все еще очень быстрая, благодаря хэш-карте.
Изменить: быстро для произвольного доступа, если вы в основном делаете циклы, вы должны рассмотреть другой контейнер, я думаю.
Edit2: И вы должны профиль, чтобы знать, стоит ли думать о другом контейнере. (Может быть, вы должны оптимизировать где-то еще … может быть).
Тот факт, что следующие функции-члены предлагаются std::unordered_map предполагает, что он основан на хэш-таблице, возможно,
отдельная цепочка со связанными списками.
bucket_count, hash_function, load_factor, max_load_count, rehash
Являются ли элементы смежными или нет, зависит от распределителя.
Распределитель по умолчанию для unordered_map а также list не выделяет
элементы в смежной памяти. Память для каждого элемента выделяется
во время его вставки.
Тем не менее, вы можете предоставить пользовательский распределитель (например, распределитель пула)
который может выделить элементы из предварительно выделенного пула памяти. Еще,
логически смежные элементы в структуре данных не могут быть физически
смежный в памяти.
Таким образом, если циклическое выполнение всех элементов является наиболее частой операцией, то
unordered_map не может быть лучшим решением. Выполнение доминирующих сценариев использования через профилировщик для всех конкурирующих решений выявит наилучшее решение.
В дополнение к этому, unordered_map не лучший выбор, чтобы зациклить на другом
причина. Обратите внимание на словонеупорядоченный«во имя, это передает это — в отличие от list, vector, или же map — нет порядка элементов. Например, член
функция rehash может изменить относительный порядок элементов. По факту,
Перефразы выполняются автоматически контейнером всякий раз, когда его коэффициент загрузки
будет превышать max_load_factor во время любой операции.
Предполагается, что std :: unordered_set является контейнером хеш-карты, поэтому мы можем предположить, что он имеет небольшое снижение производительности при сравнении с std :: vector.
Но я думаю, что вы должны проверить фактический результат профилирования, если доступ unordered_set является реальной точкой доступа.
Если реализация STL, которую вы используете, является разумной, она должна предоставлять векторную специализацию для указателя или ключа типа int. Если это правда, unordered_set, специализированный для типа указателя, будет вести себя так же, как автоматически растущий / уменьшающийся вектор, а разница в производительности будет незаметна.