0
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

C++のリングバッファ(FIFO)

Last updated at Posted at 2021-01-11

C++でのリングバッファ(FIFO)のメモ書きです。
わかりやすい例が見当たらなかったので書いてみました。

ポイントは、データの個数のみをif文でチェックして、frontやrearの位置はチェックしないことです。

frontやrearの位置をチェックしようとすると、データが0のときとデータが満杯のとき、両方ともforntとrearの位置が同じになるので、これを判別するのには別の要素が必要となり、冗長なプログラムになります。

ここ10年くらいほとんどプログラムを組んでないので、何かありましたらお手柔らかにお願いします。

# include <iostream>
# include <string.h>
using namespace std;

# define SIZE 3
class FIFOBuf {
  private:
    char array[SIZE][4];
    int rear = 0, front = 0, data_num = 0;

  public:
    int push(char *data)
    {
      if (data_num == SIZE) //full
        return false;

      data_num++;
      memcpy(array[rear], data, 4);
      rear = (rear + 1) % SIZE;

      return true;
    }

    int pop(char *data)
    {
      if (data_num == 0) //empty
        return false;

      data_num--;
      memcpy(data, array[front], 4);
      front = (front + 1) % SIZE;

      return true;
    }
};

以下テストプログラムです。

int main() {
    
    FIFOBuf buf;
    char data[4];
    
    std::cout << buf.push("123") << std::endl;
    std::cout << buf.push("456") << std::endl;
    std::cout << buf.push("789") << std::endl;
    std::cout << buf.push("abc") << std::endl;

    std::cout << buf.pop(data) << ", " << data << std::endl;
    std::cout << buf.pop(data) << ", " << data << std::endl;
    std::cout << buf.pop(data) << ", " << data << std::endl;
    std::cout << buf.pop(data) << ", " << data << std::endl;
}

実行結果

1
1
1
0
1, 123
1, 456
1, 789
0, 789

実行環境
https://www.codechef.com/ide
C++14(Gcc 6.3)にて確認しました。


21/01/13 追記:
@kazatsuyuさんからのご指摘で、
rear は常に (front + data_num) % SIZEなので不要ではないか、とのこと。その通りなので、それに従ってプログラムを変更してみます。

# define SIZE 3
class FIFOBuf {
  private:
    char array[SIZE][4];
    int front = 0, data_num = 0;

  public:
    int push(char *data)
    {
      if (data_num == SIZE) //full
        return false;

      memcpy(array[(front + data_num) % SIZE], data, 4);
      data_num++;

      return true;
    }

    int pop(char *data)
    {
      if (data_num == 0) //empty
        return false;

      memcpy(data, array[front], 4);
      data_num--;
      front = (front + 1) % SIZE;

      return true;
    }
};

こちらのほうが視覚的にもわかりやすくなっていると感じます。data_numのインクリメント、デクリメントの位置をmemcpyの後に変更してますが、副作用とかあるので、最初からmemcpyの後に置いたほうがよかったです。
正直、自分では気が付きませんでした。こういうご指摘は大変有り難いです。

0
3
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?