Utilizzando il metodo di ricerca statica vs. membro su un set STL?

Question

Sto usando un set perché, voglio usare la proprietà di ricerca rapida di un contenitore ordinato come un set. Mi chiedo se devo usare il metodo find member per ottenere il vantaggio di un container ordinato, oppure posso usare il metodo find statico negli algoritmi STL?

Il mio sospetto è che l'uso della versione statica utilizzerà una ricerca lineare anziché una ricerca binaria come voglio.

Answer 1

Hai ragione sul fatto che la versione non membro esegue una ricerca lineare, mentre la versione del membro eseguirà una ricerca O (log N). std :: set è ottimizzato per l'inserimento, il recupero e la cancellazione di O (log N).

Come punto di definizione, il metodo std :: find non è una funzione statica. Vedi qui per una descrizione di le varie cose statiche possono significare in C ++.

Answer 2

Questo dipende dall'implementazione in quanto qualcuno potrebbe aver implementato una specializzazione parziale per la 'ricerca' statica che utilizza una ricerca binaria sui set, ma tutto sommato, è probabile che la versione della funzione membro funzioni meglio.

IIRC, Scott Meyers suggerisce nel suo libro 'Effective STL' di preferire sempre la versione membro di funzioni comuni come find, swap ecc. rispetto alle funzioni non membri semplicemente perché hanno maggiori probabilità di essere un'implementazione ottimale rispetto al non -membri le versioni e di solito puoi fare affidamento sul vantaggio in termini di prestazioni della versione del membro, mentre non puoi sempre fare affidamento sul fatto che sarà presente una specializzazione parziale per una determinata funzione.