使用STL向量作为字节数据的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);

这不是完整的代码,但是很好地了解了我如何利用向量来实现这种数据流机制.

我对这个实现的主要关注是从前面移除,这需要移除每个元素(我不确定如何erase()对向量进行优化,但在最坏的情况下,每个元素移除导致整个向量的移位).另一方面,由于数据的连续性,向量是CPU高速缓存局部性的候选者(但不保证CPU高速缓存的使用).

我想过可能会使用boost::circular_buffer,但我不确定它是否适合这项工作.

我还没有为接收队列的增长编写一个上限,但是我可以很容易地做reserve(MAX_RECEIVE_BYTES)某个地方,并确保它size()永远不会超过MAX_RECEIVE_BYTES我继续附加到它的后面.

这种方法一般都可以吗？如果没有,那有什么性能问题？什么容器在这里更合适？

Answer 1

从向量的前面擦除一个元素当时可能非常慢,特别是如果缓冲区很大(除非你可以重新排序元素,你不能使用FIFO队列).

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

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

另一方面,由于数据的连续性,向量是CPU缓存局部性的候选者(但这不能保证).

std::vector保证连续存储.固定循环缓冲区也具有连续存储.

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