110

How do I replace all occurrences of a substring with another string, for std::strings?

std::string s ("One hello, two hellos."); s = s.replace("hello", "world"); // something like this
Improve this question
1

11 Answers 11

Reset to default
171

Using boost::replace_all:

#include <boost/algorithm/string.hpp> // include Boost, a C++ library ... std::string target("Would you like a foo of chocolate. Two foos of chocolate?"); boost::replace_all(target, "foo", "bar");
Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Note that you don't have to explicitly create std::string's for the pattern and replacement: boost::replace_all(target, "foo", "bar");
+1, with a caveat: replace_all will segfault for versions of boost > 1.43 on Sun Studio for any version < 12.3
See this answer for a fast non-boost implementation of replace_all.
81

Why not implement your own replace?

void myReplace(std::string& str, const std::string& oldStr, const std::string& newStr) { std::string::size_type pos = 0u; while((pos = str.find(oldStr, pos)) != std::string::npos){ str.replace(pos, oldStr.length(), newStr); pos += newStr.length(); } }
Improve this answer

5 Comments

You are messing a bit with memory here with all the calls to "replace" : complexity would be n² if you remove "o" from "ooooooo...o". I guess one can do better, but this solution has the merit of being easy to understand.
Why is this not an actual for loop, rather than an obfuscated for loop?
I am used to apply the 'least surprise' principle. For loops are for simple index increment use, most of time. Here, according to me, a while loop is clearer.
@aldo As a general rule it is better to avoid complexity and, for instance, use regex as mentioned in other replies. But depending on your need you may want to control your project dependencies. A little code snippet that does what exactly you need, no more, is sometimes better.
This is O(n^2). For O(n), one should avoid using replace repeatedly. See this implementation, for example.
45

In C++11, you can do this as a one-liner with a call to regex_replace:

#include <string> #include <regex> using std::string; string do_replace( string const & in, string const & from, string const & to ) { return std::regex_replace( in, std::regex(from), to ); } string test = "Remove all spaces"; std::cout << do_replace(test, " ", "") << std::endl;

output:

Removeallspaces
Improve this answer

4 Comments

Notice also that from can be a regular expression -- so you can use more sophisticated matching criteria if you need to. What I don't see, is how to do this without applying some form of regular expression parsing -- instead using only a direct interpretation of the from characters.
@nobar, yeah, if I remember properly the regex support in 4.8.x was not complete. Also you can have more sophisticated searches, but you get penalized time wise... It's going to be slower than the other more straight forward search and replace functions.
Please note that this will work only for very basic alphanumeric characters and nothing else without doing a lot of preprocessing depending on the type of string. I haven't found a general purpose regex based string replace yet.
I think that it makes sense to note that it's probably going to be much slower than simple string manipulation such as boost::replace_all.
19

Why not return a modified string?

std::string ReplaceString(std::string subject, const std::string& search, const std::string& replace) { size_t pos = 0; while((pos = subject.find(search, pos)) != std::string::npos) { subject.replace(pos, search.length(), replace); pos += replace.length(); } return subject; }

If you need performance, here is an optimized function that modifies the input string, it does not create a copy of the string:

void ReplaceStringInPlace(std::string& subject, const std::string& search, const std::string& replace) { size_t pos = 0; while((pos = subject.find(search, pos)) != std::string::npos) { subject.replace(pos, search.length(), replace); pos += replace.length(); } }

Tests:

std::string input = "abc abc def"; std::cout << "Input string: " << input << std::endl; std::cout << "ReplaceString() return value: " << ReplaceString(input, "bc", "!!") << std::endl; std::cout << "ReplaceString() input string not changed: " << input << std::endl; ReplaceStringInPlace(input, "bc", "??"); std::cout << "ReplaceStringInPlace() input string modified: " << input << std::endl;

Output:

Input string: abc abc def ReplaceString() return value: a!! a!! def ReplaceString() input string not modified: abc abc def ReplaceStringInPlace() input string modified: a?? a?? def
Improve this answer

1 Comment

Your inplace version actually doing unnecessary work if there are more than one string to replace. Imagine replacing long string by a short one. Replace will have to shift rest of the string on every found entry. That is both bad for cache and unnecessary.
6

My templatized inline in-place find-and-replace:

template<class T> int inline findAndReplace(T& source, const T& find, const T& replace) { int num=0; typename T::size_t fLen = find.size(); typename T::size_t rLen = replace.size(); for (T::size_t pos=0; (pos=source.find(find, pos))!=T::npos; pos+=rLen) { num++; source.replace(pos, fLen, replace); } return num; }

It returns a count of the number of items substituted (for use if you want to successively run this, etc). To use it:

