2 dimensionale vectoren

!!!Achtung: Dieser Artikel ist veraltet. Ich lasse ihn dennoch für alle lesbar, da trotzdem noch viel (meiner Meinung nach) richtiges enthalten ist!!!

 

Da ich mich in letzter Zeit immer mal wieder darüber geärgert habe, dass ich noch keine wirklich gute Implementierung für einen 2 dimensionalen vector geschrieben habe, und ständig verschachtelte Konstrukte zweier vectoren genutzt habe, habe ich mich mal dran gesetzt und ein wenig herum experimentiert. Ich habe natürlich nicht das Rad komplett neu erfunden, sondern habe mich an existierende Ideen gehalten.

In dem nachfolgenden Beitrag versuche ich die Nachteile der verschachtelten vectoren zu erklären und die generelle Funktionsweise von einem internen vector vorzustellen.

 

Nachteile der Verschachtelung:

Eine verschachtelte Datenstruktur ist im Prinzip folgendes:
std::vector<std::vector<T>>
Man hat hier also einen vector, der vectoren mit ints hält, um eine 2 dimensionale Datenstruktur zu simulieren. An sich ist diese Idee gar nicht so falsch, denn hier kann man direkt über die at Methoden oder die [] Operatoren auf die Einträge zugreifen. Warum das allerdings keine wirklich gute Idee ist, soll der nachfolge Text verdeutlichen.

Um dieses System sicher nutzen zu können, ist es zwingend erforderlich, eine eigene Klasse um den vector zu bauen, da ansonsten nicht sichergestellt werden kann, dass bei einer Größenänderung alle Zeilen und Spalten betroffen sind, da man ansonsten sehr schnell einen out of range error hervorruft oder unnötig Speicherplatz verschwendet.
Durch die Verschachtelung, kann man nun nicht alle inneren vectoren auf einmal verändern, sondern muss diese nacheinander bearbeiten und das kann unter Umständen sehr zu lasten der Performance gehen, da pro Zeile oder Spalte (je nachdem, wie man seine Datenstruktur anlegt) eine Allocation benötigt, die potentiell erst einmal teuer ist. Man kann sich das z.B. so vorstellen, als würden bei einem Imbiss mehrere Leute Pommes bestellen, und der Imbiss frittiert jede Portion einzeln nacheinander, statt alle zusammen auf einmal. Das verlängert nicht nur die Zeit, die man für die einzelnen Kunden benötigt, sondern macht diese auch unzufrieden. Die unzufriedenen Kunden wären in diesem Fall die Nutzer des Programms 😉
Da in einem vector alle Daten hintereinander im Speicher liegen, ist das Vergrößern/Verkleinern noch einmal doppelt teuer, da der nachfolgende Speicher erst einmal weiter nach hinten verschoben werden muss, damit zwischendrin Speicher angefordert werden kann. Die nachfolgenden Bilder sollen das oben genannte Problem veranschaulichen.

4x4Vector
Dieses Bild stellt einen logischen 3×3 vector dar. Das ist NICHT die Darstellung für den intern genutzten Speicher.

 

 

 

 

6x4VectorAlloc
Wieder eine Darstellung eines logischen 2 dimensionalen vectors. Diesmal jedoch mit einer Größe von 5×3. Die gestrichelten Kästchen stellen den neu allokierten Speicher dar. An sich sieht das ganz vernünftig aus, schauen wir uns allerdings mal an, was im Hintergrund wirklich passiert.

 

 

Die folgenden Bilder zeigen den Zusammenhang des internen Speichers und soll die Problematik beim Vergrößern ein wenig besser illustrieren.

4x4VectorMemory

Wie man hier gut sieht, sind die Speicherblöcke der einzelnen Zeilen direkt hintereinander im Speicher. Das ist auch gut so, da so ein Zugriff auf jede dieser Zellen in konstanter Zeit erfolgen kann. Was aber getan werden muss, wenn wir unsere Struktur vergrößern, zeigt das nächste Bild.

 

6x4VectorMemoryAlloc

