兩個聯合使用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; 
}