Container-Adapter

Container-Adapter sind keine neuen Containertypen, sondern verwenden die Standard-Container jedoch mit einer angepassten Schnittstelle für einen bestimmten Anwendungsfall.

stack

Einzubindende Header-Datei: stack

Ein Stack dient zum vorübergehenden Abspeichern von Daten, wobei das zuletzt abgelegte Datum wieder als Erstes ausgelesen wird. Ein Stack ist ein sogenannter LIFO-Speicher (LIFO = last in, first out).

Definition

Ein Stack wird wie folgt definiert:

stack<DTYP> obj;

Stack ohne Elemente zur Ablage von Daten des Typs DTYP.

stack<DTYP> obj(const stack<DTYP>& other);

Kopiert den Inhalt des Stacks other.

Elementzugriff

Naturgemäß kann nur auf das zuletzt auf dem Stack abgelegte Element zugegriffen werden.

DTYP& top();

Liefert eine Referenz auf das oberste Element zurück. Das Element verbleibt weiterhin auf dem Stack.

Dies ist die einzige Möglichkeit, auf ein Element im Stack zuzugreifen. D.h. sowohl der Zugriff über Iteratoren wie auch über eine range-for-Schleife ist nicht möglich.

Wenn mit der zurückgelieferten Referenz gearbeitet wird, dann ist dies zwar von der Laufzeit effizient, birgt aber eine gewisse Gefahr. Sehen Sie sich das folgende Beispiel an.

Zunächst wird die von top() zurückgelieferte Referenz abgespeichert. Irgendwann im Verlaufe des Programms wird dieses Element dann mittels pop() vom Stack entfernt, was wiederum dazu führt, dass das Objekt gelöscht wird.

...
// Stackelement auslesen, Referenz darauf ablegen
Window& winRef = winStack.top();
...
// Oberstes Element nun entfernen
winStack.pop(); ...
// Referenz verweist nun auf ein nicht vorhandenes Element!
// CRASH ?!?
winRef.Size(...);

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 zu undefiniertem Verhalten.

Elemente einfügen und löschen

void push (const DTYP& value);

Legt das Datum value als oberstes Element auf dem Stack ab.

DTYP& emplace (plist args);

Erstellt ein Objekt und legt es als oberstes Element auf dem Stack ab. args ist eine Auflistung der Parameter eines Konstruktors des einzufügenden Objekts. Die Methode liefert eine Referenz auf das eingefügte Element.

void pop();

Entfernt das oberste Element im Stack.

Sonstige Methoden

bool empty() const;

Liefert true zurück, wenn der Stack leer ist.

size_type size() const;

Liefert die Anzahl der Elemente im Stack zurück.

#include <print>
#include <stack>
#include <string>
using namespace std::string_literals;

import CData4;

int main()
{
    // Integer Stack definieren
    std::stack<int> intStack;
    // Wert auf Stack ablegen
    intStack.push(5);
    // Stack fuer CData4-Objekte definieren
    std::stack<CData4> objStack;
    // CData4-Objekt definieren und auf Stack ablegen
    // ctor Parameter ist std::string
    CData4 obj("Objekt 1"s);
    objStack.push(obj);
    // CData4-Objekt erstellen und auf Stack ablegen
    objStack.emplace(CData4{"Objekt 2"s});
    // objStack komplett auslesen
    while (!objStack.empty())
    {
        auto obj1 = objStack.top();
        // Objekt nach dem auslesen auch entfernen
        objStack.pop();
        std::println("Stack: {}",obj1);
    }
}

Stack: Objekt 2
Stack: Objekt 1

Übung

stack_01:

Schreiben Sie ein Programm zur Syntaxüberprüfung einer XML-Datei.

In einer XML-Datei werden die einzelnen Einträge durch sogenannte XML-Tags gekennzeichnet. Jeder Tag besteht aus einem öffnenden und einem schließenden Teil, die namentlich übereinstimmen müssen.

Dabei können folgende Fälle auftreten:

