我曾经如何从STD除去重复字符:: string的

得到了std::string这样的：我曾经如何从STD除去重复字符:: string的

std::string fileName;

其中fileName就像/tmp/fs////js//config.js 它是从什么地方来，我需要将它存储。但是当我存储它时，我需要从路径中删除额外的'/'字符，基本上只需要在目录名和文件名之间使用一个分隔符。

我可以通过一次遍历字符串一个字符，并与下一个字符比较，但它不是非常有效的去除这些。

任何人都可以提出一些有效的方法来做到这一点吗？

来源

2011-03-01 user333422

为什么你认为这是不是有效？这是O（n），你不能为这个问题找到更有效的方法。 – sashoalm

“高效”（快速，优雅或记忆）是什么意思？你能否提供你的尝试作为问题的一部分？ –

你不会找到任何更有效的 - 想想吧 - 你需要删除重复的连续的特点 - imnplication的是，即使在最好的情况下，你将不得不看每角色至少一次。

来源

2011-03-01 10:20:37 PaulJWilliams

谢谢，我会继续坚持我原来的解决方案。 – user333422

这不是100％真实的。实际的naïve算法不是O（N），而是O（N^2）（每个字符的移除本身就是一个线性操作，因为它需要从该位置到字符串末尾的所有元素被移动*）再次，在大多数情况下，除非字符串很大且有大量重复项，否则它可能比纯粹需要复制的线性算法更有效。 –

@大卫天真算法是你可能做的，如果你使用自制循环多次调用erase（）。然而，remove_if将保持O（N）。梅耶斯主张使用它是完全正确的。 – CashCow

我认为std::unique会工作，即使你的字符串是没有排序，因为所有它消除是连续的重复。

当然，它不会知道/这里是一个特殊字符，您可能会发现包含双字母的文件名也意外修改为single-leter，可能会非常糟糕。

它也是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; 
}

来源

2011-03-01 10:21:11 CashCow

是的，如果他只想删除连续的斜杠，那么这将是一个愚蠢的想法。 –

@David你错了remove_if。我会执行它来向你展示它是O（N）。 – CashCow

@CashCow在任何C++库中都不起作用，因为可能会在“remove_if”函数内复制“pred”对象。你应该实例化一个“slash_pred”对象，并使用“std :: bind1st（std :: mem_fun（＆slash_pred :: operator（）），＆pred）”将它传递给“remove_if”。 –

删除重复相邻元素是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());

来源

2011-03-01 15:11:14 Blastfurnace

可能比remove_if更好，因为谓词更整齐。 – CashCow

+1这使得非常有效地使用标准库，应该是被接受的答案，恕我直言。 –

注意我upvoted这个答案比我自己... – CashCow

我曾经如何从STD除去重复字符:: string的

回答

相关问题