У меня есть набор указателей. На первом этапе я вставляю указатели данных, а на втором этапе я перебираю весь набор и делаю что-то с элементами. Порядок не важен, мне просто нужно избегать дубликатов, что отлично работает с сопоставлением указателей.
Мой вопрос: может ли быть выгодным использовать неупорядоченный набор для той же цели. Бывает ли вставка быстрее для неупорядоченного набора?
Как прокомментировал Ами Тавори, если вам не нужен заказ, тогда обычно лучше пойти на неупорядоченные контейнеры. Причина заключалась в том, что если заказ каким-то образом улучшил производительность, неупорядоченные контейнеры по-прежнему были бы свободны в использовании, и, следовательно, все равно получили бы такую же или лучшую степень.
Недостатком неупорядоченных коллекций является то, что они обычно требуют хеш-функции для типа ключа. Если это слишком сложно или дорого сделать, то контейнеры, которые не используют хеши, могут быть лучше.
В стандартной библиотеке С++ средняя сложность вставки для std::set равна O (log (N)), тогда как для std::unordered_set это O (1). Кроме того, при использовании std::unordered_set в среднем меньше промахов в кешках.
В конце дня, однако, это просто теория. Вы должны попробовать что-то, что звучит достаточно хорошо и профилировать его, чтобы увидеть, действительно ли это.