1. Öffnender und schließender Tag stehen in unterschiedlichen Zeilen (z.B. Zeilen 2 und 15 oder 5 und 14 im nachfolgenden Listing):

<TAGNAME[ Parameter]> ... </TAGNAME>

Die Angabe von Parameter ist optional.

2. Öffnender und schließender Tag in gleicher Zeile (z.B. Zeile 3):

3. Selbstschließender Tag (z.B. Zeile 7):

Die erste Zeile einer XML-Datei gibt die XML-Version an und ist zu ignorieren.

Das Programm soll in der nachfolgenden Datei test.xml prüfen, ob alle Tags korrekt geschlossen wurden. Wird ein Fehler in der XML-Datei gefunden, ist ein Fehlertext mit einem Hinweis auf die fehlerhafte Zeile auszugeben.

<?xml version="1.0"?>
<SimBase.Document Type="ScenarioFile" version="4,5" id="test">
  <Descr>AceXML Document</Descr>
  <Filename>test.fxml</Filename>
  <Flight.Sections>
    <Section Name="Main">
      <Property Name="Title" Value="test" />
      <Property Name="Description" Value=" " />
    </Section>
    <Section Name="Options">
      <Property Name="Sound" Value="True" />
      <Property Name="Pause" Value="False" />
    </Section1>
  </Flight.Sections>
</SimBase.Document>

Bevor Sie an Lösung der Aufgabe verzweifeln, ein paar Tipps:

1. Da die XML-Tags geschachtelt vorkommen, müssen Sie sich den öffnenden Tag merken und erst beim schließenden Tag den Vergleich mit dem Tagnamen durchführen.

2. Merken Sie sich außer dem öffnenden Tag auch dessen Zeilennummer.

3. Lösen Sie beim Auftreten eines Fehlers eine Ausnahme aus.

4. Die Beispieldatei enthält keine XML-Kommentare oder mehrere XML-Tags in einer Zeile.

Bei richtiger Arbeitsweise des Programms sollten Sie folgende Ausgabe erhalten.

Zeile 10: Schliessender XML-Tag nicht gefunden

Korrigieren Sie den Fehler und prüfen Sie anschließend die Datei nochmals.

Keine XML Fehler gefunden!

queue

Einzubindende Header-Datei: queue

Während beim stack-Container das zuletzt abgelegte Element wieder zuerst ausgelesen wird (LIFO = last in, first out), wird beim queue-Container das zuerst abgelegte Element wieder zuerst ausgelesen (FIFO = first in, first out). Der queue-Container eignet sich daher als Zwischenpuffer, da er die Reihenfolge der Elemente nicht umdreht.

Definition

Die Definition einer Queue erfolgt analog zur Definition eines Stacks, nur wird anstelle des Containers stack der Container queue angegeben.

queue<DTYP> obj;

Definiert eine leere Queue zur Ablage von Daten des Typs DTYP.

queue<DTYP> obj(const queue<DTYP>& other);

Definiert eine Queue und kopiert die Daten aus der Queue other.

Elementzugriff

Im Gegensatz zu einem Stack kann bei einer Queue auf das erste und letzte Element zugegriffen werden.

DTYP& front();

Liefert eine Referenz auf das erste Element in der Queue.

DTYP& back();

Liefert eine Referenz auf das letzte Element in der Queue.

Bezüglich der zurückgelieferten Referenz (und den Konsequenzen daraus) gilt das Gleiche wie beim stack-Container.

Elemente einfügen und löschen

Zur Ablage von Elementen in eine Queue dienen ebenfalls die Methoden

void push (const DTYP& value);

Fügt das Datum value ans Ende der Queue ein.

DTYP& emplace (plist args);

Erstellt ein Objekt und fügt es ans Ende der Queue an. args ist eine Auflistung der Parameter eines Konstruktors des einzufügenden Objekts. Die Methode liefert eine Referenz auf das eingefügte Element.

void pop();

Entfernt das erste Element in der Queue.

Sonstige Methoden

bool empty() const;

Liefert true zurück, wenn die Queue leer ist.

size_type size() const;

