deque selber implementieren

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.

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.

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.

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).

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?

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.

hustbaer

DocShoe schrieb:

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...)

Naja, das ist ja fast das selbe was die typischen std::deque Implementierungen machen.
Wobei es allerdings Sinn macht, den äusseren Vektor auch durch einen Ringpuffer zu ersetzen. Dann muss man nämlich nicht dauernd Zeiger umkopieren wenn die deque als FIFO verwendet wird.

@Krauzi

da ist das deque array höllisch schnell (fast genauso schnell wie ein vector), die (nicht array) deque ungefähr 3 mal langsamer

Ich weiss ehrlich gesagt jetzt nicht was du mit "deque array" und "(nicht array) deque" meinst.