Эффективность вставки в строку

Question

Я пытаюсь написать этот пользовательский класс сложения для очень больших целых чисел, длиннее, чем long.Один из подходов, который я исследую, - это сохранить целое число в виде строки, а затем преобразовать символы в их компоненты int, а затем добавить каждый «столбец».Другой подход, который я рассматриваю, состоит в том, чтобы разбить строку на несколько строк, каждая из которых имеет размер long long, и затем преобразовать ее, используя поток строк, в длинное длинное добавление и затем рекомбинировать.

Несмотря на это, я сталкивался с тем фактом, что сложение осуществляется наиболее просто в обратном порядке, чтобы допустить перенос цифр.В таком случае мне было интересно, насколько эффективен метод вставки для строки.Кажется, поскольку строка представляет собой массив символов, все символы должны быть сдвинуты на один.Таким образом, это могло бы измениться, но казалось бы, эффективность - O (n), где n - число символов в строке.

Это правильно, или это только с наивной интерпретацией?

Редактировать: у меня теперь есть ответ на мой вопрос, но мне было интересно по связанной теме, которая более эффективна, вставляя строкув поток, затем извлекается в Int.Или делать 10 ^ n * char1 + 10 ^ n-1 * char2 ... и т.д.?

Answer 1

Насколько я знаю, вы правы.Реализация C ++ для C ++ будет выполнять вставку за O (n) раз.Он обрабатывает строку как массив символов.

Для вашей числовой реализации почему бы не сохранить числа в виде массивов целых чисел и преобразовать их в строку только для вывода?

Answer 2

Вероятно, это правильно для всех реальных реализаций std::string.При таких обстоятельствах вы можете либо сохранить цифры в обратном порядке (хотя это может быть неуклюже в других отношениях), либо использовать что-то вроде std::deque<char>.Более того, используйте std::deque<unsigned long long>, что сократит количество задействованных операций.

Конечно, для реального использования вы обычно хотите использовать существующую библиотеку, а не сворачивать собственную.