Liefert die Anzahl der Elemente in der Queue zurück.

Übung

queue_01:

Schreiben Sie ein Programm zur Lagerverwaltung von Milchprodukten. Das Lager besteht aus 3 getrennten Linien: eine für Butter, eine für Käse und eine für Milch. Es wird immer die sich am längsten im Lager befindliche Ware einer Linie als Erstes aus dem Lager entnommen.

Am Tagesbeginn erhalten Sie eine Lieferung folgender Waren:

// enum fuer die Frischwaren-Gruppen
enum Produkt {BUTTER, KAESE, MILCH};
// Die erste Lieferung von Waren
// Produkt, Anzahl Palettten, Warenbezeichnung
std::tuple<Produkt,int,std::string> lieferungen[]
{
std::tuple{MILCH, 3, "Weideglueck"s},
std::tuple{KAESE, 1, "Berghof"s},
std::tuple{MILCH, 2, "Von der Alm"s},
std::tuple{BUTTER,2, "Landgold"s},
std::tuple{KAESE, 2, "Zartschmelz"s},
std::tuple{BUTTER,2, "Die Streichzarte"s}
}

Das Einlagern und Abholen einer Ware soll über Funktionen erfolgen, die zusätzlich eine Meldung ausgeben, wie viele Paletten von welche Ware in welcher Linie eingelagert bzw. abgeholt werden.

Lagern Sie die Waren aus dem obigen Feld lieferungen in die entsprechende Linie ein.

Zu Tagesbeginn werden folgende Waren aus dem Lager geholt:

- 2 Paletten Käse
- 4 Paletten Milch
- 3 Paletten Butter

Anschließend ist eine neue Lieferung von 3 Paletten Butter "Unsere Beste" ins Lager zu stellen.

Am Tagesende ist das Lager vollständig zu leeren.

Eingelagert 3 Paletten Milch 'Weideglueck'
Eingelagert 1 Paletten Kaese 'Berghof'
Eingelagert 2 Paletten Milch 'Von der Alm'
Eingelagert 2 Paletten Butter 'Landgold'
Eingelagert 2 Paletten Kaese 'Zartschmelz'
Eingelagert 2 Paletten Butter 'Die Streichzarte'

Hole 2 Paletten Kase aus Lager:
Hole 1 Palette 'Berghof' aus Lager Kaese
Hole 1 Palette 'Zartschmelz' aus Lager Kaese
Hole 4 Paletten Milch aus Lager:
Hole 1 Palette 'Weideglueck' aus Lager Milch
Hole 1 Palette 'Weideglueck' aus Lager Milch
Hole 1 Palette 'Weideglueck' aus Lager Milch
Hole 1 Palette 'Von der Alm' aus Lager Milch
Hole 3 Paletten Butter aus Lager
Hole 1 Palette 'Landgold' aus Lager Butter
Hole 1 Palette 'Landgold' aus Lager Butter
Hole 1 Palette 'Die Streichzarte' aus Lager
Butter Neue Lieferung: 3 Paletten Butter "Unsere Beste"
Eingelagert 3 Paletten Butter 'Unsere Beste'

Alles muss raus:
Hole 1 Palette 'Die Streichzarte' aus Lager Butter
Hole 1 Palette 'Unsere Beste' aus Lager Butter
Hole 1 Palette 'Unsere Beste' aus Lager Butter
Hole 1 Palette 'Unsere Beste' aus Lager Butter
Hole 1 Palette 'Zartschmelz' aus Lager Kaese
Hole 1 Palette 'Von der Alm' aus Lager Milch

priority_queue

Einzubindende Header-Datei: queue

Der priority_queue-Container dient zum Abspeichern von Elementen nach ihrer Priorität. Die Priorität wird dabei durch einen einfachen Vergleich bestimmt. Werden im Container Elemente mit numerischen Daten abgelegt, hat ein größerer Wert standardmäßig 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 implementierungsabhängig.

Werden in einem priority_queue-Container Objekte abgelegt, muss die Klasse des Objekts zumindest den Operator < überladen, damit eine Sortierung möglich ist.

