Оправдана ли моя паранойя сложности времени в этом случае?

Question

Документация для unordered_set говорит, что 'Поиск, вставка и удаление имеют среднюю сложность с постоянным временем.' В худшем случае все они вырождаются в линейный во времени. В отличие от этого, в случае set, он говорит, что все операции Logarithmi c в размере контейнера (что, по-моему, ссылается на худший сценарий, как хорошо).

Итак, учитывая проблему, как мне определить, использовать ли set или unordered_set (мне нужны только эффективные операции вставки, поиска и удаления - их порядок не имеет значения) , Я думаю, что если я не хочу, чтобы элементы сортировались, имеет смысл всегда использовать set вместо unordered_set, так как я не знаю, когда проблема перешла в худшее состояние (и больше не является средним значением). дело). Точно так же у меня один и тот же вопрос в случае unordered_map и map.

Редактировать: я задаю этот вопрос в основном с точки зрения интервью (и в некоторой степени, конкурентного программирования) .

Answer 1

Я думаю, что если я не хочу, чтобы элементы были отсортированы, имеет смысл всегда использовать набор поверх unordered_set

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

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

Исключением является случай реального времени. ограничения, особенно если они жесткие. В этом случае вы должны учитывать сложность наихудшего случая, чтобы убедиться, что ограничения никогда не превышаются.