Die Boost C++ Bibliotheken
Die Bibliothek Boost.CircularBuffer bietet einen Ringspeicher an. Dabei handelt es sich um einen Container mit folgenden zwei wesentlichen Eigenschaften:
Die Kapazität des Ringspeichers ist konstant und wird von Ihnen vorgegeben. Die Kapazität ändert sich nicht automatisch, wenn Sie eine Methode wie push_back() aufrufen. Nur Sie können die Kapazität ändern. Die Größe des Ringspeichers wird durch die Kapazität begrenzt.
Trotz konstanter Kapazität kann beliebig oft push_back() aufgerufen werden, um Elemente im Ringspeicher abzulegen. Ist die maximale Größe erreicht und der Ringspeicher voll, werden Elemente überschrieben.
Ein Ringspeicher bietet sich an, wenn der vorhandene Speicherplatz begrenzt ist und verhindert werden soll, dass ein Container beliebig groß wird. Auch dann, wenn alte Daten keine Rolle mehr spielen, weil zwischenzeitlich genügend neue Daten vorliegen, kann ein Ringspeicher eine gute Wahl sein. So wird Speicherplatz automatisch wiederverwendet, und alte Daten werden von neuen überschrieben.
Um den Ringspeicher der Bibliothek Boost.CircularBuffer nutzen zu können, muss die Headerdatei boost/circular_buffer.hpp eingebunden werden. Die Headerdatei stellt die Klasse boost::circular_buffer zur Verfügung.
boost::circular_buffer in Aktion#include <boost/circular_buffer.hpp>
#include <iostream>
int main()
{
typedef boost::circular_buffer<int> circular_buffer;
circular_buffer cb{3};
std::cout << cb.capacity() << '\n';
std::cout << cb.size() << '\n';
cb.push_back(0);
cb.push_back(1);
cb.push_back(2);
std::cout << cb.size() << '\n';
cb.push_back(3);
cb.push_back(4);
cb.push_back(5);
std::cout << cb.size() << '\n';
for (int i : cb)
std::cout << i << '\n';
}boost::circular_buffer ist ein Template, das den Typ der zu speichernden Elemente als Parameter erwartet. So können im Beispiel 16.1 im Ringspeicher cb Ganzzahlen vom Typ int abgelegt werden.
Die Kapazität des Ringspeichers wird nicht als Template-Parameter angegeben. Stattdessen legen Sie die Kapazität bei der Instanziierung des Ringspeichers fest. Während der Standardkonstruktor von boost::circular_buffer einen Ringspeicher mit einer Kapazität von null Elementen erstellt, steht ein Konstruktor zur Verfügung, um die Kapazität auf einen beliebigen Wert zu setzen. Dieser Konstruktor wird im Beispiel 16.1 verwendet: Der Ringspeicher cb erhält eine Kapazität von drei Elementen.
Sie erhalten die Kapazität eines Ringspeichers, indem Sie die Methode capacity() aufrufen. Im Beispiel 16.1 gibt capacity() folglich 3 zurück.
Die Kapazität ist nicht gleichbedeutend mit der Anzahl gespeicherter Elemente. Während der Rückgabewert von capacity() konstant ist, kann size() unterschiedliche Werte zurückgeben. Der Rückgabewert von size() liegt immer zwischen einschließlich 0 und der Kapazität des Ringspeichers.
Wenn Sie Beispiel 16.1 ausführen, sehen Sie, dass der erste Aufruf von size() 0 zurückgibt. Zu diesem Zeitpunkt sind keine Elemente im Ringspeicher gespeichert. Nachdem dreimal push_back() aufgerufen wurde, befinden sich drei Elemente im Ringspeicher – der zweite Aufruf von size() gibt 3 zurück. Der wiederholte Aufruf von push_back() führt nicht dazu, dass der Speicher wächst. Die drei neuen Zahlen überschreiben die bisher gespeicherten drei Zahlen. Deswegen gibt size() auch beim dritten Aufruf 3 zurück.
Zur Kontrolle werden am Ende des Programms alle gespeicherten Zahlen ausgegeben. Dabei werden lediglich die Zahlen 3, 4 und 5 in die Standardausgabe geschrieben. Die zuerst gespeicherten Zahlen 0, 1 und 2 wurden von diesen überschrieben.
boost::circular_buffer#include <boost/circular_buffer.hpp>
#include <iostream>
int main()
{
typedef boost::circular_buffer<int> circular_buffer;
circular_buffer cb{3};
cb.push_back(0);
cb.push_back(1);
cb.push_back(2);
cb.push_back(3);
std::cout << std::boolalpha << cb.is_linearized() << '\n';
circular_buffer::array_range ar1, ar2;
ar1 = cb.array_one();
ar2 = cb.array_two();
std::cout << ar1.second << ";" << ar2.second << '\n';
for (int i : cb)
std::cout << i << '\n';
cb.linearize();
ar1 = cb.array_one();
ar2 = cb.array_two();
std::cout << ar1.second << ";" << ar2.second << '\n';
}Im Beispiel 16.2 werden einige Methoden eingesetzt, die nicht von anderen Containern bekannt sind. Es handelt sich hierbei um die Methoden is_linearized(), array_one(), array_two() und linearize(). Diese Methoden sind deswegen interessant, weil sie die Funktionsweise des Ringspeichers verdeutlichen.
Ein Ringspeicher ähnelt std::vector. Die Kapazität ist zwar konstant, und Elemente werden überschrieben, wenn der Speicher voll ist. Die Implementation von boost::circular_buffer könnte dennoch problemlos auf std::vector basieren. Während der Anfang und das Ende eines Vektors jedoch klar definiert sind, ist dies beim Ringspeicher nicht der Fall. So können Sie einen Vektor wie ein herkömmliches C-Array behandeln, da alle Elemente in einem zusammenhängenden Speicherblock stehen und sich das erste Element an der kleinsten Speicheradresse und das letzte Element an der größten Speicheradresse befindet. Dies ist beim Ringspeicher nicht garantiert.
Bei einem Ringspeicher von Anfang und Ende zu sprechen, mag sich merkwürdig anhören. Da Sie wie bereits gesehen bei einem Ringspeicher über einen Iterator auf Elemente zugreifen können – boost::circular_buffer bietet entsprechende Methoden wie begin() und end() an – hat auch ein Ringspeicher einen Anfang und ein Ende. Während Sie sich bei Iteratoren keine Gedanken machen müssen, wo sich der Anfang und das Ende befinden – bei Iteratoren funktioniert alles wie gewohnt automatisch – müssen Sie sich bei einem Zugriff per Zeiger auf Elemente im Ringspeicher etwas den Kopf zerbrechen. Oder Sie verwenden die vier genannten Methoden is_linearized(), array_one(), array_two() und linearize().
Die Methode is_linearized() gibt true zurück, wenn der Anfang des Ringspeichers an der kleinsten Speicheradresse liegt. In diesem Fall befinden sich sämtliche Elemente im Ringspeicher von Anfang bis Ende nacheinander an aufsteigenden Speicheradressen. Sie können demnach auf Elemente im Ringspeicher wie bei einem herkömmlichen C-Array zugreifen.
Gibt is_linearized() false zurück, liegt der Anfang des Ringspeichers nicht an der kleinsten Speicheradresse. Dies ist im Beispiel 16.2 der Fall. Während die ersten drei Elemente 0, 1 und 2 in genau dieser Reihenfolge im Speicher liegen, führt der vierte Aufruf von push_back() dazu, dass die Zahl 3 die im Ringspeicher abgelegte Zahl 0 überschreibt. Da 3 die letzte mit push_back() hinzugefügte Zahl ist, handelt es sich hierbei um das neue Ende des Ringspeichers. Den Anfang markiert die Zahl 1, die an der nächst höheren Speicheradresse liegt. Die Daten sind demnach nicht mehr nacheinander an aufsteigenden Speicheradressen gespeichert.
Wenn das Ende des Ringspeichers an einer niedrigeren Speicheradresse als der Anfang des Ringspeichers liegt, kann auf die Elemente nicht mehr wie bei einem herkömmlichen C-Array zugegriffen werden. Stattdessen muss auf zwei C-Arrays zugegriffen werden. Um die Positionen und Größen dieser Arrays nicht selbst berechnen zu müssen, stellt boost::circular_buffer die beiden Methoden array_one() und array_two() zur Verfügung.
array_one() und array_two() geben ein std::pair zurück, dessen erstes Element ein Zeiger auf das Array ist und dessen zweites Element die Größe des jeweiligen Arrays angibt. Über array_one() kann auf das Array zugegriffen werden, das an der kleinsten Adresse im Ringspeicher beginnt – über array_two() entsprechend auf das Array, das an der größten Adresse im Ringspeicher endet.
Ist der Ringspeicher linearisiert – gibt also is_linearized() true zurück – darf zwar auch array_two() aufgerufen werden. Der Aufruf ist jedoch wenig sinnvoll, da es nur ein Array im Ringspeicher gibt. Das zweite Array enthält demnach null Elemente.
Wenn Sie einen Ringspeicher wie ein herkömmliches C-Array behandeln möchten, können Sie eine Neuordnung erzwingen, indem Sie linearize() aufrufen. Dann ist garantiert, dass Sie über array_one() auf alle im Ringspeicher abgelegten Elemente zugreifen können und nicht zusätzlich array_two() aufrufen müssen.
Boost.CircularBuffer bietet mit boost::circular_buffer_space_optimized eine weitere Klasse an, um einen Ringspeicher zu erstellen. Diese Klasse wird genauso verwendet wie boost::circular_buffer und ist ebenfalls in der Headerdatei boost/circular_buffer.hpp definiert. boost::circular_buffer_space_optimized reserviert jedoch keinen Speicher bei der Instanziierung. Stattdessen wächst der Speicher dynamisch, bis die Kapazitätsgrenze erreicht ist. Werden Elemente gelöscht, schrumpft der Speicher entsprechend. boost::circular_buffer_space_optimized geht demnach effizienter mit Speicher um und kann eine gute Wahl sein, wenn ein Ringspeicher zum Beispiel eine sehr große Kapazität hat, die von einem Programm unter Umständen nicht benötigt wird.