Replace char in string with some string inplace

Question

i want to replace a character in the string with a string. can i do it in-place? As the new string has length greater than original string.Question is that can i do with using additional buffer? for example

void replaceChar(std::string &input, std::string replacementString, char charToReplace)
{
//some code here. No additional buffer
}

void main(){

  std::string input = "I am posting a comment on LinkedIn";
  std::string replacementString = "pppp";
  char charToReplace = 'o';
  replaceChar(input, replacementString, charToReplace);
}

I only want the strategy (algorithm). it would be good if algorithm will be designed keeping some language in mind that will not dynamically increase or decrease the string length once it was initilized like c++

Solution 1

std::string has a replace member, but it works in terms of numerical positions, rather than the previous content of the string. As such, you normally have to combine it with the find member in a loop, something like this:

std::string old("o");

int pos;

while ((pos = x.find(old)) != std::string::npos)
    x.replace(pos, old.length(), "pppp");

Personally, I'd rarely get concerned about how often the string gets resized, but if it's a major concern, you can use std::count to find the number of occurrences of the old string, multiply by the difference in size between the old and new strings, and use std::string::reserve() to reserve enough space. Note, however, that reserve was added in C++11 -- older implementations won't have it.

Edit: though it's not a concern with the strings you used, as @ipc pointed out, this doesn't work correctly if the replacement string contains an instance of the value being replaced. If you need to deal with that, you'll need to supply the offset in the string at which to start each search:

int pos = 0;

while ((pos = x.find(old, pos)) != std::string::npos) {
    x.replace(pos, old.length(), rep);
    pos += rep.length();
}

Or, you might prefer a for loop in this case:

    std::string old("o");
    std::string rep("pop");

for (int pos=0; 
    (pos = x.find(old, pos)) != std::string::npos; 
    pos+=rep.length())
{
    x.replace(pos, old.length(), rep);
}

Solution 2

I think you misundertand C++ std::string. It can actually change the string length dynamically. In internally does heap allocations, and will grow the buffer if necessary.

Solution 3

Here is a code that minimises the number of assignments and allocations. It is based on the following answer to a similar question: https://stackoverflow.com/a/32322122/3903076

The cases where the replacement string has length 0 or 1 are handled separately. Else, the string has to grow.

If there is not enough capacity, then an external buffer will be necessary anyway, so we just do copy-replace and swap.

The interesting case is when the string already has enough capacity, so we can actually do a non-trivial in-place replacement. We do that with a reverse copy-replace, stopping when we do not need to replace anything else.

This can be seen in the last line of the function.

void replaceChar(std::string& input, const std::string& replacementString, char charToReplace)
{
  if (replacementString.empty()) {
    input.erase(std::remove(input.begin(), input.end(), charToReplace), input.end());
    return;
  }
  if (replacementString.size() == 1) {
    std::replace(input.begin(), input.end(), charToReplace, replacementString.front());
    return;
  }

  const auto first_instance = std::find(input.begin(), input.end(), charToReplace);
  auto count = std::count(first_instance, input.end(), charToReplace);
  const auto extra_size = count * (replacementString.size() - 1);
  const auto new_size = input.size() + extra_size;

  if (input.capacity() < new_size) {
    std::string aux;
    aux.reserve(new_size);
    replace_with_range_copy(input.cbegin(), input.cend(), std::back_inserter(aux), charToReplace, replacementString.cbegin(), replacementString.cend());
    input.swap(aux);
    return;
  }

  input.resize(new_size);

  const auto rlast = std::make_reverse_iterator(first_instance);
  const auto rfirst = input.rbegin();
  const auto old_rfirst = rfirst + extra_size;

  replace_with_range_copy(old_rfirst, rlast, rfirst, charToReplace, replacementString.crbegin(), replacementString.crend());
}

Here is an implementation of the replace_with_range_copy algorithm:

template <typename InputIt1, typename OutputIt, typename T, typename InputIt2>
OutputIt replace_with_range_copy(InputIt1 first, InputIt1 last, OutputIt d_first, const T& old_value, InputIt2 new_first, InputIt2 new_last)
{
  InputIt1 next;
  while (true) {
    if (first == last) return d_first;
    next = std::find(first, last, old_value);
    d_first = std::copy(first, next, d_first);
    if (next == last) return d_first;
    d_first = std::copy(new_first, new_last, d_first);
    first = std::next(next);
  }
}

Comments

[ipc]

If the replacement string contains an 'o', this will an endless loop.

[Jerry Coffin]

@ipc: good point. I've added some commentary/code for dealing with that.

[Steven Lu]

Nit: pos should be a size_t.