ロープのデータ構造を作ろうとしています。二分木、つまり再帰的なデータ構造の一種です。
ロープの目的は、分割と連結を高速にすることです。これは、ロープ全体をコピーすることを避けることを意味します。
したがって、たとえば、ユーザーはrope1 + rope2対数時間で結果を言い、期待できる必要があります。
ただし、これには問題
があります。ロープが変更されると、その親も間接的に変更されます。
私の目標はropeの簡単な代替品を作ることなのでstring、これは受け入れられません。
これに対する私の解決策は次のとおりです。 に何らかの変更がある場合は常に、古いノードを変更せずに、わずかな変更を加えて新しいropeノードを作成します。
理論的には、これはかなりうまくいくと思います。
ただし、実際には、文字列の変更ごとに (ほとんど?)ヒープ割り当てが必要です。
1 文字の変更でも新しいヒープ オブジェクトが作成され、それ自体が遅いだけでなく、メモリの局所性が大幅に低下し、パフォーマンスに非常に悪影響を及ぼします。
この問題を解決するにはどうすればよいですか？
従来のアプローチはコピー オン ライトです。このためには、割り当てられた各ノードを参照カウントする必要があります。
変更されたノードの refcount が 1 の場合 (他の誰も参照していない場合)、複製する必要はありません。
これに関する実際的な問題は、変更を非変更操作から便利に分離することです。
char& rope::operator[] (std::string::pos)
参照された char を変更する可能性がありますが、const オーバーロードが実際に変更されない場合に強制的に選択する簡単な方法はありません。これは、ミューテーションが発生すると想定し、おそらく不要なコピーをトリガーするか、代わりに文字変換と代入をオーバーロードするプロキシを返す必要があることを意味します。
このアプローチは、std::string(文字列が単一ノードのロープと同等である) iirc の初期の実装で試行され、支持されなくなりました。部分的にはミューテーションの問題のためであり、部分的にはマルチスレッドについて心配しなければならない場合、COW と必要な参照カウントがますます高価になるためです。
あなたが言うように、ノードに2つの独立したタイプの状態が含まれている場合、ロープには追加の問題があります。それは、独自の文字列とその子ノードへの参照です(これにより、refcount /子参照の突然変異がツリーを伝播するため)。
代わりに、文字がリーフ ノードにのみ格納され、非リーフ ノードの完全なコピーを行う場合 (したがって、各ロープには独自の "ディレクトリ構造" があります)、文字のコピーを回避し、参照カウントされた共有状態が大幅に増加します。より簡単です。
これは、あなたが望む対数時間の連結を取得しますか? おそらくそうではありません：
線形時間に近いか対数時間に近いかは、refcount をインクリメントする場合とディレクトリ ツリーをコピーする場合の相対的なコストに依存します。
ただし、これがないと、高速な連結が得られますが、COW 操作をツリーに伝播する必要がある場合、任意の文字アクセスが (予期せず) 対数時間に劣化する可能性があります。
ユースケースに適している場合は、移動連結を実装できると思います。これにより、一定時間の追加が可能になり、余分な COW の複雑さを回避できます。
ただし、実際には、文字列の変更ごとに (ほとんど?) ヒープ割り当てが必要です。
頻繁なヒープ割り当てのパフォーマンスの問題を回避したい場合は、メモリのチャンクを割り当てるクラス用のメモリ プールを使用することをお勧めします。これは、OS がいっぱいになったときにのみ新しい割り当てを要求する必要があるため、発生する頻度はかなり低いはずです。 . 次に、メモリ プールへのアクセスを最適化してchar、 などの小さなブロック データ型を割り当てることができます。
Andrei Alexandrescu は、著書「Modern C++ Design」で、スモール ブロック メモリ アロケータの優れた例を紹介しています。