stlを使用した2つのセットの和集合の要素数

Question

私は2つのセットを持っていて、どれくらい多くの要素があるかを知りたいのですが、に少なくともがあります。ユニオンを別のセットに書き込むのはset_unionの<algorithm>ですが、数字だけを欲しいです。要素を保存せずにstlを使って見つけることはできますか？

Answer 1

私はMarshall Clowに同意します。私はこれを行うための既製のアルゴリズムがあるとは思わない。ここに私が夢見てきたアイデアがあります。これは、単純にカウンタをインクリメントするpush_backメソッドを提供する単純なクラスです。出力イテレータとしてstd :: back_inserterを使用します。

#include <initializer_list> 
#include <iterator> 
#include <iostream> 
#include <algorithm> 

template <typename T> 
class CountingPushBack 
{ 
    public: 
    using value_type = T; 

    void push_back(T const &) {++count;} 

    std::size_t get_count() const {return count;} 

    private: 
    std::size_t count = 0; 
}; 

int main() 
{ 
    std::initializer_list<int> il1 = { 0, 1, 2, 3, 4 }; 
    std::initializer_list<int> il2 = { 0, 2, 4, 6, 8 }; 

    CountingPushBack<int> cp; 

    std::set_union(il1.begin(), il1.end(), 
       il2.begin(), il2.end(), 
       std::back_inserter(cp)); 

    std::cout << cp.get_count() << std::endl; 
} 

Answer 2

私はそのようなアルゴリズムについて知らない。それは言われている、あなたはset_unionの勇気を使ってそれを行うことができます。このような：

#include <iostream> 
#include <set> 

// Counts the number of elements that would be in the union 
template <class Compare, class InputIterator1, class InputIterator2> 
size_t set_union_size(InputIterator1 first1, InputIterator1 last1, 
         InputIterator2 first2, InputIterator2 last2, 
         Compare comp) 
{ 
    size_t __result = 0; 
    for (; first1 != last1;) 
    { 
     if (first2 == last2) 
      return __result + std::distance(first1, last1); 
     if (comp(*first2, *first1)) 
     { 
      ++__result; 
      ++first2; 
     } 
     else 
     { 
      ++__result; 
      if (!comp(*first1, *first2)) 
       ++first2; 
      ++first1; 
     } 
    } 
    return __result + std::distance(first2, last2); 
} 

int main() { 
    std::set<int> s1 = { 0, 1, 2, 3, 4 }; 
    std::set<int> s2 = { 0, 2, 4, 6, 8 }; 
    std::cout 
     << set_union_size(s1.begin(), s1.end(), s2.begin(), s2.end(), std::less<int>()) 
     << std::endl; 
    } 

そして、これはあなたが期待するものである、7を出力します。

Answer 3

SCFrenchによって溶液が細かいですが、我々は唯一のback_insert_iteratorを必要とする一方で、それは、コンテナが必要です。次に、実装の例を示します。

#include <iostream> 
#include <iterator> 
#include <vector> 
#include <algorithm> 

template <typename T> 
class count_back_inserter { 
    size_t &count; 
public: 
    typedef void value_type; 
    typedef void difference_type; 
    typedef void pointer; 
    typedef void reference; 
    typedef std::output_iterator_tag iterator_category; 
    count_back_inserter(size_t &count) : count(count) {}; 
    void operator=(const T &){ ++count; } 
    count_back_inserter &operator *(){ return *this; } 
    count_back_inserter &operator++(){ return *this; } 
}; 

あなたは「基本的なコンテナ」に「追加」されるすべての要素のためにインクリメントされるコンストラクタにsize_t変数を渡すことによって、それを使用することができます。

int main(){ 
    std::vector<int> v1 = {1, 2, 3, 4, 5}; 
    std::vector<int> v2 = {  3, 4, 5, 6, 7}; 
    size_t count = 0; 
    set_union(v1.begin(), v1.end(), 
       v2.begin(), v2.end(), 
       count_back_inserter<int>(count)); 
    std::cout << "The number of elements in the union is " << count << std::endl; 
}