Dieses Bild stellt die Schritte dar, die für die 3 Zeilen durchgeführt werden, wenn man sie auf die oben erklärte Art und Weise ausführt.

  1. 2 zusätzliche Blöcke werden angefordert und die Zeilen 2 und 3 werden im Speicher nach hinten geschoben, um Platz zu schaffen
  2. Wieder werden 2 Blöcke angefordert (diesmal um die Zeile 2 zu vergrößern) und Zeile 3 wird nach hinten geschoben.
  3. 2 Blöcke werden angefordert, und an Zeile 3 angehängt

Wie man sieht, sind 3 allocationen nötig und Zeile 2 wird einmal und Zeile 3 sogar 2 mal verschoben. Leider ist das sogar der optimale Fall.
Wenn der vector in einem Speicherbereich liegt, der nicht genug Platz zum Vergrößern bietet, wird die gesamte Struktur verschoben, und nicht nur die dahinter liegenden Zeilen. Das kann auch bei jeder Vergrößerung einer Zeile passieren. Wenn man also seine Klasse öfter transformiert, wird die Performance bei einer gewissen Anzahl an Elementen deutlich leiden.

 

Das ein vector System

Wie also gerade beschrieben, ist es sinnvoller den Speicherplatz einmal zu reservieren, statt stückchenweise, allerdings ist das mit dieser Struktur nicht möglich.
Aus diesem Grund bietet es sich an, EINEN großen vector zu nutzen, diesen einmal zu vergrößern/verkleinern und die Daten intern EINMAL zu verschieben.
Trotzdem können wir die einzelnen Zellen genau bestimmen. Die Formel für den Index einer Zelle ist ziemlich einfach.
index = y * breite + x
Möchten wir also bei einem vector von 3 x 3 (9 Zellen) auf die Zelle x = 0 und y = 0 zugreifen, erhalten wir einen internen Index von 0 (das erste Element im vector), bei x = 2, y = 1 wäre der Index 6.

Aber wie können wir das Ganze nun transformieren?

Um diesen vector zu transformieren, benötigen wir die neue und die alte Größe. Es bietet sich an, diese beiden Dimensionen (also Höhe und Breite) getrennt von einander zu behandeln.
Neue Zeilen anzufügen ist sehr trivial. Wir vergrößern den vector um
(neueHöhe - alteHöhe) * breite
Elemente. D.h., wenn wir unseren 3 x 3 vector um 2 Zeilen erweitern wollen, fügen wir
5(neueHöhe) - 3(alteHöhe) * 3(breite) = 6
Zellen hinten an. Da wir nichts zwischen unseren alten Daten verändern, müssen wir diese auch nicht verschieben.
Schematisch dar gestellt, sieht das folgendermaßen aus:

Vector2DresizeHeight
Hier kann man ganz gut sehen, das hier die Zeilen hintereinander liegen, und deswegen die bereits vorhandenen Zeilen nicht verändert werden.
Jedoch ist auch hier nicht garantiert, dass der Vector an der momentanen Speicherposition genug Platz hat. Deswegen ist es möglich, dass er an eine andere Adresse verschoben wird. Allerdings passiert das garantiert nur einmalig und ist auch eine vergleichsweise sehr günstige Operation. Zudem können wir das auch gar nicht erst verhindern, da das im Hintergrund passiert. Wichtig ist jedoch, dass Referenzen und Zeiger auf Elemente innerhalb dieses Vectors danach ungültig sein können!
Das Verkleinern funktioniert im Prinzip genau gleich. Auch hier muss nichts verschoben werden, da die zu löschenden Daten bereits am Ende liegen.

Die Breite wird mit der gleichen Formel verändert, allerdings müssen wir jetzt intern noch die bereits vorhandenen Daten verschieben, damit sie am Ende auch an der richtigen Stelle stehen.
Dazu zuerst mal eine schematische Darstellung.

