Usando método find membro vs. estática em um conjunto STL?

Question

Eu estou usando um conjunto porque, eu quero usar o olhar rápido para cima propriedade de um recipiente classificada como um conjunto. Eu estou querendo saber se eu tiver que usar o método membro Encontrar para obter o benefício de um recipiente ordenada, ou eu posso também usar o método find estática nos algoritmos STL?

Meu palpite é que usando a versão estática usará uma pesquisa linear, em vez de uma busca binária como eu quero.

Answer 1

Está certo que o versão não-membro faz uma pesquisa linear, enquanto a versão membro fará um o (log N) pesquisa. std :: conjunto está optimizado para O (log N) inserção, recuperação e eliminação.

Como um ponto de definição, o método std :: achado não é uma função estática. Veja aqui uma descrição do as várias coisas estáticas pode significar em C ++.

Answer 2

Esta é dependente de implementação como alguém poderia ter implementado uma especialização parcial para a estática 'encontrar' que usa uma pesquisa binária em conjuntos, mas considerando todas as coisas, a versão função membro é provável que um melhor desempenho.

IIRC, Scott Meyers sugere em seu livro 'Effective STL' a preferir sempre a versão membro de funções comuns, como achado, troca etc sobre as funções de terceiros, simplesmente porque eles são mais propensos a ser uma aplicação óptima em comparação com a não -member versões e você normalmente pode contar com a vantagem da versão membro do desempenho, enquanto você não pode sempre contar com o fato de que uma especialização parcial para uma determinada função estará presente.