einige Container in STL haben keine Funktion

Question

Einige der STL-Container wie std::list und std::vector haben keine find() Methode als Member-Funktion. Warum das? Ich weiß, dass es die Alternative gibt, std::find von <algorithm> zu verwenden, aber dennoch ist diese Verwendung nicht 100% natürlich.

Answer 1

Da gibt es die std::find Funktion von algorithm, die für sie gilt.

Im Allgemeinen haben Container wie std::vector und std::list lineare Suchzeitkomplexität. Als solche an ein Mitglied find Funktion ist eine Redundanz, denn es gibt bereits std::find. Für andere Behälter (z. B. std::set oder std::map etc.) gibt es einen besseren Weg (d. H. Schneller als lineare Komplexität), um das Suchen zu implementieren. Als solche implementierten die Implementierer diesen schnelleren Suchalgorithmus als Elementfunktionen.

Answer 2

In Containern, die eine suchähnliche Funktion haben, wird die Suchmethode integriert (z. B. map, die intern mit einem Binärbaum implementiert ist, der effizient nachgeschlagen werden kann).

Andere, wie die, die Sie zitiert, wird eine Bereichssuche mit dem std::find erlauben, aber nicht über eine Suchfunktion gekennzeichnet, weil es keine algorithmische Vorteil gegenüber dem std :: finden (außer in sortierter/Sonder haben würde Fälle)

Answer 3

Das allgemeine Konstruktionsprinzip besteht darin, std::find wo möglich zu verwenden und find Elementfunktionen zu implementieren, wenn es effizienter ist.

Die Behälter, die haben ein find Mitglied Behälter sind, die haben ein effizienteres Element Look-up-Mechanismus dann die lineare Suche in std::find ausgeführt tun . Zum Beispiel binäre Suchbäume wie std::set und std::map oder Hash-Tabellen wie ihre unordered Gegenstücke.

Answer 4

Die Verwendung derselben Funktion für verschiedene Container sorgt für eine klarere API. Sie müssen nicht die Besonderheiten jedes einzelnen Containers kennenlernen, sondern einfach nur eine Funktion anwenden, die Sie für alle verwenden.

Es ist auch für die Code-Wiederverwendung - Sie den Algorithmus verwenden, die Iteratoren aus einem der Behälter nimmt, die sie zur Verfügung stellen, so dass der Algorithmus muss nicht auf den Behälter verlassen, um einen std::vector, std::list usw. sein

Answer 5

Solche Behälter wie std::vector, std::list, std::forward_list und einige andere sind sequentielle Behälter. Es gibt nichts Besseres als die sequentielle Suche, die auf diese Container angewendet werden kann. Daher muss die sequenzielle Suche für jeden sequenziellen Container nicht neu geschrieben werden, wenn sie für alle diese Container gleich ist.

Die Ausnahme ist die Klasse std::basic_string, die zunächst C-Strings simuliert, die bereits spezielle Suchfunktionen wie strchr, strstr und andere haben.

Answer 6

find, lower_bound und upper_bound Member-Funktionen sind nur vorgesehen, wenn effizienter als die Dritt Äquivalente verwendet wird, oder wenn die Nichtmitgliedern nicht angesichts der Öffentlichkeit Container API

funktionieren könnte

Beachten Sie insbesondere, dass std::string eine find Funktion hat, die std::find()-like lineare Suchmöglichkeiten für Zeichensuchen und std::search()-ähnliche Einrichtungen für Sub-String se bietet bögen: Während die Nichtmitgliedsversionen die gleiche große O-Effizienz aufweisen können, sind sie möglicherweise weniger effizient, da dedizierte Maschinencodebefehle oft für die "String" -Suche verfügbar sind. Es gibt auch historische, Bequemlichkeit und Portierbarkeit Faktoren.

Ganz abgesehen von der Frage der Effizienz, ist es bemerkenswert, dass einige Behälter:

• sind von Natur aus entweder sortiert (multi - set, map) oder unsortiert (unordered_map, unordered_set), typischerweise unsortiert (zB std::string) entweder oder leicht (std::vector)

• öffentlich unterstützen vorwärts-Iteration und/oder Direktzugriffs

• möglicherweise privat binäre Suche unterstützen

