STL-template für FIFO?

Drehleiter

Eine Alternative könnte ein Ring-Puffer sein, z.B. boost::circular_buffer. Ich kann mir vorstellen, dass er u. U. für Deiné performante als die STL-Container ist.
Gruß

Xebov

SeppJ schrieb:

Ja, aber was würdest du dabei anders/besser machen als die STL-Container?

Vergiss nicht das die STL Container für allgemeinen Gebrauch gemacht wurden.

Würde auch sagen das es ein Ring Buffer hier bringen könnte.

It0101

Tataaa!

#ifndef RINGBUFFERFIFO_HPP_
#define RINGBUFFERFIFO_HPP_

#include <string.h>

// FIFO mit fester Groesse.
template <typename T>
class RingBufferFIFO
{
public:
	RingBufferFIFO( unsigned int _uiSize )
	{
		uiMaxSize = _uiSize;
		pr = pw = Buffer = new T*[ uiMaxSize ];
		pe = Buffer + uiMaxSize;

		memset( Buffer, 0, sizeof(T*) * uiMaxSize );
	}
	~RingBufferFIFO()
	{
		for ( pw = Buffer; pw != pe; delete *pw++ );
		delete [] Buffer;
	}

	bool Put( T *Item );
	T *Get();

private:
	T **Buffer, **pw, **pe, **pr;
	unsigned int uiMaxSize;
};

// Fuegt dem Buffer hinzu ein Element
template <typename T> bool RingBufferFIFO<T>::Put( T *PutItem )
{
	if ( *pw == 0 )
	{
		*pw++ = PutItem;
		if ( pw == pe )
			pw = Buffer;
		return true;
	}
	return false;
}

// Entnimmt ein Element aus dem Buffer
template <typename T> T *RingBufferFIFO<T>::Get()
{
	T *TempItem = *pr;
	*pr++ = 0;
	if ( pr == pe )
		pr = Buffer;
	return TempItem;
}

#endif /* RINGBUFFERFIFO_HPP_ */

Edit: Bug gefixed...

It0101

schlagt mich tot, wegen STL-Ignorierung, aber ich find das template geil ^^ ( noch kürzer hab ichs leider nicht hinbekommen )

PS: ich liebe das Pointergeschubse ( das Ding hat übrigens keine Memory-Leaks ^^ )

Th69

Deine Get-Funktion ist aber fehlerhaft. Versuch mal, mehrmals hintereinander etwas zu entfernen...

Schau mal bei Wikipedia: http://de.wikipedia.org/wiki/Warteschlange_(Datenstruktur)

knivil

Es ist unvollstaendig, sehr unvollstaendig! Wie sehen die Zugriffsfunktionen aus? Wie kann ich mittels Iterator sortieren?

( das Ding hat übrigens keine Memory-Leaks ^^ )

Das kommt darauf an, wie Ringbuffer verwendet wird. Auch werden andere Bugs provoziert, insbesondere weil nicht geklaert ist, wer der Eigentuemer der Objekte ist, auf die im Buffer gezeigt wird.

ich liebe das Pointergeschubse

Ich haette die Zugriffe ueber Indizes mitels modulo realisiert.

It0101

du hast recht... ich kümmer mich gleich drum - schlampig getestet

It0101

knivil schrieb:

Es ist unvollstaendig, sehr unvollstaendig!

es kann genau die Funktionen, die ich benötige. Wenn ich Overhead gewollt hätte, hätte ich auch ein STL-Template nehmen können.

knivil schrieb:

Wie sehen die Zugriffsfunktionen aus?

Put und get, mehr ist nicht nötig

knivil schrieb:

Wie kann ich mittels Iterator sortieren?

garnicht, weil ich das nicht brauch.

knivil schrieb:

Das kommt darauf an, wie Ringbuffer verwendet wird. Auch werden andere Bugs provoziert, insbesondere weil nicht geklaert ist, wer der Eigentuemer der Objekte ist, auf die im Buffer gezeigt wird.

Üblicherweise der, der sie erzeugt hat. Und das ist bei mir nicht anders.

Übrigens bin ich der festen Überzeugung, dass dieses Template von der Performance her die allgemeiner gefassten STL-Templates schlägt.

knivil

Üblicherweise der, der sie erzeugt hat. Und das ist bei mir nicht anders.

Diese Zeile sagt was anderes:

for ( p = Buffer; p != pe; delete *p++ );

Übrigens bin ich der festen Überzeugung, dass dieses Template von der Performance her die allgemeiner gefassten STL-Templates schlägt.

Es zaehlen aber nur Messergebnisse, keine Ueberzeugungen. Ich lasse mich gern eines besseren belehren, wenn du einen Benchmark postest, so dass ich ihn auf meiner lokalen Maschine testen kann.

