Wenn man eine Array-Klasse so implementiert, wie sie üblicherweise implementiert wird, ist ihre Leistung im Vergleich zu ihrem STL-Äquivalent wie ein Vektor langsamer. Was macht also STL-Container/Algorithmen schnell?Was macht STL schnell?
STL-Algorithmen wie for_each nehmen Funktionsobjekte, die leicht inline sein können. C verwendet andererseits Funktionszeiger, die für den Compiler viel schwieriger zu optimieren sind.
Dies macht einen großen Unterschied in einigen Algorithmen wie Sortierung, in denen die Vergleichsfunktion viele Male aufgerufen werden muss.
Wikipedia hat some more information falls Sie interessiert sind.
EDIT:
Wie für die Vektorklasse STL, ich glaube nicht, dass es unbedingt schneller das, was Sie in finden könnte, sagen wir, glibc.
das ist wahrscheinlich einer der Crux Punkte: D –
interessant ... – toto
Die Standardbibliothek verwendet gute Algorithmen, wie im Falle eines Arrays (std :: vector) verdoppelt sie normalerweise den Speicher jedes Mal, wenn der Speicherplatz knapp wird, während eine naive Implementierung den Speicher jedes Mal um ein Element erhöhen kann. Da die Speichermenge sehr langsam ansteigt (alle vorhandenen Daten müssen von der alten Zuordnung in die neue Zuordnung kopiert werden), kann dies einen großen Unterschied ausmachen.
Ähnlich sind alle anderen Algorithmen auf ziemlich optimale Weise implementiert. Die Standardbibliothek verwendet normalerweise keine Art von Schleifenabrollung oder andere derartige Optimierungen auf Quellcodeebene. Es ist einfach nur ein guter und einfacher Code (mit schrecklichen Variablennamen und vielen Templates), den der Compiler dann optimiert.
Was ich sagte, ist nicht durch den C++ - Standard angegeben, aber das ist die übliche Praxis in bestehenden Implementierungen zu sein scheint.
Doppelter Speicher kann tatsächlich ziemlich schlecht sein, nachdem Sie ein Megabyte oder so erreicht haben .... –
Hassan Syed: Sie verschwenden nie mehr als 50% des zugewiesenen Speichers. Ich würde das nicht "ziemlich schlecht" nennen. –
Anscheinend std :: vector wächst um einen Faktor von 1,5: http://amitp.blogspot.com/2003_11_01_amitp_archive.html#106843046050898865 – Manuel
Die Algorithmen in der STL werden seit Jahren von allen Mathematikern und Informatikern studiert und verwenden normalerweise die absolut effizientesten Algorithmen, die Ihre Implementierung möglicherweise nicht verwendet. Die übliche Implementierung ist eine, die wahrscheinlich nicht am schnellsten ist, aber am einfachsten zu verstehen ist; Die STL verwendet wahrscheinlich eine optimierte Implementierung.
Wenn alle Arten von hochgebildeten Menschen etwas gesegnet haben (wenn sie es haben), nehmen Sie nicht an, dass Sie nicht darüber nachdenken müssen. Sie sind ziemlich fähig und qualifiziert, falsch zu liegen. –
-1: Ich würde sagen, das ist einfach keine wahre Aussage. Die "Algorithmen" sind implementierungsspezifisch. Nur das exponierte Verhalten von STL-Algorithmen/Containern usw. wird spezifiziert. Es gibt viele, viele Implementierungen der STL und sie wurden nicht alle untersucht (in der Tat, ich würde sagen die meisten nicht), um irgendwo in der Nähe einer Ebene, die Sie behaupten. Viele Implementierungen sind besser als der durchschnittliche Coder schreiben kann, aber ein guter Coder kann leicht mit ihnen konkurrieren ... –
Die meisten Array-Klassen erhöhen die Größe um ein konstantes Inkrement anstelle eines konstanten Faktors (wie es die Standardbibliothek erfordert). Das bedeutet, dass das Einfügen eines Elements ungefähr linearer Zeit statt der amortisierten konstanten Zeit für die Standardbibliothek dauert.
Jeder Entwickler, der das tun sollte, sollte seinen Computer Science Degree zurückgeben –
@DrJokepu: Sie gehen davon aus, dass der Entwickler einen Computer-Abschluss hat:) +1 –
Der Code wird in einer kompilerfreundlichen Weise geschrieben, z. Inlining usw.
natürlich sind die Algorithmen, die sie verwenden, Stand der Technik.
Zusätzlich zu guten, allgemeinen Algorithmen (wie andere bemerkt haben), ist die STL auch ziemlich effizient wegen der starken Verwendung von Vorlagen.
Template metaprograms haben die nette Eigenschaft, dass der Compiler sie aggressiv optimiert. Einige Compiler sind sehr gut darin und reduzieren Vorlagen auf den kleinsten, effizientesten, erforderlichen Code für eine bestimmte Aufgabe. Und im Allgemeinen bedeutet dies, dass Funktionen wann immer möglich inline sind und Code, um mit einem bestimmten Typ zu interagieren, auf seine einfachste Form reduziert wird. Die meisten Implementierungen der STL (und des größten Teils von Boost) nutzen dies natürlich in vollem Umfang aus.
"Die Art, wie es allgemein implementiert wird" ist eine sehr vage Sache. Jeder implementiert es auf seine Weise.Technisch gesehen ist es normalerweise * nicht implementiert *, aber wiederverwendet. –
Geben Sie an, auf welche Vorgänge Sie verweisen und wie Sie festgestellt haben, dass die Standardbibliothek schneller ist. –
@Mehrdad, Malte: Ja, ich stimme zu. Nehmen wir aber an, dass für eine Array-Klasse ein Element in der Mitte eingefügt wird, indem die Elemente einmal verschoben werden, um einen leeren Platz für das neue Element zu schaffen. Diese Implementierung ist viel langsamer als die push_back() eines Vektors. Ich bestimme es, indem ich die Zeit oder Taktzyklen erhalte. – jasonline