One more option is to do this using a simple for loop:

for (size_t pos = str.find(search); pos != std::string::npos; 
     pos = str.find(search, pos + replacement.length())) {
    str.replace(pos, search.length(), replacement);
}