Welchen STL-Container soll ich für ein FIFO verwenden?

89

Welcher STL-Container passt am besten zu meinen Anforderungen? Ich habe im Grunde einen 10 Elemente breiten Container, in dem ich ständig push_backneue Elemente pop_fronteinbaue, während ich das älteste Element (ungefähr eine Million Mal) bin .

Ich verwende derzeit ein std::dequefür die Aufgabe, habe mich aber gefragt, ob ein std::listeffizienter wäre, da ich mich nicht neu zuweisen müsste (oder ich verwechsle ein std::dequemit einem std::vector?). Oder gibt es einen noch effizienteren Container für meinen Bedarf?

PS Ich brauche keinen wahlfreien Zugriff

Gab Royer
quelle
5
Probieren Sie es mit beiden aus und nehmen Sie sich Zeit, um herauszufinden, welches für Ihre Anforderungen schneller ist.
KTC
5
Ich wollte das gerade tun, suchte aber auch nach einer theoretischen Antwort.
Gab Royer
2
das std::dequewird nicht neu zugewiesen. Es ist eine Mischung aus a std::listund a, std::vectorbei der größere Teile als a zugewiesen werden, die std::listjedoch nicht wie a neu zugewiesen werden std::vector.
Matt Price
2
Nein, hier ist die relevante Garantie aus dem Standard: "Das Einfügen eines einzelnen Elements entweder am Anfang oder am Ende einer Deque dauert immer konstant und führt zu einem einzelnen Aufruf des Kopierkonstruktors von T."
Matt Price
1
@ John: Nein, es wird wieder zugewiesen. Vielleicht verwechseln wir nur Begriffe. Ich denke, Neuzuweisung bedeutet, die alte Zuordnung zu übernehmen, sie in eine neue Zuordnung zu kopieren und die alte zu verwerfen.
GManNickG

Antworten:

194

Da es eine Vielzahl von Antworten gibt, könnten Sie verwirrt sein, aber um es zusammenzufassen:

Verwenden Sie a std::queue. Der Grund dafür ist einfach: Es handelt sich um eine FIFO-Struktur. Sie wollen FIFO, Sie verwenden eine std::queue.

Es macht Ihre Absicht allen anderen und sogar Ihnen selbst klar. A std::listoder std::dequenicht. Eine Liste kann überall eingefügt und entfernt werden, was eine FIFO-Struktur nicht tun soll, und eine Liste kann dequean beiden Enden hinzugefügt und entfernt werden, was auch eine FIFO-Struktur nicht kann.

Deshalb sollten Sie a verwenden queue.

Nun haben Sie nach der Leistung gefragt. Denken Sie immer an diese wichtige Faustregel: Guter Code zuerst, Leistung zuletzt.

Der Grund dafür ist einfach: Menschen, die Leistung vor Sauberkeit und Eleganz anstreben, kommen fast immer als Letzte ins Ziel. Ihr Code wird zu einem Brei, weil sie alles Gute aufgegeben haben, um wirklich nichts daraus zu machen.

Wenn Sie zuerst guten, lesbaren Code schreiben, lösen sich die meisten Ihrer Leistungsprobleme von selbst. Und wenn Sie später feststellen, dass Ihre Leistung fehlt, können Sie jetzt ganz einfach einen Profiler zu Ihrem netten, sauberen Code hinzufügen und herausfinden, wo das Problem liegt.

Das alles std::queueist nur ein Adapter. Es bietet die sichere Schnittstelle, verwendet jedoch innen einen anderen Container. Sie können diesen zugrunde liegenden Container auswählen, was ein hohes Maß an Flexibilität ermöglicht.

Welchen zugrunde liegenden Container sollten Sie also verwenden? Wir wissen , dass std::listund std::dequesowohl die notwendigen Funktionen ( push_back(), pop_front(), und front()), so wie entscheiden wir?

Verstehen Sie zunächst, dass das Zuweisen (und Freigeben) von Speicher im Allgemeinen nicht schnell erledigt werden kann, da Sie zum Betriebssystem gehen und es auffordern müssen, etwas zu tun. A listmuss jedes Mal, wenn etwas hinzugefügt wird, Speicher zuweisen und ihn freigeben, wenn es verschwindet.

A dequehingegen teilt in Stücken zu. Es wird weniger häufig als a zugewiesen list. Stellen Sie sich das als Liste vor, aber jeder Speicherblock kann mehrere Knoten enthalten. (Natürlich würde ich vorschlagen, dass Sie wirklich lernen, wie es funktioniert .)

Allein damit dequesollte a eine bessere Leistung erbringen, da es nicht so oft mit dem Gedächtnis zu tun hat. In Verbindung mit der Tatsache, dass Sie Daten mit konstanter Größe verarbeiten, muss diese wahrscheinlich nicht nach dem ersten Durchlauf der Daten zugeordnet werden, während eine Liste ständig zugeordnet und freigegeben wird.

Eine zweite Sache zu verstehen ist die Cache-Leistung . Das Auslagern in den Arbeitsspeicher ist langsam. Wenn die CPU dies wirklich benötigt, kann sie das Beste aus dieser Zeit herausholen, indem sie einen Teil des Arbeitsspeichers in den Cache zurücknimmt. Da eine dequeZuweisung in Speicherblöcken erfolgt, führt der Zugriff auf ein Element in diesem Container wahrscheinlich dazu, dass die CPU auch den Rest des Containers zurückbringt. Jetzt sind alle weiteren Zugriffe auf die dequeschnell, da sich die Daten im Cache befinden.

Dies ist anders als bei einer Liste, bei der die Daten einzeln zugewiesen werden. Dies bedeutet, dass Daten über den gesamten Speicher verteilt werden können und die Cache-Leistung schlecht ist.

In Anbetracht dessen dequesollte a eine bessere Wahl sein. Aus diesem Grund ist dies der Standardcontainer bei Verwendung von a queue. Trotzdem ist dies immer noch nur eine (sehr) fundierte Vermutung: Sie müssen diesen Code profilieren, indem Sie dequein einem Test und listim anderen einen verwenden, um wirklich sicher zu sein.

Aber denken Sie daran: Lassen Sie den Code mit einer sauberen Oberfläche arbeiten, und sorgen Sie sich dann um die Leistung.

John äußert die Besorgnis, dass das Einwickeln eines listoder dequeeinen Leistungsabfall verursachen wird. Noch einmal, er oder ich können es mit Sicherheit sagen, ohne es selbst zu profilieren, aber es besteht die Möglichkeit, dass der Compiler die Aufrufe, die der queuemacht, inline macht. Das heißt, wenn Sie sagen queue.push(), wird es wirklich nur sagen queue.container.push_back(), den Funktionsaufruf vollständig zu überspringen.

Dies ist wiederum nur eine fundierte Vermutung, aber die Verwendung von a queuebeeinträchtigt die Leistung nicht im Vergleich zur Verwendung des zugrunde liegenden Rohcontainers. Wie ich bereits sagte, verwenden Sie das queue, weil es sauber, einfach zu bedienen und sicher ist und wenn es wirklich zu einem Problemprofil und Test wird.

GManNickG
quelle
10
+1 - und wenn sich herausstellt, dass boost :: Circular_Buffer <> die beste Leistung hat, verwenden Sie dies einfach als zugrunde liegenden Container (es bietet auch die erforderlichen Push_back (), Pop_front (), Front () und Back () ).
Michael Burr
2
Akzeptiert für die ausführliche Erklärung (was ich brauchte, danke, dass ich mir die Zeit genommen habe). Was die gute Leistung des ersten Codes angeht, muss ich zugeben, dass dies einer meiner größten Vorgaben ist. Ich versuche immer, die Sache beim ersten Durchlauf perfekt zu machen ... Ich habe den Code mit einer Deque geschrieben, die zuerst hart war, aber da die Sache nicht war. Wenn ich nicht so gut abschneide, wie ich dachte (es soll fast in Echtzeit sein), denke ich, ich sollte es ein bisschen verbessern. Wie Neil auch sagte, hätte ich wirklich einen Profiler verwenden sollen ... Obwohl ich froh bin, diese Fehler jetzt gemacht zu haben, obwohl es nicht wirklich wichtig ist. Vielen Dank euch allen.
Gab Royer
4
-1 für die Nichtlösung des Problems und aufgeblähte nutzlose Antwort. Die richtige Antwort hier ist kurz und es ist boost :: Circular_buffer <>.
Dmitry Chichkov
1
"Guter Code zuerst, Leistung zuletzt", das ist ein großartiges Zitat. Wenn nur jeder das verstehen würde :)
thegreendroid
Ich schätze den Stress bei der Profilerstellung. Eine Faustregel zu
liefern
28

Auschecken std::queue. Es umschließt einen zugrunde liegenden Containertyp und der Standardcontainer ist std::deque.

Mark Ransom
quelle
3
Jede zusätzliche Ebene wird vom Compiler entfernt. Nach Ihrer Logik sollten wir alle nur in Assembler programmieren, da die Sprache nur eine Shell ist, die im Weg steht. Es geht darum, den richtigen Typ für den Job zu verwenden. Und queueist das ein Typ? Guter Code zuerst, Leistung später. Zur Hölle, die meiste Leistung entsteht durch die Verwendung von gutem Code.
GManNickG
2
Es tut mir leid, vage zu sein - mein Punkt war, dass eine Warteschlange genau das ist, wonach die Frage gestellt wurde, und die C ++ - Designer hielten deque für einen guten zugrunde liegenden Container für diesen Anwendungsfall.
Mark Ransom
2
Nichts in dieser Frage deutet darauf hin, dass ihm die Leistung fehlte. Viele Anfänger fragen ständig nach der effizientesten Lösung für ein bestimmtes Problem, unabhängig davon, ob ihre aktuelle Lösung akzeptabel ist oder nicht.
Jalf
1
@John, wenn er feststellen würde, dass die Leistung fehlt, queuewürde das Entfernen der Sicherheitsschale die Leistung nicht steigern, wie ich bereits sagte. Sie haben eine vorgeschlagen list, die wahrscheinlich schlechter abschneiden wird.
GManNickG
3
Die Sache mit std :: queue <> ist, dass wenn deque <> nicht das ist, was Sie wollen (aus Leistungsgründen oder aus irgendeinem Grund), es ein Einzeiler ist, es zu ändern, um eine std :: list als Hintergrundspeicher zu verwenden - as GMan sagte vor langer Zeit. Und wenn Sie wirklich einen Ringpuffer anstelle einer Liste verwenden möchten, wird boost :: Circular_buffer <> direkt in ... std :: queue <> abgelegt. Dies ist mit ziemlicher Sicherheit die 'Schnittstelle', die verwendet werden sollte. Der Hintergrundspeicher dafür kann so ziemlich nach Belieben geändert werden.
Michael Burr
7

Ich habe ständig push_backneue Elemente, während ich pop_frontdas älteste Element bin (ungefähr eine Million Mal).

Eine Million ist wirklich keine große Zahl im Computer. Verwenden std::queueSie, wie andere vorgeschlagen haben, a als erste Lösung. In dem unwahrscheinlichen Fall, dass es zu langsam ist, identifizieren Sie den Engpass mithilfe eines Profilers (raten Sie nicht!) Und implementieren Sie ihn mithilfe eines anderen Containers mit derselben Schnittstelle erneut.

Phönix
quelle
1
Nun, die Sache ist, es ist eine große Zahl, denn was ich tun möchte, soll Echtzeit sein. Obwohl Sie Recht haben, dass ich einen Profiler hätte verwenden sollen, um die Ursache zu identifizieren ...
Gab Royer
Die Sache ist, ich bin es nicht wirklich gewohnt, einen Profiler zu verwenden (wir haben gprof ein bisschen in einer unserer Klassen verwendet, aber wir sind wirklich nicht in die Tiefe gegangen ...). Wenn Sie mich auf einige Ressourcen hinweisen könnten, würde ich mich sehr freuen! PS. Ich benutze VS2008
Gab Royer
@Gab: Welchen VS2008 hast du (Express, Pro ...)? Einige kommen mit einem Profiler.
sbi
@Gab Sorry, ich benutze VS nicht mehr, kann also nicht wirklich raten
@Sbi, soweit ich das sehe, ist es nur in der Team System Edition (auf die ich Zugriff habe). Ich werde das untersuchen.
Gab Royer
5

Warum nicht std::queue? Alles was es hat ist push_backund pop_front.

nervös
quelle
3

Eine Warteschlange ist wahrscheinlich eine einfachere Schnittstelle als eine Deque, aber für eine so kleine Liste ist der Leistungsunterschied wahrscheinlich vernachlässigbar.

Gleiches gilt für die Liste . Es hängt nur von der Auswahl der gewünschten API ab.

Lavinio
quelle
Aber ich habe mich gefragt, ob der ständige Push_back die Warteschlange oder Deque dazu bringt, sich neu zuzuordnen
Gab Royer
std :: queue ist ein Wrapper um einen anderen Container, daher wäre eine Warteschlange, die eine Deque umschließt, weniger effizient als eine Raw-Deque.
John Millikin
1
Bei 10 Elementen wird die Leistung höchstwahrscheinlich ein so kleines Problem sein, dass die "Effizienz" möglicherweise besser in der Programmierzeit als in der Codezeit gemessen wird. Und die Aufrufe von der Warteschlange zum Deque durch anständige Compiler-Optimierungen wären auf nichts zurückzuführen.
Lavinio
2
@ John: Ich möchte, dass Sie mir eine Reihe von Benchmarks zeigen, die einen solchen Leistungsunterschied demonstrieren. Es ist nicht weniger effizient als eine rohe Deque. C ++ - Compiler inline sehr aggressiv.
Jalf
3
Ich habe es versucht. : DA Quick & Dirty 10-Elemente-Container mit 100.000.000 pop_front () & push_back () rand () int-Nummern bei Release-Build für Geschwindigkeit auf VC9 ergibt: Liste (27), Warteschlange (6), Deque (6), Array (8) .
KTC
0

Verwenden Sie a std::queue, aber beachten Sie die Leistungskompromisse der beiden Standardklassen Container.

Standardmäßig std::queuebefindet sich ein Adapter darüber std::deque. In der Regel ergibt dies eine gute Leistung, wenn Sie eine kleine Anzahl von Warteschlangen mit einer großen Anzahl von Einträgen haben, was wohl der häufigste Fall ist.

Allerdings sei nicht blind für die Implementierung von std :: deque . Speziell:

"... Deques haben normalerweise große minimale Speicherkosten; eine Deque, die nur ein Element enthält, muss ihr vollständiges internes Array zuweisen (z. B. das 8-fache der Objektgröße in 64-Bit-libstdc ++; das 16-fache der Objektgröße oder 4096 Bytes, je nachdem, welcher Wert größer ist , auf 64-Bit-libc ++). "

Angenommen, ein Warteschlangeneintrag ist etwas, das Sie in die Warteschlange stellen möchten, dh relativ klein. Wenn Sie also vier Warteschlangen mit jeweils 30.000 Einträgen haben, ist die std::dequeImplementierung die Option der Wahl. Wenn Sie dagegen 30.000 Warteschlangen mit jeweils 4 Einträgen haben, ist die std::listImplementierung höchstwahrscheinlich optimal, da Sie den std::dequeOverhead in diesem Szenario niemals amortisieren .

Sie werden viele Meinungen darüber lesen, wie Cache König ist, wie Stroustrup verknüpfte Listen hasst usw., und all das ist unter bestimmten Bedingungen wahr. Akzeptieren Sie es einfach nicht im blinden Glauben, da es in unserem zweiten Szenario ziemlich unwahrscheinlich ist, dass die Standardimplementierung ausgeführt std::dequewird. Bewerten Sie Ihre Nutzung und messen Sie.

Allan Bazinet
quelle
-1

Dieser Fall ist so einfach, dass Sie einfach Ihren eigenen schreiben können. Hier ist etwas, das sich gut für Situationen mit Mikrocontrollern eignet, in denen die Verwendung von STL zu viel Platz beansprucht. Es ist eine gute Möglichkeit, Daten und Signale vom Interrupt-Handler an Ihre Hauptschleife zu übergeben.

// FIFO with circular buffer
#define fifo_size 4

class Fifo {
  uint8_t buff[fifo_size];
  int writePtr = 0;
  int readPtr = 0;
  
public:  
  void put(uint8_t val) {
    buff[writePtr%fifo_size] = val;
    writePtr++;
  }
  uint8_t get() {
    uint8_t val = NULL;
    if(readPtr < writePtr) {
      val = buff[readPtr%fifo_size];
      readPtr++;
      
      // reset pointers to avoid overflow
      if(readPtr > fifo_size) {
        writePtr = writePtr%fifo_size;
        readPtr = readPtr%fifo_size;
      }
    }
    return val;
  }
  int count() { return (writePtr - readPtr);}
};
user10658782
quelle
Aber wie / wann würde das jemals passieren?
user10658782
Oh, ich dachte es könnte aus irgendeinem Grund. Keine Ursache!
Ry-