Sortierte Assoziativ-Container
Assoziativ-Container erlauben den schnellen Zugriff auf Elemente über einen frei wählbaren Schlüssel (key). Die in Assoziativ-Containern abzulegende Elemente müssen sortierbar sein und das Sortierkriterium muss der 'strict weak ordering' Bedingung genügen:
- wenn x<y true ist, dann muss y<x false sein
- wenn x<y true und y<z true ist, dann muss ebenfalls x<z true sein
- x<x muss immer false sein
Und auch für die assoziativen Container gelten weiterhin die Aussagen des Kapitels Gemeinsame Container-Eigenschaften und -Operationen.
Containertypen
set und multiset
Einzubindende Header-Datei: set
set bzw. multiset definieren einen sortierten Container, der nur aus einen Schlüssel besteht. Der Unterschied zwischen einem set und einem multiset besteht darin, dass in einem set ein Schlüssel nur einmal vorhanden sein darf, während ein multiset mehrere gleiche Schlüssel zulässt.
C++23 definiert zwei neu set-Typen: flat_set und flat_multiset. Der Unterschied zwischen set- und flat-Containern besteht darin, dass die flat-Container ihre Elemente kontinuierlich im Speicher ablegen und die set-Container nicht. Da zum Zeitpunkt der Erstellung des Tutorials noch nicht alle Compiler die neuen Typen unterstützt, wird darauf nicht weiter eingegangen.
map und multimap
Einzubindende Header-Datei: map
map bzw. multimap definieren einen sortierten Container, der außer einem Schlüssel ein zusätzliches beliebiges Datum enthält. Der Unterschied zwischen einer map und einer multimap besteht, genauso wie beim set, darin, dass in einer map der Schlüssel nur einmal vorhanden sein darf, während eine multimap mehrere gleiche Schlüssel zulässt.
Auch hierfür definiert C++23 zwei neu map-Typen: flat_map und flat_multimap. Da zum Zeitpunkt der Erstellung des Tutorials ebenfalls fast kein Compiler die neuen Typen unterstützt, wird darauf nicht weiter eingegangen.
Objekte definieren
Objekte vom Typ eines Assoziativ-Containers werden wie nachfolgend aufgeführt definiert. cont gibt den Containertyp an und KVTYP den Datentyp der im Container abzulegenden Elemente. Bei einem set oder multiset enthält KVTYP den Datentyp des Schlüssels und bei einer map oder multimap die Datentypen für den Schlüssel und das Datum.
cont<KVTYP> obj;
Container ohne Elemente (leerer Container).
cont<KVTYP> obj(iiter first, iiter last);
Kopiert die Daten aus dem Bereich [first...last) in den Container. Für die Bereichsangabe können sowohl Zeiger wie auch Iteratoren verwendet werden. Enthält der zu kopierende Bereich bei einem Set bzw. einer Map mehrere gleiche Schlüssel, ist nicht definiert, welcher Schlüssel übernommen wird.
cont<KVTYP> obj(const cont<KVTYP>& other);
Kopiert den Inhalt des Containers other in den Container.
cont<KVTYP> obj(ilist args);
Kopiert die Initialisiererliste args in den Container.
// double Feld definieren/initialisieren
double initArray[3] {1.11,2.22,3.33};
// Leere map mit int als Schluessel/float als Datum
std::map<int,float> floatMap;
// double set mit Inhalt von double Feld initialisieren
std::set<double> dblSet (initArray, initArray+3);
// Multimap mit int als Schluessel/CData4-Objekt als Datum
// und mit Initialisererliste initialisieren
std::multimap<int,CData4> demoMMap
{{1,CData4{"eins"s}},{2,CData4{"zwei"s}},
{3,CData4{"drei"s}},{4,CData4{"vier"s}}};Standardmäßig werden die Elemente in einem Assoziativ-Container aufsteigend sortiert. Um die Elemente anderweitig zu sortieren, kann als zusätzliches Template-Argument bei der Definition eines Objekts ein binäres Predicate angegeben werden. Das Predicate erhält als Parameter die zu vergleichenden Elemente per const-Referenz übergeben. Liefert das Predicate true zurück, wird das im ersten Parameter übergebene Datum vor dem im zweiten Parameter übergebenen Datum eingefügt.
#include <set>
#include <print>
// Klasse für Vergleich,
// hier einmal ein struct als Template
template <typename T>
struct Compare
{
// Vergleichsfunktion als Predicate
// sortiert hier nach fallenden Werten
bool operator() (const T& elem1, const T& elem2) const
{
return elem1>elem2;
}
};
int main()
{
// set mit Init-Liste initialisieren
// und fallend sortieren
// Inhalt des set: 4,3,2,1
std::set<int, Compare<int>> setObj {1,4,2,3};
// Set ausgeben
for (auto elem: setObj)
std::print("{},",elem);
}
4,3,2,1,
Container und Iteratoren
Auf die Elemente eines Assoziativ-Containers kann über bidirektionale Iteratoren zugegriffen werden. Zu beachten ist, dass bei einer map bzw. multimap der Iterator auf ein pair-Element verweist, dessen Member first den Schlüssel enthält und second das Datum.
#include <print>
#include <set>
#include <map>
#include <string>
using namespace std::string_literals;
import CData4;
int main()
{
// int-Set definieren/initialiseren
std::set<int> intSet {11,22,4,8,12};
// Map definieren/initialsieren mit
// int als Schluessel und Demo-Objekt als Datum
std::multimap<int,CData4> demoMap
{{1,CData4{"eins"s}},{2,CData4{"zwei"s}},
{3,CData4{"drei"s}},{4,CData4{"vier"s}}};
// set rueckwaerts durchlaufen
for (auto iter=intSet.rbegin();
iter != intSet.rend(); ++iter)
std::print("{}, ",*iter);
std::println("");
// Iterator auf map definieren
auto iter = demoMap.begin();
// und auf 3. Element verweisen
++iter; ++iter;
std::println("{}:{}\n", iter->first, iter->second);
}22, 12, 11, 8, 4,
3:drei
Elemente einfügen und löschen
Einfügen
Das Einfügen von Elementen in einen assoziativen Container erfolgt immer über den Schlüssel und nicht, wie bei den sequenziellen Containern, über eine Positionsangabe.
Wenn nicht anders angegeben, gelten die nachfolgenden Methoden für alle assoziativen Container.
std::pair<iter,bool> insert (const KVTYP& value);
Fügt in ein Set oder einer Map das Datum value ein. Die Methode liefert ein pair-Objekt zurück, das im bool-Element second den Erfolg oder Misserfolg der Einfügeoperation enthält. Das pair-Element first enthält einen Iterator auf das eingefügte bzw. auf ein bereits vorhandenes Element.
iter insert (const KVTYP& value);
Fügt in ein Multiset oder einer Multimap das Datum value ein. Als Returnwert liefert die Methode einen Iterator auf das eingefügte Element.
iter insert (citer pos, const KVTYP& value);
Fügt das Datum value so nahe wie möglich vor der Position pos ein. Die Sortierung des Containers bleibt dabei stets erhalten. Als Returnwert liefert die Methode einen Iterator auf das eingefügte Element. Ist in einem Set bzw. einer Map das einzufügende Datum bereits vorhanden, verweist der Iterator auf das vorhandene Element.
void insert (iter first, iter last);
Fügt die Elemente aus dem Bereich [first...last) in den Container ein. Enthält der Bereich mehrere gleichwertige Elemente, ist bei einem Set oder einer Map nicht definiert, welches Element eingefügt wird.
void insert (ilist args);
Fügt die Elemente der Initialisiererliste args in den Container ein. Enthält die Initialisiererliste mehrere gleichwertige Elemente, ist bei einem Set oder einer Map nicht definiert, welches Element eingefügt wird.
pair<iter, bool> insert_or_assign(const KTYP& key, DTYP value);
Weist bei einer Map das Datum value dem Element mit dem Schlüssel key zu. Enthält die Map kein Element mit dem Schlüssel key, wird ein neues Element mit dem Schlüssel key und dem Datum value in die Map eingefügt. Als Returnwert liefert die Methode ein pair-Objekt. Ist dessen bool-Element second true, wurde ein neues Element in die Map eingefügt, anderenfalls wurde das Datum value einem bestehenden Schlüssel zugewiesen. Das pair-Element first enthält einen Iterator auf das eingefügte Element.
std::pair<iter,bool> emplace (plist args);
Erstellt ein Objekt und fügt es in ein Set oder eine Map ein. args ist eine Auflistung mit den Parametern des Konstruktors eines einzufügenden Objekts. Die Methode liefert ein pair-Objekt zurück, das im bool-Element second den Erfolg oder Misserfolg der Einfügeoperation enthält. Das pair-Element first enthält einen Iterator auf das eingefügte bzw. auf das vorhandene Element.
iter emplace (plist args);
Erstellt ein Objekt und fügt es in ein Multiset oder eine Mulitmap ein. args ist eine Auflistung der Parameter des Konstruktors eines einzufügenden Objekts. Die Methode liefert einen Iterator auf das eingefügte Element.
iter emplace_hint (citer pos, plist args);
Erstellt ein Objekt und fügt es so nahe wie möglich vor der Position pos ein. args ist eine Auflistung der Parameter des Konstruktors eines einzufügenden Objekts. Als Returnwert liefert die Methode einen Iterator auf das eingefügte Element. Ist das einzufügende Datum in einem Set bzw. einer Map bereits vorhanden, verweist der Iterator auf das vorhandene Element.
pair<iter, bool> try_emplace (const DTYP& key, plist args);
Erstellt ein Objekt und fügt es in die Map mit dem Schlüssel key ein. args ist eine Auflistung der Parameter des Konstruktors eines einzufügenden Objekts. Die Methode liefert ein pair-Objekt zurück, das im bool-Element second den Erfolg oder Misserfolg der Einfügeoperation enthält. Das pair-Element first enthält einen Iterator auf das eingefügte bzw. auf das bereits vorhandene Element.
iter try_emplace (iter pos, const DTYP& key, plist args);
Erstellt ein Objekt und fügt es so nahe wie möglich vor der Position pos in die Map mit dem Schlüssel key ein. args ist eine Auflistung der Parameter eines Konstruktors des einzufügenden Objekts. Als Returnwert liefert die Methode einen Iterator auf das eingefügte Element. Ist das einzufügende Datum in der einer Map bereits vorhanden, verweist der Iterator auf das vorhandene Element.
#include <print>
#include <set>
#include <map>
#include <string>
#include <cstdlib>
using namespace std::string_literals;
import CData4;
int main()
{
// Set definieren
std::set<int> mySet;
// 4 Elemente einfügen
for (auto index=0; index<4; index++)
{
auto success = mySet.insert(std::rand()%10);
// Abprüfen ob Element eingefügt wurde
// !!! Alternativ mit Structured Binding !!!
// if (auto [pos,success] = mySet.insert(value); !success)
if (!success.second)
{
std::println("Fehler beim Einfuegen!");
exit(1);
}
}
// Set ausgeben
for (auto elem: mySet)
std::print("{}, ",elem);
std::println("");
// Multimap definieren
using mmType = std::multimap<int, std::string>;
mmType myMap;
// Neue Elemente mittels pair einfügen
myMap.insert(std::pair<int,std::string>(10,"zehn"s));
myMap.insert(make_pair(11,"elf"s));
myMap.insert(mmType::value_type(9,"neun"s));
// Neue Elemente mittels Init-Liste einfügen
myMap.insert({13,"dreizehn"s});
// Neues Element mittels emplace erstellen und einfügen
myMap.emplace(8,"acht"s);
// Multimap ausgeben
for (auto [key,value]: myMap)
std::println("key: {}, value: {}",key,value);
std::println("");
}0, 1, 4, 7,
key: 8, value: acht
key: 9, value: neun
key: 10, value: zehn
key: 11, value: elf
key: 13, value: dreizehn
Es gibt noch weitere Methoden zum Einfügen, die als Parameter einen node_type besitzen. Diese Methoden erlauben das Verschieben von Elementen zwischen zwei assoziativen Container, ohne dass dafür Kopier- oder Verschiebeoperationen ausgeführt werden.
Löschen
Das Löschen von Elementen in assoziativen Containern kann entweder über einen Iterator oder über den Schlüssel erfolgen.
iter erase (iter pos);
Löscht das Element auf das der Iterator pos verweist. Als Rückgabewert liefert die Methode einen Iterator auf das nächste nach dem gelöschten Element folgende Element.
size_type erase (const DTYP& key);
Löscht alle Elemente mit dem Schlüssel key und liefert die Anzahl der gelöschten Elemente zurück.
iter erase (citer first, citer last);
Löscht alle Elemente im Bereich [first...last). Als Rückgabewert liefert die Methode einen Iterator auf das nach dem letzten gelöschten Element folgende Element.
Weitere Methoden
void clear();
Löscht alle Elemente im Container.
void swap (CTYP& other);
Vertauscht den Inhalt von zwei Containern. Die zu vertauschenden Container müssen den gleichen Datentyp besitzen, können aber eine unterschiedliche Anzahl von Elementen haben.
Elementzugriff
Ein Set oder Multiset erlaubt keinen direkten Zugriff auf die Elemente. Es kann nur sequenziell mit einem bidirektionalen Iterator oder einer range-for-Schleife auf die Elemente zugegriffen werden, so wie im vorherigen Beispiel aufgeführt. In der Regel aber wird auf die Elemente eines Sets über die im Anschluss beschriebenen Suchfunktionen zugegriffen.
Auf die Elemente in einer Map oder Multimap kann ebenfalls mit einem Iterator oder einer range-for-Schleife zugegriffen werden. Wird über einen Iterator auf die Elemente in einer Map zugegriffen, ist der Rückgabewert ein pair vom Typ pair<const key,value>. Über den Iterator kann das Datum verändert werden aber nicht der Schlüssel, da dies die Sortierung der Map durcheinanderbringen würde. Hauptsächlich erfolgt der Zugriff auf eine Map jedoch über deren Schlüssel.
DTYP& at (const KTYP& key);
Liefert eine Referenz auf das zum Schlüssel key gehörige Datum. Enthält die Map keinen Schlüssel key, wird eine out_of_range Ausnahme ausgelöst.
DTYP& operator[] (const KTYP& key);
Liefert eine Referenz auf das zum Schlüssel key gehörige Datum.
Wird beim indizierten Schreiben eines Datums ein nicht vorhandener Schlüssel angegeben, wird ein neues Element mit diesem Schlüssel erzeugt und in die Map eingefügt (siehe Zeile 10 im folgenden Beispiel). Wird beim indizierten Auslesen eines Elements ein nicht vorhandener Schlüssel angegeben, wird ebenfalls ein neues Element erstellt und mit seinem Standardkonstruktor initialisiert.
#include <print>
#include <map>
using namespace std::string_literals;
int main()
{
// Map definieren, string ist Schlüssel und int das Datum
std::map<std::string,int> myMap;
// Neuen Eintrag in Map erstellen
myMap["KEY"] = 10;
// Datum auslesen
std::println("Datum[KEY]: {}",myMap["KEY"]);
try
{
// Zugriff mittels at()
// löst eine Ausnahme aus falls "NKEY" nicht vorhanden
std::println("Datum[NKEY]: {}",myMap.at("NKEY"));
}
catch(const std::exception& ex)
{
std::println("Fehler: {}",ex.what());
}
}Datum[KEY]: 10
Fehler: map::at
Suchen in Container
Alle Assoziativ-Container sind daraufhin optimiert, um Daten schnell über einen Schlüssel zu finden.
size_type count (const KTYP& key);
Liefert die Anzahl der Elemente mit dem Schlüssel key zurück. Bei einem set oder einer map liefert die Methode entweder 0 oder 1 zurück.
iter find (const KTYP& key);
Sucht nach dem (ersten) Element mit dem Schlüssel key und liefert einen Iterator darauf zurück. Ist das gesuchte Element nicht im Container vorhanden, verweist der zurückgelieferte Iterator auf die Position end().
iter lower_bound (const DKEY& key);
iter upper_bound (const DKEY& key);
Sucht nach dem Element, dessen Schlüssel nicht kleiner bzw. größer als key ist und liefert einen Iterator darauf zurück.
bool contains (const DKEY& key);
Liefert true zurück wenn ein Element mit dem Schlüssel key existiert.
std::pair<iter,iter> equal_range (const DKEY& key);
Ist die Kombination aus lower_bound() und upper_bound() und liefert die beiden Iteratoren in einem pair zurück.
#include <print>
#include <set>
using namespace std::string_literals;
int main()
{
std::multiset<int> mySet{1,2,2,4,5,10,11};
std::print("Set: ");
for (auto elem: mySet)
std::print("{}, ",elem);
// Erstes Element suchen dessen Schluessel >= 3 ist
auto liter = mySet.lower_bound(3);
std::println("\nlower_bound(3): {}",*liter);
// Element suchen, dessen Schluessel > 10 ist
auto uiter = mySet.upper_bound(10);
std::println("upper_bound(10): {}",*uiter);
// Liefert Iterator auf Schluessel 2 und 4 zurueck
auto [lower,upper] = mySet.equal_range(2);
std::println("equal_range(2): {},{}",*lower, *upper);
}Set: 1, 2, 2, 4, 5, 10, 11,
lower_bound(3): 4
upper_bound(10): 11
equal_range(2): 2,4
Containerkapazität
Folgende Methoden liefern Informationen über die Größe eines Containers:
bool empty();
Liefert true zurück, wenn der Container keine Elemente enthält.
size_type max_size();
Liefert die maximal mögliche Anzahl von Elementen im Container zurück.
size_type size();
Liefert die Anzahl der im Container abgelegten Elemente zurück.
Übungen
scont3_01:
Es ist die Anzahl der unterschiedlichen Wörter in einer Datei zu zählen, unabhängig von ihrer Groß-/Kleinschreibung. Für die Konvertierung von Großbuchstaben in Kleinbuchstaben kann die Bibliotheksfunktion
int tolower (int ch);
verwendet werden, die in der Header-Datei cctype deklariert ist. Als Returnwert liefert die Funktion den Kleinbuchstaben des übergebenen Buchstabens ch.
tolower() konvertiert nicht die deutschen Umlaute. Hierfür ist eine andere Funktion zu verwenden, die die aktuelle Spracheinstellung bzw. das Format einer Datei (UTF-8, UTF-16,..) mit auswertet.
Lesen Sie aus der Datei cont3.txt alle Wörter ein und speichern sie ab. Eventl. Satzzeichen sind zu ignorieren.
Geben Sie alle gefundenen Wörter aus.
Anschließend sind alle Wörter die mit einem 'd' beginnen zu suchen und auszugeben sowie die Gesamtzahl der gefunden Wörter.
In der Datei enthaltene Worte:
aktuellen, angegebenen, auf, aufbauen, aufeinander, aufgeteilt,
...
Alle Woerter mit dem Buchstaben 'd':
das,dem,den,der,die,dieses,durchlesen,
Anzahl der Woerter (ohne Duplikate): 40
scont3_02:
In dieser Übung geht es darum, eine Klasse zur Verwaltung von Adressdaten zu vervollständigen. Eine Adresse bestehen aus einem Namen, einer Telefon-Nummer und einer E-Mail-Adresse. Alle Adressdaten liegen als Strings vor.
Die Schnittstelle der Klasse ist vorgegeben, d.h. Sie müssen die Methoden nur noch implementieren und den Container für die Datenablage festlegen.
Da häufig Änderungen/Erweiterungen am Adressbuch vorgenommen werden, sollten die Adressdaten in einem entsprechenden Container abgelegt werden. Doppelte Adressen sind nicht zugelassen. Als Kriterium hierfür dient der Name.
Vervollständigen Sie die Methoden der Klasse AddressBook. An der main() Funktion sind keine Änderungen vorzunehmen.
#include <print>
#include <string>
// Adressbuch
// Eine Adresse besteht aus einem Namen, einer Telefonnr.
// und einer EMail-Adresse. Doppelte Namen sind nicht
// zulaessig
class AddressBook
{
// ??? Container fuer Adressebuch definieren
public:
// ctor
AddressBook() = default;
// dtor
~AddressBook() = default;
// Neue Adresse aufnehmen
void Insert(std::string_view name, std::string_view phone,
std::string_view email)
{
// ??? Neue Adresse ins Adressbuch aufnehmen
}
// Gibt einzelne Adresse aus
void PrintAddress(std::string_view name) const
{
// ??? Zum Parameter name gehoerige Adressdaten ausgeben
}
// Aendert Adressbuch-Eintrag
bool Update(std::string_view name, std::string_view phone,
std::string_view email)
{
// ??? Zum Parameter name gehoerige Adressdaten ueberschreiben
}
// Adresse entfernen
void Remove(std::string_view name)
{
// ??? Zum Parameter name gehoerige Adresse loeschen
}
// Ausgabe des gesamten Buches
void PrintBook()
{
// ??? Alle gespeicherten Adressdaten ausgeben
}
};
int main()
{
// Adressbuch dynamisch anlegen
AddressBook *pAddr = new AddressBook;
// Einige Eintraege hinzufuegen
pAddr->Insert("Emil Maier", "0111/4545", "emai@sonst.net");
pAddr->Insert("Agathe Maier", "0111/4545", "agma@sonst.net");
pAddr->Insert("Franzi Lehmann", "08888/1234", "fral@kostnix.de");
pAddr->Insert("Gustav Schulze", "09999/1111", "gusch@lucky.com");
// Komplettes Adressbuch ausgeben
std::println("Inhalt Adressbuch:");
pAddr->PrintBook();
// Einen Eintrag abaendern
std::println("\nAendere Telefon-Nummer von Gustav Schulze:");
// Und geaenderten Eintrag ausgeben
if (!pAddr->Update("Gustav Schulze", "09999/7777",
"gusch@lucky.com"))
std::println("Aenderung fehlgeschlagen!");
else
{
std::println("Neuer Eintrag ist:");
pAddr->PrintAddress("Gustav Schulze");
}
// Eintrag entfernen
std::println("\nEntferne Franzi Xelsbrot:");
pAddr->Remove("Franzi Xelsbrot");
// Nochmals komplettes Adressbuch ausgeben
std::println("\nNeuer Inhalt Adressbuch:");
pAddr->PrintBook();
// Adressbuch loeschen
delete pAddr;
}Inhalt Adressbuch:
Name: Agathe Maier
Tel.: 0111/4545, EMail: agma@sonst.net
Name: Emil Maier
Tel.: 0111/4545, EMail: emai@sonst.net
Name: Franzi Lehmann
Tel.: 08888/1234, EMail: fral@kostnix.de
Name: Gustav Schulze
Tel.: 09999/1111, EMail: gusch@lucky.com
Aendere Telefon-Nummer von Gustav Schulze:
Neuer Eintrag ist:
Name: Gustav Schulze
Tel.: 09999/7777, EMail: gusch@lucky.com
Entferne Franzi Xelsbrot:
Franzi Xelsbrot nicht im Adressbuch vorhanden!
Neuer Inhalt Adressbuch:
Name: Agathe Maier
Tel.: 0111/4545, EMail: agma@sonst.net
Name: Emil Maier
Tel.: 0111/4545, EMail: emai@sonst.net
Name: Franzi Lehmann
Tel.: 08888/1234, EMail: fral@kostnix.de
Name: Gustav Schulze
Tel.: 09999/7777, EMail: gusch@lucky.com
scont3_03:
Schreiben Sie ein Programm zur Verwaltung eines Aktiendepots. Da häufig im Depot nach einer Aktie gesucht wird, ist für das Depot ein entsprechender Container zu verwenden.
Ein Eintrag im Aktiendepot besteht aus dem Namen der Aktie und dem aktuellen Kurs. Der Aktienname ist als string abzulegen und der Kurs als float-Wert.
Fügen Sie folgende Aktien sowie deren Kurs zum Aktiendepot hinzu:
VW, 12.00 EUR
Ford, 34.45 EUR
BMW, 54.45 EUR
Daimler Chrysler, 123.50 EUR
Geben Sie den Inhalt des Aktiendepots aus.
Erhöhen Sie den Aktienkurs der VW Aktien um 10.00 EUR und geben Sie die Aktie aus.
Fügen Sie eine Porsche-Aktie mit einem Kurswert von 560.00 EUR hinzu.
Benennen Sie in Aktiendepot die Aktie Daimler Chrysler in Daimler.
Geben Sie das Aktiendepot nochmals aus.
BMW Aktie: 54.45 EUR
Daimler Chrysler Aktie: 123.50 EUR
Ford Aktie: 34.45 EUR
VW Aktie: 12.00 EUR
-- VW Aktie stiegt um 10.00 EUR --
VW Aktie: 22.00 EUR
-- Porsche Aktien hinzufuegen --
-- Daimler Chrysler in Daimler umbenennen --
BMW Aktie: 54.45 EUR
Daimler Aktie: 123.50 EUR
Ford Aktie: 34.45 EUR
Porsche Aktie: 560.00 EUR
VW Aktie: 22.00 EUR