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: Einigen 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, Dictionnary,...) siehe auch Datenstrukturen

mögliche Operationen

Welche Operationen hätte man denn gerne bei einer solchen Container Datenstruktur?
Was benötigt ein Algorithmus? Wer organisiert die Daten?
Diese Organisation erfolgt über Jahre, indem durch Erfahrungen gesammelt wird was Algorithmen für Anforderungen an Datenstrukturen stellen sollten.

Auflistung der möglichen Operationen von Container Datenstrukturen:

(v = value)

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 Element überschreiben

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

   4 v = c.largest()/smallest()
   Das größte bzw. kleinste Element 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 Element entfernen

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

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

   13 c.removeSmallest()/Largest()
   das kleinste bzw. größte Element 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: unterstützt die ersten 3
• dynamischens Array: wie Array, zusätzlich c.append & c.removeLast
• Dictionnary: wie Array ausserdem c.geht(key), c.insert(key,value), c.remove(key)
• verkettete Liste:c.first(), c.insert(pos, value), c.remove(pos), c.get(pos)
• doppelt verkettete Liste:* wie Liste + ...
• Stack(Stapel): LIFO (Last In First Out) c.last(), c.append(), c.removeLast()
• Queue: FIFO (First In First Out) c.first(), c.append(), c.removeFirst()
• Deque: (Double Ended Queue) wie STACK + QUEUE
• MinPriorityQueue: c.smallest(), c.removeSmallest(), c.insert()
• MaxPriorityQueue: c.largest(), c.removeLargest(), c.insert()
• MinMaxPriorityQueue: MinPriorityQueue + MaxPriorityQueue