循環バッファの実装

Question

はい、再び、私は非常にまっすぐ進む実装に再び来る：

// write data always! if buffer is already full, overwrite old data! 
    void Put(const CONTENT_TYPE &data) 
    { 
     buffer[ inOffset++] = data; 
     inOffset%=size; 

     // was data overwritten, skip it by increment read offset 
     if (inOffset == outOffset) 
     { 
      outOffset++; 
      outOffset%=size; 
      std::cout << "Overwrite" << std::endl; 
     } 
    } 

    CONTENT_TYPE Pull() 
    { 
     CONTENT_TYPE data = buffer[ outOffset++ ]; 
     outOffset %= size; 
     return data; 
    } 

しかし、この単純なアルゴリズムは、バッファのサイズのみ-1 1の要素を利用して！ sizeof（要素）バイトを - 私はそれを避けたい場合は

は、私が唯一のsizeof私を無駄に別のカウンタ変数を追加（counter_var）で解決策を見つけました。

Q：メモリを浪費しないソリューションはありますか？それはとてもひどいシンプルに見えますが、私は

備考:-)それをキャッチすることはできません。いくつかのより多くの空のために保護するためのコードの行読み込み、他のものがありますが、これは問題には重要ではありません。アルゴリズムは言語に依存せず、またC++のコード例を与えても、C++のタグは付けられません。

Answer 1

-1などのオフセットの1つに特別なセンチネル値を使用して、バッファがいっぱいであるか空であることを示すことができます。これはオフセットをチェックして変更するコードを複雑にします。

// write data always! if buffer is already full, overwrite old data! 
void Put(const CONTENT_TYPE &data) 
{ 
    buffer[ inOffset++] = data; 
    inOffset%=size; 

    // was data overwritten, skip it by setting read offset to sentinel 
    if (inOffset == outOffset || outOffset == -1) 
    { 
     outOffset = -1; 
     std::cout << "Overwrite" << std::endl; 
    } 
} 

CONTENT_TYPE Pull() 
{ 
    if (outOffset == -1) 
     outOffset = inOffset; 
    CONTENT_TYPE data = buffer[ outOffset++ ]; 
    outOffset %= size; 
    return data; 
} 

bool IsEmpty() 
{ 
    return outOffset == inOffset; 
} 

Answer 2

モジュロ操作を行う時点を別にすれば、それを処理できます。アクセスごとに読み込みポインタと書き込みポインタを増やすと仮定します。増加した後で直ちにモジュロをリードし、ライトポインタがモジュロ直前に読み込みを行うと、| write-read |フルバッファの長さは、特別なケースハンドリングなしに、バッファの長さになります。それが機能するためには、あなたの書き込みポインタは常には% buffer_length使用する必要がありますが、は% (2 * buffer_length)を保存します。

特別なケースとして扱うのは通常はお勧めではないので、マイナスのセンチネル値を導入するのは通常、size_t（つまり符号なし整数）を使用する場所にありません。 。

void put(const ELEMENT& element) { 
    if (nElements == size) throw "put: buffer full"; 
    buffer[(start + nElements++) % size] = element; 
} 

ELEMENT get() { 
    if (nElements == 0) throw "get: buffer empty"; 
    ELEMENT& value = buffer[start]; 
    start = (start + 1) % size; 
    --nElements; 
    return value; 
} 

もちろん、置き換えることができる：

Answer 3

あなたはその場で2番目のインデックスを見つけるために変換し、その後、2つの整数を使用し、もう1つは、インデックスと他の要素数であれば、すべてのスロットを埋めることができますあなたが好きなら、if (foo > size) foo -= size;でmodオペレーションを実行してください。