Warteschlangen

Das letzte noch fehlenden Element der Sequence Container: std::deque. Im Prinzip wie ein Vektor, aber das Einfügen und Entfernen an Anfang und Ende sind in O(1) möglich. Das macht sie perfekt für die Implementierung von Warteschlangen (deswegen auch deque: double ended queue).

Video

Quellcode

#include <iostream>
#include <deque>
#include <memory>
#include <functional>

class ExecutionManager
{
  std::deque<std::function<void ()>> mTasks;

public:
  
  void addTask(std::function<void ()> const &task) {
    mTasks.push_back(task);
  }
  
  void execute()
  {
    while (!mTasks.empty()) {
      auto task = mTasks.front();
      mTasks.pop_front();
      task();
    }
  }
};

void taskFn()
{
  std::cout << "taskFn() aufgerufen\n";
}

struct TaskFunctor
{
  void operator()()
  {
    std::cout << "TaskFunctor aufgerufen\n";
  }
};

int main()
{
  ExecutionManager e;
  
  e.addTask([]() { std::cout << "Erster Task\n"; });
  e.addTask(taskFn);
  e.addTask(TaskFunctor());
  e.addTask(taskFn);
  
  e.execute();
}

Erklärung

Ziel der Übung ist diesmal die Entwicklung einer Klasse, die eine Menge an Tasks (oder Jobs, je nachdem, wie man das bezeichnen will) verwaltet und ausführt. Ultimativ soll dass natürlich mal parallel geschehen, aber es soll ja langsam losgehen. Die zentrale Datenstruktur einer solchen Klasse ist eine Warteschlange, in der Jobs gesammelt werden können und aus der sie dann zur Ausführung entnommen werden. Das geschieht typischerweise nach FIFO-Manier: first in, first out. Mit einer std::deque lässt sich das wunderbar realisieren, indem man einfach Tasks ans Ende stopft und am Anfang entnimmt (man könnte das auch mit std::list realisieren, aber std::deque bietet zusätzlich noch den wahlfreien Zugriff, falls man dann doch mal mitten in die Warteschlange greifen muss).

Der ExecutionManager oben bietet zwei grundlegende Funktionen: addTask(), um einen neuen Task aufzunehmen und execute(), um die gesammelten Jobs auszuführen. Tasks sind hierbei einfache Funktionsobjekte, die vom ExecutionManager aufgerufen werden. Dank std::function lässt sich das gut abstrahieren, ob nun hier ein Funktionspointer, eine Lambda-Funktion oder ein Funktionsobjekt verwendet wird. Die übergebenen Funktionsobjekte werden mittels push_back() ans Ende der std::deque angehängt. Diese Operation ist laut Standard in O(1) und damit unabhängig vom Füllstand der Queue effizient. execute() entnimmt jeweils einen Job am Anfang der Queue und führt ihn aus. Dazu dient die Methode front(). Diese holt ebenso wieder in O(1) das erste Element aus der Liste. Da man bei so einer Warteschlange den Job typischerweise dann entfernen will, um ihn nicht nochmal auszuführen, findet noch die Methode pop_front() Verwendung, die genau das tut. Auch hier ist wieder O(1) angesagt. Praktisch wäre hier eine Methode, die front() und pop_front() vereinigt, da das nun mal eine typische Verwendung von std::deque als Warteschlange ist. Leider gibt es die entsprechende Funktion nicht. So sind also immer zwei Aufrufe angesagt.

Wichtig im Code oben ist noch die Prüfung auf !mTasks.empty() in Zeile 18. Ein Aufruf von front() auf eine leere std::deque resultiert in undefiniertem Verhalten, so ziemlich dem unangenehmsten, was der C++-Standard zu bieten hat. Theoretisch dürfte das Programm in diesem Fall dann die komplette Platte löschen. Das wäre zwar weder robust, noch besonders freundlich, aber standardkonform. Ergo geht man undefinierten Verhalten am besten aus dem Weg. In unserem Fall, indem wir vorher prüfen, ob in der std::deque überhaupt noch Elemente enthalten sind.