stack Container
queue Container
priority_queue Container
bitset Container
Beispiel und Übung
In dieser Lektion werden wir uns vier spezielle Container der Standard Bibliothek ansehen. Die allgemeinen Container, wie z.B. vector, folgen in einer späteren Lektion.
Beginnen werden wir mit dem Container stack. Und wie alle Standard Bibliothek Komponenten liegt auch der stack-Container wieder im Namensraum std. Die explizite Angabe des Namensraums wurde in den folgenden Beispielen der Übersichtlichkeit wegen weggelassen.
Das Einsatzgebiet einer Stack-Klasse sollten Sie aus dem bisherigen Kursverlauf schon kennen, zumal Sie sich in einer der vorangegangen Lektionen auch schon selbst einmal an der Realisierung einer solchen Klasse versuchen konnten. Trotzdem zur Erinnerung noch einmal: eine Stack-Klasse dient zum vorübergehenden Abspeichern von Daten, wobei der zuletzt abgelegte Wert auch wieder als erstes ausgelesen wird. Ein Stack ist also ein LIFO-Speicher (LIFO = last in, first out).
Da wir uns hier mit der Standard Bibliothek befassen, weist der stack Container der Standard Bibliothek gegenüber der Implementierung in einer der vorangegangen Übungen einen wichtigen Unterschied auf: er ist als Template realisiert und damit für alle Datentypen gültig, d.h. der stack Container kann für die Ablage von beliebigen Standard-Datentypen (wie z.B. int oder double) und zur Ablage von Objekten eingesetzt werden. Die einzige 'Einschränkung' besteht darin, dass alle in einem Stack abgelegten Daten den selben Datentyp besitzen müssen.
Für die Verwendung des stack Containers müssen Sie die Datei <stack> einbinden.
|
|
Für die Definition eines Stacks geben Sie zuerst den Container
stack an, gefolgt von einem <...> Klammerpaar.
Innerhalb dieses Klammerpaars steht der Datentyp der Daten, die im
Container abgelegt werden sollen. Im Anschluss daran folgt der Name des
Stack-Containers.
 // stack für ints definieren stack<int> intStack; // stack für Objekte der Klasse Window definieren stack<Window> winStack; |
