In C++, what's the fastest way to replace all occurrences of a substring within a string with another string?

Question

I'm looking for the most efficient (in terms of "fastest") way to replace all occurrences of a substring within a string with another string. All I've came up with so far is:

std::string StringReplaceAll(const std::string &cstSearch, const std::string &cstReplace, const std::string &cstSubject)
{
    if(cstSearch.length() > cstSubject.length() || cstSearch == cstReplace || cstSubject.empty() || cstSearch.empty() || cstSubject.find(cstSearch) == std::string::npos)
    {
        return cstSubject;
    }

    std::ostringstream                                  ossReturn;
    std::string::const_iterator                         ci(cstSubject.cbegin());
    const std::string::const_iterator::difference_type  ciFindSize(std::distance(cstSearch.cbegin(), cstSearch.cend()));

    for(std::string::const_iterator ciNow; (ciNow = std::search(ci, cstSubject.cend(), cstSearch.cbegin(), cstSearch.cend())) != cstSubject.cend(); ci = ciNow)
    {
        std::copy(ci, ciNow, std::ostreambuf_iterator<char> (ossReturn));
        std::copy(cstReplace.cbegin(), cstReplace.cend(), std::ostreambuf_iterator<char> (ossReturn));
        std::advance(ciNow, ciFindSize);
    }

    std::copy(ci, cstSubject.cend(), std::ostreambuf_iterator<char> (ossReturn));

    return ossReturn.str();
}

... and this one is way(!!!) too slow for my needs :-(

Looking forward to learn from you guys!

Answer 1

First, I'd use std::string, rather than std::ostringstream, to build up the results; std::ostringstream is for formatting, and there's no formatting to be done here. Other than that, you've got basically the correct algorithm; using std::search to find where the next replacement should be done. I'd use a while loop to make things a bit more readable, which gives:

std::string
replaceAll( std::string const& original,
            std::string const& before,
            std::string const& after )
{
    std::string retval;
    std::string::const_iterator end     = original.end();
    std::string::const_iterator current = original.begin();
    std::string::const_iterator next    =
            std::search( current, end, before.begin(), before.end() );
    while ( next != end ) {
        retval.append( current, next );
        retval.append( after );
        current = next + before.size();
        next = std::search( current, end, before.begin(), before.end() );
    }
    retval.append( current, next );
    return retval;
}

(Note that using std::string::append will be faster than using std::copy; the string knows how many it must add, and can resize the string accordingly.)

Afterwards, it would be trivial to catch the special case where there is nothing to replace, and return the initial string immediately; there might be some improvements to be had using std::string::reserve as well. (If before and after have the same length, retval.reserve( original.size() ) is a clear win. Even if they don't, it could be a win. As for first counting the number of substitutions, then exactly calculating the final size, I don't know. You'll have to measure with your actual use cases to find out.)