c++ - std::string size() は O(1) 操作ですか?

Question

std::string size() は O(1) 操作ですか?

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

score 36 · Accepted Answer

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

「(注 A)」とマークされたエントリは、一定の複雑さを持つ必要があります。

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

size()「注 A」は、コンテナが変更されたときにサイズを維持する必要がないように、線形の複雑さを許可する必要があると信じている人々をなだめるために、特に標準に追加されました。

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

score 8 · Accepted Answer

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) 実装です。

score 7 · Accepted Answer

7

はい、std::string::size() は O(1) です。

于 2008-11-01T20:13:52.957 に答える

score 5 · Accepted Answer

規格のセクション 23.1 の表 65 を参照してください。「a.size()」は「(注 A)」としてリストされており、「これらのエントリは ... 一定の複雑さを持つ必要がある」と述べています。

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

score 5 · Accepted Answer

文字列の場合、ロープ⁽¹⁾を使用しないすべての文字列の実装で、size()操作は一定でなければなりません。標準には、操作がである必要があるという明示的な要件はありません。最も近いのは、一定時間である必要がある一般的な要件ですが、他の複雑さを測定する余地があります。O(1)size()

では、なぜO(1) でなければならないのでしょうか?

これは、文字列自体の内容からはサイズを計算できないことに由来します。C では NUL ターミネータを使用して文字列の末尾を決定しますが、C++ では NUL は文字列内の他の文字と同じように有効です。^{文字列のサイズは内容(2)}から計算できないため、文字列の実際のサイズとは無関係に、外部で処理する必要があります。

⁽¹⁾ C++03 標準では、実装でロープを文字列の実装として使用できますが、実際には、標準ライブラリの現在の実装ではロープを使用していません。

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

score 2 · Accepted Answer

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

score -2 · Accepted Answer

size_type __CLR_OR_THIS_CALL size() const

{   // return length of sequence

    return (_Mysize);

}

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

c++ - std::string size() は O(1) 操作ですか?

8 に答える 8

Related

Reference