Der auf diese Weise definiert Stack ist natürlich noch leer.
Für die Ablage von Elementen auf dem Stack dient die Memberfunktion push(...). Sie erhält als Parameter das abzulegende Element. Achten Sie aber bitte darauf, dass das abzulegende Element auch mit dem Datentyp übereinstimmt, für den der Stack definiert wurde.
// int auf Stack ablegen intStack.push(5); // Window-Objekt auf Stack ablegen Window myWin(...); ... winStack.push(myWin); |
|
|
Um auf das oberste Element zuzugreifen, dient die Memberfunktion top(). top() liefert nur eine Referenz auf das Element zurück, d.h. das Element selbst verbleibt weiterhin im Stack. Beachten Sie bitte, dass eine Referenz zurückgeliefert wird und nicht das Objekt selbst. Dies hat Konsequenzen wenn Sie das zurückgelieferte Element verändern. Im nachfolgenden Beispiel hat der Veränderung der Variablen val keinen Einfluss auf den im Stack abgelegten Wert. Wird dagegen die Referenz selbst abgelegt und darüber eine Veränderung vorgenommen, so verändert sich natürlich auch das Element auf dem Stack. In wie weit dies aber 'saubere' Programmierung ist sei einmal dahingestellt.
// zurückgegebene Referenz in Variable umspeichern int val = intStack.top(); // Wert verändern val++; // val erhält wieder ursprünglichen Wert vom Stack val = intStack.top(); // Nun zurückgegebene Referenz abspeichern int& refVal = intStack.top(); // Wert über Referenz verändern refVal++; // Liefert jetzt veränderten Wert zurück int newVal = intStack.top(); |
Sehen wir uns einmal an was passiert, wenn Sie ein Objekt aus dem Stack auslesen. Wird die zurückgelieferte Referenz einem bereits bestehenden Objekt zugewiesen, so wird der Zuweisungsoperator der entsprechenden Klasse ausgeführt, d.h. es wird eine Kopie des obersten Stackelements erstellt. Wird dagegen die Referenz einem neuen Objekt zugewiesen, so wird anstelle des Zuweisungsoperators der Kopierkonstruktor ausgeführt. Speichern Sie aber die Referenz ab dann beachten Sie bitte, dass Änderungen am Objekt auf das im Stack abgelegt Objekt wirken.
// Objekt direkt auslesen // Führt zum Aufruf des Zuweisungsoperators der Klasse Window Window winOne(...); winOne = winStack.top(); // Hier wird der copy-ctor aufgerufen Window winTwo(winStack.top()); // Referenz ablegen // Weitere Veränderungen von winRef wirken sich auf das Stackelement aus Window& winRef = winStack.top(); |
So, nun wird's wieder etwas einfacher. Um das oberste Element vom Stack zu entfernen (top() liefert ja nur eine Referenz auf das Element zurück), dient die Memberfunktion pop(). Der Aufruf dieser Memberfunktion führt bei Stacks mit Objekten auch zum Aufruf des Destruktors des entfernten Objekts.
// Obersten Wert vom Stack entfernen intStack.pop(); // Oberstes Objekt vom Stack entfernen // Führt zum Aufruf des dtor von Window winStack.pop(); |
|
Die durch top() zurückgelieferte Referenz verweist nach pop() damit auf ein Objekt, das nicht mehr existiert. Ein weiterer Zugriff über die Referenz führt dann im besten Fall dazu, dass das Programm einfach beendet wird. |
Damit kennen Sie die wichtigsten Memberfunktionen des stack-Templates. Außer den bisher aufgeführten Memberfunktionen stehen u.a. noch die Memberfunktionen empty() und size() zur Verfügung. empty() liefert true, wenn der Stack keine Elemente enthält und size() die Anzahl der Elemente im Stack.
Fernen können Stacks noch mit den üblichen Vergleichsoperatoren wie
z.B. == oder < verglichen werden. Sind auf einem Stack Objekte abgelegt,
dann führt der Vergleich zum Aufruf der entsprechenden
Vergleichs-Memberfunktionen bzw. (friend-)Vergleichsfunktionen. Beachten
Sie, dass die Klasse der Objekte nur die Operatoren == und
< definieren muss; die restlichen Vergleichsoperatoren
werden dann intern aus diesen beiden gebildet. Der Vergleich erfolgt
Element für Element. Im nachfolgenden Beispiel ist damit der astack
kleiner als der istack, da das zweite Element von istack
größer ist als das zweite Element von astack.
istack.push(1); istack.push(6); astack.push(1); astack.push(3); astack.push(5); if (astack<istack) cout << "astack < istack\n"; else cout << "astack >= istack\n"; |
Außer den erwähnten Memberfunktionen enthält der stack Container noch diverse typedefs, wovon wir uns den in der Praxis am wichtigsten jetzt noch kurz anschauen wollen.
Die Implementierung des stack Container enthält eine typedef-Anweisung in etwa folgender Form :
typedef typename _Sequence::value_type value_type;
value_type repräsentiert hierbei den Datentyp des Elements, das im stack Containers abgelegt ist. Sehen wir das Einsatzgebiet von value_type anhand eines kleinen Beispiels an.
Vorgegeben sind die nachfolgenden Anweisungen. Dort wird ein int-Stack definiert, von dem zu einem beliebigen Zeitpunkt ein Wert ausgelesen wird. Da top() eine Referenz auf das zuletzt abgelegte Element zurückliefert, muss die Zielvariable den Datentyp int oder int& haben.
// Stack für int definieren stack<int> myStack; .... // Wert aus dem Stack auslesen int val = myStack.top(); |
Wenn Sie zu einem späteren Zeitpunkt während der Programmentwicklung den Entschluss fassen, anstelle von int-Werten nun long-Werte auf dem Stack abzulegen, so müssen Sie unter anderem alle Stellen korrigieren, an denen Werte vom Stack ausgelesen werden.
Tun Sie dies nicht, so weisen Sie den long-Wert vom Stack weiterhin einer int-Variablen zu, was ja bekanntlich zum Verlust von Informationen führen kann.
// Stack für long definieren stack<long> myStack; .... // Autsch! Zuweisung long an int int val = myStack.top(); |
Und solche Fehler können Sie durch den Einsatz von value_type vermeiden. Da value_type immer dem aktuellen Datentyp des stack Containers entspricht, kann damit das Verarbeiten von Elementen eines stack Container wie folgt 'typsicher' durchgeführt werden:
Um sich Schreibarbeit zu sparen, wird zunächst für den Stacktyp mittels typedef ein entsprechendes Symbol definiert (im Beispiel ist dies stackType). Bei der anschließenden Definition des Stacks wird als Datentyp des Stacks das mittels typedef definierte Symbol angegeben. Die Definition von Daten, welche auf dem Stack abgelegt oder ausgelesen werden sollen, erfolgt dann in der Weise, dass als Datentyp das typedef Symbol, gefolgt von ::value_ptr angegeben wird.
// Stack für long definieren typedef stack<long> stackType; stackType myStack; .... // Datentyp des Ziels entspricht immer dem Datentyp des Stack-Elements stackType::value_type val = 10; myStack.push(val); ... val = myStack.top(); |
Und egal für welchen Datentyp Sie den Stack dann letztendlich einsetzen, durch die Festlegung des Ziel-Datentyps über value_type haben Sie rechts und links vom Zuweisungsoperator immer die gleichen Datentyp stehen. Wurde der Stack (wie im Beispiel oben) für die Ablage von long-Werten definiert, dann entspricht stackType::value_type dem Datentyp long. Wurde der Stack für Window-Objekte definiert, dann entspricht stackType::value_type nun dem Datentyp Window. Ist doch eine feine Sache, oder?
Während beim vorherigen stack Container die zuletzt abgelegten Elemente wieder zuerst ausgelesen werden (LIFO = last in, first out), werden beim queue Container die zuerst abgelegten Elemente auch wieder zuerst ausgelesen (FIFO = first in, first out). Der queue Container eignet sich daher sehr gut als Zwischenpuffer, da er die Reihenfolge der Elemente nicht umdreht.
Für die Verwendung des queue Containers müssen Sie die Datei <queue> einbinden.
Die Definition einer Queue erfolgt analog zur Definition eines Stacks, nur dass hier anstelle des stack Containers der queue Container angegeben wird. Die so definierte Queue ist natürlich ebenfalls noch leer.
// queue für ints definieren queue<int> intQueue; // queue für Objekte der Klasse Window definieren queue<Window> winQueue; |
Zur Ablage von Elementen in die Queue dient hier ebenfalls die Memberfunktion push(...). Sie erhält als Parameter das abzulegende Element. Und auch hier gilt: in der Queue wird eine Kopie des übergebenen Elements abgespeichert und nicht das Original.
// int in Queue ablegen intQueue.push(5); // Window-Objekt in Queue ablegen Window myWin(...); ... winQueue.push(myWin); |
Um die in einer Queue abgelegten Elemente auszulesen wird die Memberfunktion front() verwendet. Sie liefert eine Referenz auf das nächstes, d.h. älteste, Element in der Queue. front() entfernt das per Referenz zurückgelieferte Element nicht aus der Queue, dies muss mit einer weiteren Memberfunktion gesondert durchgeführt werden.
Außer den Zugriff auf das älteste Element gestattet der queue Container auch den Zugriff auf das zuletzt abgelegte Element (neustes Element) über die Memberfunktion back(). back() liefert ebenfalls wie front() nur eine Referenz auf das Element.
// Ältestes Queue-Element auslesen und als Referenz ablegen // Ablage der Referenz hier effizient, aber auch fehleranfällig! Window& winRef = winQueue.front(); // Zuletzt abgelegten int Wert auslesen int newest = intQueue.back(); |
Bezüglich der zurückgelieferten Referenz (und den Konsequenzen daraus) gilt das Gleiche wie beim stack Container.
Zum Entfernen des ältesten Elements aus der Queue dient die Memberfunktion pop(). Der Aufruf dieser Memberfunktion führt bei Queues mit Objekten auch zum Aufruf des Destruktors des entfernten Objekts. Es gibt aber keine Memberfunktion um das zuletzt abgelegte (neueste) Element aus einer Queue zu entfernen.
// Ältesten Wert aus der Queue entfernen intQueue.pop(); // Ältestes Objekt aus der Queue entfernen // Fuehrt zum Aufruf des dtor von Window winQueue.pop(); |
Die restlichen Schnittstellen des queue Containers wie empty(), size(), die Vergleichsoperatoren und der Typ value_type entsprechen denen des stack Containers.
Der priority_queue Container dient zum Abspeichern von Elementen, wobei die Elemente beim Auslesen nach ihrer Priorität sortiert ausgegeben werden. Die Priorität wird dabei durch einen einfachen Vergleich bestimmt. Bei numerischen Werten hat ein höherer Wert standardmäßig auch eine höhere Priorität. Damit eignet sich der priority_queue Container z.B. zum einfachen Sortieren. Bei Elementen mit gleicher Priorität ist die Reihenfolge der implementierungsabhängig. Werden in einem priority_queue Container Objekte abgelegt, so muss die Klasse der Objekte zumindest den Operator < überladen damit eine Sortierung möglich ist.
Das Sortierkriterium, das die Prioritäten-Reihenfolge festlegt, kann aber auch frei definiert werden. Wie dies erfolgt, sehen wir uns nachher gleich an.
Beginnen wir aber mit den einfacheren Dingen. Zuerst müssen Sie für die Verwendung des priority_queue Containers ebenfalls wieder die Datei <queue> einbinden.
Die Definition einer priority_queue erfolgt im einfachsten Fall analog zur Definition einer 'normalen' Queue, nur dass hier jetzt als Datentyp priority_queue anstelle von queue angegeben wird. Auch die Ablage, das Auslesen und das Entfernen erfolgen mit den gleichnamigen Memberfunktionen push(...), top() und pop(). Lediglich die Memberfunktion front() existiert bei einer Prioritätsqueue nicht. Im nachfolgenden Beispiel werden zunächst drei int-Werte in der Prioritätsqueue abgelegt. Diese Werte dann aus der Prioritätsqueue nacheinander ausgelesen. Wie Sie der Programmausgabe entnehmen können, werden die Werte mit fallender Priorität (Wertigkeit) ausgegeben. Beachten Sie im Beispiel auch bitte den Einsatz des typedef Symbols value_type. Durch den Einsatz von value_type können Sie leicht den Datentyp der Elemente in der Prioritätsqueue anpassen.
Ebenfalls implementiert im priority_queue Container sind die Memberfunktionen size() und empty(). Sie entsprechenden den gleichnamigen Memberfunktionen der normalen Queue.
// typedef für Priority-Queue typedef priority_queue<int> queueType; // Priority-Queue definieren queueType myPrio; // Werte ablegen myPrio.push(10); myPrio.push(5); myPrio.push(20); // Variable zum Auslesen definieren queueType::value_type val; // Werte der Priorität nach auslesen while (!myPrio.empty()) { cout << myPrio.top() << ','; myPrio.pop(); } |
 20,10,5, |
