Sortierte Assoziative Container der STL

Sortierte Assoziative Container der STL
FB Informatik
Prof. Dr. R.Nitsch
Ö Elementzugriff O(log2N)
• Speichern die Daten intern in einer Baumstruktur
• Das mathematische Konzept einer Relation oder eine diskrete Abbildung wird mit
map realisiert, das einer Menge mit set
• multimap und multiset erlauben mehrfache identische Schlüssel
Erklärung siehe
STL-Algorithmen
Container
set<T>
Zugriff
O(log N)
Einfügen / Löschen
Beginn Mitte Ende
O(1)
O(1)
O(1)
multiset<T>
O(log N)
O(1)
O(1)
O(1)
map<Key,T>
O(log N)
O(1)
O(1)
O(1)
multimap<Key,T>
O(log N)
O(1)
O(1)
O(1)
Iterator
Iterator-Kategorie
set<T>::iterator
constant bidirectional1)
set<T>::const_iterator
constant bidirectional
multiset<T>::iterator
constant bidirectional1)
multiset<T>::const_iterator
constant bidirectional
map<key,T>::iterator
mutable bidirectional
map<key,T>::const_iterator
constant bidirectional
multimap<Key,T>::const_iterator
mutable bidirectional
multimap<Key,T>::const_iterator
constant bidirectional
1) Microsoft Visual C++ weicht hier vom Standard ab und realisiert "mutable bidirectional" Iteratoren /
05.01.2009
C++ Standard Template Library (STL)
25
Assoziativer Container map
FB Informatik
Prof. Dr. R.Nitsch
• map speichert Paare von Daten und Schlüsseln
Key
Data
• Die Schlüssel sind eindeutig, d.h. es gibt keine 2 Datensätze
mit gleichem Schlüssel (keine Duplikate).
MatrikelNr Sudent
• Die assoziierten Daten werden durch direkte Angabe des
Schlüssels gefunden.
TelNr
Name
• Eine sortierte Anordnung der Schlüssel ist für den assoziativen
Location
Node
Zugriff nicht erforderlich, aber vorteilhaft: Durch sortierte
Anordnung der Schlüssel in map verbessert sich die
Beispiele assoziierter
Zugriffszeit ( O(logN) )
Daten im map-Element
• Der Typ der gespeicherten Elemente ist pair<const Key, T>
– Die Konstanz des Schlüssels gewährleistet, dass er nach dem Einfügen nicht mehr
verändert werden kann. Dies würde die Sortierung zerstören.
• Deklaration der Klasse in der STL
template< class Key,
class T,
class Compare = std::less<Key> >
class map { /*…*/ };
// Typ der Schlüssel
// Typ der Daten
// Typ des Sortierers
// (Key::operator< ist voreingestellt)
Anwendungsbeispiele folgen
05.01.2009
C++ Standard Template Library (STL)
26
Anwendungsbeispiel - Wörterbuch
void main(void) {
map< string, string > dictionary;
FB Informatik
Prof. Dr. R.Nitsch
// Leeres Wörterbuch erzeugen
dictionary.insert(pair<string,string>("Baum","tree"));
// Eintrag aufnehmen
dictionary.insert(pair<string,string>("Auto","car"));
// noch ein Eintrag
cout << dictionary["Baum"] << endl;
// Assoziativer Zugriff
map<string,string>::iterator iter = dictionary.begin();
for( ; iter!=dictionary.end(); ++iter )
cout << (*iter).first << ' ' << (*iter).second << endl;
// Sortierte Ausgabe
}
tree
Auto car
Baum tree
• Falls absteigende Sortierung gewünscht ist:
class Comp {
public: bool operator()(string s1,string s2) { return s2<s1; }
};
void main(void) {
Comp compare;
map<string,string,Comp> dictionary(compare);
// weiter wie oben
}
05.01.2009
C++ Standard Template Library (STL)
// Sortierte Ausgabe
Buch book
Auto car
27
Container map und multimap : Übersicht und Typdefinitionen
FB Informatik
Prof. Dr. R.Nitsch
Typdefinitionen
• map definiert folgende öffentlichen Datentypen
key_type
mapped_type
Typ Key der Schlüsselwerte
Typ T der zugeordneten Werte
value_type
pointer
reference
X::key_compare
Typ der gespeicherten Werte, pair<const Key,T>
entspricht pair<const Key,T>*
entspricht pair<const Key,T>&
Typ des Funktionsobjekts Compare, das die
Sortierreihenfolge der Schlüssel festlegt
Weitere Typen wie Sequenz-Container
…
map-Element
Key
T
value_type
Typ pair<Key,T>
key_type
mapped_type
Fortsetzung des Beispiels:
typedef dient hier der Abkürzung
void main(void) {
// wie bisher
Achtung: Ist die Suche nach dem Schlüssel
typedef map<string,string,Comp> MapType
erfolglos, wird ein neues map-Element für
cout << dictionary.size();
2
diesen Schlüssel angelegt. Die Assoziierten
MapType::key_type key = "Ei";
// Typ ist string
Daten werden mit dem Standardkonstruktor
cout << dictionary[key];
T() erzeugt (hier: string() ).
cout << dictionary.size();
3
dictionary[key] = "egg";
// Schreibender Zugriff auf assoziierte Daten
MapType::mapped_type word;
// Typ ist string Weitere Informationen zum Einfügen, Suchen und
word = dictionary[key];
Löschen von Daten finden Sie hier:
egg
cout << word;
Breymann: C++. S. 516
}
http://www.cplusplus.com/reference/stl/map/
05.01.2009
C++ Standard Template Library (STL)
28
Beispiel: Ein Telefonbuch mit class map
FB Informatik
Prof. Dr. R.Nitsch
typedef map<string,long> PhoneMap;
string ist der key_type und long ist der mapped_type
typedef PhoneMap::value_type MapElement;
MapElement entspricht jetzt pair<string,long>
typedef dient hier der Abkürzung
void main() {
// Einfügen mit operator[ ] und insert:
PhoneMap directory;
directory.insert(MapElement("IRedViel",732457));
directory["HauMich"] = 163248;
directory["BinDumm"] = 843756;
directory.insert(MapElement("IRedViel",732458)); // 2. Telefon; wird nicht ausgeführt, weil Schlüssel
// schon existiert
// immer noch kein 2. Telefon. Überschreibt 1. Nummer
directory["IRedViel"] = 732458;
PhoneMap::const_iter iter = directory.begin();
const_iter weil read-only Zugriff ausreicht
for( ; iter!=directory.end(); ++iter)
// Sortierte Ausgabe:
cout << (*iter).first << ' '
BinDumm 843756 HauMich 163248 IRedViel 732458
<< iter->second << ' ';
// Suchen im Telefonbuch …
string name = "BinLaden";
// Suchen mit operator[ ]:
// O( logN )
long number = directory[name];
// number = 0; Achtung: Suchfehler gibt es hier nicht!! Für "BinLaden"
// existiert jetzt ein Eintrag.
iter = directory.find(name)
// Suchen mit Iterator und find
// O( logN )
if( iter!=directory.end() )
// Prüfen, ob Iterator dereferenzierbar ist
cout << (*iter).second;
// O( 1 )
iterator find(k) liefert Iterator
else
auf gefundenen Eintrag oder "pastcout << name << " hat kein Telefon!" << endl;
the-end" Iterator wenn nicht gefunden
directory.erase(iter); // Leereintrag "BinLaden" wieder löschen
}
void erase(iter) löscht einzelnes Element an Position iter
05.01.2009
C++ Standard Template Library (STL)
29
Sortierter Assoziativer Container multimap
FB Informatik
Prof. Dr. R.Nitsch
• Unterschiede zu map
– Elemente mit identischem Schlüssel (Duplikate) dürfen mehrfach vorkommen. Die
assiziierten Daten dürfen sich dabei durchaus unterscheiden (Beispiel: mehrere
Telefonnummern unter gleichem Namen)
– Es gibt keinen Indexoperator T& operator[ ](const key_type& k)
05.01.2009
C++ Standard Template Library (STL)
30
Sortierter Assoziativer Container set
FB Informatik
Prof. Dr. R.Nitsch
• entspricht der Klasse map, nur dass Schlüssel und Daten zusammenfallen.
• set speichert wie map keine Duplikate
• set hat keinen Indexoperator. Einfügen nur mit insert(key)
• Deklaration der Klasse in der STL
void main(void) {
set<string> names;
// Einfügen mit insert
names.insert("IchSchonWieder");
names.insert("BinSchlau");
names.insert("BinDumm");
set<string>::iterator iter = names.begin(); // Sortierte Ausgabe
for( ; iter!=names.end(); ++iter )
BinDumm BinSchlau IchSchonWieder
cout << *iter << endl;
names.insert("IchSchonWieder");
// Duplikat nicht eingefügt. Wie erkennt man erfolgreiches Einfügen?
pair<SetIter,bool> success;
pair<iterator,bool> insert(key)
success = names.insert("IchSchonWieder");
if(success.second==true)
cout << *(success.first) << " eingefuegt";
Duplikat
else cout << "Duplikat";
31
C++ Standard Template Library (STL)
}05.01.2009
Container set : Übersicht und Typdefinitionen
FB Informatik
Prof. Dr. R.Nitsch
• Deklaration der Klasse in der STL
template< class Key
class Compare = std::less<Key> >
class set { /*…*/ };
// Typ der Schlüssel
// Typ des Sortierers
// (Key::operator< ist voreingestellt)
Definition eines set-Containers: set<Konto> myset;
Typdefinitionen
• set definiert folgende öffentlichen Datentypen
key_type
value_type
pointer
reference
key_compare
…
Typ Key der Schlüsselwerte
auch Typ Key, im Gegensatz zu map
entspricht Key*
entspricht Key&
Typ Compare. Funktionsobjekt, das die
Sortierreihenfolge der Schlüssel festlegt
Weitere Typen wie Sequenz-Container
set-Element
Key
value_type
key_type
Weitere Informationen:
Weitere Informationen zum Einfügen, Suchen und Löschen von Daten finden Sie hier:
http://www.cplusplus.com/reference/stl/set/
Breymann: C++. S. 523
05.01.2009
C++ Standard Template Library (STL)
32