Container

der Begriff Container stammt ursprünglich aus der Schiffahrt, Container kann mehrere Bedeutungen annehmen.

in der Schiffahrt:
Behälter der Güter lagern und transportieren kann.

in der Datenverarbeitung:
- Computertechnik: eine Dateiformat die verschiedenartige Datenformate enthalten kann. (siehe Containerformat)
- Server: Teil einer Server-Software und Enterprise Java Beans (EJB) verwaltet. Der Container speichert die Daten und prüft die Verfügbarkeit für jeden autorisierten Client. (siehe EJB-Container)
- in Programmiersprachen: Einige Programmiersprachen wie Java oder C++ verfügen über Containerklassen. In C++ sind sie in der Stardbibliothek C++Standardbibliothek
- in der Informatik (und bei uns in der Vorlesung): ein abstraktes Objekt, das Elemente des gleichen Typs speichert (Array, Liste, Dictionary,...) siehe auch Datenstrukturen

mögliche Operationen

Welche Operationen hätte man denn gerne bei einer solchen Container-Datenstruktur? Was benötigen Algorithmen häufig? Wie sollten die Daten organisiert sein, damit Algorithmen effizient damit arbeiten können?
Eine solche Anforderungsanalyse ist sehr aufwendig und kann sich über Jahre erstrecken, weil Erfahrungen gesammelt werden müssen, welche Anforderungen an Datenstrukturen in vielen Algorithmen immer wieder auftreten.
Wir listen im folgenden nur das Resultat, also die wichtigsten Operationen von Container-Datenstrukturen auf.

Sei c eine Container-Datenstruktur und v ein darin gespeicherter Wert:

Lesender Zugriff
0. c.size() – gibt die Anzahl der Elemente im Container an
1 v = c.get(i) – das i-te Element im Container lesen
1b. Variante: v = c.get(pos) – das Element an Position pos lesen (pos ist ein geeignetes Hilfsobjekt, das in Abhängigkeit von der Art der Datenstruktur eine Position im Container referenziert. Im Falle v = c.get(i) ist pos eine natürliche Zahl, aber es gibt auch andere Möglichkeiten, die Position zu kodieren.)
1c. Variante: v = c.get(key) – das Element mit dem Schlüssel key lesen (Beachte den Unterschied zu 1b: In 1b markiert pos eine Position im Container, hier in 1c bezieht sich key auf eine Eigenschaft der Datenelemente, die von der Position im Container unabhängig ist.)
2a. v = c.first() – erstes Element lesen (äquivalent zu v = c.get(0))
2b. v = c.last() – letztes Element lesen (äquivalent zu v = c.get(v.size()-1))
3a. v = c.smallest() – das kleinste Element lesen (dies bezieht sich auf eine Eigenschaft der Datenelemente, im Unterschied zu 2a, wo es um die Position im Container geht.)
3b. v = c.largest() – das größte Element lesen (dies bezieht sich auf eine Eigenschaft der Datenelemente bzw. Schlüssel, im Unterschied zu 2b, wo es um die Position im Container geht.)

Schreibender Zugriff
4a. v.set(i, value) – i-tes Element überschreiben (c.size() bleibt unverändert)
4b. v.set(pos, value) – Element an der Stelle pos überschreiben (c.size() bleibt unverändert)
4c. v.set(key, value) – Element mit dem Schlüssel key überschreiben (c.size() bleibt unverändert)
5a. c.insert(i, v) – Objekt als i-tes in den Container einfügen (Werte ab i werden eine Position nach hinten verschoben, c.size() erhöht sich um 1)
5b. c.insert(pos, v) – Objekt an Position pos in den Container einfügen (Werte ab pos werden eine Position nach hinten verschoben, c.size() erhöht sich um 1)
5c. c.insert(key, v) – Objekt unter dem Schlüssel key in den Container einfügen (Wenn der Schlüssel schon vergeben war, wird ein Fehler signalisiert. c.size() erhöht sich um 1)
6a. c.prepend(v) – Objekt am Anfang einfügen (äquivalent zu tt>c.insert(0, v), c.size() erhöht sich um 1)
6b. c.append(v) – Objekt am Ende anhängen (äquivalent zu tt>c.insert(c.size(), v), c.size() erhöht sich um 1)
7a. c.remove(i) – i-tes Element aus dem Container löchen (Werte ab pos werden eine Position nach vorn verschoben, c.size() verringert sich um 1)
7b. c.remove(pos) – Objekt an Position pos aus dem Container löchen (Werte ab pos werden eine Position nach hinten verschoben, c.size() verringert sich um 1)
7c. c.remove(key) – Objekt unter dem Schlüssel key aus dem Container löchen (Wenn der Schlüssel nicht vergeben war, wird ein Fehler signalisiert. c.size() verringert sich um 1)
8a. c.removeFirst() – das erste Element aus dem Container entfernen (äquivalent zu c.remove(0), c.size() verringert sich um 1)
8b. c.removeLast() – das letzte Element aus dem Container entfernen (äquivalent zu c.remove(c.size()-1), c.size() verringert sich um 1)
9a. c.removeSmallest() – das kleinste Element aus dem Container entfernen (dies bezieht sich auf eine Eigenschaft der Datenelemente bzw. Schlüssel, im Unterschied zu 8a, wo es um die Position im Container geht. c.size() verringert sich um 1)
9b. c.removeLargest() – das größte Element aus dem Container entfernen (dies bezieht sich auf eine Eigenschaft der Datenelemente bzw. Schlüssel, im Unterschied zu 8b, wo es um die Position im Container geht. c.size() verringert sich um 1)