• eine solche spezialisierte öffentliche API für Elementzugriff haben, dass potenzielle Wiederverwendung des Algorithmus relativ begrenzt (z ist unordered_map::bucket/::begin(n) et al)

Es ist auch von Interesse, die in einem vector Suche kann über sehr viele Algorithmen erfolgen:

• std::find tut eine Brute-Force-linearen O (n) suchen, die "Findet" Elemente mit niedrigerem Index zuerst,

• std::binary_search erfordert einen sortierten Vektor, springt jedoch herum, um O (log2n) -Komplexität zu erreichen.

• andere Optionen wie Extrapolation suchen und Hashing könnte

anwendbar Wie würden Sie wählen, welche als Mitglieder zu implementieren und hinzufügen? Scheint ein bisschen willkürlich. Dennoch kann die Auswahl, die zu verwenden ist, in Bezug auf die Leistung wichtig sein: Für eine Million Elemente, find, werden eine halbe Million Elementvergleiche vor einer Übereinstimmung und die volle Million wenn das Element nicht vorhanden ist, während typischerweise ~ 20 Vergleiche benötigt Weg.

Die Behälter mit find bieten nicht typischerweise eine solche Flexibilität und die find und/oder lower_bound/upper_bound sie bieten können als Ersatz für die Dritt Äquivalente und wahrscheinlich der einzige vernünftige Weg zu suchen, um die Container zu sehen.

Answer 7

Wie in anderen Kommentaren erwähnt, ist das Designprinzip, dass vector::find() so effizient wie eine Nichtmitgliedsfunktion std::find() implementiert werden kann. Die Vorteile der Verwendung des letzteren sind, dass es die Datenstrukturen und die Operatoren, die auf die Datenstruktur einwirken, entkoppelt, was die Wartbarkeit erhöht (dies ist vorteilhaft für die Entwickler der Bibliothek).

jedoch die Vorteile des ersteren ist, dass es die API zwischen allen Containern konsistent machen würde, und Client-Code macht weniger ausführlich. Dies würde die Lernfähigkeit und Lesbarkeit erhöhen (dies ist vorteilhaft für die Benutzer der Bibliothek). Eine konsistente API würde auch erlauben, generischen Code zu schreiben. Bedenken Sie:

template <typename Container, typename T> 
void foo(const Container& c, const T& x) { 
    if (std::find(c.begin(), c.end(), x) != c.end()) { 
     // ... 
    } 
} 

Die obige ineffizient ist, wenn Container ein std::map oder std::set ist. Um es effizienter zu machen, würden wir tun müssen:

template <typename Container, typename T> 
void foo(const Container& c, const T& x) { 
    if (c.find(x) != c.end()) { 
     // ... 
    } 
} 

Aber dann ist es nicht kompilieren für std::vector und std::list. Dies stellt die Belastung für die Nutzer der Bibliothek ihre eigene generische Funktion manuell Fach/überlastet für jede Art zu schreiben, wollen sie unterstützen:

template <typename T> 
bool contains(const std::vector<T>& c, const T& x) { 
    return std::find(c.begin(), c.end(), x) != c.end(); 
} 

template <typename T> 
bool contains(const std::set<T>& c, const T& x) { 
    return c.find(x) != c.end(); 
} 

template <typename Container, typename T> 
void foo(const Container& c, const T& x) { 
    if (contains(c, x)) { 
     // ... 
    } 
} 

Ich nehme zur Kenntnis, dass diese Art von Design-Entscheidungen ist hart, aber meiner Meinung nach ist dass die Designer der STL hier einen Fehler gemacht haben. Die sehr kleine Wartbarkeitslast scheint die bessere API und Konsistenz für die Benutzer ziemlich wert zu sein. Kurz gesagt, da find für einige Container (für die Performance) eine Memberfunktion sein muss, sollte find eine Memberfunktion für alle Container sein (aus Konsistenzgründen). Beachten Sie, dass ich vollkommen einverstanden bin mit anderen Algorithmen, die keine Mitgliederfunktionen sind.

_{(Ich meine, komm schon, ein Container ist per Definition etwas, das Zeug enthält. Es sollte trivial für Benutzer sein, eine generische und effiziente "enthält" -Funktion zu schreiben. Tatsächlich würde ich argumentieren, dass es hinzugefügt werden sollte zum Container Konzept}