Replace $number with $number+1 in std::string

Question

I want to detect $number substring in std::string and then replace it with $number + 1.

For example, the string Hello$9World$1 should become Hello$10World$2.

Here's my code:

#include <iostream>
#include <string>

void modifyDollarNumber(std::string &str)
{
    for (size_t i = str.length(); i --> 0 ;)
    {
        if (str[i] == '$')
        {
            size_t j = i + 1;
            while (j < str.length() && isdigit(str[j]))
            {
                ++j;
            }
            size_t len = j - (i + 1);
            if (len)
            {
                std::string sub = str.substr(i + 1, len);
                int num = std::stoi(sub) + 1;
                str.erase(i + 1, len);
                sub = std::to_string(num);
                str.insert(i + 1, sub);
            }
        }
    }
}

int main()
{
    std::string str = "!$@#$34$1%^&$5*$1$!%$91$12@$3";
    modifyDollarNumber(str);
    std::cout << "Result : " << str << '\n';
}

And I can get the result I want which is

Result : !$@#$35$2%^&$6*$2$!%$92$13@$4
Program ended with exit code: 0

But I want to improve my code so it can be as fast as possible.

How can I simplify modifyDollarNumber() function?

Answer 1

Few observations.

I. You don't need to scan the whole string, character-by-character. str.find('$') will do it for you (and remember to start the second search, and all subsequent ones, from the last reference detected.)

II. Rather than taking substrings, parsing them, erasing and inserting—why not increment in-place? You know exactly your number span (from the one past '$' to the one past the last digit.) If this string only consists of '9's, insert a single '1' right after '$' and change all nines into zeroes. If there are digits less than nine, increment the rightmost non-nine, and change all the subsequent nines into zeroes, if any, no insertion/erasure required. Proceed with the next search.

III. As @AJNeufeld mentioned, string reconstruction can be done in a separate buffer, though vast testing is needed to decide if this is a faster option.

Answer 2

You've misspelt std::size_t throughout, and also std::isdigit (which is missing the necessary include of <cctype> - note also that passing plain char to the character classification functions is risky - cast to unsigned char first).

The in-place modification of your string involves copying increasing parts of it multiple times (even when the replacement string is of the same length). You can avoid that quite simply by using std::string::replace() instead of erase()+insert():

            std::string sub = str.substr(i + 1, len);
            int num = std::stoi(sub) + 1;
            str.replace(i + 1, len, std::to_string(num));

This still leaves a lot of copying when the increment adds a digit (9, 99, 999, ...) - I think your test-case should include at least one of each. To avoid that problem (and to make the usage more intuitive to the caller), it may be better to write a function that returns a copy of the string (so accept it by const reference):

#include <algorithm>
#include <cctype>
#include <string>

std::string modifyDollarNumber(const std::string& str)
{
    std::string result;
    result.reserve(str.length());
    auto out = std::back_inserter(result);

    auto pos = str.cbegin();
    while (pos != str.cend()) {
        auto dollar_pos = std::find(pos, str.cend(), '$');
        std::copy(pos, dollar_pos, out);
        // no more substitutions?
        if (dollar_pos == str.cend()) { break; }

        // copy the dollar sign
        result += '$';
        pos = dollar_pos + 1;

        // is it followed by a number?
        auto digit_end = std::find_if(pos, str.end(),
                           [](unsigned char c){ return !std::isdigit(c); });
        if (digit_end == pos) { continue; }

        // copy the incremented number
        auto num = std::stoul(std::string{pos, digit_end});
        result.append(std::to_string(num+1));
        pos = digit_end;
    }

    return result;
}

#include <iostream>
int main()
{
    const std::string str = "$1 $-22 $027 $$ $";
    std::cout << "Result : " << modifyDollarNumber(str) << '\n';
}

But if raw speed is more important than readability, you'll need to benchmark with some representative inputs to see which is best for you.

Answer 3

String manipulation can be slow. Inserting and deleting characters requires shifting characters in memory, if modifying in place, or allocating and freeing temporaries.

It could be faster to allocate one destination character buffer (char[] or wchar_t[]), and copy characters into it, performing the translations as required, and then converting into a std::string at the end.

The destination buffer would need space for str.length() + std::count(str.begin(), str.end(), '$') characters, since $9 can become $10, etc.