STL assoziative Container. Teil 6

STL assoziative Container. Teil 6
Bewerten Sie diesen Artikel




c ++ Anfänger, Standard Template Library, assoziative Container STL C ++, pair c ++, Karte<> c ++Alle bisherigen Arten von Behältern (im Detail diskutiert oder erwähnt: Vektor, Liste, und) - Eine konsistente Sammlung, in dem die Elemente sequentiell nacheinander angeordnet, aber sie unterscheiden sich miteinander, um die Elemente zugreifen.

Eine andere große Gruppe von Behältern sind sogenannte assoziative Container, das sind, tatsächlich, Tabellen, Suche nach Werten, die für einige gemacht Schlüssel.

Aber bevor Detaillierung assoziative Container, achten Sie auf eine solche Klasse-Vorlage (в составе STL) wie Paar<>. Dies ist ein ziemlich einfaches Design. Jedes Objekt stellt ein verbundenes Paar von Feldern zuerst und zweite. Bei der Konstruktion von Tabellen (in AWL oder in Ihren eigenen Klassen) Diese Felder können der Schlüssel sein,, und der Wert. Aber wir werden nicht hetzen - eine Klasse-Vorlage Paar<> und kann selbst von Interesse sein, unabhängig von Containern.

Wir können, beispielsweise, bestimmen Klasse 2D-Darstellung von Punkten in der Ebene für eine große Klasse von geometrischen Problemen (файл point.h):

Punkt p(*Dies); Mittel, das schafft eine neue Variable (Objekt) Klasse Punkt, und nannte sie eine Copykonstruktor. Genommen den Wert des aktuellen Objekts zu initialisieren *Dies – wie durch die angezeigte Zeiger Dies. dh. eine neue Variable Punkt p erstellt, als Kopie des aktuellen Objekts. Der Rest von euch allen ist zu verstehen,.

Ergebnis:c ++ Anfänger, Standard Template Library, assoziative Container STL C ++, Paar<> c ++

jetzt, wenn wir sehen,, was eine Klasse-Vorlage Paar<>, wir können zur Übersicht gehen von, Was sind die grundlegenden assoziativen STL-Containern.

Im Gegensatz zu der zuvor diskutierten konsekutiv Behälter, wobei die Lage des Elements durch ihre Position unter anderen Elemente bestimmt, Assoziativ Behälter werden als ein Paar von Elementen gespeichert (Paar<>) <Schlüssel, Bedeutung>. Um die Werte des Elements finden Sie wollen, seinen Schlüssel zu suchen, welche die verschiedensten Typen sein.

Notiz: Wir können davon ausgehen,, in Feld oder Vektor Die Suche ist der Schlüsselindex, die hat immer ganze Zahl Bedeutung. Analog, generic-Typ-Tabelle (hashtable) Karte<>, von denen wir assoziativ starten, kann eingesehen werden, als Array oder Vektor (zur Erleichterung des Verständnisses ). Es kann von jedem indiziert werden (aber immer nur ein) Zufallsschlüssel Typ, Typ: Titel[ 'ein’ ], или Bezahlung[ “Ivanov” ].

Eines der am häufigsten verwendeten ist assoziativ STL Containern Karte<> - Tabelle, ein Array von Paaren <Schlüssel, Bedeutung>, in dem die Suche auf einem Schlüsselelement ausgeführt. Der Schlüssel kann jede Art von komplex, vorausgesetzt, das gibt es für diese Art von Operation Vergleich (Mehr-weniger), oder eine solche Operation durch den Benutzer durchgeführt und festgelegt wird, wenn das Erstellen einer Tabelle. Zur Veranschaulichung der einfachen Anwendung Karte<> Wir verwenden das bereits früher diskutierte Beispiel mit einer Basis von Studenten der Fakultät für Informations:

Ergebnis:c ++ Anfänger, Standard Template Library, assoziative Container STL C ++, pair c ++, Karte<> c ++Selbst eine oberflächliche Beispiel (bis wir gingen tief in die Details der assoziative Container) Es ermöglicht Ihnen, einige Schlussfolgerungen zu sehen und ziehen:

  • Elemente, in dem Tisch platziert, Es ist nicht in der Reihenfolge ihrer Räumlichkeiten platziert (wie mit Vektor oder Liste), und in sortierter Reihenfolge von Schlüsselwert (FIO);

  • Deshalb ist die Datentypschlüssel muss vorhanden sein oder Vergleichsoperation, oder es muss vom Benutzer erstellt werden;

auf die Suche nach (von Schlüssel) assoziative Container eine serielle Suche aller Elemente nicht verwenden, eine hocheffiziente und hoch entwickelte Algorithmen, seit Jahren gearbeitet (und sogar Jahrzehnte) существования STL . Im Allgemeinen implementieren Karte<> gebrauchte Technik der rot-schwarzen Bäume ... aber die Details, die nicht grundlegend. Eine wichtige Schlussfolgerung aus dieser Tatsache sollte die sein, dass die Suche nach assoziativen Containern ist sehr schnell, und es ist viel besser, als wenn man versucht, es manuell zu implementieren.

Newsletter neue Lektionen über die Programmierung:

Öl

Etwa Öl

praktische Erfahrungen über die Softwareentwicklung 40 Jahre. Lehrer Globale Logik internationales Softwareunternehmen. IBM Developer Works Permanent Autor von Publikationen. Wissenschaftliche Herausgeber der Computerliteratur-Verlag "Symbol-Plus", Sankt Petersburg.

Hinterlasse eine Antwort

Platz Code in Tags: <pre class="lang:c ++ dekodieren:true ">DEIN CODE</Vor>