Зачем использовать неупорядоченный контейнер? (C++)

Я уже пытался найти это, но ничего не нашел.

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

Это чисто служебная вещь, т.е. Потребуется больше обработки для вставки/удаления в ассоциативный контейнер, поскольку она должна проходить сортировку? Я не слишком разбираюсь в системной стороне вещей, но в моей голове я чувствую, что неупорядоченный контейнер требует больше "поддержки", чем тот, который автоматически организован.

Если бы кто-нибудь мог пролить некоторый свет, это было бы действительно оценено.

Ответ 1

Чисто абстрактно рассмотрите тот факт, что упорядочение элементов - это дополнительная "функция", за которую вам нужно заплатить, поэтому, если вам это не нужно (например, в поисковом словаре), вам не придется платить для этого.

Технически это означает, что неупорядоченный контейнер может быть реализован с ожидаемой сложностью поиска и вложения O (1), а не O (log n) упорядоченных контейнеров, используя хеш-таблицы.

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

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

Ответ 2

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

Эти функции не являются эксклюзивными. Контейнер может быть ассоциативным, и если он есть, отдельно может также быть неупорядоченным.

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

Ответ 3

Мы используем Unordered Container, когда упорядочение объектов не является необходимым, и вам больше всего нужна производительность поиска объектов, потому что неупорядоченный контейнер имеет самый быстрый поиск/вставку в любом месте - O (1), а не Ordered Container (ассоциативный контейнер принимает O (log n)) и контейнеры последовательностей принимают O (n)).