如何从std :: string中删除重复字符

Question

我有这样的std::string：

std::string fileName;

[fileName类似于/tmp/fs////js//config.js它来自某个地方，我需要存储它。但是当我存储它时，我需要从路径中删除多余的'/'字符，基本上在目录名和文件名之间只需要一个分隔符。

我可以通过一次遍历字符串一个字符并与下一个字符进行比较来删除这些字符，但是效率不高。

有人可以建议一些有效的方法吗？

Answer 1

[您将找不到比这更有效的东西-考虑一下-您需要删除连续的重复字符-含义是，即使在最佳情况下，您也必须查看每个字符至少一次。

Answer 2

删除重复的相邻元素是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 3

我认为std::unique仍然可以工作，即使您的字符串没有排序，因为它删除的只是连续的重复项。

当然，这里不知道/是一个特殊字符，您可能会发现包含双字母的文件名也被意外地修改为单字母，可能是烦人的。

也是O（N），但您不能避免。

一种可以很好工作的算法是std :: remove_if，因为您可以放入自己的“ functor”，该functor可以保持状态，以便知道最后一个字符是什么。

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

Answer 4

时间上的O（n）+内存上的O（n）

void clean_path(std::string& path) {
    std::string new_path;
    char sep = '/';
    for (auto i = 0; i < path.size(); ++i) {
        if (path[i] == sep && !new_path.empty() && new_path.back() == sep)
            continue;
        new_path.push_back(path[i]);
    }
    path = new_path;
}