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ötigt ein Algorithmus? 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:

c.size() ist immer unterstützt

   1 a) v = c.get(i) / b)v = c.get(pos)
   i-tes Objekt suchen

   2 v.set(i, value)
   i-tes Objekt überschreiben

   3 a) v = c.first()/last()
   erstes bzw. letztes Objekt erhalten

   4 v = c.largest()/smallest()
   Das größte bzw. kleinste Objekt erhalten

   5 v = c.get(key)
   Verallgemeinerung von 1 für beliebige Schlüssel (nicht nur integer)
   den Key(Schlüssel) einer Value(Wert) erhalten.

   6 c.append(v)
   Objekt am Ende anhängen (mit c.set() verwandt)

   7 c.prepend(v)
   Objekt vorne einfügen

   8 c.insert(i, v)
   Objekt an beliebiger Position einfügen (Werte werden ab i verschoben)

   9 c.insert(key, v)
   Ein Schlüssel-Wert Paar einfügen

   10 c.removeFirst()/Last()
   Das erste bzw. letzte Objekt entfernen

   11 c.remove(i)
   Das Objekt an Position i entfernen

   12 c.remove(key)
   Einen Schlüssel entfernen

   13 c.removeSmallest()/Largest()
   das kleinste bzw. größte Objekt entfernen

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

• Array
  Das Array ist die einfachste Datenstruktur, in einem Array können Variablen gespeichert werden. Die Größe ist nicht veränderbar
  das Array unterstützt die ersten 3 Operationen
• Dynamisches Array:
  die Größe ist veränderbar also die unterstützen Operationen sind dieselben wie die des Arrays, zusätzlich unterstützt das dynamische Array c.append & c.removeLast
• 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