Gibt es diese Datenstruktur in der STL?



  • Abend,

    ich suche folgende Datenstruktur: Sie hat eine feste Anzahl N Elemente und wenn N hinzugefügt wurden, dann soll wieder von vorne begonnen werden (sprich das Element, dessen Einfügung am längsten zurück liegt, wird überschrieben).
    Ich glaub das nennt man Ringpuffer oder so. Gibt es da was fertiges in der STL? Falls nein: Mit welcher Struktur bau ich das am besten nach?



  • gibts nicht.
    am besten selber bauen, dazu einen vector.

    vielleicht sowas:

    void RingBuffer::tuDazu(T const& t){
      if(vec.count()<mysize)
        vec.pushback(t);
      else
      {
        vec[writepos]=t;
        writepos=(writepos+1)%size;
      }
    }
    


  • Merci Mausi





  • Ne danke. Boost stinkt zum Himmel. Overdesigner Frickelcode für Theoretiker gepaart mit absolut anfängerunfreundlicher Doku. Nein Danke.



  • Ne danke. Boost stinkt zum Himmel. Overdesigner Frickelcode für Theoretiker gepaart mit absolut anfängerunfreundlicher Doku. Nein Danke.

    So ein Schwachsinn... Da gibts etwas, das macht genau was du willst, ist einfach zu benutzen, hat eine gute, anfängerfreundliche Einleitung(http://www.boost.org/doc/libs/1_37_0/libs/circular_buffer/doc/circular_buffer.html) und du willst es nicht benutzen, weil es zu boost gehört und du für vieles von Boost zu blöd bist?



  • Eventuell hilft ihm volkards Code aber wesentlich mehr, da er plötzlich versteht wie etwas funktioniert. Wenn er dann verstanden hat wie die Dinge funktionieren wird er auch plötzlich eine Library wie Boost bevorzugen.

    MfG SideWinder



  • JustAnotherNoob schrieb:

    Ne danke. Boost stinkt zum Himmel. Overdesigner Frickelcode für Theoretiker gepaart mit absolut anfängerunfreundlicher Doku. Nein Danke.

    So ein Schwachsinn... Da gibts etwas, das macht genau was du willst, ist einfach zu benutzen, hat eine gute, anfängerfreundliche Einleitung(http://www.boost.org/doc/libs/1_37_0/libs/circular_buffer/doc/circular_buffer.html) und du willst es nicht benutzen, weil es zu boost gehört und du für vieles von Boost zu blöd bist?

    Klar, deine Arroganz hat mich jetzt überzeigt.
    Oh, doch nicht.
    Ich finde boost einfach scheisse. Punkt.

    Hab mir die Klasse jetzt selber geschrieben, so wie es volkard vorgeschlagen hat. Dauerte ca. 2 Minuten und die Klasse hat 3 Methoden - genau die, die ich brauche. Und nicht 10 Billionen wie dieses boost Ding.



  • Ich gehe mal frecherweise davon aus, daß unverdientes0_0 diese Datenstruktur als Cache benutzen will, um andere teure Suchen oder Berechnungen oft schneller zu machen. Wenn das so wäre, würde er die Datenstruktur sehr schnell an seine Anwendung anpassen wollen, zum Beispiel wird bei jedem erfolgreichen find das gefundene Element um 10 Positionen nach vorne geückt, um weitere Suchen zu beschleunigen, weil das bei seiner Datenlage vielleicht zufällig klappt.
    Zufällig benutze ich einen ähnlichen Puffer im Moment, wo das Cachen ca um Faktor 1000000 beschleunigt und das Vorrückwen nochmal Faktor 1000 zusätzlich bringt.



  • SideWinder schrieb:

    Eventuell hilft ihm volkards Code aber wesentlich mehr, da er plötzlich versteht wie etwas funktioniert. Wenn er dann verstanden hat wie die Dinge funktionieren wird er auch plötzlich eine Library wie Boost bevorzugen.

    Sollte er dann nicht auch den std::vector selbst schreiben?



  • Vor allem würde ich dann was schnelleres als Vector nehmen.

    Wenn er nen FIFO ( is doch so gemeint oder? ) bauen will, dann fügt er vorn was ein und löscht hinten was weg. D.h. der Vector macht ständig Kopieroperationen.

    Wenn die Elemente nur Pointer sind, geht das ja wenigstens schnell...



  • It0101 schrieb:

    Vor allem würde ich dann was schnelleres als Vector nehmen.
    Wenn er nen FIFO ( is doch so gemeint oder? ) bauen will, dann fügt er vorn was ein und löscht hinten was weg. D.h. der Vector macht ständig Kopieroperationen.
    Wenn die Elemente nur Pointer sind, geht das ja wenigstens schnell...

    Ja, er will FIFO, aber mit fester Größe, dafür ist der RingBuffer extrem schlau. Mußt Du unbedingt mal googlen, wie der Trick da geht, daß es eben doch mit Vector push/peek/pop in O(1) geht.



  • Jop, dann kann man doch den RingBuffer nehmen. Der dürfte vermutlich performanter sein, als ein vector... Wenn er nicht gerade intern auf Vector basiert ( was ich nicht glaube ).

    Da die Anzahl der Elemente fix ist, kann man doch mit new ein array anlegen und dann nur die Pointer verschieben ( Elemente sollten dann zwangsläufig Pointer sein ). Würde mich interessieren, aber hab hier auf Arbeit gerade anderes zu tun 😉 Vielleicht code ich zu Hause sowas mal selber.



  • It0101 schrieb:

    Jop, dann kann man doch den RingBuffer nehmen. Der dürfte vermutlich performanter sein, als ein vector... Wenn er nicht gerade intern auf Vector basiert ( was ich nicht glaube ).

    Da die Anzahl der Elemente fix ist, kann man doch mit new ein array anlegen und dann nur die Pointer verschieben ( Elemente sollten dann zwangsläufig Pointer sein ). Würde mich interessieren, aber hab hier auf Arbeit gerade anderes zu tun 😉 Vielleicht code ich zu Hause sowas mal selber.

    WAS FÜR EIN VERSCHIEBEN DER POINTER?
    Der Ringbuffer muß gar nix verschieben.
    http://en.wikipedia.org/wiki/Circular_buffer#Circular_buffer_mechanics

    Statt
    - das Array selber anzulegen und Kopierkonstruktor und Zuweisungsoperator zu verbioeten und einen Destruktor zu bauen,
    kann man einfach
    - das Array als vector anlegen.



  • aso verstehe... Ich hatte jetzt zu sehr an FIFOs gedacht 😉
    Der Pointer wandert praktisch bei Schreiboperationen immer eins weiter.

    Jo stimmt. Da brauch man immer nur an einer Stelle überschreiben. Nix Löschen und nix einfügen. Ein Array von konstanter Länge. Eindeutig ein Fall für new [] 😉



  • It0101 schrieb:

    aso verstehe... Ich hatte jetzt zu sehr an FIFOs gedacht 😉
    Der Pointer wandert praktisch bei Schreiboperationen immer eins weiter.

    Jo stimmt. Da brauch man immer nur an einer Stelle überschreiben. Nix Löschen und nix einfügen. Ein Array von konstanter Länge. Eindeutig ein Fall für new [] 😉

    Nö. Eindeutig ein Fall für eine Array-Klasse. Entweder selber schreiben oder... Aber hier dürfte vector um genau 0.00% langsamer sein. Und natürlich, hat man keine sinnvollen Defaultwerte, braucht man noch eine Wachstumsphase. Dann braucht man zuätzlich noch was, um die aktuelle Größe zu speichern. Und placement-new im push.
    In

    void RingBuffer::tuDazu(T const& t){ 
      if(vec.count()<mysize) 
        vec.pushback(t); 
      else 
      { 
        vec[writepos]=t; 
        writepos=(writepos+1)%mysize; 
      } 
    }
    

    hatte ich dazu pfiffigerweise einfach vector() benutzt. Aber ob der hier gesuchte RingBuffer überhaupt wachsen können soll, ist nicht bekannt.


Log in to reply