Заменить символ в строке с некоторой строкой inplace

Question

Я хочу заменить символ в строке строкой. могу ли я сделать это на месте? Поскольку новая строка имеет длину больше исходной строки. Вопрос: что я могу сделать с использованием дополнительного буфера? , например

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); 
} 

Я только хочу стратегию (алгоритм). было бы хорошо, если бы алгоритм был разработан с учетом некоторого языка, который не будет динамически увеличивать или уменьшать длину строки после ее инициализации, например, C++.

Answer 1

std::string имеет член replace, но он работает с точки зрения численных позиций, а не предыдущего содержимого строки. Таким образом, вы обычно должны объединить его с find элементом в петле, что-то вроде этого:

std::string old("o"); 

int pos; 

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

Лично я редко получаю обеспокоены тем, как часто строка получает изменения размера, но если это вызывает серьезную озабоченность , вы можете использовать std::count, чтобы найти количество вхождений строки old, умножить на разницу в размере между старой и новой строками и использовать std::string::reserve() для резервирования достаточно места. Обратите внимание, однако, что reserve был добавлен в C++ 11 - у старых реализаций его не будет.

Редактирование: хотя это не касается строк, которые вы использовали, как указывал @ipc, это не работает правильно, если строка замены содержит экземпляр заменяемого значения. Если вам придется иметь дело с этим, вам нужно поставить смещение в строке, с которой начинается каждый поиск:

int pos = 0; 

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

Или, вы можете предпочесть for цикл в этом случае:

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); 
} 

Answer 2

Я думаю, что вы неправильно поняли C++ std :: string. Это может фактически изменить длину строки динамически. Внутренне выделяет кучи и при необходимости вырастет буфер.

Answer 3

Вот код, который минимизирует количество назначений и распределений. Он основан на следующем ответе на аналогичный вопрос: https://stackoverflow.com/a/32322122/3903076

Случаи, в которых заменяющая строка имеет длину 0 или 1, обрабатываются отдельно. Иначе, строка должна расти.

Если емкости недостаточно, тогда во всех случаях потребуется внешний буфер, поэтому мы просто заменим и заменим копии.

Интересный случай, когда строка уже имеет достаточную емкость, поэтому мы можем фактически сделать нетривиальную замену на месте. Мы делаем это с обратной копией-заменой, останавливаясь, когда нам не нужно ничего заменять.

Это видно в последней строке функции.

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()); 
} 

Вот реализация алгоритма replace_with_range_copy:

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); 
    } 
}