文字列の挿入の効率

Question

私は非常に長い整数より大きいこのカスタム追加クラスを作成しようとしています。私が調べているアプローチの1つは、文字列として整数を保持してから、文字をintコンポーネントに変換し、各「列」を追加することです。私が検討している別のアプローチは、長い文字列のサイズである複数の文字列に文字列を分割し、長い文字列ストリームを使用してそれを追加して再結合することです。

私は、数字の持ち越しを可能にするために、逆順で最も簡単に追加が行われたという事実を知りました。これは私が文字列の挿入メソッドの効率を疑問に思っていた場合です。文字列はすべての文字が1つ以上の文字にシフトされなければならない文字の配列であるようです。だからそれは変わるだろうが、効率はO（n）と思われる。ここで、nは文字列中の文字数である。

これは正しいのですか、これは純粋な解釈でのみですか？

編集：今私の質問に答えているが、より効率的な関連トピックについては、ストリングをストリームに挿入してからintに抽出することに不思議に思っていた。または10^n * char1 + 10^n-1 * char2 ...などの処理をしますか？

Answer 1

私が知る限り、あなたは正しいです。 StringのC++実装はO（n）時間に挿入を実行します。文字列を文字配列として扱います。

数値実装では、数値を整数の配列として格納し、出力用に文字列に変換するのはなぜですか？

Answer 2

std::stringの実際の実装ではおそらく正しいでしょう。このような状況では、数字を逆に格納するか（別の方法では不器用かもしれません）、そうでない場合はstd::deque<char>のようなものを使用します。より良いことに、std::deque<unsigned long long>を使用すると、関連する操作の数が減ります。

もちろん、実際に使用するには、独自のライブラリを使用するのではなく、既存のライブラリを使用する必要があります。