实现可变长度环形缓冲区的 C++ 代码与思路

作者

在多线程或高性能 IO 场景中，环形缓冲区（Ring Buffer）是一种常见的数据结构。
它将一个固定大小的数组视作循环队列，读写指针在达到数组末尾后会自动回绕到开头。

传统的环形缓冲区大小在编译时就确定，难以在运行时根据实际负载动态扩容。
下面介绍一种 可变长度环形缓冲区 的实现思路，既保留了环形缓冲区的高效读写特性，又能够在必要时自动扩容。

1. 设计思路

  1. 使用 std::vector 作为底层存储
    std::vector 允许我们在需要时扩容，同时提供连续内存。

  2. 维护读写指针

    • size_t head_：下一个写入位置
    • size_t tail_：下一个读取位置

  3. 扩容策略
    当写入操作发现缓冲区已满（(head_ + 1) % capacity_ == tail_），
    通过 vector::reserve/resize 将容量扩容为 2 * capacity_（或根据负载动态增大）。

  4. 扩容时的数据重排
    由于读写指针可能跨越数组末尾，扩容后需要把未读的数据移动到新数组的起始位置，保持读写顺序。

  5. 并发安全
    对单生产者/单消费者场景，可以使用无锁的实现；
    对多生产者/多消费者，需要加锁或使用原子操作。
    这里仅给出单线程版本，后续可按需添加 std::mutex 或 std::atomic.

2. 代码实现

#include <vector>
#include <stdexcept>
#include <cstring>   // memcpy

template<typename T>
class RingBuffer {
public:
    explicit RingBuffer(size_t capacity = 8)
        : buf_(capacity), capacity_(capacity),
          head_(0), tail_(0), size_(0) {}

    // 写入一个元素
    void push(const T& value) {
        if (full()) {
            grow();
        }
        buf_[head_] = value;
        head_ = next(head_);
        ++size_;
    }

    // 读取一个元素
    T pop() {
        if (empty()) {
            throw std::runtime_error("RingBuffer: pop from empty buffer");
        }
        T value = buf_[tail_];
        tail_ = next(tail_);
        --size_;
        return value;
    }

    bool empty() const { return size_ == 0; }
    bool full()  const { return size_ == capacity_; }
    size_t size() const { return size_; }
    size_t capacity() const { return capacity_; }

private:
    // 下一个位置（环绕）
    size_t next(size_t pos) const { return (pos + 1) % capacity_; }

    // 扩容并重排数据
    void grow() {
        size_t new_cap = capacity_ * 2;
        std::vector <T> new_buf(new_cap);

        // 把当前数据从 tail_ 开始复制到 new_buf
        if (tail_ < head_) {
            // 数据未跨界
            std::memcpy(&new_buf[0], &buf_[tail_],
                        sizeof(T) * size_);
        } else {
            // 数据跨界
            size_t first_part = capacity_ - tail_;
            std::memcpy(&new_buf[0], &buf_[tail_],
                        sizeof(T) * first_part);
            std::memcpy(&new_buf[first_part], &buf_[0],
                        sizeof(T) * head_);
        }

        buf_ = std::move(new_buf);
        head_ = size_;
        tail_ = 0;
        capacity_ = new_cap;
    }

    std::vector <T> buf_;
    size_t capacity_;
    size_t head_;
    size_t tail_;
    size_t size_;
};

说明

  • 构造函数
    允许指定初始容量，默认 8。
  • push
    写入前判断是否已满，若满则 grow()。
  • pop
    读取前判断是否为空。
  • grow
    1. 计算新容量为两倍。
    2. 新建 new_buf。
    3. 根据读写指针位置复制未读数据，保持顺序。
    4. 替换旧缓冲区并重置指针。

3. 使用示例

#include <iostream>

int main() {
    RingBuffer <int> rb(4);  // 初始容量 4

    for (int i = 1; i <= 10; ++i) {
        rb.push(i);
        std::cout << "Pushed " << i << ", size=" << rb.size() << "\n";
    }

    while (!rb.empty()) {
        std::cout << "Popped " << rb.pop() << "\n";
    }

    return 0;
}

运行结果：

Pushed 1, size=1
Pushed 2, size=2
Pushed 3, size=3
Pushed 4, size=4
Pushed 5, size=5   // 自动扩容
Pushed 6, size=6
Pushed 7, size=7
Pushed 8, size=8
Pushed 9, size=9
Pushed 10, size=10
Popped 1
Popped 2
Popped 3
Popped 4
Popped 5
Popped 6
Popped 7
Popped 8
Popped 9
Popped 10

4. 性能与扩展

  • 时间复杂度

    • push、pop：平均 O(1)。
    • grow：O(n)，但在多次 push 后触发次数少，整体摊销保持 O(1)。

  • 内存占用
    每次扩容都会复制一次数据，若数据量极大可考虑采用两段式存储或锁定的扩容策略。

  • 多线程
    通过 std::mutex 或 std::atomic 保护 head_、tail_ 与 size_。
    对于单生产者/单消费者，可采用无锁环形缓冲区（CAS 操作）进一步提升性能。

5. 结语

可变长度环形缓冲区兼具循环队列的低延迟和动态扩容的灵活性。
在需要处理异步流、音视频帧或网络包的 C++ 项目中，使用上述实现可以显著简化数据管理逻辑，提升系统吞吐量。

发表评论