n列表的交集

Question

我一直在試圖找出一種方法來查找C++中的N個列表的交集。

單擊我的方法是排序，合併和迭代。

還有其他方法嗎？

請分享您的建議。

Answer 1

使用未排序列表的解決方案將變得更加混亂。據推測，你會有一個「答案」列表，最初是空的。然後，你會找出兩個清單，並逐一進行;對於每個元素，您需要掃描其他列表以查看它是否存在於該列表中 - 如果存在匹配項，則將該元素存儲在答案中。然後，您將創建一個新的空答案列表，並逐步通過另一個原始列表，在上一個答案列表中搜索匹配元素，並添加到新答案列表中。重複令人厭惡。

這不是特別有效。

對於「排序，合併和迭代」解決方案，使用成對的列表也不如同時並行遍歷N個排序列表，只選擇出現在所有列表中的元素作爲回答。

Answer 2

排序使用std::sort（或者，如果它是一個std::list，使用std::list::sort），然後計算使用std::set_intersection反覆交叉每個列表（它適用於前兩個名單，然後對結果和第三列表，然後將結果和第四列表，等等）。