は、私は単純に文字列のコンテナである「スライディングウィンドウ」を必要とするアプリケーションを働いていますコンテナタイプ

Question

は、

Window = ["the", "dog", "is", "hungry"] 

アプリケーション・プロセスに大きなテキストファイルと、ウィンドウが追加されますベスト新しい文字列を末尾に置き、最初の要素を削除します。

Window = ["dog", "is", "hungry", now"]

たびにウィンドウが変化するので、それはなり

Window <- Window.AddToEnd("now") and Window.DeleteFirst() 

そして、「今」が追加される次の単語であると言う、プロセスは順序が重要な要素の上で実行される（つまり、インデックスは重要です）。

私は文字列のベクトルに行き、両端キューを試しました。 人々が最高だと思うものが私は不思議でしたか？

要約すると、私は、常に新しい要素が追加され、最初の要素が削除されるインデックス付けされた文字列のコンテナが必要です。私はまた、コンテナの多くを繰り返し処理する必要があります。

情報のいくつかの他のビット：

1. 文字が容器
2. に一度修正されることはありません窓要素は（ポップの外側と論じたようにプッシュする）に変更されることはない
3. サイズのウィンドウは実行時まで知りません（ユーザが何かを渡す）
4. ウィンドウはサイズを決して変更しません。開始時に初期化されると、アプリケーション全体のサイズにとどまります。

任意の提案を大幅にあなたがstd::dequeを使用することができ、乾杯デビッド

Answer 1

をいただければ幸いです。

std::listも同じ機能を共有する。

---

あなたは/割り当て解除メモリを割り当てる回数を制限する場合は、あなたもそうのようなstd::vectorを使用することができます。

#include <vector> 
#include <string> 

int main() { 

    std::vector<std::string> strs; 

    // ... 

    std::string tmp; 
    while (true) { 
     for (size_t i = 1; i < strs.size(); ++i) 
      strs[i-1] = std::move(strs[i]); 
    // strs.erase(strs.begin()); also works. 

     std::cin >> tmp; 
     strs.back() = tmp; 
    } 

    return 0; 
} 

そして、これはあなたが必要しかし、多くの場所に保持することを可能にし、値を移動するだけです。 cplusplus.comによれば、std::dequeに加え

Answer 2

、

だけでなく、その端部ではなく、要素の効率的な挿入および欠失を有する、配列の先頭に、ベクターと同様の機能を提供。ただしベクトルとは異なり、デクはすべての要素を連続した格納場所に格納することは保証されません

また、固定サイズのベクトルを使用して開始インデックスを保存することもできます。

したがって、円形配列のように動作します。最初のインデックスは0であり、最初は[a、b、c、d]である。 'e'が入った後は[e、b、c、d]ですが、始めのインデックス= 1になります。 i番目の要素はv[(beginning_index + i) % v.size()]です。このスキームは自分で実装するのには簡単です。

Answer 3

以下は、コンテナのサイズが実行時には一定ですが、クラステンプレートのインスタンス化中に設定される循環コンテナのクラステンプレートの例です。これを使用するには、事前にサイズを把握しておくか、あらかじめ計算しておく必要があります。サイズが分からない場合は、テンプレートや別のコンテナなしで同様のアルゴリズムを使用することを検討してください。サイズが極端に大きくない場合、これは非常にうまく動作します。追加される要素が含まれている配列のサイズを超え始めると、addString()関数でわかるように、呼び出されているforループがあり、その配列内のすべてをシフトしなければなりません。これは100または1000sの要素のオーダーの配列では問題ありませんが、サイズが100,000または1,000,000の配列になったときはうまくいきます。これはボトルネックとなり、かなり遅くなりますが、これはすべてを1つのスペースだけ左にシフトし、配列、リスト、またはコンテナの最後に追加するメカニズムを提供します。

#include <iostream> 
#include <memory> 
#include <string> 


template<unsigned Size> 
class CircularContainer { 
public: 
    const static unsigned SIZE = Size; 
private: 
    std::string data_[SIZE]; 
    unsigned counter_; 

public: 
    CircularContainer() : counter_(0) {} 

    void addString(const std::string& str) { 
     // In a real container this would be a member and not static 
     // If you have a static here, and you have multiple instances 
     // It will still increment across all instances. 
     //static unsigned counter = 0; 

     if (counter_ < SIZE) { 
      data_[counter_++ % SIZE] = str; 
     } else { 
      // This function can be expensive on large data sets 
      // due to this for loop but for small structures this 
      // is perfectly fine. 
      for (unsigned u = 0; u < SIZE-1; u++) { 
       data_[u] = data_[u+1]; 
      } 
      data_[SIZE - 1] = str; 
     } 
    } 

    std::string& getString(unsigned idx) { 
     if (idx < 0 || idx >= SIZE) { 
      return std::string(); 
     } else { 
      return data_[idx]; 
     } 
    } 

    unsigned size() const { 
     return SIZE; 
    } 
}; 

int main() { 

    CircularContainer<4> cc; 

    cc.addString("hello"); 
    cc.addString("world"); 
    cc.addString("how"); 
    cc.addString("are"); 

    for (unsigned u = 0; u < cc.size(); u++) { 
     std::cout << cc.getString(u) << "\n"; 
    } 
    std::cout << std::endl; 

    cc.addString("you"); 
    cc.addString("today"); 

    for (unsigned u = 0; u < cc.size(); u++) { 
     std::cout << cc.getString(u) << "\n"; 
    } 


    std::cout << "\nPress any key and enter to quit." << std::endl; 
    char c; 
    std::cin >> c; 

    return 0; 
} 

これでこれに適応できます。このクラス内の生の配列の配列を交換し、ポインタリンケージでヒープを使用してください。そして、中間にある他のものはすべて既にリンクされているため、begとendのポインタを適切なデータに再割り当てするだけです。鎖。私は任意の型を取るために、このクラスを拡張してきたし、代わりにそのデータ型の生の配列を使用しての、私はここでstd::shared_ptrの使用を配列で置き換え

---

編集の再設計です上記のクラス。 static counterを使用して問題を修正し、メンバーにしました。

それでも、指定された配列と、その配列のインデックスを囲む同じテクニックを使用します。ここでの唯一の違いは、std::shared_ptr<T>の配列を使用していることです。これにより、クラステンプレートのスコープに対するローカルスタックではなく、格納されたオブジェクトがヒープ上に置かれます。メモリのクリーンアップは自動的に実行する必要がありますが、必ずしも保証されません。明示的に必要な場合を除き、このクラステンプレートに追加するのが難しい場合を除き、head & tailの位置を追跡する必要はあまりありません。