一些字符串替換字符串焦炭就地

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()預留足夠的空間。但是請注意，在C++ 11中添加了reserve - 較早的實現不會擁有它。

編輯：雖然不像您使用的字符串那樣擔心，但正如@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

我認爲你misundertand 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); 
    } 
}