如何讀取兩個物品流並收集未複製的物品

Question

假設我們有兩個大的清單或數據流，並且我們希望同時讀取和收集僅在一個物流中的物品。

樣品：

列表＃1：1，4，5

列表＃2：1，3，5，6

結果：4，3，6

注1：這兩個列表都太大，我們不想將它們排序。

注2：每個流中的項目都是唯一的。所以我們不需要擔心單個列表中的重複項目

什麼是執行此操作的最佳（最快）方式？

在此先感謝。

Answer 1

如果只有一次通過，並且未對流進行排序，則不可能。否則，你可以使用散列表，實際上它比排序快一點。

另外，看看http://en.wikipedia.org/wiki/MapReduce的方法。如果你有非常大的數據，這對你來說是很好的解決方案。

Answer 2

計算每個值的出現次數。只打印出現一次的值。

#include <unordered_map> 
#include <vector> 
#include <iterator> 
#include <iostream> 

template<typename InputIterator, typename OutputIterator> 
void 
uniq (InputIterator b0, InputIterator e0, 
     InputIterator b1, InputIterator e1, 
     OutputIterator u) 
{ 
    std::unordered_map<typename std::iterator_traits<InputIterator>::value_type, int> m; 

    while (b0 != e0) 
     ++m [*b0++]; 

    while (b1 != e1) 
     ++m [*b1++]; 

    for (auto &mi : m) 
    { 
     if (mi.second == 1) 
     *u++ = mi.first; 
    } 
} 

int 
main() 
{ 
    std::vector<int> s0 ({1, 4, 5}); 
    std::vector<int> s1 ({1, 3, 5, 6}); 
    std::vector<int> r; 

    uniq (s0.begin(), s0.end(), s1.begin(), s1.end(), std::back_inserter (r)); 

    for (auto i : r) 
    std::cout << i << " "; 
}