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!
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.)
I asked about this same thing at http://hardforum.com/showthread.php?t=979477 years ago.
I don't remember it all that well, but the following code was in comment #31 and I think it was faster than my other attempts (but not faster than MikeBlas' metered_string example):
#include <iostream>
#include <string>
#include <algorithm>
#include <iterator>
#include <sstream>
using namespace std;
inline string replaceAll(const string& s, const string& f, const string& r) {
if (s.empty() || f.empty() || f == r || f.size() > s.size() || s.find(f) == string::npos) {
return s;
}
ostringstream build_it;
typedef string::const_iterator iter;
iter i(s.begin());
const iter::difference_type f_size(distance(f.begin(), f.end()));
for (iter pos; (pos = search(i , s.end(), f.begin(), f.end())) != s.end(); ) {
copy(i, pos, ostreambuf_iterator<char>(build_it));
copy(r.begin(), r.end(), ostreambuf_iterator<char>(build_it));
advance(pos, f_size);
i = pos;
}
copy(i, s.end(), ostreambuf_iterator<char>(build_it));
return build_it.str();
}
int main() {
const string source(20971520, 'a');
const string test(replaceAll(source, "a", "4"));
}
See the thread for more examples and lots of discussion.
If I remember correctly, it was really easy to make things faster than boost's replace_all.
Here's a clearer c++0x version:
#include <string>
#include <algorithm>
#include <iterator>
#include <sstream>
#include <ostream>
using namespace std;
string replace_all_copy(const string& s, const string& f, const string& r) {
if (s.empty() || f.empty() || f == r || f.size() > s.size()) {
return s;
}
ostringstream buffer;
auto start = s.cbegin();
while (true) {
const auto end = search(start , s.cend(), f.cbegin(), f.cend());
copy(start, end, ostreambuf_iterator<char>(buffer));
if (end == s.cend()) {
break;
}
copy(r.cbegin(), r.cend(), ostreambuf_iterator<char>(buffer));
start = end + f.size();
}
return buffer.str();
}
int main() {
const string s(20971520, 'a');
const string result = replace_all_copy(s, "a", "4");
}
// g++ -Wall -Wextra replace_all_copy.cc -o replace_all_copy -O3 -s -std=c++0x
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With