賦值vs std :: swap和合並並保留重複項在單獨對象中

假設我有兩個std::set<std::string> s。第一個old_options需要與new_options中包含的其他選項合併。我不能僅僅使用std::merge（嗯，我這樣做，但不僅如此），因爲我也檢查雙打，並相應地提醒用戶。爲此，我有賦值vs std :: swap和合並並保留重複項在單獨對象中

void merge_options(set<string> &old_options, const set<string> &new_options) 
{ 
    // find duplicates and create merged_options, a stringset containing the merged options 
    // handle duplicated the way I want to 
    // ... 
    old_options = merged_options; 
}

是它更好地使用

std::swap(merged_options, old_options);

或我的任務？

有沒有更好的方式來過濾重複和合並後返回set比連續通話std::set_intersection和std::set_union檢測愚弄和合並set S'我知道它比一次遍歷要慢，並且同時做兩次，但這些集很小（性能不重要），我相信標準比我更信任自己。

來源

2011-03-06 rubenvb

這有什麼錯

void merge_options(set<string> &old_options, const set<string> &new_options) 
{ 
    for (set<string>::iterator i = new_options.begin(); 
     i != new_options.end(); ++i) 
     if (old_options.find(*i) != old_options.end()) 
      warn_duplicate(*i); 
     else 
      old_options.insert(*i); 
}

這是一個簡單的O（米 LG ñ）算法，其中米 = new_options.size()和ñ = old_options.size()。

來源

2011-03-06 16:16:39

簡單，是的，但在性能上並不相同（如果你忽略了因素2，這在大O中應該不重要）。我想到了一個同步遍歷，它基本上是O（log（max（M，N））。這確實會獲得性能，但正如Jerry所說，這更復雜，也許在這裏沒有用處。我不想錯過一個C++庫函數 – rubenvb 2011-03-06 16:34:05

@rubenvb：我認爲同時遍歷將是O（max（m，n））。它和你的版本的區別在於：1）分配和拷貝更少（假設C++ 03）和2）我認爲我更清楚。我不認爲標準庫有這樣做的更短的方式，但我必須承認''讓我感到驚訝。 – 2011-03-06 16:40:32

是的，'日誌'是二進制搜索，愚蠢的我'= s'。 @Blastfurnace也有不錯的一個。（和''一直讓我感到驚訝，因此問題） – rubenvb 2011-03-07 10:32:21

鑑於（如您所述）性能並不關鍵，我會使用賦值和雙通道算法。它更簡單，更易於理解;如果你真的需要它所獲得的價值，那麼只需使用swap等「技巧」即可。編寫你自己的算法不會是件壞事，但除非你有真正的用途，否則我不會感到麻煩。

來源

2011-03-06 16:13:00

這部分是對larsmans的回答。有一個remove_copy_if算法將他的for循環封裝到一個函數中。以下使用C++ 0x lambda作爲謂詞。

void merge_options(set<string> &old_options, const set<string> &new_options) 
{ 
    remove_copy_if(
     new_options.begin(), 
     new_options.end(), 
     inserter(old_options, old_options.end()), 
     [&](const string &s) { 
      return (old_options.count(s)) ? warn_duplicate(s), true : false; 
     } 
    ); 
}

來源

2011-03-06 22:04:53 Blastfurnace

@larsmans解決方案的複雜性與我想的相同嗎？ – rubenvb 2011-03-07 10:32:49

是的，同樣的複雜性。 lambda introducer中的'＆'是做什麼的？我還不熟悉lambda。 – 2011-03-07 10:50:07

@larsmans：這是一個捕獲子句，它允許lambda訪問封閉範圍中的變量。 '＆'通過引用訪問所有捕獲的變量。在這種情況下，它允許lambda查看（並修改）old_options集。 – Blastfurnace 2011-03-07 14:39:18

賦值vs std :: swap和合並並保留重複項在單獨對象中

回答

相關問題