STD :: Stringの実装におけるこの最適化は許可されますか？

StackOverflow https://stackoverflow.com/questions/4682603

質問

私はただの実装について考えていました std::string::substr. 。それは新しいものを返します std::string オブジェクト、それは私には少し無駄に思えます。元の文字列の内容を参照し、暗黙的にに割り当てることができるオブジェクトを返してみませんか std::string？実際のコピーの一種の怠zyな評価。そのようなクラスは次のように見えるかもしれません：

template <class Ch, class Tr, class A>
class string_ref {
public:
    // not important yet, but *looks* like basic_string's for the most part

private:
    const basic_string<Ch, Tr, A> &s_;
    const size_type pos_;
    const size_type len_;    
};

このクラスのパブリックインターフェイスは、実際のすべての読み取り専用操作を模倣します std::string, 、したがって、使用法はシームレスになります。 std::string その後、aを取る新しいコンストラクターを持つことができます string_ref したがって、ユーザーが賢くなることはありません。結果を「保存」しようとした瞬間、コピーを作成することになってしまうので、データを指して、それを背後に変更することに実際の問題はありません。

このコードは次のとおりです。

std::string s1 = "hello world";
std::string s2 = "world";
if(s1.substr(6) == s2) {
    std::cout << "match!" << std::endl;
}

2を超えないでしょう std::string 合計で構築されたオブジェクト。これは、多くの文字列操作を実行するコードの有用な最適化のようです。もちろん、これは単に当てはまるわけではありません std::string, 、しかし、その内容のサブセットを返すことができる任意のタイプに。

私の知る限り、実装はこれを行いません。

質問の中核は次のとおりです。

暗黙的にに変換できるクラスが与えられます std::string 必要に応じて、ライブラリライターがメンバーのプロトタイプを変更してタイプを変更することは標準に準拠していますか？またはより一般的には、図書館の作家は、これらのタイプのケースの通常のオブジェクトの代わりに「プロキシオブジェクト」を最適化として返すための余裕を持っていますか？

私の腸は、これが許可されておらず、プロトタイプが正確に一致する必要があるということです。返品タイプだけで過負荷にならないことを考えると、図書館の作家がこれらのタイプの状況を利用する余地は残されません。私が言ったように、答えはノーだと思いますが、私は尋ねたと思いました:-)。

役に立ちましたか？

解決

このアイデアはです コピーオンワイト, 、しかし、バッファー全体を牛にする代わりに、バッファのどのサブセットが「実際の」文字列であるかを追跡します。 （COWは、通常の形で、一部のライブラリの実装で使用されていました。）

したがって、これらの詳細を完全に内部にすることができるため、プロキシオブジェクトやインターフェイスの変更はまったく必要ありません。概念的には、ソースバッファー、バッファの参照カウント、およびこのバッファ内の文字列の開始と終了の4つを追跡する必要があります。

操作がバッファーをまったく変更するときはいつでも、独自のコピーを作成します（最初からデリミターから）、古いバッファーの参照カウントを1つ減らし、新しいバッファーの参照カウントを1つに設定します。参照カウントルールの残りの部分は同じです。コピーとカウントを1つに増やし、文字列を破壊し、カウントを1つずつ減らし、ゼロと削除に到達します。

substr 開始と終了のデリミターが明示的に指定されている場合を除き、新しい文字列インスタンスを作成するだけです。

他のヒント

これは、コピーオンワイトまたは牛と呼ばれる比較的広く使用されている非常によく知られている最適化です。基本的なことは、サブストリングとは関係ありませんが、

s1 = s2;

これで、この最適化の問題は、複数のスレッドをサポートするターゲットで使用されることになっているC ++ライブラリの場合、ターゲットプラットフォームの場合、ストリングの参照カウントにアトミック操作を使用してアクセスする必要がある（またはさらに悪いことに、Mutexで保護されていることです。原子動作を供給しません）。これは十分に高価であるため、ほとんどの場合、単純な非コウストリングの実装がより速くなります。