Vector2DresizeWidth
Wie man sieht, kann hat man hier ein bisschen mehr Arbeit, als beim Höhen verändern, ist aber prinzipiell auch recht einfach. Damit wir jede Zeile nur einmal verschieben müssen, fangen wir an, uns von hinten nach vorne zu arbeiten, weil wir sonst möglicherweise noch zu verschiebende Einträge überschreiben würden. D.h. zuerst auf die benötigte Breite festsetzen und dann die vorhandenen Elemente entsprechend nach hinten verschieben.
Beim Verkleinern arbeiten wir uns diesmal von vorne nach hinten und verschieben die Einträge, die behalten werden sollen, nach vorne.

Je nach Bedarf, kann man nun seine vector2D Klasse die Iteratoren von std::vector nach außen anbieten, und damit eine Iteration von außen über alle Elemente ermöglichen.

 

Zeilen und Spalten Modelle

Jetzt kommen wir zu einem Bereich, der bei solchen Implementierungen oft vergessen wird. Wir haben nun einen funktionierenden 2 dimensionalen vector und Zugriff auf alle Elemente. Wenn wir aber nur über eine Spalte/Zeile iterieren wollen, sind wir gezwungen, das über die Indexes zu machen.
Das hat aber den Nachteil, dass keine Funktionen genutzt werden können, die Iteratoren erwarten.
Dazu habe ich folgende Lösung entwickelt:
Die Vector2D Klasse stellt Methoden bereit, die eine Art „Modell“ ihrer Zeilen und Spalten zurück liefert. Diese Modelle beinhalten lediglich einen Index auf die Zeile/Spalte und eine Referenz auf das Vector2D Objekt. Diese Modelle bieten direkten Zugriff auf die darunter liegenden Elemente der Zeile/Spalte und stellen auch Iteratoren bereit. Prinzipiell nicht sonderlich kompliziert.

Mit diesen Modellen können wir nun die range based for Loops und andere nette Dinge nutzen, die uns vorher verwehrt geblieben sind.

Eine vollständige Implementierung und Dokumentation des oben beschriebenen Systems findet ihr hier:
Vector2D.h
Dokumentation

 

Ich freue mich über jedwede Kritik und Kommentare

mfg

SigSlot, eine Beziehung ohne Wissen.

!!!Achtung: Dieser Artikel ist veraltet. Ich lasse ihn dennoch für alle lesbar, da trotzdem noch viel (meiner Meinung nach) richtiges enthalten ist!!!

 

Eine Beziehung, ohne davon zu wissen?! Wie soll das gehen?

Ich weiß, es ist eine ziemlich seltsame Aussage, aber ich rede hier auch nicht von einer Zwischenmenschlichen Beziehung, sondern von einem bekannten Programmier-Pattern.

Was ist eigentlich ein Pattern?

Ein Pattern ist im Prinzip ein Lösungsvorschlag zu einem bekannten Problem. Die Pattern haben den Vorteil, dass sich schon viele kluge Menschen darüber Gedanken gemacht haben und dadurch eine Lösung zu Stande gekommen ist, die mit hoher Wahrscheinlichkeit für die entsprechenden Problemfälle gut zu benutzen ist. Das heißt natürlich nicht, dass man alle Probleme mit Hilfe dieser Patterns lösen muss. Man sollte immer abwägen, ob dem eigentlichen Problem damit geholfen ist oder ob man sich damit nur noch mehr Probleme auferlegt.

Aber genug von Patterns im Allgemeinen, kommen wir zu unserem spezifischen Problem.

Das observer bzw. listener Pattern:

Dieses Pattern beschreibt, wie 2 Objekte unterschiedlichen Typs miteinander kommunizieren können, ohne von einander zu wissen, wobei die Kommunikation eine Einbahnstraße darstellt.

Das heißt im Prinzip haben wir auf der einen Seite einen Sender und auf der anderen Seite mehrere Empfänger. Diese Empfänger lauschen jetzt darauf, bis der Sender sich meldet und ihnen ein Signal sendet, das sie verarbeiten können. Den Sender interessiert nicht, wer alles das Signal empfangen hat, oder was mit dem Signal genau passiert, er weiß lediglich, dass er es versendet hat. Damit ist seine Arbeit getan.

