より形式的にはstr、問題の文字列を 、その長さを とするl。substr上記は、次の関数を使用して簡単に実現できることを認識しています。
str.substr(1) str.substr(0,l-1)しかし、このページによると、上記の方法はO(l).
で同じことを達成する方法はありO(1)ますか?
編集：この質問を重複としてマークする前に、文字列の終端文字を削除するためにO(1)実装を求めていることに注意してください。これが重複しているように見える質問への回答はどれも、明らかにその質問がそれを求めていないため、これに答える努力をしていません。
これを実際に保証している標準については知りませんが、以下の複雑さを想定するのは合理的です。
str.resize(str.length() - 1);
O(1) です。仮定があなたの場合に十分でない場合は、独自の文字列クラスを作成できます。適切な文字列クラスを作成するために費やす労力が、最後の文字を削除するための O(1) 保証に見合うだけの価値があることを確認してください。
関数はsubstr文字を削除しません。その関数を呼び出す文字列は変更されないため、すべての文字はそのまま残ります。それにもかかわらず、終端文字以外のすべてを含む部分文字列を選択するためにそれを呼び出すのに必要な時間は、他のすべての文字のコピーを作成する必要があるため、 O( n ) になります。
文字列から文字を削除するのに必要な時間は、削除された文字を置き換えるために後続のすべての文字をシフトすることsubstrです。通常、文字列にはn 個の文字があるため、任意の文字を削除する複雑さは O( n ) です。
任意の長さの文字列の最初の文字を一定時間削除する方法はありません。文字列の末尾から固定文字数Cの文字を削除するのは一定時間で実行できるため、最後の文字 ( C = 0) を削除すると O(1) になります。
シーケンスの終端に要素を頻繁に追加または削除する必要がある場合は、その操作により適したデータ構造を検討することができます。listとの両方dequeが適しています。
std::stringO(1) 時間で a の最後の文字を削除するには、
resize弦を1単位下げるだけです。
代わりに式の結果が必要な場合 (元の文字列を変更するのではなく)、 以外のクラスを使用する必要がありますstd::string。イテレータのペアでうまくいきます。