Row Insertion Efficiency

Question

I am trying to write this custom add class for very large integers larger than the long one. One approach I'm studying is to save an integer as a string, and then convert the characters to their int components and then add each “column”. Another approach that I am considering is to split a string into several lines, each of which has a length of a long length, and then cast it using a stream stream into a long addition and subsequent recombination.

Regardless of the fact that I came across the fact that the addition was made most easily in the reverse order to ensure the transfer of numbers. In this case, I was interested to know the effectiveness of the insert method for the string. It looks like the string is an array of characters that need to be wrapped to all characters. So that would change, but seemingly the efficiency is O (n), where n is the number of characters in the string.

Is this correct, or is it just with a naive interpretation?

Edit: I now have an answer to my question, but I was interested to know which topic is more efficient by inserting a string into the stream, and then retrieving it in int. Or do 10 ^ n * char1 + 10 ^ n-1 * char2 ... etc.?

Answer 1

As far as I know, you're right. An implementation of String C ++ will perform the insert at O ​​(n) time. It treats the string as an array of characters.

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

Answer 2

This is probably true for all real implementations of std::string . In these circumstances, you may need to either save the numbers in reverse order (although this can be awkward in other ways), or use something like std::deque<char> . Better yet, use 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 folding your own.