Facts

• Jede dieser Operationen kann sehr effizient implementiert werden.
• Keine Datenstruktur ist bekannt, die alle diese Operationen effizient implementiert.

Beispiele

Je nachdem welche Operation effizient sein soll, wird eine andere Container Datenstruktur ausgewählt. Die Operation 0. (c.size()) wird von allen Containern effizient unterstützt.

• (statisches) Array
  Das Array ist die einfachste und Datenstruktur, es kann einfach als aufeinanderfolgender Bereich von Speicherzellen implementiert werden. Jede dieser Speicherzellen nimmt ein Objekt als Datenelement auf. Die Größe ist nicht veränderbar (daher der Name statisch).
  Das statische Array unterstützt die Operationen 1a. c.get(i) und 4a. c.set(i, v).
• Dynamisches Array:
  Die Größe ist veränderbar, aber nur durch Anfügen oder Entfernen eines Elements am Ende des Arrays. Die unterstützen Operationen sind dieselben wie die des statischen Arrays, zusätzlich unterstützt das dynamische Array die Operationen 6b. c.append(v) und 8b. c.removeLast(). Wir beschreiben im Abschnitt Amortisierte Komplexität, wie man dies effizient implementieren kann.
• Dictionary
  Ein Dictionary besteht aus einem Key(Schlüssel) und einem Value(Wert). Jeder Schlüssel bekommt einen Wert zugewiesen.
  Es unterstützt dieselben Operationen wie das Array ausserdem noch c.get(key), c.insert(key,value), c.remove(key)
• Verkettete Liste
  Im Gegensatz zum Array müssen die Speicherzellen nicht nacheinenander im Speicher abgelegt sein.
  Sie unterstützt die Operationen: c.first(), c.insert(pos, value), c.remove(pos), c.get(pos)
• Doppelt verkettete Liste:
  Im Gegensatz zur verketteten Liste, hat jedes Element einen Zeiger auf das vorherige Objekt sowie auf das darauffolgende Objekt
  Sie unterstützt dieselben Operationen wie die Liste + ...
• Stack(Stapelspeicher)
  speichert/stapelt die Objekte mit push in einen Speicher wiederrum mit pop kann das oberste Element herausgeholt werden: LIFO (Last In First Out)
  Operationen: c.last(), c.append(), c.removeLast()
• Queue
  Eine Queue ist wie eine Warteschlange an der Kasse im Supermarkt, bedient wird derjenige der als erster an die Kasse kommt: FIFO (First In First Out)
  Operationen: c.first(), c.append(), c.removeFirst()
• Deque
  (Double Ended Queue) wie STACK + QUEUE, Objekte können an beiden Enden entfernt oder eingefügt werden
• MinPriorityQueue
  Warteschlange, die die schnellsten Jobs vorzieht (z.B. an der Kasse im Supermarkt diejenigen, die die wenigsten Produkte kaufen möchten)
  Mögliche Operationen: c.smallest(), c.removeSmallest(), c.insert()
• MaxPriorityQueue
  Warteschlange, die die größten Jobs vorzieht
  Unterstützte Operationen sind: c.largest(), c.removeLargest(), c.insert()
• MinMaxPriorityQueue
  MinPriorityQueue + MaxPriorityQueue kombiniert die 2 vorherigen Verfahren