warum Vector die remove () -Memberfunktion nicht zur Verfügung stellt, während die Liste zur Verfügung stellt?

Die Frage ist nicht, warum std::vector die Operation nicht anbietet, sondern warum std::list sie anbietet. Das Design der STL konzentriert sich auf die Trennung der Container und der Algorithmen mittels Iteratoren, und in allen Fällen, in denen ein Algorithmus effizient in Form von Iteratoren implementiert werden kann, ist dies die Option.

Es gibt jedoch Fälle, in denen bestimmte Operationen mit Kenntnis des Containers viel effizienter durchgeführt werden können. Das ist der Fall, wenn Elemente aus einem Container entfernt werden. Die Kosten für die Verwendung des remove-Erase -Idioms sind linear in der Größe des Containers (der nicht viel reduziert werden kann), aber das verbirgt die Tatsache, dass im schlimmsten Fall alle außer einer dieser Operationen kopiert von den Objekten (das einzige übereinstimmende Element ist das erste), und diese Kopien können ziemlich große versteckte Kosten darstellen.

Wenn die Operation als Methode in std::list implementiert wird, ist die Komplexität der Operation immer noch linear, aber die zugehörigen Kosten für jedes der entfernten Elemente sind sehr niedrig , ein paar Zeiger Kopieren und Freigeben eines Knotens im Speicher. Gleichzeitig kann die Implementierung als Teil der Liste stärkere Garantien bieten: Zeiger, Referenzen und Iteratoren auf Elemente, die nicht gelöscht werden, werden in der Operation nicht ungültig gemacht.

Ein weiteres Beispiel für einen Algorithmus, der in dem spezifischen Container implementiert wird, ist std::list::sort , der mergesort verwendet, der weniger effizient ist als std::sort , aber keine Iteratoren mit wahlfreiem Zugriff erfordert.

Im Grunde werden Algorithmen als freie Funktionen mit Iteratoren implementiert, es sei denn gibt es einen starken Grund, eine bestimmte Implementierung in einem konkreten Container bereitzustellen.

Ich glaube, der Grund dafür ist, dass std::list eine sehr effiziente remove -Methode anbietet (wenn sie als doppelt verknüpfte Liste implementiert wird, werden nur die Zeiger auf das Element angepasst und der Speicher freigegeben), während die Elemententfernung für std::vector ist vergleichsweise langsam.

Der Trick remove+erase ist der Standardweg, der für alle Containertypen funktioniert, die den erforderlichen Iteratortyp bieten. Vermutlich wollten die Designer der STL auf diesen Unterschied hinweisen. Sie hätten entscheiden können, allen Containern eine remove -Methode zu geben, was remove+erase für alle Container außer denen wären, die einen besseren Weg wussten, aber sie taten es nicht.

Dies scheint auf den ersten Blick die Idee des generischen Codes zu verletzen, aber ich glaube nicht, dass es wirklich so ist. Ein einfacher, generischer remove , der leicht zugänglich ist, macht es einfach, generischen Code zu schreiben, der gut mit allen Containertypen kompiliert, aber am Ende generischen Code, der in 9 von 10 Fällen extrem langsam und im zehnten sehr schnell läuft ist nicht wirklich generisch, es sieht einfach so aus.

Das gleiche Muster kann bei std::map::find vs. dem generischen std::find gefunden werden.

Da das Löschen von Elementen aus einer Liste billig ist, während dies für einen Vektor teuer ist, müssen alle folgenden Elemente verschoben werden, d. h. kopiert / verschoben werden.

Ich stelle mir vor, dass es aus Effizienzgründen langsamer ist, zufällige Elemente aus einem Vektor zu entfernen als aus einer Liste. Es könnte ein wenig mehr tippen für Situationen wie diese, aber zumindest ist es offensichtlich in der Schnittstelle, dass die std::vector nicht die beste Datenstruktur ist, wenn Sie dies oft tun müssen.