deque selber implementieren

[Ein ehemaliger Benutzer]

Hallo Leute, ich versuche seit geraumer Zeit eine deque zu implementieren.
Ich habe jetzt 3 ansätze versucht:
1.) Als doppelt verkettete liste (pro push_back/front ein knoten)
2.) Als doppelt verkette liste (jeder knoten beinhaltet ein immer gleich großes array): d.h. es wird einfach ein neuer knoten erstellt sollte das front bzw back array voll sein und an das bestehene vorgeschoben bzw angehängt.
3.) Als container der 2 vectoren enthält für das jeweilige push/pop bei front/back.

1.) O(1) push/pop front/back, aber O(n) bei index zugriff
2.) so wie 1 nur wesentlich effizienter
3.) wie 1 nur alle O(1). problematisch ist allerdings wenn man nicht gleichmäßig auf die deque zugreift (wenn z.b. wenn 200 mal push_front aufgerufen wird, dannach aber 200 mal pop_back. aktuell wird der komplette vektor reversed und dann an den back vector ge push_back'ed. daraus resultiert eine durchschnittliche O(1), aber wenn jetzt abwechselnt pop_back und pop_front gemacht wird bin ich wieder bei O(n).

Ich hab jetzt gelesen, dass die deque normalerweise als vector von vectoren implementiert wird. ich kann mir da aber nicht genau vorstellen wie das funktionieren soll wenn ich O(1) bei push/pop front haben will. Bitte erklärung

[Die erinnerung]

Ich hätte das so gemacht:

Ich hätte ein Klasse geschrieben, die zwei Variablen speichert (über templates).

Dann einen Vektor angelegt, der die Klasse als Datentyp übernimmt.

[Ein ehemaliger Benutzer]

Die erinnerung schrieb:

Ich hätte das so gemacht:

Ich hätte ein Klasse geschrieben, die zwei Variablen speichert (über templates).

Dann einen Vektor angelegt, der die Klasse als Datentyp übernimmt.

hä? was für zwei variablen sollen das sein? und was soll mir dann soll dann ein klassen array (was der vector defacto ist) bringen?

[seldon]

Deques funktionieren üblicherweise etwa so:

+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+
          |   |   |
          |   |   |  +---+---+---+
          |   |   +->| 7 | 8 | 9 |
          |   |      +---+---+---+
          |   |  +---+---+---+
          |   +->| 4 | 5 | 6 |
          |      +---+---+---+
          |  +---+---+---+
          +->| 1 | 2 | 3 |
             +---+---+---+

Natürlich mit längeren Blöcken. Der Index (das Zeigerarray) wird von Zeit zu Zeit in der Größe verdoppelt, wie man es von Vektor kennt. Damit ist die Adressierung in der Mitte O(1), Anfügen an beiden Enden amortisiert O(1), und Zeiger, Referenzen und Iteratoren behalten bei Operationen an den Enden ihre Gültigkeit (es sei denn, das Objekt, das sie referenzieren, wird gelöscht).

[rean]

War die Implementierung von 3. nur der erste Wurf oder was spricht gegen Folgendes:

template< class T >
class MyDeque
{
public:
	typedef typename std::vector< T >::size_type size_type;

	MyDeque() : frontStart( 0 ), backStart( 0 )
	{}

	void push_back( const T& t )
	{
		//Falls front nicht aufgefüllt ist, ...
		if( frontStart != 0 )
		{
			//...setzen wir das neue Element an das Ende von front.
			front[ --frontStart ] = t;
		}
		else
		{
			//...ansonsten einfach normales push_back.
			back.push_back( t );
		}
	}

	void push_front( const T& t )
	{
		//Falls back nicht augefüllt ist,...
		if( backStart != 0 )
		{
			//...setzen wir das neue Element an den Anfang von back.
			back[ --backStart ] = t;
		}
		else
		{
			//...ansonsten fügen wir es zu front hinzu.
			front.push_back( t );
		}
	}

	void pop_back()
	{
		//Fall back schon leer ist...
		if( back.empty() )
		{
			//...und front noch Elemente hat...
			if( front.size() == frontStart )
			{
				throw std::out_of_range( "MyDeque::pop_back : No more objects!" );
			}

			//..."entfernen" wir das letzte Element von front.
			++frontStart;
			return;
		}

		//...ansonsten normales pop_back.
		back.pop_back();
	}

	void pop_front()
	{
		//Falls front schon leer ist...
		if( front.empty() )
		{
			//...und back noch Elemente hat...
			if( back.size() == backStart )
			{
				throw std::out_of_range( "MyDeque::pop_front : No more objects!" );
			}

			//..."entfernen wir das letzte Element von back.
			++backStart;
			return;
		}

		//...ansonsten entfernen wir das erste Element von front.
		front.pop_back();
	}

	T operator[]( size_type index )
	{
		if( index < ( front.size() - frontStart ) )
		{
			return front[ front.size() - 1 - index ];
		}
		else
		{
			return back[ index + backStart - ( front.size() - frontStart ) ];
		}
	}

	size_t size() const
	{
		return front.size() - frontStart + back.size() - backStart;
	}

private:
	//Dieser vector enthält den ersten Teil der Elemente in umgekehrter Reihenfolge.
	std::vector< T > front;
	//Dieser vector enthält den zweiten Teil der Elemente in normaler Reihenfolge.
	std::vector< T > back;

	//Index des ersten nicht entfernten Elements in front.
	size_type frontStart;
	//Index des ersten nicht entfernten Elements in back.
	size_type backStart;
};

[hustbaer]

@rean
Na z.B. dass es nur Unsinn ist?

Wenn man einen Ring-Puffer will, dann sollte man auch einen Ring-Puffer implementieren, und nicht ein komisches Gebastel das hinten und vorne nur Probleme macht.

Krauzi hat doch schon selbst beschrieben dass da nur Unsinn bei rauskommt wenn man immer push_back() und pop_front() macht.

[Ethon]

Ich weiß nicht welche exakten Anforderungen eine deque erfüllen muss, aber könnte man nicht einfach 2 Vektoren nehmen? Das letzte Element des ersten Vektors wäre das logisch erste Element, das letzte Element des zweiten Vektors wäre das logisch letzte Element. Dann wäre push_front ein push_back auf den ersten Vektor und push_back ein push_back auf den zweiten Vektor.

Edit: Ah lol, fast das Selbe war ja schon da.

[rean]

@hustbaer
Im Gegensatz zu der vom TE beschriebenen Implementierung hat mein Vorschlag aber auch bei abwechselndem push_back, pop_front O(1).
Das heißt aber noch lange nicht, dass ich eine eigene Implementierung für sinnvoll halte.

[hustbaer]

@rean:
Und dass der Speichervarbrauch dabei ständig wächst ist dir egal?
Nur mal als Tip: ne deque wird häufig als FIFO verwendet.
Da wird immer nur push_back und pop_front gemacht.

[Ein ehemaliger Benutzer]

Meine Implementierung macht es jetzt so:
Es werden mehrere kleinere arrays konstanter Größer erstellt und in einem deque array (innere deque) verwaltet (die ist nach außen nicht sichtbar). Die nach außen sichtbare deque (mit der dann gearbeitet wird) verwaltet nur die beiden äußeren container der inneren deque und pusht oder popt je nach bedarf (also wenn die äußeren container voll bzw leer sind).

Laufzeiten:
amortisiertes O(1) bei push/pop back/front
O(1) bei index zugriff [].

ich würde mich freuen, wenn noch jemand über den code gucken könnte und eventuell vorhandene fehler aufspürt:
http://codepad.org/AteVfW6D

EDIT: hab ganz vergessen, dass man hier ja auch code posten kann
EDIT2 und 3: code aktualisiert
EDIT4: wenn die deque noch jemand braucht: damit so ordnungsgemäß auch bei ungeraden blockgrößen funktioniert musst man nur in zeile 191 und 211 gehen und zu m_DeltaFront = m_DeltaBack ändern (nur notwendig für den codepad link).

#ifndef _XSTD_XDEQUE_H_
#define _XSTD_XDEQUE_H_

#include <cstdlib>
#include <cassert>
#include <cstring>

namespace xstd
{

template<class T>
class xdeque
{
private:
    class blocks /* innere deque: saves all the blocks/arrays */
    {
    public:
        size_t m_Size, m_MaxSize;
        T ** m_Blocks;
        size_t m_DeltaFront; /* delta of the frontmost array */

        /* recenter moves the saved blocks so that there is euqal free space to either end */
        void recenter( )
        {
            size_t delta_back = m_MaxSize - m_Size - m_DeltaFront;
            size_t max = (m_DeltaFront > delta_back) ? m_DeltaFront : delta_back; 
            size_t min = (m_DeltaFront == max) ? delta_back : m_DeltaFront;
            if( max > min )
            {
                size_t diff = max - min;
                size_t delta = diff / 2;
                if( delta == 0 )
                    delta = 1;

                if( max == m_DeltaFront )
                {
                    /* move all elements by delta to the right */
                    std::memmove( m_Blocks + m_DeltaFront - delta, m_Blocks + m_DeltaFront, sizeof(T *) * m_Size );
                    m_DeltaFront -= delta;
                }
                else
                {
                    /* move all elements by delta to the left */
                    std::memmove( m_Blocks + m_DeltaFront + delta, m_Blocks + m_DeltaFront, sizeof(T *) * m_Size );
                    m_DeltaFront += delta;
                }
            }
        }

        void resize( size_t nSize )
        {
            void * new_blocks = realloc( m_Blocks, sizeof(T *) * nSize );
            assert(new_blocks);

            m_Blocks = (T **)new_blocks;
            m_MaxSize = nSize;
        }

    public:
        block_array( size_t blocks )
            : m_Blocks(NULL), m_Size(0), m_MaxSize(0), m_DeltaFront(0)
        {
            assert( blocks != 0 );

            m_DeltaFront = blocks / 2;
            resize( blocks );
            recenter();
        }

        ~block_array( )
        {
            free( m_Blocks );
        }

        size_t size()    { return m_Size; }
        bool emtpy()     { return m_Size == 0; }

        void push_front( T * arr )
        {
            if( m_DeltaFront == 0 )
            {
                if( m_Size == m_MaxSize )
                    resize( m_MaxSize * 2 ); /* if resize didn't fail there is no space at the back */ 

                recenter();
            }

            m_Blocks[ --m_DeltaFront ] = arr;
            m_Size++;
        }

        void push_back( T * arr )
        {
            if( m_Size == m_MaxSize )
                resize( m_MaxSize * 2 );
            else if( m_DeltaFront != 0 )
                recenter();

            m_Blocks[ m_DeltaFront + m_Size++ ] = arr;
        }

        T * pop_front()
        {
            assert( m_Size != 0 );

            m_Size--;
            return m_Blocks[ m_DeltaFront++ ];
        }

        T * pop_back()
        {
            assert( m_Size != 0 );

            return m_Blocks[ m_DeltaFront + --m_Size ];
        }

        T * front()
        {
            assert( m_Size != 0 );
            return m_Blocks[ m_DeltaFront ];
        }

        T * back()
        {
            assert( m_Size != 0 );
            return m_Blocks[ m_DeltaFront + m_Size - 1 ];
        }

        T *& operator[]( size_t i )
        {
            assert( m_Size != 0 && i < m_Size );
            return m_Blocks[ m_DeltaFront + i ];
        }
    } m_Blocks;

    size_t m_DeltaFront, m_DeltaBack;
    size_t m_Size;
    const size_t m_BlockSize;

public:
    xdeque( size_t nBlockSize = 128 )
        : m_Blocks(nBlockSize), m_BlockSize(nBlockSize), m_DeltaBack(nBlockSize/2), m_DeltaFront( nBlockSize - (nBlockSize/2) ), m_Size(0)
    {
        m_Blocks.push_back( new T[m_BlockSize] );
    }

    ~xdeque( )
    {
        while( !empty() )
            pop_back();
    }

	size_t size()   { return m_Size; }
    bool empty()	{ return m_Size == 0; }

    void push_back( T val )
    {
        if( m_DeltaBack == m_BlockSize )
        {
            m_Blocks.push_back( new T[m_BlockSize] );
            m_DeltaBack = 0;
        }

        m_Blocks.back()[ m_DeltaBack++ ] = val;
        m_Size++;
    }

    void push_front( T val )
    {
        if( m_DeltaFront == 0 )
        {
            m_Blocks.push_front( new T[m_BlockSize] );
            m_DeltaFront = m_BlockSize;
        }

        m_Blocks.front()[ --m_DeltaFront ] = val;
        m_Size++;
    }

    T pop_back( )
    {
        assert( m_Size != 0 );
        m_Size--;
        T val = m_Blocks.back()[ --m_DeltaBack ];

        if( m_Size == 0 )
        {
            /* reset deltas and do not delete the last block */
            m_DeltaBack = m_BlockSize / 2;
            m_DeltaFront = m_DeltaBack;
        }
        else if( m_DeltaBack == 0 )
        {
            delete[] m_Blocks.pop_back();
            m_DeltaBack = m_BlockSize;
        }

        return val;
    }

    T pop_front( )
    {
        assert( m_Size != 0 );
        m_Size--;
        T val = m_Blocks.front()[ m_DeltaFront++ ];

        if( m_Size == 0 )
        {
            m_DeltaBack = m_BlockSize / 2;
            m_DeltaFront = m_DeltaBack ;
        }
        else if( m_DeltaFront == m_BlockSize )
        {
            delete[] m_Blocks.pop_front();
            m_DeltaFront = 0;
        }

        return val;
    }

    T& operator[]( size_t i )
    {
        assert( i < m_Size );

        size_t num_of_elements_first_array = m_BlockSize - m_DeltaFront;

        if( i < num_of_elements_first_array ) /* i must be in the first array, the formula below doesn't work here */
            return m_Blocks[0][ m_DeltaFront + i ];

        i -= num_of_elements_first_array;
        return m_Blocks[ 1 + i / m_BlockSize ][ i % m_BlockSize ];
    }
};

}

#endif

[Incocnito]

Also bei mir kackt das Program schon bei etwas mehr als 100 Elementen ab:

int main()
{
    xdeque<int> ints;
    for(int i = 0; i <= 200; i++)
        ints.push_back(d);
    for(unsigned i = 0; i < ints.size(); ++i)
        std::cout << ints[i] << " ";
}

"Programm.exe funktioniert nicht mehr [...]"

Wundert mich aber auch nicht bei den ganzen new's und delete's und den ganzen Zeigern, und noch Sachen wie memmove etc.
Da muss einfach irgendwann was schief laufen

[rean]

hustbaer schrieb:

@rean:
Und dass der Speichervarbrauch dabei ständig wächst ist dir egal?
Nur mal als Tip: ne deque wird häufig als FIFO verwendet.
Da wird immer nur push_back und pop_front gemacht.

Weil es ja auch unmöglich wäre den Code so zu erweitern, dass ab einem gewissen Schwellwert die Objekte wieder an den Anfang kopiert werden.

[Ein ehemaliger Benutzer]

Incocnito schrieb:

Also bei mir kackt das Program schon bei etwas mehr als 100 Elementen ab:

int main()
{
    xdeque<int> ints;
    for(int i = 0; i <= 200; i++)
        ints.push_back(d);
    for(unsigned i = 0; i < ints.size(); ++i)
        std::cout << ints[i] << " ";
}

"Programm.exe funktioniert nicht mehr [...]"

Wundert mich aber auch nicht bei den ganzen new's und delete's und den ganzen Zeigern, und noch Sachen wie memmove etc.
Da muss einfach irgendwann was schief laufen

hab iwie die falsche version hochgeladen...

[hustbaer]

rean schrieb:

hustbaer schrieb:

@rean:
Und dass der Speichervarbrauch dabei ständig wächst ist dir egal?
Nur mal als Tip: ne deque wird häufig als FIFO verwendet.
Da wird immer nur push_back und pop_front gemacht.

Weil es ja auch unmöglich wäre den Code so zu erweitern, dass ab einem gewissen Schwellwert die Objekte wieder an den Anfang kopiert werden.

Ja, man könnte da irgendwie rumbasteln, damit der Speicherverbrauch nicht ständig wächst.

Wenn man das macht, dann ändern sich aber die Adressen der Elemente (da ja umkopiert wird). Und dann könnte man auch gleich einen dynamischen Ringpuffer verwenden. Der muss bei ständigem push_back() + pop_front() nämlich gar nix umkopieren.

@Krauzi
Das recenter() kannst du dir sparen, wenn du die "innere deque" gleich als dynamischen Ringpuffer auslegst.
Und natürlich bietet es sich an std::vector zu verwenden.

[Ein ehemaliger Benutzer]

hm durch was kann ich mir denn meine innere deque sparen?
zum thema vector: kann ich so leider nicht verwenden, da ich meine deque eigentlich in c schreiben sollte. ich hab mir zwar bereits eine vektor "klasse" in c geschrieben, allerdings sollten die structs optimales größe/performance verhältniss haben (das schließt den einsatz eines vectors eigentlich aus).

[Ein ehemaliger Benutzer]

hm jetzt den code gefixt, aber irgendwie klappt etwas noch nicht wenn man alle elemente entfernt hat und wieder mit hinzufügen beginnt. das kann ich mir aber nicht erklären, da wie man bei den pop methoden erkennen kann alles wieder resetet wird.

EDIT: fehler war ziemlich einfach: beim reseten wurde die deltas falsch gesetzt.
bei einer geraden blockgröße hat alles gepasst weil da beide deltas gleich waren (und das sollten sie auch sein, es wird ja beim push_front/back --front bzw back++ gemacht).

[hustbaer]

Krauzi schrieb:

hm durch was kann ich mir denn meine innere deque sparen?

Na z.B. indem du einen dynamischen Ringpuffer verwendest. Wie ich schon gesagt habe, ändern sich dann aber die Adressen der Elemente wenn die Puffergrösse angepasst werden muss.

Falls du dir unter "dynamischem Ringpuffer" nix vorstellen kannst... stell dir einen normalen vector vor + start offset (wo ist das erste Element?) + länge + "wrap around" am Ende. D.h. wenn das Array 10 Elemente gross ist, Start-Offset ist 8 und Länge ist 5, dann sieht es im Speicher so aus:

pos      0 1 2 3 4 5 6 7 8 9
element  3 4 5 . . . . . 1 2

Und wenn das Ding zu klein wird, dann musst du es eben resizen - ganz normal wie man es bei einem Vektor auch machen würde.

Ich wollte aber auch gar nicht vorschlagen die innere deque ganz einzusparen. Sondern nur das recenter() zu sparen - was du eben wie beschrieben mit einem dynamischem Ringpuffer machen kannst.

Wobei: amortisiert O(1) für push/pop an beiden Enden + O(1) für Lookup bekommst du mit einem dynamischem Ringpuffer ohne innere Deque auch. Die innere Deque bringt nur was, wenn entweder die Elemente teuer zu kopieren sind, oder es notwendig ist dass die Adressen der Elemente stabil bleiben.

zum thema vector: kann ich so leider nicht verwenden, da ich meine deque eigentlich in c schreiben sollte. ich hab mir zwar bereits eine vektor "klasse" in c geschrieben, allerdings sollten die structs optimales größe/performance verhältniss haben (das schließt den einsatz eines vectors eigentlich aus).

OK. Nur wieso postest du dann im C++ Forum?

[Ein ehemaliger Benutzer]

danke für die antwort.

hustbaer schrieb:

Krauzi schrieb:

hm durch was kann ich mir denn meine innere deque sparen?

Na z.B. indem du einen dynamischen Ringpuffer verwendest. Wie ich schon gesagt habe, ändern sich dann aber die Adressen der Elemente wenn die Puffergrösse angepasst werden muss.

das wäre an und für sich net gute idee, allerdings wollte ich zumindest ein bisschen code wiederverwenden. da bietet sich die innere deque gut an, da ich die selber als deque implementierung zur verfügung stellen kann.
Ich habe dazu mal ein paar performance tests gemacht (100*10^6 char durchjagen), da ist das deque array höllisch schnell (fast genauso schnell wie ein vector), die (nicht array) deque ungefähr 3 mal langsamer. die msvc std::deque hat so lange gebraucht dass ich keine ergebnisse hab

hustbaer schrieb:

zum thema vector: kann ich so leider nicht verwenden, da ich meine deque eigentlich in c schreiben sollte. ich hab mir zwar bereits eine vektor "klasse" in c geschrieben, allerdings sollten die structs optimales größe/performance verhältniss haben (das schließt den einsatz eines vectors eigentlich aus).

OK. Nur wieso postest du dann im C++ Forum?

die deque in c (mit der wurden die teste durchgeführt) ist typlos, deshalb muss beim constructor die element größe (sizeof) übergeben werden, push und pop vorgänge laufen dann über memcpy und zeiger auf die elemente, in die dann sizeof(typ) bytes gelesen oder eben geschrieben wird.

EDIT: der grund dass ich hier poste ist, dass die c deque wirklich keiner mehr versteht. c++ ist einfach wesentlich übersichtlicher als c (ordentlich geplant vorausgesetzt natürlich).

[DocShoe]

Das mit dem Ringpuffer finde ich eine schicke Idee, aber warum nur einen? Wenn die deque z.B. aus std::vector<std::unique_ptr<circular_buffer>> bestünde kann man beim push_front/push_back einfach einen neuen circular_buffer vorn/hinten einfügen, ohne dass man die Größe ändern müsste oder Objekte kopiert werden. Ist natürlich die Frage, was teurer zu kopieren ist, wenn der vector realloziert. Ein recenter() ist auch nicht mehr notwending, da man leere Ringpuffer am Anfang/Ende einfach löschen könnte. (gut, das könnte man jetzt auch recenter nennen...)

[pumuckl]

DocShoe schrieb:

Ist natürlich die Frage, was teurer zu kopieren ist, wenn der vector realloziert.

Reallikation des vector = move der unique_ptr = N Pointer-Kopien.