std::string str = "one two three"; int n = findAndReplace(str, "one", "1");
Improve this answer

1 Comment

I tried this sample under GCC but it wouldn't compile - it didn't like the use of T::size_t. Replacing T::size_t with typename T::size_type fixes the problem.
5

Performant O(n) replace all

Many other answers repeatedly call std::string::replace, which requires the string to be overwritten repeatedly, which results in poor performance. In contrast, this uses a std::string buffer so that each character of the string is only traversed once:

void replace_all( std::string& s, std::string const& toReplace, std::string const& replaceWith ) { std::string buf; std::size_t pos = 0; std::size_t prevPos; // Reserves rough estimate of final size of string. buf.reserve(s.size()); while (true) { prevPos = pos; pos = s.find(toReplace, pos); if (pos == std::string::npos) break; buf.append(s, prevPos, pos - prevPos); buf += replaceWith; pos += toReplace.size(); } buf.append(s, prevPos, s.size() - prevPos); s.swap(buf); }

Usage:

replace_all(s, "text to replace", "new text");

Full example:

#include <iostream> void replace_all( std::string& s, std::string const& toReplace, std::string const& replaceWith ) { std::string buf; std::size_t pos = 0; std::size_t prevPos; // Reserves rough estimate of final size of string. buf.reserve(s.size()); while (true) { prevPos = pos; pos = s.find(toReplace, pos); if (pos == std::string::npos) break; buf.append(s, prevPos, pos - prevPos); buf += replaceWith; pos += toReplace.size(); } buf.append(s, prevPos, s.size() - prevPos); s.swap(buf); } int main() { std::string s("hello hello, mademoiselle!"); replace_all(s, "hello", "bye"); std::cout << s << std::endl; }

Output:

bye bye, mademoiselle!

Note: Previous versions of this answer used std::ostringstream, which has some overhead. The latest version uses std::string::append instead, as recommended by @LouisGo.

Improve this answer

2 Comments

Note that even it's O(n) while using stringstream, it might be still comparably slow than string operation while the size of string is ~600 characters. Refer to my naive profiling;
Note that even it's O(n) while using stringstream, it might be still comparably slow than string operation while the size of string is ~600 characters. benchmark. I'll suggest to use std::string::append
3

The easiest way (offering something near what you wrote) is to use Boost.Regex, specifically regex_replace.

std::string has built in find() and replace() methods, but they are more cumbersome to work with as they require dealing with indices and string lengths.

Improve this answer

1 Comment

There are also the boost string algorithms, including replace_all (regex might be a bit heavy-weight for such simple substitution).
3

I believe this would work. It takes const char*'s as a parameter.

//params find and replace cannot be NULL void FindAndReplace( std::string& source, const char* find, const char* replace ) { //ASSERT(find != NULL); //ASSERT(replace != NULL); size_t findLen = strlen(find); size_t replaceLen = strlen(replace); size_t pos = 0; //search for the next occurrence of find within source while ((pos = source.find(find, pos)) != std::string::npos) { //replace the found string with the replacement source.replace( pos, findLen, replace ); //the next line keeps you from searching your replace string, //so your could replace "hello" with "hello world" //and not have it blow chunks. pos += replaceLen; } }
Improve this answer

7 Comments

Given that size_type for a string is unsigned, your >= check in the loop condition will always be true. You have to use std::string::npos there.
size_type is not unsigned. It's unsigned on many platforms, but not all.
Why in the world is this not part of std::string? Is there any other serious String class in the world of programming that does not offer a 'find and replace' operation? Surely it's more common than having two iterators and wanting to replace the text between them?? Sometimes std::string feels like a car with a tunable spectrum windshield but no way to roll down the driver's window.
@Spike0xff boost has roll_down_window
@gustafr: My mistake. I've worked on systems where older compilers defined size_t improperly.
|
3 
#include <string> using std::string; void myReplace(string& str, const string& oldStr, const string& newStr) { if (oldStr.empty()) { return; } for (size_t pos = 0; (pos = str.find(oldStr, pos)) != string::npos;) { str.replace(pos, oldStr.length(), newStr); pos += newStr.length(); } }

The check for oldStr being empty is important. If for whatever reason that parameter is empty you will get stuck in an infinite loop.

But yeah use the tried and tested C++11 or Boost solution if you can.

Improve this answer

Comments

1 
// Replace all occurrences of searchStr in str with replacer // Each match is replaced only once to prevent an infinite loop // The algorithm iterates once over the input and only concatenates // to the output, so it should be reasonably efficient std::string replace(const std::string& str, const std::string& searchStr, const std::string& replacer) { // Prevent an infinite loop if the input is empty if (searchStr == "") { return str; } std::string result = ""; size_t pos = 0; size_t pos2 = str.find(searchStr, pos); while (pos2 != std::string::npos) { result += str.substr(pos, pos2-pos) + replacer; pos = pos2 + searchStr.length(); pos2 = str.find(searchStr, pos); } result += str.substr(pos, str.length()-pos); return result; }
Improve this answer

1 Comment

We only need to search for new matches from the last match, that's why the algorithm carefully tracks the last match in pos. pos2 always stores the next match, so we concatenate the string between pos and pos2 to the result, then advance pos and pos2. If no other match can be found, we concatenate the remainder of the string to result.
0

Here is my pure C++ Standard Library replace_all implementation with the focus on best performance as possible. Maximum 1 reallocation can be made when necessary. The code is well commented.

/// /// string replace all pattern occurences with replacement /// returns number of performed replaces /// assert() may be replaced with any kind of error reporting /// may be easy changed to pure C implementation /// NOTE: result of string_replace_all("xxx", "xx", "XX") is undefined, may ends with: "XXx" or "xXX" (for #2b) /// size_t string_replace_all(std::string& s, const char* pattern, size_t pattern_len, const char* replacewith, size_t replacewith_len) { if (s.empty()) return 0; // no space to search if (pattern_len == 0) return 0; // nothing to find // sanity checks: assert(pattern != nullptr); if (replacewith_len != 0) assert(replacewith != nullptr); size_t l = s.size(), founds = 0; // string size, number of performed replaces const char* const pattern_end = pattern + pattern_len; char* it2, *it = &s.front(); // ,processed string first character char* dst, *end = it + l; // ,end of processed string // I hope nobody has a such idea, but of course... assert(pattern_end <= it || pattern >= end); // ...pattern can't be the part of the string if (replacewith_len != 0) assert(replacewith + replacewith_len <= it || replacewith >= end); // ...replacewith can't be the part of the string if (replacewith_len > pattern_len) { // #1 possible growing: // 1st pass - compute grow size: while ((it = std::search(it, end, pattern, pattern_end)) != end) { it += pattern_len; ++founds; } if (founds == 0) return 0; size_t osz = l, nsz = l + founds * (replacewith_len - pattern_len); // old size, compute new size // 2nd pass: if (nsz > s.capacity()) { // #1a realloaction needed std::string s2; // it's better to allocate new string and just write from the beginging s2.reserve(nsz); // allocate enough memory it = &s.front(); // rewind 'it' (as source) it2 = std::search(it, end, pattern, pattern_end); assert(it2 != end); // first found must exists do { s2.append(it, it2 - it); // append [it, it2) unchanged s2.append(replacewith, replacewith_len); // append replacement in the pattern place it = it2 + pattern_len; // jump over found pattern } while ((it2 = std::search(it, end, pattern, pattern_end)) != end); s2.append(it, end - it); // extend with fragment after last found assert(s2.size() == nsz); // to make sure std::swap(s, s2); // s2 becomes s and original s will be free } else { // #1b no reallocation needed: s.resize(nsz); // extending size with null bytes - should not reallocate end = &s.front() + nsz; // expected string end after 2nd pass char* oend = &s.front() + osz; // old end / real current string end it = std::find_end(&s.front(), oend, pattern, pattern_end); assert(it != oend); // first found must exists do { // first move following (after pattern) fragment to the right: char* b = it + pattern_len; // fragment begin l = oend - b; // fragment length end -= l; // moving destination std::char_traits<char>::move(end, b, l); // move right: b -> end // then insert replacement: end -= replacewith_len; std::char_traits<char>::copy(end, replacewith, replacewith_len); oend = it; } while ((it = std::find_end(&s.front(), oend, pattern, pattern_end)) != oend); } } else if (replacewith_len < pattern_len) { // #2 possible shrinking: it = std::search(it, end, pattern, pattern_end); if (it == end) return 0; std::char_traits<char>::copy(it, replacewith, replacewith_len); // paste replacement on the first pattern found dst = it + replacewith_len; // destination of the following fragments it += pattern_len; // continue from pattern end ++founds; while ((it2 = std::search(it, end, pattern, pattern_end)) != end) { // first move preceding (before this and after previous) pattern to the dest: l = it2 - it; std::char_traits<char>::move(dst, it, l); // move left: dst <- it dst += l; // then insert replacement: std::char_traits<char>::copy(dst, replacewith, replacewith_len); dst += replacewith_len; it = it2 + pattern_len; // continue from pattern end ++founds; } l = end - it; std::char_traits<char>::move(dst, it, l); // move fragment after last pattern dst += l; s.resize(dst - &s.front()); // update string size (to lower) } else { // #3 - replacing without size affection: // detect: pattern == replacewith if (std::char_traits<char>::compare(pattern, replacewith, pattern_len) == 0) return 0; // perform simple replacing: while ((it = std::search(it, end, pattern, pattern_end)) != end) { std::char_traits<char>::copy(it, replacewith, replacewith_len); it += replacewith_len; ++founds; } } return founds; } // std::string arguments overload inline size_t string_replace_all(std::string& s, const std::string& pattern, const std::string& replacewith) { return string_replace_all(s, pattern.data(), pattern.size(), replacewith.data(), replacewith.size()); } // null termiated arguments overload inline size_t string_replace_all(std::string& s, const char* pattern, const char* replacewith) { assert(pattern != nullptr); return string_replace_all(s, pattern, std::strlen(pattern), replacewith, (replacewith != nullptr) ? std::strlen(replacewith) : 0); }

Tests

void make_test(const char* str, const char* p, const char* r, const char* expect, std::string& target) { target = str; size_t c = string_replace_all(target, p, r); std::printf("string_replace_all('%s', '%s', '%s') => %i '%s' %s\n", str, p, r, (int)c, target.c_str(), target == expect ? "OK" : "FAIL!"); } void make_test(const char* str, const char* p, const char* r, const char* expect) { std::string target; make_test(str, p, r, expect, target); } int main() { std::string reserved; reserved.reserve(128); make_test("abc", "x", "XX", "abc"); // #1 not found make_test("abc", "x", "", "abc"); // #2 not found make_test("abc", "x", "X", "abc"); // #3 not found make_test("axbcxdxxefxgxh", "x", "XXXX", "aXXXXbcXXXXdXXXXXXXXefXXXXgXXXXh"); // #1a middle make_test("xaxbcdxefxgxhx", "x", "XXXX", "XXXXaXXXXbcdXXXXefXXXXgXXXXhXXXX"); // #1a edges make_test("abxdxefgxhixj", "x", "XX", "abXXdXXefgXXhiXXj", reserved); // #1b middle make_test("xxabxxcdxexfx", "x", "XX", "XXXXabXXXXcdXXeXXfXX", reserved); // #1b edges make_test("abxxdexxxxgh", "xx", "X", "abXdeXXgh"); // #2 middle make_test("xxabxxxxcdxxefxx", "xx", "X", "XabXXcdXefX"); // #2 edges make_test("abxxxcdxexf", "x", nullptr, "abcdef"); // #2 middle remove make_test("xxabxxxcdxefxx", "x", nullptr, "abcdef"); // #2 edges remove make_test("xxxxxxxxxxxxxxx", "x", nullptr, ""); // #2 remove all make_test("abxxcxdexxxxf", "xx", "XX", "abXXcxdeXXXXf"); // #3 middle make_test("xxabxxxcxxxxx", "xx", "XX", "XXabXXxcXXXXx"); // #3 edges make_test("abxxcd", "x", "x", "abxxcd"); // #3 equals }

Output:

string_replace_all('abc', 'x', 'XX') => 0 'abc' OK string_replace_all('abc', 'x', '') => 0 'abc' OK string_replace_all('abc', 'x', 'X') => 0 'abc' OK string_replace_all('axbcxdxxefxgxh', 'x', 'XXXX') => 6 'aXXXXbcXXXXdXXXXXXXXefXXXXgXXXXh' OK string_replace_all('xaxbcdxefxgxhx', 'x', 'XXXX') => 6 'XXXXaXXXXbcdXXXXefXXXXgXXXXhXXXX' OK string_replace_all('abxdxefgxhixj', 'x', 'XX') => 4 'abXXdXXefgXXhiXXj' OK string_replace_all('xxabxxcdxexfx', 'x', 'XX') => 7 'XXXXabXXXXcdXXeXXfXX' OK string_replace_all('abxxdexxxxgh', 'xx', 'X') => 3 'abXdeXXgh' OK string_replace_all('xxabxxxxcdxxefxx', 'xx', 'X') => 5 'XabXXcdXefX' OK string_replace_all('abxxxcdxexf', 'x', '(null)') => 5 'abcdef' OK string_replace_all('xxabxxxcdxefxx', 'x', '(null)') => 8 'abcdef' OK string_replace_all('xxxxxxxxxxxxxxx', 'x', '(null)') => 15 '' OK string_replace_all('abxxcxdexxxxf', 'xx', 'XX') => 3 'abXXcxdeXXXXf' OK string_replace_all('xxabxxxcxxxxx', 'xx', 'XX') => 4 'XXabXXxcXXXXx' OK string_replace_all('abxxcd', 'x', 'x') => 0 'abxxcd' OK
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.