Как я могу реализовать эффективную замену строки целого слова в C ++ без регулярных выражений?

Question

Возможно, я упускаю из виду нечто очевидное, но мне было интересно, каким может быть самый быстрый способ реализации замены целых слов в C ++.Сначала я рассматривал просто объединение пробелов в поисковом слове, но это не учитывает границы строк или знаки препинания.

Это моя текущая абстракция для замены (не целого слова):

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

Если бы я рассматривал только пробелы как границу слова, я, вероятно, мог бы реализовать это, сравнив начало и конец строки поиска со строкой поиска, чтобы покрыть границы строки, а затем добавив Заменить (L ').'+ find + L' ') .... но мне было интересно, есть ли более элегантное решение, которое бы эффективно включало пунктуацию.

Давайте рассмотрим слово как любую коллекцию символов, котораяразделенные пробелами или знаками препинания (скажем так: "# $% & '() * +, -. / как минимум, что соответствует (c > 31 && c < 48)).

В моемПриложение Я должен вызывать эту функцию для довольно большого массива коротких строк, которые могут включать в себя различные Unicode, которые я не хочу разделять новые слова.Я хотел бы избежать включения каких-либо внешних библиотек, но с STL все в порядке.

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

Answer 1

Я думаю, что вы можете сделать это, выполняя сопоставление всего слова и делая это эффективно.Ключ должен:

• определять границы "целого слова", используя 'std :: isalpha', который должен работать с Юникодом и любым языковым стандартом.
• замените «не на месте», создав отдельную строку «output», которую вы поменяете местами с «input» в конце обработки, вместо того, чтобы выполнять работу «in place» над самой строкой «input».

Вот мой взгляд на вашу функцию:

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

PS Я не был уверен, что 'replace_all' пытался выполнить в вашем первоначальном примере, поэтому я удалил его из своего решения для ясности.

PPS Этот код был бы намного чище с Regex-es.Можете ли вы положиться на функциональность C ++ TR1 или C ++ 2011?Они предоставляют стандартную библиотеку регулярных выражений.

Answer 2

Это мой быстрый ответ, но я не знаю, насколько быстро это решение ... Есть несколько решений этой проблемы:
1. Используя итераторы, сравните каждое слово (разделенное пробелом), воссоздав строку для каждого вхождения:

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

Тестирование программы:

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

Выход:

The quick brown godzilla jumps over sleepy dog godzilla godzilla godzilla

1. Разделив строку на вектор и пройдя через вектор и заменив каждое вхождение - просто ... нет кода, но вы понимаете ...