STL Container-Klassen Template-Klasse Eigenschaften

STL Container-Klassen
Template-Klasse
std::vector<T>
std::array<T>
std::list<T>
std::forward_list<T>
Eigenschaften
 Reine Sequenz von Ts;
 Dynamische Größenveränderung
 kein Verwaltungsoverhead
 Anfügen am Ende O(1) (jedoch
Möglichkeit der Reallokation)
 Anfügen am Anfang und in der Mitte in
O(n)
 Indizierung in O(1)
 Random access-iterators
 C++-Version von C-Vektoren
 Feste Größe
 Benötigt keinen dynamischen Speicher
 Doppelt verkettete Liste
 Einfügen am Anfang, in der Mitte und
am Ende in O(1)
 Zusätzlicher Verwaltungsaufwand: 2
Zeiger pro Element
 Keine Indizierung
 Bidirectional iterators
 Einfach verkettete Liste
 Forward iterators
 Rest wie bei list<T>
Voraussetzungen
Standard*
Anwendungsgebiete
 Sortieren
 Binäre Suche
 Heaps
 Stacks
 Listenersatz
Standard*

Ersatz von std::vector, wenn keine
Größenveränderung nötig
Standard*

Stacks und Queues
Standard*

Wie bei list<T>
STL Container-Klassen (C++11-Version)
std::deque<T>
std::set<T>
std::multi_set<T>




std::map<K,V>
std::multi_map<K,V>

std::unordered_set<T>


std::unordered_map<K,V>


std::bit_set<N>


Mischung aus Liste und Vektor
Indizierung in O(1)
Geordneter Binärbaum (Rot-SchwarzBaum)
Suchen, Einfügen und Löschen in O(log
n)
Standard*
Queues
Standard*
Zusätzlich: Definition von
operator< oder
Vergleichsprädikat

Wie set<T>, die Elemente sind jedoch
(Key,Value)-Paare mit einem
funktionalen Zusammenhang zwischen
Key und Value
Hash-Container mit Vektor der Größe m
von einfach verketteten Listen, die die
Elemente halten.
Suchen, Einfügen und Löschen in O(1),
wenn m und n annähernd gleich groß
sind und die Hash-Funktion gut streut.
Iterieren ist langsamer als bei set<T>
Wie hash_set<T>, die Elemente sind
jedoch (Key,Value)-Paare mit einem
funktionalen Zusammenhang zwischen
Key und Value
Menge, bei der jedes Element durch ein
Bit repräsentiert wird.
Feste Größe: N Elemente
Wie bei set<T>

Standard*
Zusätzlich bei
benutzerdefinierten Objekten
vom Type T oder bei
Nichtstandardverhalten:
hash-Funktionsobjekt und
Äquivalenz-Funktionsobjekt für T
Wie hash_set<T>

*T muss zuweisbar und kopierbar sein und einen Default-Konstruktor besitzen.

Mengen, die häufig erzeugt und
wieder gelöscht werden (z.B. in
Schleifen)
Mengen, über die häufig iteriert
wird
Speicherung von SchlüsselWertpaaren

Mengen, in denen häufig gesucht,
eingefügt oder gelöscht wird
Nicht für Mengen, die häufig
erzeugt oder über die häufig
iteriert wird

Wie bei unordered_set<>

Kleine Mengen mit bekannter
Elementanzahl
Hash-Funktionsobjekte für Hash-Container
Hash-Funktionsobjekte sind structs oder classes, die den Funktionsaufrufoperator () überladen. Das Basisformat eines Hash-Objekts HashT für eine
hash_set<T> ist wie folgt:
struct HashT
{
unsigned operator()(const T& x) const
{
unsigned hash_val = hash-Wert für x;
return hash_val;
}
};
Der Typ HashT wird dann als Template-Parameter hinzugefügt:
typedef
std::unordered_set<T,HashT>
HashSetT.
Benötigt das Hash-Funktionsobjekt weitere Informationen (über x hinaus), um Elemente vom Typ T zu hashen, muss HashT diese in Instanzvariablen zugänglich
halten. Konsequenterweise benötigt HashT dann auch einen Konstruktor. Die Instanzvariablen sind dann meist const-Referenzen.
Hash-Container (unordered_set/unordered_map) speichern eine (normalerweise per Default-Konstruktor erzeugte) Instanz von HashT in einer Instanzvariable
und verwenden diese, um die Elemente vom Typ T beim Einfügen und Suchen zu hashen. Hat HashT keinen Defaultkonstruktor (weil die Hash-Funktion externe
Informationen zur Errechnung des Hash-Werts benötigt), muss man sich eines speziellen Konstruktors von unordered_set/unordered_map bedienen:
struct HashT
{
// Konstruktor
HashT(const ExternInfo& _info) : info(_info) {}
unsigned operator()(const T& x) const
{
unsigned hash_val = hash-Wert auf der Basis von x und info;
return hash_val;
}
const ExternInfo& info;
};
typedef unordered_set<T,HashT> HashTSet;
ExternInfo info;
unsigned n = 7853; // Größe der Hash-Tabelle (vorzugsweise eine Primzahl))
// Erzeuge eine Instanz von unordered_set mit einem Hash-Funktionsobjekt ohne Defaultkonstruktor
HashTSet my_hash_set(n,HashT(info));
Vergleichsobjekte
Vergleichsobjekte sind Funktionsobjekte, die die Äquivalenz von zwei Elementen vom Typ T feststellen. Im Prinzip gilt für Vergleichsobjekte das, was zuvor für
Hash-Objekte festgehalten wurde. Logischerweise definiert ein Vergleichsobjekt jedoch den überladenen Funktionsaufrufoperator anders:
struct EquivT
{
bool operator()(const T& x, const T& y) const
{
Vergleiche x und y hinsichtlich Äquivalenz und gib true oder false zurück;
}
};
Der Typ EquivT ist der dritte Template-Parameter von unordered_set/ unordered _map:
typedef unordered_set<T,HashT,EquivT> HashTSet;
Benötigt EquivT wiederum externe Informationen, um die Äquivalenz von x und y zu bestimmen, benötigt man wieder einen speziellen Konstruktor des HashContainers:
ExternInfo info;
unsigned n = 7853; // Größe der Hash-Tabelle (vorzugsweise eine Primzahl))
HashTSet my_hash_set(n, HashT(info), EquivT(info));