找到兩組聯合的大小？

有什麼方法可以找到兩組聯合的大小。我知道找到兩組聯合的大小？

s1 = {2 4 5 6} size 4 

s2 = {1 4 5 9 10} size 5 

s3 = {1 2 4 5 6 9 10} size 7 

complexity of set_union is 2*(s1 size + s2 size)-1

是否有其他方法來獲得兩套更快的方法的工會的大小，我需要的只是能做到這一點

vector <int> s3(s1.size() , s2.size()); auto it=set_union(s1.begin() , s1.end() , s2.begin() ,s2.end(), s3.begin()); int size = it - s3.begin();

打印尺寸

例子大小不希望形成新的聯合集合的值。如果你知道更快的方法，請建議。

來源

2017-06-03 shaurya uppal

的。如果我說的方法是唯一可行的方法，請告訴這一點。 –

如何在不知道集合內容的情況下計算出集合的大小？猜猜你的工作或許 –

s1和s2已經知道了s3正在使用空間和時間這兩者都有所減少 –

你可以在set_union的最後一個參數中加一個計數迭代器。例如。

int count = 0; 
it=set_union(s1.begin() , s1.end() , s2.begin() ,s2.end(), boost::make_function_output_iterator([&count](int){ ++count; }));

或非升壓相當於該輸出迭代器

struct counter { 
    using difference_type = void; 
    using value_type = void; 
    using pointer = void; 
    using reference = void; 
    using iterator_category = std::output_iterator_tag; 
    int count = 0; 
    void operator&(int) { ++count } 
    counter& operator++ { return *this; } 
};

來源

2017-06-03 22:10:09 Caleth

OP沒有將這個問題標記爲[tag：boost]，所以我至少會指定答案是[tag：boost]。 – Zereges

我已經給出了一個手動將lambda擴展到該模板的示例 – Caleth

一個顯而易見的方法是執行相同的迭代set_union，但不是複製元素，只是碰到一個計數器。這使得時間複雜度保持不變，但完全避免了空間使用。

從理論上講，可以設計一個OutputIterator只計算元素，以便可以重新使用set_union算法。是否值得讓你的迭代器嘎嘎完成STL期望它是一個不同的問題的麻煩......重新實現set_union來做簡單的計算可能會更容易。

來源

2017-06-03 19:56:17

找到兩組聯合的大小？

回答

相關問題