两个联合使用stl的联合计数元素

Question

我有两套，我想知道有多少元素至少在一组。这是一个函数set_union在<algorithm>它写联合在另一个集合，但我只想要的数字。我可以在不保存元素的情况下使用stl找到它吗？

Answer 1

我同意马歇尔克洛;我不相信有一个现成的算法来做到这一点。这是我一直在玩的一个想法。这是一个简单的类，它提供了一个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; 
}