我的循环缓冲区出了什么问题？

Question

最近我参加了一次工作面试，被要求实现循环缓冲区类。要求不使用任何容器（包括STL）。

我的代码如下：

template<class T>
class CircularFifo
{
    T *    _data;
    size_t _size;

    size_t _read;  // last readen elem
    size_t _write; // next write index

    CircularFifo(CircularFifo const &) = delete;
    CircularFifo & operator=(CircularFifo const &) = delete;
    CircularFifo(CircularFifo &&) = delete;
    CircularFifo & operator=(CircularFifo &&) = delete;

public:
    explicit inline
    CircularFifo(size_t size = 2048)
        : _data(new T[size])
        , _size(size)
        , _read(-1)
        , _write(0)
    {
        if (0 == _size)
        {
            throw std::runtime_error("too empty buffer");
        }

        if (1 == _size)
        {
            throw std::runtime_error("too short buffer");
        }

        if (-1 == size)
        {
            throw std::runtime_error("too huge buffer");
        }
    }

    inline ~CircularFifo()
    {
        delete []_data;
    }

    inline T read()
    {
        if (_read == _write)
        {
            throw std::runtime_error("buffer underflow");
        }
        return _data[(++_read) % _size];
    }

    inline void write(T const & obj)
    {
        if (_read == _write)
        {
            throw std::runtime_error("buffer overflow");
        }
        _data[(_write++) % _size] = obj;
    }
};

面试官表示代码风格很好，但缓冲区中存在一个错误，这将使该类不可靠。她要求我找到它，但我完全失败了。她也没有向我透露这个错误。

我重新检查了一切：泄漏、算术、可能的溢出等等。我的头几乎要爆炸了。我不知道哪里出错了。请帮帮我。

P.S. 对于我的混乱英语，我感到抱歉。

- J. Doe

---

我看到的第一件事是，你没有遵循3/5规则。 - NathanOliver

在read函数中，您需要检查_read不等于_write，然后在使用_read之前对其进行预增。这对我来说似乎有点可疑。 - Colin

类中定义的成员函数默认情况下是inline的。（这不是一个错误，只是一个小的可读性问题，在面试中可能会让你看起来不太好。） - nwp

检查 if (-1 == size) 无法涵盖所有溢出情况。 - wkl

@NathanOliver 你说得对。在现实世界中，这是一个错误。但算法本身必须存在错误。我会修复它，以免混淆。 - J. Doe

它是否只是编译？size、read和write成员的类型为size_t，应该是无符号的。因此，您不能将它们赋值或与-1进行比较。 - howdihow

Answer 1

可能是_read初始化为-1，而_write初始化为0，但在读取函数中检查它们是否相等？当缓冲区首次初始化并尝试进行读取时，if检查将成功，即使尚未向缓冲区添加任何内容。

- Trevor

---

在一次面试中，面临压力时，我不认为那是一个容易发现的错误。我知道在面试中，我个人曾经在更简单的代码上犯过更严重的错误。 - Trevor

Answer 2

您的代码中有几个bug。首先，正如另一个答案中已经指出的那样，通过将_read初始化为-1，如果您尝试在写入之前读取，将会读取到垃圾数据。其次，如果您没有读取任何内容，但您写入了size项，则_write将环绕并覆盖缓冲区的开头，因为_read永远不会等于_write。

但即使您将_read和_write都初始化为有效值，也无法工作，因为在您的代码中，条件_read == _write意味着“缓冲区为空”和“缓冲区已满”。两个索引中的一个必须在另一个索引之前停止一个元素。如果_read == _write表示“缓冲区为空”，那么(_read+1)%size == _write应该表示“缓冲区已满”。

通过以这种方式实现循环缓冲区，您将始终浪费一个元素（最多可以存储size-1项）。

还有一种实现循环缓冲区的方法，不会浪费一个元素。这里有一篇文章，介绍了两种实现循环缓冲区的方式。

- Vladan Bato

---

非常启发性的文章！ - J. Doe

Answer 3

当 _read 或 _write 溢出时，会出现问题。当大小不是2的幂时，您会跳过元素。这在循环缓冲区中不是预期的行为。

每次操作后，它们应该被赋值为模数 _size。

另外，顺带一提，我不会使 size 成为带有任意值的默认参数。如果用户不知道他们应该使用什么大小，则他们不理解数据结构的目的和危险。

第二点。我认为非关键异常，例如“缓冲区溢出/下溢”，应该是仅在调试时才进行断言（也许零大小）。如果发生这样的情况，那么这是由用户造成的严重错误，而不是特殊情况。它们源于用户代码中的逻辑错误，而不是像可寻址内存数量这样的不可控制限制。

但是大小为一也应该完全没问题。

- Sopel

---

你需要一个额外的插槽，这样你就可以区分满缓冲区和空缓冲区。 - Malcolm McLean

当错误处理是必需的时候，我想你是正确的。 - Sopel

Answer 4

除了初始化错误之外，您还有这个问题：

当您添加元素时，会检查（_read == _write），然后执行_write ++。因此，在_write字段溢出其类型之前，您可以在不阅读的情况下进行写入。您需要在写入之前检查((_write - _read) == _size)，而不是(_read == _write)。

- Andrew Kashpur