Используете статический метод поиска членов на множестве STL?

Question

Я использую набор, потому что я хочу использовать свойство быстрого поиска отсортированного контейнера, такого как набор. Мне интересно, должен ли я использовать метод find member, чтобы получить выгоду от отсортированного контейнера, или я могу также использовать метод статического поиска в алгоритмах STL?

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

Answer 1

Вы правы, что версия, не являющаяся членом , выполняет линейный поиск, в то время как версия участника выполняет поиск O (log N). std :: set оптимизирован для вставки, извлечения и удаления O (log N).

Как точка определения, метод std :: find не является статической функцией. Смотрите здесь для описания различные вещи, которые статические могут означать в C ++.

Answer 2

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

IIRC, Скотт Мейерс предлагает в своей книге «Эффективный STL» всегда отдавать предпочтение версии-члену общих функций, таких как find, swap и т. Д., А не функциям, не являющимся членами, просто потому, что они с большей вероятностью будут оптимальной реализацией по сравнению с В версиях-членах и вы обычно можете рассчитывать на преимущество в производительности версии участника, тогда как вы не всегда можете рассчитывать на то, что будет присутствовать частичная специализация для данной функции.