Dem Empfänger ist der letztendliche Sender auch egal, da er lediglich mitbekommt, dass ein Signal an kommt und nicht wer es sendet.

 

Verschiede Begrifflichkeiten:

Im Laufe dieses Posts werden einige Begrifflichkeiten im Bezug auf das Pattern auftauchen, die ich hier mal näher erklären möchte.

Signal: Im Prinzip ist ein Signal nichts anderes als man erwarten würde. Es signalisiert, dass ein Ereignis eingetreten ist und sendet das an seine Empfänger. Es kümmert sich nicht darum, warum es etwas schickt, noch an wen es etwas schickt. Alle Empfänger die auf dieses Signal „lauschen“ erhalten es auch.

Slot: Ein Slot ist eine Funktion, die durch ein Signal ausgelöst wird. Ein Slot weiß nicht, woher ein Signal kommt oder warum es gesendet wurde, er erhält lediglich die durch das Signal bereit gestellt Informationen.

Empfänger/Receiver: Ein Receiver ist ein Objekt, das ein oder mehrere Slots besitzt.

Verbindung/Connection: Die Beziehung von einem Signal zu einem Slot nennt man Connection.

Emit: Emit heißt so viel wie „aussenden“ und bezeichnet den Vorgang, wenn ein Signal ausgelöst wird.

Wie man sich nun denken kann, setzt sich SigSlot demzufolge aus den beiden Begriffen Signal und Slot zusammen 😉

 

Überblick über einige Implementierungen:

Für dieses System gibt es verschiedene Implementierungen, die einen besser, die anderen schlechter. Die Beste mir bekannte, dafür auch die aufwendigste, bietet das Qt Framework. Hierbei wurde das Pattern geschickt in die Sprache „verflochten“, sodass eine sehr intuitive und effektive Nutzung möglich ist. Allerdings ist das Signal/Slot System ein sehr, sehr großer Teil des Frameworks und hat viele Abhängigkeiten, sodass eine Nutzung in kleineren Projekten zu viel Overhead und Konfigurationsarbeit mit sich ziehen würde.

Eine andere mir bekannte Implementierung ist in der boost Library. Auch wenn ich mich bisher nicht sonderlich intensiv mit boost::signals bzw. boost::signals2 (die Thread sichere Variante) beschäftigt habe, ist das mit Sicherheit keine schlechte Alternative. Allerdings sind viele Leute der Ansicht, dass die boost::signals(2) Library nicht performant genug ist.

Nach ein wenig mehr Recherche habe ich die sigslot Implementierung gefunden. Auf den ersten Blick eine sehr robuste, allerdings auch veraltete Implementierung. Durch C++11 könnte man den Code wesentlich einfacher und sauberer gestalten. Der Hauptgrund, warum ich letztendlich gegen diese Implementierung bin ist, dass sie Rekursion nicht beachtet. Wenn man ein signal/Slot löscht, während man in der „emit“ Phase ist, läuft man unweigerlich in einen Error. Das ständig im Auge zu behalten, wann ich wo welche Objekte löschen darf, war mir ein Dorn im Auge; … ein ziemlich großer sogar.

Damit war letztendlich die Entscheidung gefallen, etwas eigenes zu entwickeln. Nach ein wenig herumprobieren und Stolpern über den ein oder anderen Denkfehler, habe ich schlussendlich ein Konzept entwickelt, was meinen Anforderungen stand hält und sich der Features des C++11 Standards bedient.

Ein kurzer Überblick der Probleme:

Es gibt, wie bereits gezeigt, verschiedene Möglichkeiten dieses Pattern zu implementieren. Um aber mal einen kleinen Überblick über die Probleme zu geben, die während der Entwicklung einer Implementierung entstehen können, versuche ich Schritt für Schritt aufbauende Beispiele zu liefern, wie man etwas angehen kann und was dabei die Nachteile sind.

