Die Verwendung von statischen vs. Mitglied find-Methode auf einem STL-Set?

Question

Ich bin mit einem Satz, weil ich das schnelle Nachschlagen Eigenschaft eines sortierten Behälter, wie ein Satz verwenden möchten. Ich frage mich, ob ich den Fund Member-Methode zu verwenden, haben den Vorteil einer sortierten Behälter zu bekommen, oder kann ich auch die statische Methode find in den STL-Algorithmen verwenden?

Meine Vermutung ist, dass die statische Version verwendet, wird eine lineare Suche anstelle einer binären Suche verwenden, wie ich will.

Answer 1

Sie haben Recht, dass die Nichtmitglied Version eine lineare Suche der Fall ist, während das Element Version eine O (log N) Suche tun. std :: Satz wird für O optimiert (log N) Insertion, Abrufen und Löschen.

Als Punkt der Definition, die std :: find-Methode ist keine statische Funktion. Sehen Sie hier für eine Beschreibung von die verschiedenen Dinge statisch in C ++ bedeuten kann.

Answer 2

Dies ist abhängig von der Implementierung als jemand eine partielle Spezialisierung für die statische ‚find‘ umgesetzt haben könnten, die auf Sätze eine binäre Suche verwendet, aber alles in allem, die Member-Funktion Version ist wahrscheinlich eine bessere Leistung.

IIRC, schlägt Scott Meyers in seinem Buch ‚Effective STL‘ immer die Elementversion von gemeinsamen Funktionen wie finden bevorzugen, tauschen usw. über die Nicht-Member-Funktionen, nur weil sie eher eine optimale Umsetzung auf die nicht verglichen werden -Mitglied Versionen und Sie können in der Regel auf dem Leistungsvorteil der Elementversion verlassen, während Sie nicht immer auf der Tatsache verlassen, dass eine partielle Spezialisierung für eine bestimmte Funktion vorhanden sein wird.