std :: string size（）はO（1）操作ですか？

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

  •  05-07-2019
  •  | 
  •  

質問

std :: string size（）はO（1）操作ですか？

使用しているSTLの実装は、VC ++に組み込まれているものです

役に立ちましたか？

解決

MSVCのstring :: size（）の実装が一定の複雑さを持っているかどうかを尋ねている場合、答えはイエスです。しかし、 Don Wakefield は、C ++標準の23.1で表65について言及しています。 size（）の複雑さは、「注A」に記載されている内容に従う必要があると述べています。注Aのコメント：

  

＆＃8216;＆＃8216;（注A）＆＃8217;＆＃8217;とマークされたエントリ   一定の複雑さが必要です。

ただし、それは、これらのエントリが一定の複雑さを持つことを意味するものではありません。標準では非常に具体的な用語が使用されており、「あるべき」です。必須ではないことを意味します。

'Note A'は、特に size（）に線形の複雑さを持たせるべきだと考えている人たちをなだめるために標準に追加されました。変更。

したがって、一定の複雑さを持つ size（）に頼ることはできませんが、定数 string :: size（を持たない実装があるかどうかは正直わかりません）。

他のヒント

msvc ++の質問に答える簡単な方法を次に示します。

プロジェクトでコードを書く：

string happy;
happy.size();

.size呼び出しを強調表示し、右クリックして定義に移動します。

私のインストール（vs2005sp1）で、これはxstring：1635に送られます。これは次のようになります。

size_type __CLR_OR_THIS_CALL size() const
    {   // return length of sequence
    return (_Mysize);
    }

そのため、文字列には_Mysizeという名前のメンバーが含まれているように見えますが、それを返すだけです。

つまり、これはO（1）実装です。

はい、std :: string :: size（）はO（1）です。

規格のセクション23.1の表65を参照してください。 ＆quot; a.size（）＆quot; ＆quot;（注A）＆quot;としてリストされています。これは、「これらのエントリ...は一定の複雑さを持たなければならない」と述べています。

セクション21.3では、文字列はシーケンス（23.1）の要件に準拠していると述べています。事実上、size（）は一定時間です。

文字列の場合、 ropes を使用しないすべての文字列実装に対して、 size（）操作 が一定である必要があります（1）。オペレーションに O（1）を要求する明示的な要件はありません。最も近いのは、 size（） すべきという一般的な要件です。 >一定の時間であるが、他の複雑さの尺度の余地がある。

では、なぜO（1）にする必要があるのでしょうか？

これは、文字列自体の内容からサイズを計算できないという事実に由来しています。 CではNULターミネータを使用して文字列の終わりを判別しますが、C ++ではNULは文字列内の他の文字と同様に有効です。文字列のサイズはコンテンツからは計算できないため（2）、文字列の実際のサイズとは無関係に外部で処理する必要があります。

（1） C ++ 03標準では、実装は文字列の実装として ropes を使用できますが、実際には、標準の現在の実装はどれもありませんライブラリはそれらを使用します。

（2）実装がロープを使用する場合、ブロックがリンクリストまたは同様のリンクを介してリンクされている場合、操作はロープが構築されたブロックの数によってサイズに依存する可能性がありますコンストラクト、またはサイズが異なることが許可されている場合。しかし、 ropes は、私が知っている標準ライブラリの実装では使用されていません。

コンテナのパフォーマンスはSTLによって少なくともO（N）であることが保証されていますが、std :: stringを含む多くのコンテナはこれをO（1）として実装できます。通常、単純な変数を返すか、_End-_Beginのようなことをして、それを返します。

size_type __CLR_OR_THIS_CALL size() const

{   // return length of sequence

    return (_Mysize);

}

したがって、最終的にはこのようになる可能性がありますが、確実ではありません。

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