kennen:stl
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
— | kennen:stl [2020-07-27 10:02] (aktuell) – angelegt - Externe Bearbeitung 127.0.0.1 | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
+ | ====== Schablonen der Standardbibliothek ====== | ||
+ | > Programme = Algorithmen + Datenstrukturen | ||
+ | >> | ||
+ | |||
+ | ===== Konzept ===== | ||
+ | ==== Der Wunsch nach einer allgemeinen Bibliothek ==== | ||
+ | <code cpp> | ||
+ | Datenstrukturen: | ||
+ | k | Feld, Liste, Baum, Menge, Tabelle, Stapel, Warteschlange, | ||
+ | | | ||
+ | | | ||
+ | *----- j Algorithmen | ||
+ | / | ||
+ | i / | ||
+ | Elementtypen | ||
+ | bool, char, int, float, double | ||
+ | nutzerdefiniert: | ||
+ | </ | ||
+ | |||
+ | Eine universelle Bibliothek von Algorithmen und Datenstrukturen | ||
+ | für Elemente beliebigen Typs steht vor dem Problem der Komplexität: | ||
+ | |||
+ | * i unterschiedliche Datentypen, j verschiedene Datenbehälter und k Prozeduren erfordern i*j*k Implementierungen. | ||
+ | * Keine Bibliothek wäre vollständig. Jeder neue Elementtyp, jeder neue Container, jeder neue Algorithmus würde eine Welle von Ergänzungen notwendig machen (die dann wegen Zeitmangel vermutlich unterbleiben). | ||
+ | * Einige Aufgaben lassen sich auf bestimmten Datenstrukturen einfacher umsetzen, andere lassen sich nicht vollständig vorausbestimmen. So gibt es unterschiedlichste Sortierkriterien. Die Schnittstellen der allgemeinen Routinen [[.: | ||
+ | |||
+ | Eine allgemeine Bibliothek muss | ||
+ | * die häufigsten Problemstellungen abdecken, | ||
+ | * effizient arbeiten, | ||
+ | * aus voneinander unabhängigen, | ||
+ | * einfach zu ergänzen sein, | ||
+ | * einfach und sicher nutzbar sein. | ||
+ | |||
+ | ==== a) Allgemeinheit: | ||
+ | Datentyp-parametrisierte Klassen und Funktionen ([[.: | ||
+ | müssen nur einmal geschrieben werden. | ||
+ | Diese Beobachtung wurde von Alexander Stepanov und Meng Lee nach Erfahrungen mit | ||
+ | generischen Algorithmen in [[.: | ||
+ | konsequent weitergedacht und in der Standard-Schablonen-Bibliothek | ||
+ | (standard template library = STL) umgesetzt. | ||
+ | Die STL wurde 1994 in den Standard-Prozess von C++ aufgenommen, | ||
+ | als dieser beinahe schon als abgeschlossen betrachtet wurde. | ||
+ | Allein ihre Beschreibung nahm im Standard 1998 etwa ein Viertel des Seitenumfangs ein. | ||
+ | |||
+ | Der Template-Mechanismus reduziert die Komplexität auf j+k durch | ||
+ | |||
+ | * datentypunabhängige [[# | ||
+ | * vom Containertyp unabhängige [[# | ||
+ | * Entkopplung der Algorithmen von den Containern durch [[# | ||
+ | * Hilfsfunktionen und -klassen für bestimmte Nuancen (Aspekte, " | ||
+ | |||
+ | <code cpp> | ||
+ | Container | ||
+ | |||
+ | Felder | ||
+ | vector< | ||
+ | deque< | ||
+ | list< | ||
+ | set< | ||
+ | map<Key, Value> | ||
+ | ... output | ||
+ | | ||
+ | | ||
+ | </ | ||
+ | Anstatt alles miteinander zu verzahnen, | ||
+ | führt das Trennen der Datenhaltung von den Algorithmen | ||
+ | und das Dazwischenschieben der Iterator-Idee | ||
+ | zu einer überschaubaren Menge von Bausteinen. | ||
+ | Der Nutzer kann diese in unterschiedlicher Weise kombinieren, | ||
+ | um seinen beabsichtigten Zweck zu realisieren | ||
+ | (z.B. [[.: | ||
+ | |||
+ | ==== b) Begriffe ==== | ||
+ | Für den Umgang mit den Schablonen der Standard-Bibliothek sind folgende Bezeichnungen wichtig: | ||
+ | * ** Algorithmus ** : eine oder mehrere Elementfolgen (Bereiche) bearbeitende Funktion. | ||
+ | * ** Bereich ** : durch zwei Iteratoren [first, last) begrenzte Folge von Elementen, dessen rechte Begrenzung '' | ||
+ | * ** Container ** : Datenbehälter, | ||
+ | * ** Iterator ** : Objekt, mit dem über Folgen von Elementen iteriert und nacheinander auf die Elemente zugegriffen werden kann; besitzt eine einheitliche, | ||
+ | * ** Funktor ** : Funktionsobjekt, | ||
+ | * ** Prädikat ** : Funktion oder Funktor, welche/r beim Funktionsaufruf einen Wahrheitswert liefert; ergibt '' | ||
+ | |||
+ | ==== c) Container + Algorithmen + Iteratoren = Effizienz ==== | ||
+ | <code cpp> | ||
+ | Anwenden von | ||
+ | auf einige oder | if( praedikat(*iterator) ) ... | ||
+ | alle Elemente | ||
+ | im Bereich | ||
+ | | | ||
+ | v | ||
+ | eines Containers | ||
+ | </ | ||
+ | Um nach einer Datenerfassung Doubletten aus einem [[# | ||
+ | zu entfernen, | ||
+ | kann man so vorgehen: | ||
+ | |||
+ | <code cpp> | ||
+ | #include < | ||
+ | |||
+ | template <class Container> | ||
+ | void sortiere_und_entferne_Dopplungen(Container& | ||
+ | { | ||
+ | std::sort( c.begin(), c.end() ); | ||
+ | typename Container:: | ||
+ | c.erase(neuesEnde, | ||
+ | } | ||
+ | </ | ||
+ | Sortieren eines Bereiches und einmalige Elemente nach vorn rücken sind als generische [[# | ||
+ | [[# | ||
+ | Das Entfernen der überzähligen Elemente an Ende des Bereiches | ||
+ | muss der Container allerdings selbst durchführen, | ||
+ | da nur er über die entsprechenden Methoden verfügt. | ||
+ | |||
+ | Der Container muss vorsortiert werden, | ||
+ | weil '' | ||
+ | um schnell zu arbeiten. | ||
+ | Erkennen von Doubletten ohne Änderung der Reihenfolge | ||
+ | würde eine zum Quadrat der Elementanzahl proportionale Laufzeit erfordern. | ||
+ | Algorithmen und Containermethoden wurden so entworfen, | ||
+ | dass sie möglichst effizient sind. | ||
+ | Container besitzen keine teuren Methoden. | ||
+ | So wurde bei '' | ||
+ | '' | ||
+ | da alle Elemente um einen Platz nach hinten rücken müssten. | ||
+ | Wer es dennoch tun will, muss umständlicher schreiben: | ||
+ | |||
+ | <code cpp> | ||
+ | v.insert(v.begin(), | ||
+ | </ | ||
+ | Für das Laufzeitverhalten in Abhängigkeit von der Anzahl n der Elemente | ||
+ | wird die O-Notation benutzt. Typische Laufzeit-Komplexitäten sind: | ||
+ | |||
+ | | O(1) | konstant | ||
+ | | O(log n) | logarithmisch | ||
+ | | O(n) | linear | ||
+ | | O(n log n)| | Quick Sort| | ||
+ | | O($n^2$) | ||
+ | | O($n^3$) | ||
+ | | O(exp n) | exponentiell | ||
+ | | O(n!) | kombinatorisch | Rundreiseproblem | schon für kleine n| | ||
+ | |||
+ | ===== Algorithmen | ||
+ | Algorithmen der Standardbibliothek bearbeiten einen oder mehrere durch [[# | ||
+ | eingegrenzte Bereiche mit gleichartigen Elementen. | ||
+ | Die Algorithmen der Standard-Bibliothek (Header | ||
+ | < | ||
+ | < | ||
+ | gehören folgenden Gruppen an: | ||
+ | |||
+ | * [[.: | ||
+ | * [[.: | ||
+ | * [[.: | ||
+ | <code cpp> | ||
+ | #include < | ||
+ | #include < | ||
+ | |||
+ | void demo() | ||
+ | { | ||
+ | float array[] = { 5, 3, 7, 2, 4 }; | ||
+ | float* first = array; | ||
+ | float* last = array + sizeof(array)/ | ||
+ | |||
+ | int n = std:: | ||
+ | std:: | ||
+ | std:: | ||
+ | |||
+ | std:: | ||
+ | std:: | ||
+ | } | ||
+ | </ | ||
+ | ==== Bereiche als Parameter ==== | ||
+ | Seit C++20 können die Algorithmen auch den Bereich [first, | ||
+ | <code cpp> | ||
+ | std:: | ||
+ | </ | ||
+ | Diese Versionen sind im Namensbereich '' | ||
+ | Als '' | ||
+ | auf den '' | ||
+ | Bei fehlerhafter Nutzung liefern diese [[Concepts]] aussagekräftigere Fehlermeldungen. | ||
+ | |||
+ | ===== Container ===== | ||
+ | * Nicht-sortierende [[# | ||
+ | * automatisch sortierende [[# | ||
+ | Gleichartige [[# | ||
+ | geben den Containern eine weitgehend einheitliche Benutzerschnittstelle. | ||
+ | Bei unzureichendem [[# | ||
+ | |||
+ | ==== Sequentielle Container ==== | ||
+ | < | ||
+ | < | ||
+ | < | ||
+ | |||
+ | Sequentielle Container übernehmen Elemente in vorgegebener Reihenfolge | ||
+ | und behalten diese Folge bei. | ||
+ | Jeder Container hat spezielle Stärken: | ||
+ | * Ein [[.: | ||
+ | * eine [[.: | ||
+ | * eine [[.: | ||
+ | <code cpp> | ||
+ | std:: | ||
+ | std:: | ||
+ | std:: | ||
+ | </ | ||
+ | < | ||
+ | < | ||
+ | < | ||
+ | < | ||
+ | < | ||
+ | < | ||
+ | (Beinahe-Container) | ||
+ | |||
+ | " | ||
+ | [[# | ||
+ | |||
+ | Ein [[.: | ||
+ | Er kann also weder wachsen noch schrumpfen. | ||
+ | Dafür kommt er ohne dynamischen Speicher aus. | ||
+ | |||
+ | Der [[.: | ||
+ | da die Anzahl seiner '' | ||
+ | Er kann seine Größe nicht zur Laufzeit ändern, | ||
+ | also keine Bits einfügen oder entfernen. | ||
+ | Er kann genutzt werden, | ||
+ | wenn nicht die Flexibilität eines [[.: | ||
+ | |||
+ | Die [[.: | ||
+ | kann nur in Vorwärtsrichtung durchlaufen werden. | ||
+ | Damit gibt es nur Methoden zum Einfügen / Entfernen //nach// einer angegebenen Position. | ||
+ | |||
+ | Initialisiererlisten [[.: | ||
+ | nehmen Anfangswerte für Container wie '' | ||
+ | um sie zur Anfangswertbelegung an andere Container zu übergeben. | ||
+ | |||
+ | Die Schablone '' | ||
+ | mit ihren zwei Spezialisierungen [[.: | ||
+ | und '' | ||
+ | wurde im Standardisierungsprozess mit | ||
+ | allgemeinen Containermerkmalen ausgestattet | ||
+ | und kann damit als Container für Zeichenfolgen aufgefasst werden. | ||
+ | hat jedoch zusätzliche Methoden zur Zeichenkettenverarbeitung | ||
+ | wie Suchen und Ersetzen. | ||
+ | |||
+ | Für numerische Anwendungen (eine historische Domäne von [[.: | ||
+ | wurde die Schablone [[.: | ||
+ | Die Implementierung ist (auf bestimmten Rechnern) so optimierbar, | ||
+ | dass die Rechenoperationen parallel (und eben nicht sequentiell) ausgeführt werden. | ||
+ | |||
+ | ==== Assoziative Container ==== | ||
+ | < | ||
+ | < | ||
+ | |||
+ | Assoziative Container verbinden die gespeicherten Werte mit Schlüsseln, | ||
+ | nach denen die Elemente sortiert gehalten werden. | ||
+ | Die natürliche Sortierreihenfolge ist durch den | ||
+ | für den Schlüsseltyp '' | ||
+ | über das [[# | ||
+ | Ein anderes Sortierkriterium kann als | ||
+ | zweistelliges Prädikat '' | ||
+ | Als Schlüssel können beliebige Typen dienen, | ||
+ | sofern für sie ein Vergleichskriterium definiert ist. | ||
+ | |||
+ | * Tabellen (Zuordnungen) [[.: | ||
+ | * Die [[.: | ||
+ | * Mengen [[.: | ||
+ | * In [[.: | ||
+ | <code cpp> | ||
+ | std:: | ||
+ | Meier 6135 | ||
+ | Meier | ||
+ | Meyer | ||
+ | Schulze 5180 Schulze 5180 | ||
+ | |||
+ | std:: | ||
+ | { 1 2 3 4 5 } { 5 5 4 3 3 } | ||
+ | </ | ||
+ | Da assoziative Container meist als balancierte Binärbäume implementiert sind, | ||
+ | haben Operationen zumeist logarithmisches [[# | ||
+ | |||
+ | ==== Hash-Container ==== | ||
+ | < | ||
+ | < | ||
+ | |||
+ | Die in C++11 hinzugekommenen Container | ||
+ | [[.: | ||
+ | und | ||
+ | [[.: | ||
+ | und ihre " | ||
+ | durch den die Position des Elements in konstanter Zeit gefunden wird, also O(1) statt O(log N). | ||
+ | Hier kommt es nicht auf die Reihenfolge an, sondern auf Schnelligkeit. | ||
+ | ==== Allgemeine Container-Eigenschaften ==== | ||
+ | === Typdefinitionen === | ||
+ | |||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | |||
+ | Alle Container stellen einheitliche Typbezeichnungen für Werte, | ||
+ | konstante und nichtkonstante Referenzen | ||
+ | sowie Vorwärts- und Rückwärts-[[# | ||
+ | zur Verfügung. | ||
+ | Für Größenangaben des Containers wird | ||
+ | '' | ||
+ | für Abstandsangaben '' | ||
+ | als vorzeichenbehafteter Ganzzahltyp festgelegt. | ||
+ | [[# | ||
+ | definieren zusätzlich den Schlüsseltyp und Typen für Schlüssel- | ||
+ | und Wertevergleich. | ||
+ | Die Typbezeichnungen erleichtern den Container-Austausch: | ||
+ | |||
+ | <code cpp> | ||
+ | typedef std:: | ||
+ | Container v; | ||
+ | Container:: | ||
+ | </ | ||
+ | === Erzeugen, Kopieren, Zerstören === | ||
+ | |||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | |||
+ | Ein neuer Container ist zu Beginn leer. | ||
+ | Er kann sich die Inhalte eines gleichartigen Containers '' | ||
+ | oder eines Bereiches '' | ||
+ | [[# | ||
+ | eine bestimmte '' | ||
+ | mit demselben '' | ||
+ | Die Container besitzen ihre Inhalte | ||
+ | und sind dann für deren Freigabe verantwortlich. | ||
+ | Die dynamische Speicherverwaltung erfolgt im Hintergrund automatisch, | ||
+ | eine Speicherfreigabe durch den Anwender ist nicht erforderlich. | ||
+ | |||
+ | <code cpp> | ||
+ | void konstruktor_demo(Container const& c) | ||
+ | { | ||
+ | Container c0; // leer | ||
+ | Container c1(c); | ||
+ | Container c2(c.rbegin(), | ||
+ | } | ||
+ | </ | ||
+ | === Nicht-modifizierender Zugriff (Größe, Vergleiche) === | ||
+ | |||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | |||
+ | Container liefern ihre Elementanzahl mit '' | ||
+ | Bei '' | ||
+ | |||
+ | <code cpp> | ||
+ | void groesse_demo(Container const& c) | ||
+ | { | ||
+ | if (c.empty()) std::cout << " | ||
+ | else std::cout << " | ||
+ | } | ||
+ | </ | ||
+ | Auf gleichartige Container können Vergleichsoperatoren angewendet werden, | ||
+ | sofern für die Elemente die Operatoren '' | ||
+ | Zwei Container gelten als inhaltsgleich, | ||
+ | wenn beide Container die gleiche Anzahl von Elementen enthalten | ||
+ | und jedes Element des einen | ||
+ | mit dem entsprechenden Element des anderen Containers gleich ist. | ||
+ | Ein Container wird als (lexikographisch) kleiner eingestuft, | ||
+ | sobald beim Durchmustern eines seiner Elemente kleiner ist als das entsprechende Element | ||
+ | im anderen Container oder bei bisher gleichwertigen Elementen | ||
+ | dieser Container weniger Elemente enthält. | ||
+ | |||
+ | <code cpp> | ||
+ | void vergleich_demo(Container const& c) | ||
+ | { | ||
+ | Container kopie = c; | ||
+ | if (kopie == c) std::cout << " | ||
+ | if (kopie < c ) std::cout << "Da ist was schiefgegangen\n"; | ||
+ | } | ||
+ | </ | ||
+ | === Nicht-modifizierender Zugriff (assoziative Container) === | ||
+ | |||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | |||
+ | '' | ||
+ | liefern das Vergleichskriterium für Werte bzw. Schlüssel | ||
+ | des assoziativen Containers. | ||
+ | |||
+ | Assoziative Container können effizient bestimmen, | ||
+ | wie oft ein Schlüsselwert '' | ||
+ | Die Position des (ersten) Elementes bestimmt '' | ||
+ | Bei Misserfolg gibt die Methode '' | ||
+ | Die erste / letzte Iterator-Position, | ||
+ | bei der '' | ||
+ | liefern die Methoden '' | ||
+ | '' | ||
+ | Mit '' | ||
+ | |||
+ | <code cpp> | ||
+ | void nachschlagen(std:: | ||
+ | { | ||
+ | std:: | ||
+ | if (i != telefonbuch.end()) | ||
+ | std::cout << i->first << " hat die Nummer " << i-> | ||
+ | else | ||
+ | std::cout << name << " hat kein Telefon\n"; | ||
+ | } | ||
+ | </ | ||
+ | === Zuweisungen === | ||
+ | |||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | |||
+ | Bei einer Zuweisung übernimmt ein Container alle Elemente vom rechsseitigen Container. | ||
+ | Ein globaler Tausch '' | ||
+ | für Kopie, Zuweisung und Destruktion aller Elemente erfordern. | ||
+ | Der Methodenaufruf '' | ||
+ | durch internen Zeigertausch in konstanter Zeit. | ||
+ | |||
+ | === Direkter Elementzugriff === | ||
+ | |||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | |||
+ | Der Referenzzugriff auf das erste bzw. letzte Element mit | ||
+ | '' | ||
+ | wenn ein solches Element existiert ('' | ||
+ | |||
+ | Beim Index-Zugriff in [[.: | ||
+ | und [[.: | ||
+ | sollte sichergestellt sein, | ||
+ | dass '' | ||
+ | Beim Zugriff mit dem Index-Operator '' | ||
+ | muss dies der Anwender sicherstellen. | ||
+ | Die Methode '' | ||
+ | eine '' | ||
+ | |||
+ | Der Indexzugriff '' | ||
+ | liefert den zu dem Schlüssel '' | ||
+ | Existiert kein Element mit dem angegebenen Schlüssel, | ||
+ | wird es automatisch angelegt und ein Standardwert zugeordnet. | ||
+ | |||
+ | > Tatsächlich ist '' | ||
+ | >> --- Bjarne Stroustrup [Die C++ Programmiersprache 17.4.1.7] | ||
+ | |||
+ | <code cpp> | ||
+ | void erfassen(std:: | ||
+ | { | ||
+ | ++tabelle[wort]; | ||
+ | } | ||
+ | </ | ||
+ | === Iterator-Zugriff === | ||
+ | |||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | |||
+ | [[# | ||
+ | von [[.: | ||
+ | und [[.: | ||
+ | erlauben wahlfreien Zugriff. | ||
+ | Die bidirektionalen Iteratoren der [[# | ||
+ | erlauben keine Schlüsseländerungen, | ||
+ | |||
+ | Die Methode '' | ||
+ | '' | ||
+ | Bei leeren Containern sind die Ergebnisse beider Methoden identisch. | ||
+ | Reverse-Iteratoren durchlaufen den Container in der umgekehrten Elementfolge: | ||
+ | '' | ||
+ | '' | ||
+ | |||
+ | <code cpp> | ||
+ | | ||
+ | | ||
+ | | ||
+ | [.......................] | ||
+ | ^ : ^ : | ||
+ | | : | ||
+ | | ||
+ | </ | ||
+ | |||
+ | === Einfügen === | ||
+ | |||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | |||
+ | Ein '' | ||
+ | '' | ||
+ | Eine ganzer Bereich '' | ||
+ | Für [[# | ||
+ | wo mit der Suche nach der geeigneten Stelle zum Einfügen begonnen werden soll, | ||
+ | die " | ||
+ | Die '' | ||
+ | um ein neues Container-Element direkt im Container zu erschaffen. | ||
+ | Damit werden unnötige Kopien bzw. Verschiebungen vermieden. | ||
+ | |||
+ | <code cpp> | ||
+ | void einfuegen_demo(Container& | ||
+ | { | ||
+ | Container:: | ||
+ | c.push_back(wert); | ||
+ | } | ||
+ | </ | ||
+ | Größenänderungen '' | ||
+ | mit Standardwert oder angegebenem '' | ||
+ | oder entfernen überzählige Elemente am Ende des Containers. | ||
+ | |||
+ | Assoziative und ungeordnete Container beherrschen seit [[kennen: | ||
+ | das Verschmelzen (Spleißen) von Sequenzen. | ||
+ | Schon vorhandene Elemente verbleiben im Quellcontainer, | ||
+ | <code cpp> | ||
+ | void verschmelzen_demo(Container& | ||
+ | { | ||
+ | target.merge(source); | ||
+ | for (auto [k,v] : target) std::cout << k << ' ' << v << ' | ||
+ | std::cout << "\nnot merged, target already contained: | ||
+ | for (auto [k,v] : source) std::cout << k << ' ' << v << ' | ||
+ | } | ||
+ | </ | ||
+ | Auch einzelne Knoten lassen sich umhängen: | ||
+ | <code cpp> | ||
+ | void umhaengen(Container& | ||
+ | { | ||
+ | target.insert(source.extract(src.find(1))); | ||
+ | target.insert(source.extract(2)); | ||
+ | auto r = target.insert(source.extract(3)); | ||
+ | if (!r.inserted) | ||
+ | { | ||
+ | r.node.key() = 4; // anderen Schlüssel wählen, dann einfügen | ||
+ | target.insert(r.position, | ||
+ | } | ||
+ | for (auto [k,v] : target) std::cout << k << ' ' << v << ' | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | === Löschen === | ||
+ | |||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | |||
+ | Um ein Element zu löschen, muss dessen '' | ||
+ | [[# | ||
+ | Auch ein Teilbereich '' | ||
+ | Für [[# | ||
+ | löscht '' | ||
+ | |||
+ | <code cpp> | ||
+ | void loeschen_demo(Container& | ||
+ | { | ||
+ | c.erase(c.begin()); | ||
+ | c.clear(); | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | |||
+ | ==== Laufzeitverhalten ==== | ||
+ | Containermethoden zeigen folgendes Laufzeitverhalten bei n Elementen im Container: | ||
+ | |||
+ | | | vector | deque | list | set/ | ||
+ | | Indexzugriff | ||
+ | | Listenoperationen | ||
+ | | Operationen vorn | - | O(1) | O(1) | - | -| - | - | | ||
+ | | Operationen hinten | O(1)+ | O(1) | O(1) | - | -| - | - | | ||
+ | | Iteratoren | ||
+ | Dabei bedeutet | ||
+ | > - nicht implementiert wegen schlechten Zeitverhaltens, | ||
+ | > + durchschnittliches Verhalten, gelegentlich Zusatzaufwand. | ||
+ | |||
+ | ===== Iteratoren ===== | ||
+ | < | ||
+ | |||
+ | Die [[# | ||
+ | und [[# | ||
+ | verbindenden Iteratoren gehören [[# | ||
+ | mit unterschiedlichen Fähigkeiten an. | ||
+ | [[# | ||
+ | durchlaufen Bereiche in umgekehrter Folge. | ||
+ | [[# | ||
+ | bieten eine zeigerartige Schnittstelle | ||
+ | für Einfügeoperationen, | ||
+ | |||
+ | ==== Kategorien | ||
+ | Anhand der (hier abgekürzt bezeichneten) Kategorien | ||
+ | können Algorithmen mit optimalem Zeitverhalten für die Sequenz | ||
+ | umgesetzt werden. | ||
+ | |||
+ | | Abkürzung | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | |||
+ | Ausgabe-Iteratoren '' | ||
+ | |||
+ | <code cpp> | ||
+ | *iter = wert; | ||
+ | ++iter; | ||
+ | </ | ||
+ | Eingabe-Iteratoren '' | ||
+ | Ein Vergleich mit einem anderen Iterator ist möglich, | ||
+ | um z.B. ein Ende zu definieren. | ||
+ | Ein zweiter Durchlauf mit einer Kopie kann andere Werte liefern. | ||
+ | Wandert der Iterator über zusammengesetzte Typen, | ||
+ | ist der Komponentenzugriff mit dem Pfeil-Operator möglich. | ||
+ | |||
+ | <code cpp> | ||
+ | while (iter != ende) | ||
+ | { | ||
+ | wert = *iter; | ||
+ | ++iter; | ||
+ | } | ||
+ | </ | ||
+ | Vorwärts-Iteratoren '' | ||
+ | Sie lassen sich zuweisen und kopieren. | ||
+ | Im Gegensatz zu Ein- und Ausgabe-Iteratoren ist festgelegt, | ||
+ | dass Kopien über die gleichen Elemente wie die Vorlage wandern, | ||
+ | mehrere Durchläufe sind möglich. | ||
+ | |||
+ | <code cpp> | ||
+ | while (*iter != wert) | ||
+ | { | ||
+ | *ziel++ = *iter++; | ||
+ | } | ||
+ | </ | ||
+ | Bidirektionale Iteratoren '' | ||
+ | auch in entgegengesetzter Richtung über die Elemente laufen. | ||
+ | |||
+ | <code cpp> | ||
+ | while (first != last) | ||
+ | { | ||
+ | --last; | ||
+ | } | ||
+ | </ | ||
+ | Sofern die Iteratoren als Klassen definiert sind, | ||
+ | sind die Präfixvarianten von Inkrement bzw. Dekrement | ||
+ | gegenüber den Postfixvarianten effizienter, | ||
+ | da kein temporärer Iterator für den Ergebniswert gebildet werden muss. | ||
+ | Wo möglich, sollte '' | ||
+ | |||
+ | Iteratoren mit wahlfreiem Zugriff '' | ||
+ | können wie Zeiger direkt an eine beliebige Stelle positioniert werden. | ||
+ | Auch der Feldzugriff ist möglich. | ||
+ | Abstandsberechnungen sind sehr einfach, | ||
+ | Tests auf davor / dahinter erfolgen mit den Vergleichsoperatoren. | ||
+ | |||
+ | <code cpp> | ||
+ | void iterator_demo(Container const& c) // vector< | ||
+ | { | ||
+ | Container:: | ||
+ | Container:: | ||
+ | Container:: | ||
+ | if (n > 0) | ||
+ | { | ||
+ | last = first + n/2; | ||
+ | Container:: | ||
+ | } | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | ==== Reverse-Iteratoren ==== | ||
+ | Rückwärts-Iteratoren '' | ||
+ | laufen in umgekehrter Richtung über einen Bereich. | ||
+ | Mit ihrer Hilfe ist es problemlos möglich, | ||
+ | die Verarbeitungsreihenfolge umzukehren, | ||
+ | ohne neue Algorithmen implementieren zu müssen. | ||
+ | Jedes Weitersetzen wird einfach in ein Zurücksetzen umgedeutet. | ||
+ | Wegen der " | ||
+ | jedoch um ein Element verschoben. | ||
+ | |||
+ | <code cpp> | ||
+ | | ||
+ | | ||
+ | | ||
+ | [.......................] | ||
+ | ^ : ^ : | ||
+ | | : | ||
+ | | ||
+ | | ||
+ | </ | ||
+ | Mit '' | ||
+ | |||
+ | ==== Iterator-Adapter ==== | ||
+ | Iterator-Adapter vereinheitlichen | ||
+ | Einfügen, Ein- und Ausgaben unter Ausnutzung der Zeigerschreibweise. | ||
+ | So verallgemeinert, | ||
+ | Anwendung des Kopier-Algorithmus '' | ||
+ | |||
+ | <code cpp> | ||
+ | while (first != last) *insert++ = *first++; | ||
+ | while (input != ende) *output++ = *input++; | ||
+ | </ | ||
+ | Einfüge-Iteratoren sind Iterator-Adapter, | ||
+ | mit denen das Zuweisen von Werten | ||
+ | in ein Einfügen in einen Container umgedeutet wird: | ||
+ | |||
+ | <code cpp> | ||
+ | void inserter_demo(Container const& c) | ||
+ | { | ||
+ | Container:: | ||
+ | Container c2; | ||
+ | Container:: | ||
+ | |||
+ | std:: | ||
+ | std:: | ||
+ | std:: | ||
+ | |||
+ | *hier = wert; // c2.insert(position, | ||
+ | *vorn = wert; // c2.push_front(wert); | ||
+ | *hinten = wert; // c2.push_back(wert); | ||
+ | } | ||
+ | </ | ||
+ | Mit den Inserter-Funktionen ist es einfach, einen Bereich an einen Container anzuhängen: | ||
+ | |||
+ | <code cpp> | ||
+ | std:: | ||
+ | </ | ||
+ | Ausgabestrom-Iteratoren geben Elemente aus, auch direkt aus Algorithmen heraus: | ||
+ | |||
+ | <code cpp> | ||
+ | std:: | ||
+ | std:: | ||
+ | </ | ||
+ | Eingabestrom-Iteratoren passen Eingabeströme an das Zeigerkonzept an. | ||
+ | Das Einlesen von Elementen ist auch in Algorithmen möglich. | ||
+ | |||
+ | <code cpp> | ||
+ | double summe = 0.0; | ||
+ | std:: | ||
+ | std:: | ||
+ | |||
+ | while (input != ende) // summe = std:: | ||
+ | { | ||
+ | summe += *input; | ||
+ | ++input; | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | ===== Hilfsmittel ===== | ||
+ | < | ||
+ | |||
+ | Nur die [[# | ||
+ | '' | ||
+ | die restlichen sind daraus herleitbar. | ||
+ | Für beliebige Wertpaare gibt es den Behälter [[# | ||
+ | [[# | ||
+ | (Stapel und Warteschlangen) sowie | ||
+ | [[# | ||
+ | ergänzen die Standard Template Library. | ||
+ | |||
+ | |||
+ | ==== Vergleichsoperatoren ==== | ||
+ | Um Vergleiche von Objekten selbstdefinierter Typen vorzunehmen, | ||
+ | genügt es, ''<'' | ||
+ | |||
+ | | Operation | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | |||
+ | Um diese Äquivalenzen zu nutzen, | ||
+ | muss man lediglich die Schablonen | ||
+ | des Namensbereiches '' | ||
+ | |||
+ | <code cpp> | ||
+ | #include < | ||
+ | using namespace std:: | ||
+ | </ | ||
+ | Für die Vergleichsoperatoren wurde ein Unternamensraum von '' | ||
+ | um Mehrdeutigkeiten oder falsche Operator-Aufrufe zu vermeiden. | ||
+ | |||
+ | ==== Paare ==== | ||
+ | Paare von Werten unterschiedlichster Typen | ||
+ | kommen an verschiedenen Stellen in der Standardbibliothek vor, | ||
+ | z.B. als Elemente '' | ||
+ | eines [[.: | ||
+ | aber auch als Rückgabewert des Algorithmus [[.: | ||
+ | |||
+ | <code cpp> | ||
+ | template <class Typ1, class Typ2> | ||
+ | struct pair | ||
+ | { | ||
+ | Typ1 first; | ||
+ | Typ2 second; | ||
+ | // ... Konstruktoren, | ||
+ | }; | ||
+ | </ | ||
+ | Zwei Paare sind gleich, wenn beide Bestandteile gleich sind. | ||
+ | Die Sortierung von Paaren erfolgt zuerst nach der Komponente '' | ||
+ | bei wertgleicher Komponente '' | ||
+ | |||
+ | ==== Container-Adapter ==== | ||
+ | < | ||
+ | < | ||
+ | |||
+ | <code cpp> | ||
+ | push(x) | ||
+ | <-- [...............] < | ||
+ | | ||
+ | | ||
+ | </ | ||
+ | Stapel '' | ||
+ | und Warteschlangen '' | ||
+ | sind Container-Adapter. | ||
+ | Ihre Funktionalität kann von einem beliebigen Container geliefert werden, | ||
+ | der aber vom Adapter vollständig umhüllt wird. | ||
+ | Der Standard-Containertyp ist [[.: | ||
+ | |||
+ | Prioritätswarteschlangen '' | ||
+ | ordnen Elemente mit großen Werten (=Prioritäten) so ein, | ||
+ | dass sie zuerst wieder herauskommen. | ||
+ | Fehlen Angaben zum Containertyp bzw. zum Vergleichskriterium, | ||
+ | werden [[.: | ||
+ | bzw. [[# | ||
+ | |||
+ | Die Container-Adapter besitzen neben Konstruktor und Vergleichen nur wenige Methoden. | ||
+ | |||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | |||
+ | <code cpp> | ||
+ | void umstapeln(std:: | ||
+ | { | ||
+ | std:: | ||
+ | |||
+ | while (!s.empty() && !q.full()) | ||
+ | { | ||
+ | q.push( s.top() ); | ||
+ | s.pop(); | ||
+ | } | ||
+ | while (!q.empty()) | ||
+ | { | ||
+ | std::cout << q.front() << ' | ||
+ | q.pop(); | ||
+ | } | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | ==== Funktionsadapter ==== | ||
+ | < | ||
+ | |||
+ | Funktionen, die als Wahrheitswert liefern, | ||
+ | ob eine Bedingung erfüllt ist, werden Prädikate genannt. | ||
+ | Erwarten Algorithmen Funktionen als Parameter, | ||
+ | müssen das nicht unbedingt Funktionen sein. | ||
+ | Es kann sich auch um Objekte handeln, | ||
+ | die die Schnittstelle einer Funktion besitzen. | ||
+ | Dazu sind bei diesen Objekten die | ||
+ | [[.: | ||
+ | '' | ||
+ | |||
+ | Neben Prädikaten definiert die Standardbibliothek | ||
+ | auch arithmetische Funktionsobjekte (Funktoren). | ||
+ | Die Funktoren '' | ||
+ | sind einstellig, d.h. sie verarbeiten nur ein Argument. | ||
+ | Die anderen Funktoren sind zweistellig. | ||
+ | |||
+ | | Arithmetik-Funktoren | Vergleichsprädikate | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | | '' | ||
+ | |||
+ | Für [[# | ||
+ | Prädikattyp die Sortierreihenfolge fest. [[begriffe# | ||
+ | |||
+ | <code cpp> | ||
+ | std:: | ||
+ | </ | ||
+ | An [[# | ||
+ | werden Funktoren als Objekt übergeben (deshalb mit Klammern): | ||
+ | |||
+ | <code cpp> | ||
+ | std:: | ||
+ | </ | ||
+ | |||
+ | Polymorphe Funktionsadapter '' | ||
+ | nehmen sowohl Funktoren, Funktionszeiger als auch [[.: | ||
+ | Ob ihnen ein Wert zugewiesen wurde, kann vor dem Aufruf geprüft werden: | ||
+ | |||
+ | <code cpp> | ||
+ | std:: | ||
+ | f = [](double x) { return std:: | ||
+ | if (f) std::cout << f(1) << ' | ||
+ | </ | ||
+ | |||
+ | Binder [[.: | ||
+ | koppeln die Parameter eines Funktors '' | ||
+ | an Werte, Referenzen [[.: | ||
+ | oder Ergebnisse anderer Binder-Funktoren. | ||
+ | <code cpp> | ||
+ | using namespace std:: | ||
+ | std:: | ||
+ | | ||
+ | | ||
+ | </ | ||
+ | ==== Platzhalter ==== | ||
+ | |||
+ | Die im besonderen Namensraum definierten '' | ||
+ | leiten das erste, zweite, ... Argument des Binderaufrufs weiter an die angegebene Position. | ||
+ | In funktionalen Sprachen wird die Reduktion der Parameteranzahl (bis auf einen) als [[wpde> | ||
+ | |||
+ | Negierer kehren die Ergebniswerte eines Prädikates um. | ||
+ | Die Funktionen '' | ||
+ | erstellen Negierer für ein- bzw. zweistellige Prädikate. | ||
+ | Um alle Elemente zu zählen, die nicht größer als 20 sind, könnte man schreiben: | ||
+ | |||
+ | <code cpp> | ||
+ | std:: | ||
+ | int n = std:: | ||
+ | </ | ||
+ | |||
+ | Methoden von Objekten werden eingekapselt, | ||
+ | damit die korrekte (möglicherweise virtuelle) Methode | ||
+ | mit den richtigen Objektzeigern bzw. -referenzen aufgerufen wird. | ||
+ | Für Objektzeiger liefert '' | ||
+ | |||
+ | <code cpp> | ||
+ | void zeichnen(std:: | ||
+ | { | ||
+ | std:: | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | ==== Referenzwrapper ==== | ||
+ | |||
+ | Mit den von den Hilfsfunktionen '' | ||
+ | lässt sich ein Multi-Index-Zugriff auf Datenmengen verwirklichen: | ||
+ | <code cpp> | ||
+ | #include < | ||
+ | #include < | ||
+ | #include < | ||
+ | #include < | ||
+ | #include < | ||
+ | |||
+ | int main() | ||
+ | { | ||
+ | std:: | ||
+ | std:: | ||
+ | std:: | ||
+ | |||
+ | unsigned seed = std:: | ||
+ | shuffle (begin(v), end(v), std:: | ||
+ | std:: | ||
+ | |||
+ | for (int n: o) std::cout << n << ' '; std::cout << " | ||
+ | for (int n: v) std::cout << n << ' '; std::cout << " | ||
+ | for (int n: p) std::cout << n << ' '; std::cout << " | ||
+ | return 0; | ||
+ | } | ||
+ | </ | ||
kennen/stl.txt · Zuletzt geändert: 2020-07-27 10:02 von 127.0.0.1