It0101

knivil schrieb:

Üblicherweise der, der sie erzeugt hat. Und das ist bei mir nicht anders.

Diese Zeile sagt was anderes:
for ( p = Buffer; p != pe; delete *p++ );

Diese Zeile löscht das Element, weil ich sonst vom Eigentümer verlangen müsste, den Buffer mit "get" komplett zu entleeren.
Hat schlicht und ergreifend praktische Gründe.

Das Template hat im Gegensatz zur STL nicht den Anspruch der allgemeinen Verwendbarkeit. Es ist für mich und im Dienste der maximalen Performance entwickelt.

It0101

knivil schrieb:

Es zaehlen aber nur Messergebnisse, keine Ueberzeugungen. Ich lasse mich gern eines besseren belehren, wenn du einen Benchmark postest, so dass ich ihn auf meiner lokalen Maschine testen kann.

Die werde ich nachliefern.
g++ auf Linux, wenns recht ist.

It0101 schrieb:

knivil schrieb:
Üblicherweise der, der sie erzeugt hat. Und das ist bei mir nicht anders.

Diese Zeile sagt was anderes:
for ( p = Buffer; p != pe; delete *p++ );
Diese Zeile löscht das Element, weil ich sonst vom Eigentümer verlangen müsste, den Buffer mit "get" komplett zu entleeren.

Aber damit ist nicht mehr klar, wer der Eigentümer ist.

It0101 schrieb:

Hat schlicht und ergreifend praktische Gründe.

Praktisch ist es eben genau nicht. Kann man sehr leicht aufzeigen:

// in irgendeinem Block
{
  RingBufferFIFO<int> buffer(20);

  // ... irgendwo im nirgendwo passt der Programmierer nicht richtig auf,
  // da er sich nicht mehr recht erinnert, dass RingBufferFIFO jeglichem
  // Eigentümer Standard widerspricht.
  int agreatvalue = 256;
  buffer.Put(&agreatvalue);

  // ... viel später, aber agreatvalue ist noch im Puffer.
} // <- BAMMMMM; BUMMM; WELTUNTERGANG ... naja nicht so extrem, aber eben nicht praktisch.

Grüssli

unskilled

Dravere schrieb:

aber eben nicht praktisch

gut, dass du das noch dazu schreibst

It0101

Wie wäre denn eure Vorgehensweise mit den Eigentümerrechten speziell für diese Komponente?

Ich lass mich ja gern belehren...

It0101 schrieb:

Wie wäre denn eure Vorgehensweise mit den Eigentümerrechten speziell für diese Komponente?

So wie immer: Wer die Ressourcen anfordert, der gibt sie auch wieder frei.

Schreib am besten den RingBufferFIFO so um, dass er nicht zwingt, dass Zeiger gespeichert werden. Wenn der Programmierer Zeiger Speichern möchte, kann er dies angeben: RingBufferFIFO<int*> . Dann weiss er aber auch, dass er dafür verantwortlich ist, den Speicher wieder freizugeben. Er ist dann sogar in der Lage, allenfalls einen shared_ptr zu verwenden, wenn er dies möchte und als sinnvoll erachtet.

Grüssli

It0101

Ok, dann werd ich das so machen. Das klingt vernünftig

Xebov

Ich hab das bei mir so geregelt das ich als Template Parameter noch eine Klasse mitnehme die ebenfalls Template ist und eine static delete Funktion hat, die rufe ich beim Entfernen eines Elements auf.

Nexus

Xebov schrieb:

Ich hab das bei mir so geregelt das ich als Template Parameter noch eine Klasse mitnehme die ebenfalls Template ist und eine static delete Funktion hat, die rufe ich beim Entfernen eines Elements auf.

Das ist natürlich auch eine Möglichkeit, geht allerdings eher in Richtung Smart-Pointer und Destruction-Policy. Kommt halt drauf an, ob vorrangig Zeiger auf dynamisch angelegte Objekte gespeichert werden. Man sollte aber dran denken, dass der Heap einen Geschwindigkeits- und Speicher-Overhead mit sich bringt, der besonders für kleine Objekte lästig sein kann. Von daher kann es in dieser Hinsicht effizienter sein, nur Speicher für den Ringpuffer anzufordern und die Objekte da reinzukonstruieren.

Für maximale Performance könnte man auf dem Stack arbeiten. Dabei rate ich zu std::tr1::array , das hat im Release-Modus keinen Overhead gegenüber einem C-Array, aber im Debug-Modus wertvolle Laufzeitprüfungen. Das Containertemplate könnte zum Beispiel so aussehen:

template <typename T, size_t Size>
class RingBufferQueue
{
    public:
        // ...
    private:
        std::tr1::array<T, Size> MyBuffer;
};