Die wohl einfachste Möglichkeit um ein Signal zu versenden, ist eine Methode die eine Methode eines anderen Objekts aufruft.

class Label
{
public:
    void onButtonClicked()
    {
        // mach was
    }
};

class Button
{
    Label* m_pLabel;

public:
    Button(Label* pLabel)
        : m_pLabel(pLabel)
    {}

    void clicked()
    {
        m_pLabel->onButtonClicked();
    }
};

int main()
{
    Label label;
    Button button(&label);
    button.clicked();
}

Wie man sieht, ist das ganze sehr zweckmäßig über zwei einfache Methoden in den Klassen Label und Button geregelt. Label::onButtonClicked wird aufgerufen, wenn Button::clicked aufgerufen wird. Das Ganze bringt aber gewisse Unschönheiten mit sich. Will man denn jedes mal auch ein Label haben, wenn man einen Button erstellt? Was ist, wenn ich das nicht möchte?

Wie man sieht ist die Benutzung solch eines Designs zwar einfach aber auch sehr beschränkt. Ich muss mir für jeden Anwendungsfall meine eigene Button Klasse erstellen und alle Objekte, die ein Signal erhalten sollen, mindestens als Zeiger oder Referenz bekannt machen. Das bringt noch einen Haufen Probleme mit sich. Was ist z.B. wenn das Objekt, welches das Signal erhalten soll, gelöscht wird? Dann sind Aufräumarbeiten von Außen nötig. Das gilt es allerdings zu vermeiden, da solche Konstrukte äußerst fehleranfällig und schlecht zu warten sind.

Wir haben also mehrere große Nachteile:

  • Sender muss Empfänger explizit kennen
  • schlechte Erweiterbarkeit
  • kein automatisches Aufräumen bei Löschung von Objekten

Schauen wir uns die ersten 2 Punkte an, erkennen wir einen gewissen Zusammenhang, den wir uns im nächsten Abschnitt näher anschauen wollen.

Eine Möglichkeit das Ganze ein wenig generischer zu machen, wäre für unsere Buttonklasse einen std::vector mit Zeigern vom Typen Receiver (Empfänger) oder ähnlichem zu füllen. Wir könnten eine abstracte Methode „onButtonApply“ einführen, und somit unsere Empfänger dynamisch hinzufügen oder auch wieder löschen.

Das sähe dann in etwa so aus:

class Receiver
{
public:
    virtual void onButtonClicked() = 0;
};

class Label : public Receiver
{
public:
    void onButtonClicked()
    {
        // mach was
    }
};

class Button
{
    std::vector<Receiver*> m_pReceivers;

public:
    void addReceiver(Receiver* pReceiver)
    {
        m_pReceivers.push_back(pReceiver);
    }

    void clicked()
    {
        for (auto pRec : m_pReceivers)
            pRec->onButtonClicked();
    }
};

int main()
{
    Label label;
    Button button;
    button.addReceiver(&label);
    button.clicked();
}

Die Nachteile hier liegen auf der Hand:

  • Button ruft immer eine explizite Methode der Objekte auf
  • Dementsprechend für jedes Signal eine eventuell nur einmal genutzte Methode in der Interface Klasse
  • Kein automatisches Aufräumen

Ist zwar an sich keine allzu schlechte Sache, aber für eine generische Lösung noch viel zu beschränkt.

Überlegen wir also ein Stück weiter:

C++ bietet uns die Möglichkeit Funktionszeiger zu nutzen. Funktionszeiger sind im Prinzip Zeiger auf eine Stelle im Code. Jede Funktion hat ihre eigene Adresse, die man dadurch referenzieren kann. Schwieriger wird es bei Methoden (Klassenfunktionen). Diese funktionieren ein wenig anders, was den Aufwand für eine generische Lösung erhöht aber nicht unmöglich werden lässt.
Wir könnten uns dabei die STL zu Nutze machen und std::function und std::bind nutzen. Ein guter Weg, den wir im nächsten Schritt mal weiter verfolgen möchten.