Sehen wir uns noch ein weiteres Beispiel für den Einsatz des priority_queue Containers an. Da die Ablage von einfachen Datentypen in einer Prioritätsqueue wohl eher seltener vorkommt, wollen wir uns im folgenden Beispiel einmal die Ablage von Aktienkursen in einer solchen Queue ansehen. Die Aktienkurse sollen dabei nach fallendem Wert ausgegeben werden, d.h. als 'Priorität' soll der aktuelle Kurs dienen.
Ein Aktienkurs setzt sich zusammen aus dem Namen eines Unternehmens (der AG) und dem aktuellen Wert der Aktien. Damit kann der Aktienkurs in einem pair abgelegt werden. Da die Sortierreihenfolge der Queue nach dem Aktienwert erfolgen soll, muss als erstes Element des pair auch der Aktienwert stehen. Denken Sie beim Einsatz eines pair immer daran, dass das erste Element eines pair immer Vorrang beim Vergleich hat. Würde als erstes pair-Element der Name des Unternehmens stehen, so würde die Prioritätsqueue die Unternehmen alphabetisch sortieren.
Für das pair bietet es sich an, mittels typedef ein entsprechendes Symbol zu definieren. Dieses Symbol wird dann bei der Definition der Prioritätsqueue angegeben.
// pair für Aktienkurs typedef pair<double,string> stock; // Prioritätsqueue für Aktienkurs priority_queue<stock> stockQueue; |
Danach kann die Prioritätsqueue mit beliebig vielen Aktienkursen 'gefüllt' werden.
// Prioritätsqueue mit Aktienkursen belegen
stockQueue.push(stock(11.11,"One"));
stockQueue.push(stock(44.44,"Four"));
stockQueue.push(stock(22.22,"Two"));
|
Das Auslesen der Aktienkurse erfolgt dann mit den Befehlen top() und pop(). Beachten Sie bitte, dass die Prioritätsqueue keine Operationen kennt, mit denen Sie die Queue durchlaufen können. Für solche Anwendungsfälle gibt es andere Container die wir uns später ansehen werden.
// Ausgabe der Aktienkurse
while (!stockQueue.empty())
{
stock actStock = stockQueue.top();
cout << "Unternehmen: " << actStock.second << "\Aktienkurs: "
<< actStock.first << endl;
stockQueue.pop();
}
|
Standardmäßig werden die Elemente in einer Prioritätsqueue fallend sortiert. Wollen Sie eine andere Sortier-Reihenfolge, so können Sie das Sortierkriterium selbst festlegen.
Um das Sortierkriterium festzulegen, müssen Sie einen entsprechenden Funktionsoperator zur Verfügung stellen. Funktionsoperatoren wurden ja schon in der Lektion Überladen von speziellen Operatoren eingeführt. Sie können Sie sich die Funktionsoperatoren hier nochmals ansehen.
Der für den Vergleich verwendete Funktionsoperator (im folgenden functor genannt) erhält die beiden zu vergleichenden Elemente per const-Referenz übergeben und liefert als Returnwert einen bool-Wert zurück. Ist der Rückgabewert des functors true, so wird in der Queue zuerst das als zweiten Parameter übergebene Element abgelegt dann das erste Element. Bei Rückgabe von false wird die Ablagereihenfolge umgedreht. Aber sehen wir uns dies anhand des Beispiel zur Ablage von Aktienkursen einmal an. Diesmal sollen die Aktienkurse in aufsteigender Reihenfolge (also der umgekehrten normalen Priorität) abgelegt werden.
Zum Überladen des functors definieren wir uns die Klasse CompareStocks. Da die Aktienkurse als stock Datentyp (über typedef Anweisung) abgelegt werden, erhält der functor die zu vergleichenden Elemente auch als stock Parameter übergeben. Wenn wir die Aktienkurse in aufsteigender Reihenfolge in der Prioritätsqueue ablegen wollen, so müssen die beiden übergebenen Elemente dann umgekehrt abgelegt werden, wenn der Kurs des im ersten Parameter übergebenen Elements größer ist als der des Elements im zweiten Parameter. Folglich muss der functor dann true zurückliefern wenn gilt, s1.first > s2.first (first ist der Kurswert der Aktie im pair!).
// Funktionsobjekt
struct CompareStocks
{
bool operator()(const stock& s1, const stock& s2) const
{
return (s1.first > s2.first);
}
};
|
Möchten Sie bei der vorgegebenen pair-Struktur zum Beispiel nach dem Unternehmensnamen sortieren, so müssten Sie im functor lediglich anstelle des pair Elements first einen Vergleich mit dem pair Element second durchführen. Sie sehen, solche eigen definierten Sortierkriterien gestatten eine relativ flexible Anwendung der Prioritätsqueue.
|
|
Ist der functor definiert, so muss er 'nur noch' mit der priority_queue 'verknüpft' werden. Dies geschieht folgendermaßen:
Zuerst ist ein entsprechendes Objekt der functor-Klasse zu definieren. Dieses functor-Objekt ist dann dem Konstruktor des Prioritätsqueue Objekts zu übergeben. Beachten Sie bitte im nachfolgenden Beispiel die geänderte Definition des Queue-Objekts.
#include <vector> #include <queue> .... CompareStocks cmpFunc; // Definition der Funktionsobjekts priority_queue<stock, std::vector<stock>, CompareStocks> stockQueue(cmpFunc); |
Innerhalb der spitzen Klammer steht zunächst (wie gewohnt) der Datentyp der Elemente der Prioritätsqueue. Danach folgt der Container-Typ, der intern für die Prioritätsqueue verwendet wird. Sie sollten bis auf weiteres dort die Angabe std::vector<DTYP> stehen lassen. DTYP muss mit dem Datentyp der Elemente der Prioritätsqueue übereinstimmen. Zum Schluss folgt noch die Klasse des functors. Beachten Sie bitte, dass nun in jedem Fall auch die Header-Datei <vector> einzubinden ist.
Wenn Sie die Prioritätsqueue jetzt wie nachfolgend angegeben füllen, so erhalten Sie die darunter stehende Ausgabe. Die Ausgabe erfolgt nun in aufsteigender Sortierung nach Aktienkursen, d.h. die Prioritäten wurden umgedreht.
stockQueue.push(stock(11.11,"One")); stockQueue.push(stock(44.44,"Four")); stockQueue.push(stock(22.22,"Two")); |
|
Company: One value: 11.11 |
|
|
Das Klassen-Template bitset dient zum Abspeichern von Bitfolgen. Die Anzahl der Bits in der Folge ist nicht an irgendwelche Größen von Standard-Datentypen gebunden. So können in einem bitset zum Beispiel 16 oder sogar 10000 Bits abgespeichert werden. Da ein Bit entweder gesetzt sein kann (1-Wert) oder nicht (0-Wert), werden bitset-Objekte in der Regel zum Abspeichern von so genannten Flags eingesetzt. Aber bitset-Objekte können auch noch für einen anderen Zweck angewandt werden, den wir uns am Ende dieser Lektion ansehen werden.
Wenn Sie bitsets verwenden, so müssen Sie die Header-Datei <bitset> einbinden. Denken Sie auch immer daran, dass sowohl bitset wie auch die bisherigen Container alle im Namensraum std liegen. Die Angabe des Namenraums wurde bei den Beispielen immer weggelassen
Um ein bitset Objekt zu definieren, wird nach dem Namen des Klassen-Templates bitset in spitzen Klammern die Anzahl der Bits für das bitset-Objekt angegeben. Bei einem solchermaßen definierten bitset sind alle Bits auf 0 gesetzt.
// Definition eines einfachen bitset-Objekts mit 50 Bits, alle auf 0 gesetzt
bitset<50> myFlags;
|
Sie können ein bitset bei seiner Definition auch gleich initialisieren. Dies geschieht durch Aufruf des entsprechenden Konstuktors. Dabei stehen Ihnen folgende Möglichkeiten zur Verfügung:
// bitset mit 8 Bits mit dem Wert 7 (00000111) initialisieren bitset<8> myFlags(7UL); // String mit 0/1 Folge, 8 Bits string stringFlags("10010011"); // String in Bits 'umwandeln' bitset<8> yourFlags(stringFlags); // niederwertige Flags extrahieren (0011) bitset<4> lowFlags(stringFlags,0,4); // höherwertige Flags extrahieren (1001) bitset<4> highFlags(stringFlags,4,4); |
|
myFlags: 00000111 |
Beachten Sie ferner, dass Sie hier einen string angeben müssen und keinen char-Zeiger, d.h. die Anweisung
bitset<8> myFlags("01010101");
erzeugt einen Fehler beim Übersetzen des Programms!
Werden bitsets ausgegeben, z.B. mit den Stream cout, so wird der Inhalt des bitsets als 0/1 Folgen ausgegeben. Es werden dabei aber immer alle Bits eines bitsets ausgegeben, d.h. bei einem bitset mit z.B. 50 Bits werden auch alle 50 Bits ausgegeben. Und auch das ist möglich: Sie können ein bitset sogar einlesen, z.B. mit den Stream cin. Die Eingabe darf dabei natürlich nur aus 0/1 Kombinationen bestehen. Ein Beispiel hierzu folgt weiter unten.
Das Klassen-Template bitset definierte eine relativ große Anzahl von Operationen, um die Bits in einem bitset zu verarbeiten. Wir werden uns an dieser Stelle nur die wichtigsten ansehen. Für die restlichen Operationen sei wieder auf die Online-Hilfe verwiesen.
Die Memberfunktion size() liefert die Anzahl der Bits in einem bitset als size_t Wert zurück. Wollen Sie wissen, ob beliebige Bits in einen bitset gesetzt sind, so können Sie dies mit der Memberfunktion any() abprüfen. Sie liefert true zurück wenn mindestens ein Bit gesetzt ist. Wenn Sie es noch genauer wissen wollen, dann liefert die Memberfunktion count() die Anzahl der gesetzten Bits zurück (siehe auch Programmausgabe).
bitset<8> myFlags(string("10100011"));
cout << "size:" << myFlags.size() << ',' << "any:"
<< myFlags.any() << ',' << "count:" << myFlags.count() << endl;
|
|
size:8,any:1,count:4 |
Mithilfe der Memberfunktion test(...) können Sie ein bestimmtes Bit innerhalb des bitsets abprüfen. test(...) erhält als Parameter den Index des abzuprüfenden Bits und liefert true zurück, wenn das entsprechende Bit gesetzt ist (siehe auch Programmausgabe).
bitset<8> myFlags(string("10100011"));
for (size_t i=0; i<myFlags.size(); i++)
cout << (myFlags.test(i) ? 'S' : '.');
|
|
SS...S.S |
Zum Setzen, Löschen und Invertieren von Bits dienen die Memberfunktionen set(...), reset(...) und flip(...). Diese Memberfunktionen erhalten als Parameter den Index des zu manipulierenden Bits und alle drei Memberfunktionen haben auch noch weitere Formen um z.B. alle Bits in eine bitset gleichzeitig manipulieren zu können.
bitset<50> manyBits(0x5FFul); // höchstwertigstes Bit setzen manyBits.set(49); // niederwertigstes Bit löschen manyBits.reset(0); // Bit 30 invertieren manyBits.flip(30); |
Als Alternative für den Zugriff auf ein bestimmtes Bit (anstelle von test(...), set(...) und reset(...)) steht auch der Indexoperator [] zur Verfügung.
bitset<8> myFlags(0x07ul);
// höchstwertiges Bit setzen
myFlags[7] = 1;
|
Nachfolgend sehen Sie nochmals einen etwas komplexeren Einsatz eines bitsets. Das bitset besteht dabei aus 4 Flags. Je nach Zustand der Flags wird dann im Programm der auszugebende Text gesteuert. Dazu werden den Flags mittels enum-Konstanten zuerst symbolische Namen zugewiesen. So soll zum Beispiel das erste Flag FARBE dazu dienen, die Ausgabe einer Farbinformation zu steuern. Nach der Definition des bitset-Objekts flags werden in diesem bitset zwei beliebig Bits gesetzt, einmal durch die set(...) Memberfunktion und einmal über den Indexoperator. Im Anschluss daran wird je nach Zustand der vier Flags (Bits) ein entsprechender Text ausgegeben.
// Flagnummern als enums
enum choices {FARBE, FAHRZEUG, GESCHW, STRECKE};
// bitset mit 4 Flags
bitset<4> flags;
// Zwei beliebige Flags setzen
flags.set(rand()%4);
flags[rand()%4] = 1;
// Je nach Flag entsprechenden Text ausgeben
cout << "Das " << ((flags[FARBE])?"rote":"gelbe");
cout << ((flags[FAHRZEUG])?" Fahrrad ":" Auto ");
cout << "fährt " << ((flags[GESCHW])?"schnell":"langsam");
cout << " um die " << ((flags[STRECKE])?"Kurve":"Ecke") << endl;
|
|
|
Aber außer zum Abspeichern von einzelnen Bits können Sie ein bitset auch zum Konvertieren einer in einem string abgelegten 0/1 Folge in einen numerischen Wert oder umgekehrt verwenden. Dazu stellt bitset die beiden Memberfunktionen to_ulong() und to_string() zur Verfügung. Sehen wir uns beide Memberfunktionen am Besten anhand eines Beispiels an.
// bitset mit 8 Bits definieren bitset<8> toNumeric; // bitset einlesen, als 0/1 Folge cin >> toNumeric; // 0/1 Folge als numerischen Wert ausgeben cout << "Eingelesener Wert: " << toNumeric.to_ulong() << endl; // bitset mit 01010101 initialiseren bitset<8> toString(0x55); // 0/1 Folge in string umwandeln string converted = convBitset.template to_string<char,char_traits<char>, allocator<char> >(); cout << "Als string: " << converted << endl; |
Im Beispiel wird zuerst ein bitset mit 8 Bits definiert. Dieses bitset wird dann mittels cin eingelesen (nur 0 und 1 als Eingabe zugelassen!). Anschließend wird die eingelesene 0/1 Folge mit der Memberfunktion to_long() in einen unsigned long Wert umgewandelt und dann ausgegeben. Danach wird ein weiteres bitset definiert, dass bei seiner Definition mit dem Wert 0x55 initialisiert wird. Um die im bitset abgelegten Bits in einen 0/1 String zu konvertieren, wird die Memberfunktion to_string() aufgerufen. Beachten Sie bitte den etwas 'kryptische' Aufruf der Memberfunktion. to_string() ist als Funktions-Template definiert und erfordert deshalb die angegebene aufwändige Schreibweise.
Damit wollen wir an dieser Stelle die Behandlung des bitsets beenden. Wie bereits erwähnt, besitzt das Klassen-Template noch eine Reihe weiterer Operatoren wie z.B. <<= um alle Bits eines bitsets um eine bestimmte Anzahl von Stellen nach links zu schieben.
|
|
Gefundene Primzahlen: |
// Beispiel zu bitset // Bestimmung der Primzahlen #include <iostream> #include <bitset> using std::cout; using std::endl; using std::bitset; // Bereich der Primzahlen const int MAX = 100; // main() Funktion int main() { int index; // Schleifenvariablen für Primzahlbestimmung int prim; bitset<MAX> primes; // Bitset mit 'Primzahlen' // Alle Zahlen als Primzahlen markieren primes.set(); // 0 und 1 sind keine Primzahlen! primes.reset(0); primes.reset(1); index = 2; // Aktuelle Primzahl ist 2 do { // Durchsuche alle Zahlen ab der aktuellen Primzahl+1 // und entferne diejenigen, die durch die Primzahl teilbar sind for (prim = index+1; prim<MAX; prim++) { // Wenn Zahl noch nicht entfernt wurde if (primes.test(prim)) { // prüfe, ob Zahl durch Primzahl teilbar if (prim%index == 0) // Wenn ja, dann ist Zahl keine Primzahl primes.reset(prim); } } // Suche nächste noch vorhandene Zahl, // dies ist auch die nächste Primzahl index++; if (index<MAX) { do { if (primes.test(index)) // nächste Primzahl gefunden break; index++; } while (index<MAX); } } while (index<MAX); // Alle gefundenen Primzahlen ausgeben cout << "Gefundene Primzahlen:\n"; for (index=0; index<MAX; index++) { if (primes.test(index)) cout << index << ','; } cout << endl; return 0; } |
Übung:Schreiben Sie ein Programm, dass die Ankunftszeiten von Flügen nach Flugnummern sortiert ausgibt. Verwenden Sie zum Sortieren einen entsprechenden Container der Standard Bibliothek.
Die Flugdaten sind in einer Klasse Flight abzulegen, die folgende Eigenschaften besitzt: Flugnummer als string, Ankunftszeit in Stunde und Minute als unsigned char.
Legen Sie vier Flugdaten in einem entsprechenden Container ab und geben Sie diese dann aus.
Zusatz (nur für die Hardcore-Programmierer!): Erweitern Sie das Programm so, dass die Flugdaten nach aufsteigender Ankunftszeit ausgegeben werden.
Die nachfolgende Ausgabe zeigt die Ausgabe nach aufsteigender Ankunftszeit
|
Flug: 222, Ankunft: 09:00 |
Lösung
ansehen!
Wenn
Sie Objekte in einem Stack ablegen, so sollte die entsprechende
Klasse den Zuweisungsoperator, den Kopierkonstruktor und den
Destruktor definieren wenn sie nicht trivial ist. Eine
nicht-triviale Klasse enthält entweder dynamische Eigenschaften
oder weitere eingeschlossene Objekte. Ferner sollten die
Vergleichsoperatoren < und == für die Klasse definiert sein.
Diese Anforderungen an eine Klasse gelten übrigens für alle
Objekte die in Containern der Standard Bibliothek abgelegt
werden sollen.
Beachten
Sie bitte, dass für den functor hier der Klassentyp struct
verwendet wurde! Der überladene Funktionsoperator muss natürlich
public sein, damit der priority_queue
Container darauf auch Zugriff hat.
Beispiel: