Verwenden von STL-Vektor als FIFO-Container für Byte-Daten

Question

Ich habe einen Thread ausgeführt, der einen Strom von Bytes von einem seriellen Anschluss liest. Es tut dies kontinuierlich im Hintergrund und liest aus dem Strom, der zu verschiedenen, getrennten Zeiten hereinkommt. Ich speichere die Daten in einem Container wie so:

ByteVector read_bytes = serial_port->ReadBytes(100); // read 100 bytes; returns as a "ByteVector" 
receive_queue.insert(receive_queue.end(), read_bytes.begin(), read_bytes.end()); 

Wenn ich bereit bin, zu lesen:

using ByteVector = std::vector<std::uint8_t>; 
ByteVector receive_queue; 

Wenn Daten kommen aus dem seriell Port, ich es bis zum Ende der Byte-Warteschlange anhänge Daten in der Warteschlange empfängt, entferne ich es von vorne:

unsigned read_bytes = 100; 
// Read 100 bytes from the front of the vector by using indices or iterators, then: 
receive_queue.erase(receive_queue.begin(), receive_queue.begin() + read_bytes); 

Dies ist nicht der vollständige Code, sondern gibt eine gute Vorstellung davon, wie ich den Vektor für diesen Daten-Streaming-Mechanismus bin verwendet.

Mein Hauptanliegen bei dieser Implementierung ist die Entfernung von der Vorderseite, die Verschiebung jedes Element entfernt erfordert (ich bin mir nicht sicher, wie optimiert erase() ist für Vektor, aber im schlimmsten Fall, jede Elemententfernung führt zu einer Verschiebung von der gesamte Vektor). Auf der anderen Seite sind Vektoren wegen der zusammenhängenden Natur der Daten Kandidaten für eine CPU-Cache-Lokalität (aber die CPU-Cache-Nutzung ist nicht garantiert).

Ich habe gedacht, vielleicht mit boost::circular_buffer, aber ich bin mir nicht sicher, ob es das richtige Werkzeug für den Job ist.

Ich habe noch nicht eine obere Grenze für das Wachstum der Empfangswarteschlange codiert, jedoch konnte ich irgendwo leicht tun ein reserve(MAX_RECEIVE_BYTES), und stellen Sie sicher, dass size() niemals größer als MAX_RECEIVE_BYTES ist, wie ich auf der Rückseite davon anhängen weiter .

Ist dieser Ansatz im Allgemeinen in Ordnung? Wenn nicht, welche Leistungsbedenken gibt es? Welcher Container wäre hier angemessener?

Answer 1

Das Löschen eines Vektors von der Vorderseite eines Vektors kann ziemlich langsam sein, besonders wenn der Puffer groß ist (es sei denn, Sie können Elemente neu anordnen, was mit einer FIFO-Warteschlange nicht möglich ist).

Ein Ringpuffer ist eine ausgezeichnete, vielleicht ideale Datenstruktur für eine FIFO-Warteschlange fester Größe. Aber es gibt keine Implementierung in der Standardbibliothek. Sie müssen es selbst implementieren oder eine Implementierung von Drittanbietern wie die von Ihnen entdeckte Boost verwenden.

Die Standardbibliothek bietet eine übergeordnete Struktur für eine wachsende FIFO-Warteschlange: std::queue. Für eine Datenstruktur niedrigerer Ebenen ist die doppelendige Warteschlange eine gute Wahl (std::deque, die der Standardcontainer von std::queue ist).

Auf der anderen Seite sind Vektoren Kandidaten für CPU-Cache-Lokalität wegen der zusammenhängenden Natur der Daten (aber das ist nicht garantiert).

Die kontinuierliche Speicherung von std::vector ist garantiert. Ein fester zirkularer Puffer hat auch einen kontinuierlichen Speicher.

Ich bin nicht sicher, was über Cache-Lokalität von std::deque garantiert wird, aber es ist in der Praxis in der Regel ziemlich gut, da die typische Implementierung eine verknüpfte Liste von Arrays ist.

Answer 2

Die Leistung ist schlecht, was wichtig ist oder nicht. Vom Kopf abzunehmen bringt eine Kaskade von Bewegungen mit sich.Aber STL hat Warteschlangen für genau diesen Zweck, benutzen Sie einfach einen.