Das Sortierkriterium, das die Prioritäten-Reihenfolge festlegt, kann optional mittels eines binären Predicate definiert werden.

Definition

Die Definition einer priority_queue mit der Standardsortierung erfolgt analog zur queue.

priority_queue<DTYP> obj;

Definiert eine leere priority_queue zur Ablage von Daten des Typs DTYP.

priority_queue<DTYP> obj(const priority_queue<DTYP>& other);

Definiert eine priority_queue und kopiert die Elemente aus der priority_queue other.

Elementzugriff

DTYP& top();

Liefert eine Referenz auf das Element mit der höchsten Priorität zurück. Das Element verbleibt weiterhin in der Queue.

Elemente einfügen und löschen

Das Einfügen und Entfernen von Elementen erfolgt analog zum Container queue mit den Methoden

void push (const DTYP& value);

Sortiert das Datum value in die priority_queue ein.

void emplace (plist args);

Erstellt ein Objekt und sortiert es in die priority_queue ein. args ist eine Auflistung der Parameter eines Konstruktors des einzufügenden Objekts.

void pop();

Entfernt das Element mit der höchsten Priorität.

Sonstige Methoden

bool empty() const;

Liefert true zurück, wenn die Queue leer ist.

size_type size() const;

Liefert die Anzahl der Elemente in der Queue zurück.

Sortierkriterium für priority_queue

Standardmäßig werden die Elemente in einer priority_queue so sortiert, dass das Element mit dem größten Wert zuerst ausgelesen wird. Soll die Sortierung in einer abweichenden Reihenfolge erfolgen, kann das Sortierkriterium über ein binäres Predicate definiert werden. Das Predicate erhält die beiden zu vergleichenden Elemente per const-Referenz übergeben und liefert als Returnwert einen bool-Wert zurück.

Die Definition eines priority_queue Objekts mit einer anwenderdefinierten Sortierung sieht folgendermaßen aus:

priority_queue<DTYP, CONT<DTYP>, BPRED> qName;

DTYP gibt wiederum den Datentyp der in der Queue abzulegenden Daten an. CONT definiert den der Queue zugrunde liegenden Container und BPRED ist das anzuwendende binäre Predicate für die Sortierung. Als Container CONT sollte entweder der Container vector oder queue verwendet werden.

// Functor, sortiert priority_queue fallend
template <typename T>
struct SortFunc
{
   bool operator () (const T& val1, const T& val2)
   { return val1 > val2; }
};
// priority_queue definieren
std::priority_queue<int, std::vector<int>,
                    SortFunc<int>> ique;

Übung

scont1_02:

Schreiben Sie ein Programm, das Flugdaten in einen Container ablegt.

Die Flugdaten sind in einer Klasse Flight abzulegen, die folgende Eigenschaften besitzt: Flugnummer als string, Ankunftszeit in Stunden und Minuten als unsigned char.

Die Abarbeitung/Ausgabe der Flüge soll nach aufsteigender Ankunftszeit erfolgen.

Legen Sie vier Flugdaten im Container ab und geben Sie diese dann aus.

Flug EW 333, Ankunft 17:38
Flug X 111, Ankunft 10:59
Flug LH 444, Ankunft 10:38
Flug UA 222, Ankunft 09:00;

Flug: UA 222, Ankunft: 09:00
Flug: X 111, Ankunft: 10:59
Flug: LH 444, Ankunft: 10:38
Flug: EW 333, Ankunft: 17:38

In diesem Kapitel

Teil 1:Grundlagen

Teil 2:Objektorientierung

Teil 3:Standardbibliothek

Anhänge

Container-Adapter

stack

Definition

Elementzugriff

Elemente einfügen und löschen

Sonstige Methoden

Übung

queue

Definition

Elementzugriff

Elemente einfügen und löschen

Sonstige Methoden

Übung

priority_queue

Definition

Elementzugriff

Elemente einfügen und löschen

Sonstige Methoden

Sortierkriterium für priority_queue

Übung