gotw＃43-45を参照してください：

http://www.gotw.ca/gotw/043.htm

http://www.gotw.ca/gotw/044.htm

http://www.gotw.ca/gotw/045.htm

さらに悪いことに、GNU C ++ライブラリなどの牛を使用したライブラリは、ABIが破壊されるため、単純な実装に戻すことはできません。 （ただし、C ++は救助に0倍、とにかくABIのバンプが必要になるので！:)）

以来 substr 戻り値 std::string, 、プロキシオブジェクトを返す方法はありません。また、リターンタイプやオーバーロードを変更するだけではありません（言及した理由のため）。

彼らはこれを作ることによってこれを行うことができます string それ自体が別の文字列のサブになることができます。これは、すべての使用法に対してメモリペナルティを意味します（追加の文字列と2つのsize_typesを保持するため）。また、すべての操作は、文字があるか、プロキシであるかを確認するためにチェックする必要があります。おそらく、これは実装ポインターで行うことができます。問題は、可能性のあるエッジケースのために汎用クラスを遅くしていることです。

これが必要な場合は、最良の方法は別のクラスを作成することです。 substring, 、文字列、POS、長さから、弦から秘密の構成要素。あなたはそれをとして使用することはできません s1.substr(6), 、しかし、あなたはすることができます 

 substring sub(s1, 6);

また、変換を避けるために、サブストリングと文字列を取る共通操作を作成する必要があります（それが全体であるため）。

あなたの具体的な例に関して、これは私のために働きました：

if (&s1[6] == s2) {
    std::cout << "match!" << std::endl;
}

それは汎用解決策についてあなたの質問に答えないかもしれません。そのためには、@Gmanが示唆するように、サブストリング牛が必要です。

あなたが話しているのは、Java'sのコア機能の1つです（またはそうでした） java.lang.String クラス （http://fishbowl.pastiche.org/2005/04/27/the_string_memory_gotcha/）。多くの点で、Javaのデザイン String クラスとC ++のs basic_string テンプレートは似ているので、の実装を書くことを想像してください basic_string この「サブストリング最適化」を利用するテンプレートが可能です。

あなたが考慮する必要があることの1つは、 c_str() const メンバー。別のサブストリングとしての文字列の場所に応じて、新しいコピーを作成する必要がある場合があります。 C_STRが要求された文字列が後続のサブストリングではない場合、内部配列の新しいコピーを作成する必要があります。これには使用が必要だと思います mutable すべてではないにしても、ほとんどのデータメンバーのキーワード basic_string 実装は、他のものの実装を大幅に複雑にします const メソッドコンパイラは、プログラマーをConst正確性で支援できなくなったためです。

編集： 実際、対応するため c_str() const と data() const, 、タイプの単一の可変フィールドを使用できます const charT*. 。最初に設定されています NULL, 、それはインスタンスごとに、新しいものへのポインターに初期化される可能性があります charT いつでも配列 c_str() const また data() const 呼び出され、で削除されます basic_string 非デストラクタではない場合NULL.

STD :: Stringが提供するよりも多くのパフォーマンスが必要な場合にのみ、必要に応じて機能するものを書いてください。私は以前に文字列のバリエーションを使っていました。

私自身の好みは、コピーオンワイトではなく、マット不可能な文字列を使用し、boost :: shared_ptrまたは同等物を使用することですが、文字列の長さは実際には16を超えている場合にのみ、文字列クラスには短いためのプライベートバッファーもあります。文字列。

これは、文字列クラスに少し重量がある可能性があることを意味します。

また、コレクションリストには、元のオブジェクトの寿命が無傷である限り、他の場所に住んでいるクラスの「サブセット」を見ることができる「スライス」クラスもあります。あなたの場合、私は文字列をスライスしてサブストリングを見ることができました。もちろん、それはヌル終端ではなく、コピーせずにそれを作る方法もありません。そして、それは文字列クラスではありません。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top