コンテナ内の定数文字列を連続的に割り当てます

Question

私はstd::vectorがconst std::stringであると言います。

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

今ここでデフォルトの動作は、実際の文字列のコンテナが含まれる文字列の繰り返し処理を行う場合、ほとんどのデータの任意のプリフェッチを無効にし、ヒープ、上の任意の場所に割り当てることができるということです。しかし

strs.push_back("Foo"); // allocates char block on heap 
strs.push_back("Boo"); // allocates char block on heap 

、文字列であるため、「constの」私はchar型のブロックが連続して割り当てられるか、文字列の繰り返し処理を行う場合、最も効率的なキャッシュの動作を有するために（可能な場合）互いに近接するようにしたいと思います。

この動作を実現する方法はありますか？

Answer 1

メモリ領域アロケータと呼ばれるカスタムアロケータが必要です。詳細については、WikipediaやGoogleで調べることができますが、基本的な考え方は、ハードウェアスタックに似たものです。大きなチャンクを1つ割り当ててからポインタをインクリメントして、使用済みのチャンクにします。これは、多くの連続した要求に非常に迅速に対応できますが、空き領域や割り当てには対応できません。解放はすべて一度に行われます。

Answer 2

これは本当に簡単なことですが、決して変更されない文字列を押すと、独自のアロケータを書くのは簡単です。大きなブロックのメモリを割り当て、ブロック内でポインタfreeをオフセット0に設定します。新しい文字列strncpyの格納先が必要な場合は、freeになり、を使用してfreeを増やしてください。メモリブロックの終わりを追跡し、必要に応じて別のブロックを割り当てます。

Answer 3

連続プールからすべての文字列を割り当てるプライベートアロケータ（std::vectorの2番目のテンプレートパラメータ）を書くことができます。 また、 （std::basic_stringのプライベートケースです）の代わりにstd::stringを使用することができます。独自のアロケータを同様に指定することができます。一般的に、私はその時期を「時期尚早最適化」と言いますが、あなたがここでパフォーマンスを測定して見たと信じています...私は支払う価格がいくらかのメモリを浪費すると思います。

Answer 4

ベクトルは連続したメモリであることが保証されており、配列と相互運用可能な です。単独でリンクされたリストではありません。

"Contiguityは実際にベクトル抽象化の一部です。実際、C++ 03標準は保証を明示的に追加するように改訂されました。

出典：http://herbsutter.com/2008/04/07/cringe-not-vectors-are-guaranteed-to-be-contiguous/

使用reserve()連続するようにそれを強制し、再割り当てないようにします。

#include <iostream> 
#include <vector> 
#include <string> 
#include <algorithm> 
#include <iterator> 
using namespace std; 

int main() 
{ 
    // create empty vector for strings 
    vector<const string> sentence; 

    // reserve memory for five elements to avoid reallocation 
    sentence.reserve(5); 

    // append some elements 
    sentence.push_back("Hello,"); 
    sentence.push_back("how"); 
    sentence.push_back("are"); 
    sentence.push_back("you"); 
    sentence.push_back("?"); 

    // print elements separated with spaces 
    copy (sentence.begin(), sentence.end(), 
      ostream_iterator<string>(cout," ")); 
    cout << endl; 

return 0; 
} 

Answer 5

実際はありません。

std::stringはPODではなく、内容を「オブジェクトの内部」に保持しません。さらに、その内容を単一のメモリブロックに格納する必要もありません。

また、std::vector（すべての配列）は、その内容が1つのタイプ（=等しいサイズ）である必要があるため、異なる長さの文字列のリテラル「配列」を作成することはできません。

あなたの最高のショットは、長さを想定し、あなたが本当に異なる長さが必要な場合は、代替のデータのためだけstd::vector<char>プラスの連続した文字列が開始インデックスのstd::vector<unsigned>std::vector<std::array<char, N> >

を使用することです。

---

魅力的なアイデアは、文字列のために独自のアロケータをされたローリング、あなたはstd::vector<char>上で、それをベースにして、その上に独自のstd::basic_stringをロールアップし、それらのコレクションを作ることができます。

具体的には、特定のstd::stringの実装に大きく依存していることに注意してください。文字列の長さがバッファよりも大きければ、N個の文字の内部バッファがあり、メモリを外部に割り当てるものもあります。これが実装上の場合でも、文字列のバッファ全体に連続したメモリは得られません。

std::stringを使用すると、（特定のSTL実装に依存しない限り）一般的に目的を達成できず、ニーズに合わせて別の文字列を実装する必要があると私は結論づけます。

Answer 6

カスタムアロケータは素晴らしいですが、すべての文字列を単一のstd::vector<char>またはstd::stringに格納し、元の文字列にオフセットでアクセスするのはなぜですか？

シンプルで効果的です。