Как удалить повторяющиеся символы из std :: string

Question

У меня есть std::string вот так:

std::string fileName;

, где fileName похоже на /tmp/fs////js//config.js Оно исходит откуда-то, и мне нужно его сохранить.Но когда я сохраняю его, мне нужно удалить лишние символы '/' из пути, в основном мне нужен только один разделитель между именами каталогов и именами файлов.

Я могу удалить их, перебирая строку со знаком один символвремя и сравнение со следующим символом, но это не очень эффективно.

Кто-нибудь может предложить какой-нибудь эффективный способ сделать это?

Answer 1

Удаление дубликатов смежных элементов - это работа для std::unique.В этом случае вам нужно предоставить свой собственный предикат, но он O (n) и очень прост.

struct both_slashes {
    bool operator()(char a, char b) const {
        return a == '/' && b == '/';
    }
};

std::string path("/tmp/fs////js//config.js");

path.erase(std::unique(path.begin(), path.end(), both_slashes()), path.end());

Answer 2

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

Answer 3

Я думаю, что std::unique будет работать, даже если ваша строка не отсортирована, потому что все, что она удаляет, это последовательные дубликаты.

Конечно, она не будет знать, что / здесь особый символ, и вы можетенайдите имена файлов, которые содержат двойные буквы, также неожиданно измененные на однострелочные, возможно, раздражающие.

Это также O (N), но вы не можете этого избежать.

Один алгоритмэто будет хорошо работать, это std :: remove_if, потому что вы можете вставить свой собственный «функтор», который может сохранять состояние, чтобы он знал, каким был последний символ.

struct slash_pred
{
  char last_char;

  slash_pred()
   : last_char( '\0' ) // or whatever as long as it's not '/'
  {
  }

  bool operator()(char ch)
  {
      bool remove = (ch == '/') && (last_char == '/');
      last_char = ch;
  }
};

path.erase( std::remove_if( path.begin(), path.end(), 
      slash_pred() ), path.end() );

O (N), но должен работать.

Для несогласных, которые думают, что remove_if может быть O (N ^ 2), это может быть реализовано так:

template< typename ForwardIterator, typename Pred >
ForwardIterator remove_if( ForwardIterator read, ForwardIterator end, Pred pred )
{
   ForwardIterator write = read; // outside the loop as we return it
   for( ; read!=end; ++read )
   {
      if( !pred( *read ) )
      {
         if( write != read ) // avoid self-assign
         {
            *write = *read;
         }
         ++write;
      }
   }
   return write;
}