c++ - 使用 STL vector 作为字节数据的 FIFO 容器

Question

我有一个正在运行的线程，它从串行端口读取字节流。它在后台连续执行此操作，并在不同的、不同的时间从流中读取数据。我将数据存储在这样的容器中:

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

当数据从串口进来时，我把它追加到字节队列的末尾:

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());

当我准备好读取接收队列中的数据时，我将其从前端移除:

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

这不是完整的代码，但很好地说明了我如何将 vector 用于此数据流机制。

我对这个实现的主要关注是从前面删除，这需要移动每个删除的元素(我不确定 erase() 对 vector 的优化程度如何，但在最坏的情况下，每个元素的移除都会导致整个 vector 的移动)。另一方面，由于数据的连续性， vector 是 CPU 缓存局部性的候选者(但不能保证 CPU 缓存的使用)。

我考虑过可能使用 boost::circular_buffer，但我不确定它是否适合这项工作。

我还没有为接收队列的增长编写上限，但是我可以很容易地在某处执行 reserve(MAX_RECEIVE_BYTES)，并确保 size() 永远不会大于 MAX_RECEIVE_BYTES，因为我会继续追加到它的后面。

这种做法大体上可行吗？如果不是，存在哪些性能问题？什么容器在这里更合适？

Answer 1

一次从 vector 的前面删除一个元素可能会非常慢，尤其是在缓冲区很大的情况下(除非您可以对元素重新排序，而这在 FIFO 队列中是做不到的)。

对于固定大小的 FIFO 队列，循环缓冲区是一种优秀的、也许是理想的数据结构。但是标准库中没有实现。您必须自己实现或使用第三方实现，例如您发现的 Boost 实现。

标准库为不断增长的 FIFO 队列提供了一个高级结构:std::queue。对于较低级别的数据结构，双端队列是一个不错的选择(std::deque，它是 std::queue 的默认底层容器)。

On the flip side, vectors are candidates for CPU cache locality because of the contiguous nature of the data (but this is not guaranteed).

std::vector 的连续存储是有保证的。一个固定的循环缓冲区也有连续存储。

我不确定 std::deque 的缓存局部性有什么保证，但它在实践中通常非常好，因为典型的实现是数组的链表。