#include <functional>
#include  <vector>
#include <iostream>

class Label
{
public:
     void onButtonClicked()
     {
          std::cout << "called!";
     }
};

class Button
{
     std::vector<std::function<void()>> m_pReceivers;

public:
     void addReceiver(std::function<void()> func)
     {
          m_pReceivers.push_back(func);
     }

     void clicked()
     {
          for (auto pFunc : m_pReceivers)
               pFunc();
     }
};

int main()
{
     Label label;
     Button button;
     button.addReceiver(std::bind(&Label::onButtonClicked, &label));
     button.clicked();
}

Super! Wir haben nun einen std::vector in dem wir verschiede Objekte beliebiger Typs mitsamt ihrer Methode aufnehmen können.

Allerdings bleiben noch 2 weitere Problem:

  • mühsam zu erweitern
  • kein automatisches Aufräumen

Um das Erweitern zu vereinfachen lagern wir den Signal Code aus Button in eine eigene Klasse Signal aus und erstellen uns einen public Member von Signal in Button. Diesen nennen wir „clicked“.

Das mag auf dem ersten Blick ein wenig verwirren, allerdings macht das bei näherem Hinsehen durchaus Sinn, so vorzugehen.

Dadurch betrachten wir nun die Signale nicht länger als reine Funktion, sondern als Objekte, was sie ja eigentlich auch sein sollen. Sie besitzen nun gewisse Automatismen, welche nötig sind um das Programm am Laufen zu halten und Fehlern vorzubeugen.

Diese Signal Objekte besitzen nun jeweils ihre eigene Liste der Empfänger und der Methoden, die sie aufrufen.

#include <functional>
#include  <vector>
#include <iostream>

class Label
{
public:
    void onButtonClicked()
    {
        std::cout << "clicked!";
    }

    void onButtonReleased()
    {
        std::cout << "released!";
    }
};

class Signal
{
    std::vector<std::function<void()>> m_pReceivers;

public:
    void addReceiver(std::function<void()> func)
    {
        m_pReceivers.push_back(func);
    }

    void emit()
    {
        for (auto pFunc : m_pReceivers)
            pFunc();
    }
};

class Button
{
public:
    // unsere beiden public Signal Member
    Signal clicked;
    Signal released;
};

int main()
{
    Label label;
    Button button;
    button.clicked.addReceiver(std::bind(&Label::onButtonClicked, &label));
    button.clicked.emit();
    button.released.addReceiver(std::bind(&Label::onButtonReleased, &label));
    button.released.emit();
}

Da wir nun Signale als Objekte betrachten und nicht als reine Funktionen, haben wir die Möglichkeit das Signal eigenständig arbeiten zu lassen. Sie halten ihre eigene Liste auf Empfänger und können die „Verbindung“ zu ihren Slots eigenständig trennen, wenn eines der beiden nicht mehr existiert.

Aber wie setzen wir das automatische disconnecten nun um?
Mein Lösung dazu ist, dass alle Objekte, die ein Signal empfangen sollen, von einer gemeinsamen Basisklasse erben müssen. Diese Basisklasse enthält den nötigen Code zum Lösen einer Verbindung. D.h. im Klartext: Das Empfänger Objekt sendet im Destruktor eine Anweisung an alle mit ihm verbundenen Signale, um die Verbindung zu trennen.
Das hat zwar zur Folge, dass ich nicht mehr alle beliebigen Objekte an mein Signal übergeben kann, sondern nur noch diese, die von der Receiver Klasse erben, aber das gibt mir auch entsprechende Sicherheit, dass ich mich um das Aufräumen nicht mehr kümmern muss.
Da ein Beispiel für die weitere Implementierung ein wenig zu weit gehen würde, poste ich hier ein paar Links, die zu meiner Implementierung führen.
Der Code ist dokumentiert und kann hier nachgelesen werden:

connection.h
receiver.h
receiver.cpp
signal.h

Ich würde mich über ein paar Kommentare freuen, gerne auch Kritik und Verbesserungsvorschläge 😉

mfg