我曾經如何從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的

回答

相關問題