¿Cómo puedo implementar un reemplazo de cadena de palabra completa eficiente en C++ sin expresiones regulares?

Question

Tal vez estoy pasando por alto algo obvio, pero me preguntaba cuál sería la forma más rápida de implementar el reemplazo de cadenas enteras en C++. Al principio consideré simplemente concatenar espacios a la palabra de búsqueda, pero esto no considera los límites de la cadena o la puntuación.

Ésta es mi abstracción actual de reemplazo (no de palabras completas):

void Replace(wstring& input, wstring find, wstring replace_with) { 
    if (find.empty() || find == replace_with || input.length() < find.length()) { 
     return; 
    } 
    for (size_t pos = input.find(find); 
       pos != wstring::npos; 
       pos = input.find(find, pos)) { 

     input.replace(pos, find.length(), replace_with); 
     pos += replace_with.length(); 
    } 
} 

Si sólo se consideran espacios como un límite de la palabra, probablemente podría aplicar esto comparando el comienzo y el final de la búsqueda cadena contra la cadena de búsqueda para cubrir los límites de la cadena, y luego con un Reemplazar (L '' + buscar + L '') .... pero me preguntaba si había una solución más elegante que incluiría la puntuación de manera eficiente .

Consideremos que una palabra es cualquier colección de caracteres separados por espacios en blanco o signos de puntuación (para simplificar, digamos! "# $% & '() * +, -./Como mínimo - que sucede para corresponder a (c > 31 && c < 48)).

En mi aplicación tengo que llamar a esta función en una gran variedad de cadenas cortas, que pueden incluir varias Unicode que no quiero dividir las palabras nuevas. También me gustaría evitar incluyendo cualquier biblioteca externa, pero STL está bien.

El propósito de no usar expresiones regulares es la promesa de menos sobrecarga y el objetivo de una función rápida adecuada para esto tarea particular sobre un gran conjunto de datos.

Answer 1

Creo que puede hacer esto, haciendo coincidir palabras enteras y hacerlo de manera eficiente. La clave es:

• detectar límites "de palabra completa" usando 'std :: isalpha', que debe trabajo con Unicode & cualquier configuración regional.
• sustituya "fuera de lugar" creando una cadena de 'salida' separada que intercambie con 'entrada' al final del proceso, en lugar de hacer el trabajo "en su lugar" en la cadena 'de entrada'.

Esta es mi opinión sobre su función:

#include <cctype> // isalpha 
#include <ciso646> // or, not 
#include <string> // wstring 

using std::size_t; 
using std::wstring; 

/// @brief Do a "find and replace" on a string. 
/// @note This function does "whole-word" matching. 
/// @param[in,out] input_string The string to operate on. 
/// @param[in] find_string The string to find in the input. 
/// @param[in] replace_string The string to replace 'find_string' 
///   with in the input. 
void find_and_replace(wstring& input_string, 
         const wstring& find_string, 
         const wstring& replace_string) 
{ 
    if(find_string.empty() 
     or find_string == replace_string 
     or input_string.length() < find_string.length()) 
    { 
    return; 
    } 

    wstring output_string; 
    output_string.reserve(input_string.length()); 
    size_t last_pos = 0u; 
    for(size_t new_pos = input_string.find(find_string); 
     new_pos != wstring::npos; 
     new_pos = input_string.find(find_string, new_pos)) 
    { 
    bool did_replace = false; 
    if((new_pos == 0u 
      or not std::isalpha(input_string.at(new_pos - 1u))) 
     and (new_pos + find_string.length() == input_string.length() 
       or not std::isalpha(input_string.at(new_pos + find_string.length())))) 
    { 
     output_string.append(input_string, last_pos, new_pos - last_pos); 
     output_string.append(replace_string); 
     did_replace = true; 
    } 
    new_pos += find_string.length(); 
    if(did_replace) 
    { 
     last_pos = new_pos; 
    } 
    } 
    output_string.append(input_string, last_pos, 
         input_string.length() - last_pos); 

    input_string.swap(output_string); 
} 

P. S. No estaba seguro de lo que 'replace_all' estaba tratando de lograr en su ejemplo inicial, por lo que lo eliminé de mi solución para mayor claridad.

P.P.S. Este código sería mucho más limpio con Regex-es. ¿Puede confiar en la funcionalidad C++ TR1 o C++ 2011? Proporcionan una biblioteca estándar 'regex'.

Answer 2

Esta es mi respuesta rápida, pero no sé qué tan rápido es la solución ... Existen pocas soluciones a este problema:
1.Mediante el uso de iteradores, comparar cada palabra (delimitado por el espacio), recreando la secuencia para cada caso:

string& remove_all_occurences(string& s, const string& str_to_remove, const string& str_to_put){ 
       typedef string::size_type string_size; 
       string_size i = 0; 
       string cur_string; 
       cur_string.reserve(s.size()); 

       // invariant: we have processed characters [original value of i, i) 
       while (i != s.size()) { 
       // ignore leading blanks 
       // invariant: characters in range [original i, current i) are all spaces 
        while (i != s.size() && isspace(s[i])) 
        ++i; 

        // find end of next word 
        string_size j = i; 
        // invariant: none of the characters in range [original j, current j)is a space 
        while (j != s.size() && !isspace(s[j])) 
         j++; 
         // if we found some nonwhitespace characters 


        if (i != j) { 
         // copy from s starting at the beginning to i, placing str to replace, and finishing with j to the end of s 
         cur_string = s.substr(i,j-i); 
         if(cur_string == str_to_remove){ 
          s = s.substr(0,i) + str_to_put + s.substr(j,s.size() - j); 
         } 
         i = j; 
        } 
       } 
       return s; 
      } 

Prueba del programa:

void call_remove_all_occurences(){ 
       string my_str = "The quick brown fox jumps over sleepy dog fox fox fox"; 
       cout << remove_all_occurences(my_str,"fox","godzilla") << endl; 
      } 

Salida:

The quick brown godzilla jumps over sleepy dog godzilla godzilla godzilla 

1. por división Hilo en vector y que pasa por vector y reemplaza cada ocurrencia - simple ... no tiene el código, pero se entiende ...