सी ++

Question

में दो एसटीएल सेटों के एक चौराहे के आकार की गणना कैसे करें I को दो सेट (std :: <set> से सेट) दिया गया है, जिसमें से मैं छेड़छाड़ के आकार को जानना चाहता हूं। मैं <algorithm> से std :: set_intersection का उपयोग कर सकता हूं, लेकिन मुझे इसे किसी अन्य कंटेनर में छेड़छाड़ की प्रतिलिपि बनाने के लिए आउटपुट इटरेटर प्रदान करना होगा।

एक सरल तरीके से

set<int> s1{1,2,3,4,5}; 
    set<int> s2{4,5,6,7,8,9,0,1}; 

    vector<int> v; 

    set_intersection(
     s1.begin(), s1.end(), s2.begin(), s2.end(), 
     inserter(v, v.begin())); 

जो v.size() के बाद चौराहे के आकार देता होगा। हालांकि, चौराहे को भी संग्रहीत किया जाना चाहिए, भले ही हम इसके साथ कुछ भी न करें।

कि बचने के लिए, मैं एक डमी उत्पादन iterator वर्ग है, जो केवल गिना जाता है को लागू करने की कोशिश की है, लेकिन यह आवंटित नहीं करता है: जो हम कर सकते थे का उपयोग कर

template<typename T> 
class CountingOutputIterator { 
private: 
    int* counter_; 
    T dummy_; 
public: 
    explicit CountingOutputIterator(int* counter) :counter_(counter) {} 
    T& operator*() {return dummy_;} 
    CountingOutputIterator& operator++() { // ++t 
    (*counter_)++; 
    return *this; 
    } 
    CountingOutputIterator operator++(int) { // t++ 
    CountingOutputIterator ret(*this); 
    (*counter_)++; 
    return ret; 
    } 
    bool operator==(const CountingOutputIterator& c) { 
    return counter_ == c.counter_; // same pointer 
    } 
    bool operator!=(const CountingOutputIterator& c) { 
    return !operator==(c); 
    } 
}; 

set<int> s1{1,2,3,4,5}; 
    set<int> s2{4,5,6,7,8,9,0,1}; 

    int counter = 0; 
    CountingOutputIterator<int> counter_it(&counter); 
    set_intersection(
     s1.begin(), s1.end(), s2.begin(), s2.end(), counter_it); 

जिसके बाद काउंटर चौराहे का आकार रखता है।

हालांकि यह बहुत अधिक कोड है। मेरे प्रश्न हैं:

1) क्या पूरे चौराहे को संग्रहीत किए बिना चौराहे के आकार को प्राप्त करने के लिए मानक (लाइब्रेरी) तरीका या मानक चाल है? 2) चाहे स्वतंत्र है या नहीं, स्वतंत्र डमी इटेटरेटर के साथ दृष्टिकोण अच्छा है?

Answer 1

यह एक पाश है कि दो सेट के माध्यम से ले जाता है तत्वों मिलान की तलाश में लिखने के लिए मुश्किल नहीं है, या आप इस है, जो एक कस्टम इटरेटर तुलना में बहुत सरल है कर सकता है:

struct Counter 
{ 
    struct value_type { template<typename T> value_type(const T&) { } }; 
    void push_back(const value_type&) { ++count; } 
    size_t count = 0; 
}; 

template<typename T1, typename T2> 
size_t intersection_size(const T1& s1, const T2& s2) 
{ 
    Counter c; 
    set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), std::back_inserter(c)); 
    return c.count; 
} 

Answer 2

आप ऐसा कर सकता है:

auto common = count_if(begin(s1), end(s1), [&](const auto& x){ return s2.find(x) != end(s2); }); 

यह बेहतर कुशल नहीं है लेकिन सबसे प्रयोजनों के लिए काफी तेजी से किया जाना चाहिए।

Answer 3

ऐसा कोई फ़ंक्शन लिखना बहुत कठिन नहीं है जो ऐसा करता है। This दिखाता है कि कैसे set_intersection किया जाता है [हालांकि वास्तविक क्रियान्वयन निश्चित रूप से आसानी से अलग हो सकता है]

तो हम बस उस कोड का समय लग सकता है, और यह एक छोटा सा संशोधित:

template <class InputIterator1, class InputIterator2> 
    size_t set_intersection_size (InputIterator1 first1, InputIterator1 last1, 
           InputIterator2 first2, InputIterator2 last2) 
{ 
    size_t result = 0; 
    while (first1!=last1 && first2!=last2) 
    { 
    if (*first1<*first2) ++first1; 
    else if (*first2<*first1) ++first2; 
    else { 
     result++; 
     ++first1; ++first2; 
    } 
    } 
    return result; 
} 

मेरे अनुभव में हालांकि जब, आप जानना चाहते हैं कि चौराहे में कितने हैं, आप आमतौर पर जल्दी या बाद में जानना चाहते हैं कि कौन से तत्व भी हैं।

Answer 4

आप के उपयोग को आसान बना सकता आपका दृष्टिकोण एक उचित बिट:

struct counting_iterator 
{ 
    size_t count; 
    counting_iterator& operator++() { ++count; return *this; } 
    // other iterator stuff 
}; 

size_t count = set_intersection(
    s1.begin(), s1.end(), s2.begin(), s2.end(), counting_iterator()).count;