7

の実装を考えていたところですstd::string::substr。それは新しいオブジェクトを返しますがstd::string、これは私には少し無駄に思えます。元の文字列の内容を参照し、暗黙的に に代入できるオブジェクトを返さないのはなぜstd::stringですか? 実際のコピーの一種の怠惰な評価。このようなクラスは次のようになります。

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次に、を受け取る新しいコンストラクターを持つことができる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、ライブラリ作成者がメンバーのプロトタイプを戻り値の型に変更することは標準に準拠していますか? または、より一般的には、ライブラリの作成者は、これらのタイプのケースで、最適化として通常のオブジェクトの代わりに「プロキシ オブジェクト」を返す余裕がありますか?

私の直感では、これは許可されておらず、プロトタイプは正確に一致する必要があります。戻り値の型だけでオーバーロードできないことを考えると、ライブラリの作成者がこれらのタイプの状況を利用する余地はありません。私が言ったように、答えはノーだと思いますが、私は尋ねると思いました:-)。

4

6 に答える 6

6

この考え方はcopy-on-writeですが、バッファー全体を COW する代わりに、バッファーのどのサブセットが「実際の」文字列であるかを追跡します。(通常の形式の COW は、一部のライブラリ実装で使用されていました (使用されていますか?)。)

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

オペレーションがバッファを変更するときはいつでも、独自のコピーを作成し (開始デリミタと終了デリミタから)、古いバッファの参照カウントを 1 減らし、新しいバッファの参照カウントを 1 に設定します。残りの参照カウント規則は同じです: コピーしてカウントを 1 増やす、文字列を破棄してカウントを 1 減らす、ゼロに到達して削除する、など。

substr明示的に指定された開始区切り文字と終了区切り文字を除いて、新しい文字列インスタンスを作成するだけです。

于 2011-01-13T16:49:18.683 に答える
3

これは、コピー オン ライトまたは COW と呼ばれる、比較的広く使用されている非常によく知られた最適化です。基本的なことは、部分文字列とは関係ありませんが、次のような単純なものです。

s1 = s2;

この最適化の問題は、複数のスレッドをサポートするターゲットで使用されることになっている C++ ライブラリの場合、アトミック操作を使用して文字列の参照カウントにアクセスする必要があることです (さらに悪いことに、ターゲット プラットフォームの場合はミューテックスで保護されます)。アトミック操作は提供しません)。これは十分にコストがかかるため、ほとんどの場合、単純な非 COW 文字列の実装の方が高速です。

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++ ライブラリなどの COW を使用したライブラリは、ABI を壊してしまうため、単純な実装に単純に戻すことはできません。(ただし、とにかく ABI バンプが必要になるため、C++0x が助けになります! :))

于 2011-01-13T17:01:19.050 に答える
1

return以来、プロキシオブジェクトをsubstr返すstd::string方法はなく、戻り値の型やオーバーロードを変更することはできません(あなたが言及した理由により)。

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

これが必要な場合、最善の方法はsubstring、文字列、位置、および長さから構成し、文字列に変換する別のクラス を作成することです。として使用することはできませんs1.substr(6)が、行うことはできます

 substring sub(s1, 6);

また、変換を回避するために、部分文字列と文字列を取る一般的な操作を作成する必要があります (それが全体のポイントであるため)。

于 2011-01-13T16:49:56.863 に答える
0

あなたが話しているのは、Javaのjava.lang.Stringクラス(http://fishbowl.pastiche.org/2005/04/27/the_string_memory_gotcha/ )のコア機能の1つです(またはそうでした)。String多くの点で、JavaのクラスとC ++のテンプレートの設計は似ているので、この「部分文字列の最適化」を利用basic_stringしてテンプレートの実装を作成することは可能だと思います。basic_string

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

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

于 2011-01-13T17:06:26.903 に答える
0

std::string が提供する以上のパフォーマンスが本当に必要な場合にのみ、必要な方法で動作するものを作成してください。以前に文字列のバリアントを扱ったことがあります。

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

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

コレクション リストには、元のオブジェクトの有効期間が無傷である限り、別の場所に存在するクラスの「サブセット」を参照できる「スライス」クラスもあります。したがって、あなたの場合、文字列をスライスして部分文字列を表示できます。もちろん、null で終了することはありません。また、コピーせずに null で終了する方法もありません。また、文字列クラスではありません。

于 2011-01-13T17:39:18.360 に答える
0

あなたの特定の例に関して、これは私にとってはうまくいきました:

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

汎用ソリューションについての質問には答えられない場合があります。そのためには、@GMan が示唆するように、部分文字列 CoW が必要です。

于 2011-01-13T16:59:46.420 に答える