c++ - std::string::substrメンバー関数の複雑さは何ですか?

Question

std::string::substrメンバー関数の複雑さは? 標準または実装定義で定義されていますか?

Answer 1

単純な実装は O(k) です。ここで、k は結果の部分文字列の長さです。std::string はコピーオンライトをサポートしていません。O(1) 部分文字列操作が必要な場合は、 Ropeなどのデータ構造を使用します。

Answer 2

C++11 標準はsubstr、21.4.7.8 または私が見つけた他のどこでも、のパフォーマンス特性を定義していません。実際には、結果の長さでほぼ確実にO(n)パフォーマンスを期待できます。n

Answer 3

これは、標準がそれについて言わなければならないすべてです：

n3242、21.4.7.8

1. 必要：pos <= size()
2. スロー: out_of_rangeifpos > size()
3. 効果: コピーする文字列の有効な長さを、とrlenの小さい方として決定します。nsize() - pos
4. 戻り値: basic_string<charT,traits,Allocator>(data()+pos,rlen).

したがって、答えはノーです。複雑さは定義されていません。

編集: n3242 に従って修正、pos > size not pos >= size