Efficiency of insert in string

Question

I'm trying to write this custom addition class for very large integers, bigger than long long. One approach which I'm investigating is keeping the integer as a string and then converting the characters to their int components and then adding each "column". Another approach I'm considering is to split up the string into multiple strings each of which is the size of a long long and then casting it using a string stream into a long long adding and then recombining.

Regardless I came across the fact that addition is done most easily in reverse to allow to the carrying over of digits. This being the case I was wondering the efficiency of the insert method for the string. It seems since a string is an array of chars that all the chars would have to be shifted over one. So it would vary but it would seem the efficiency is O(n) where n is the number of chars in the string.

Is this correct, or is this only with a naive interpretation?

Edit: I now have answer to my question but I was wondering on a related topic which is more efficient, inserting a string into a stream then extracting into an int. Or doing 10^n*char1+10^n-1*char2...etc?

Answer 1

As far as I know, you are correct. The C++ implementation of String will perform an insert in O(n) time. It treats the string as a character array.

For your numeric implementation, why not store the numbers as arrays of integers and convert to string only for output?

Answer 2

It's probably correct with all real implementations of std::string. Under the circumstances, you might want to either store the digits in reverse (though that could be clumsy in other ways) or else use something like an std::deque<char>. Better still, use an std::deque<unsigned long long>, which will reduce the number of operations involved.

Of course, for real use you usually want to use an existing library rather than rolling your own.