एल्गोरिदम दो सेटों के चौराहे में तत्वों को हटाने के लिए

Question

मेरे पास एक विजुअल स्टूडियो 2008 सी ++ 03 एप्लिकेशन है जहां मेरे पास दो मानक कंटेनर हैं। मैं एक कंटेनर से सभी कंटेनर (सेट के चौराहे) में मौजूद सभी आइटमों को हटाना चाहता हूं।

कुछ इस तरह:

std::vector<int> items = /* 1, 2, 3, 4, 5, 6, 7 */; 
std::set<int> items_to_remove = /* 2, 4, 5*/; 

std::some_algorithm(items.begin, items.end(), items_to_remove.begin(), items_to_remove.end()); 

assert(items == /* 1, 3, 6, 7 */) 

वहाँ एक मौजूदा एल्गोरिथ्म या पैटर्न है कि ऐसा करने के लिए या मैं अपने खुद के रोल करने की जरूरत क्या करेंगे है?

धन्यवाद के साथ

Answer 1

प्रयास करें:

items.erase(
    std::remove_if(
     items.begin(), items.end() 
     , std::bind1st(
      std::mem_fun(&std::set<int>::count) 
      , items_to_remove 
     ) 
    ) 
    , items.end() 
); 

std::remove(_if) वास्तव में, कुछ भी दूर नहीं करता, क्योंकि यह iterators और नहीं कंटेनर के साथ काम करता है। यह क्या करता है श्रेणी के अंत में निकाले जाने वाले तत्वों को पुन: व्यवस्थित करता है, और कंटेनर के नए अंत पर एक पुनरावर्तक देता है। नए अंत के पिछले सभी तत्वों को वास्तव में कंटेनर से निकालने के लिए erase पर कॉल करें।

अद्यतन: यदि मुझे सही याद है, मानक पुस्तकालय के एक घटक के सदस्य फ़ंक्शन को बाध्यकारी मानक सी ++ नहीं है, क्योंकि कार्यान्वयन को फ़ंक्शन में डिफ़ॉल्ट पैरामीटर जोड़ने की अनुमति है। आप अपना स्वयं का फ़ंक्शन या फ़ंक्शन-ऑब्जेक्ट बनाकर सुरक्षित रहेंगे जो यह जांचता है कि तत्व निकालने के लिए आइटम के सेट में निहित है या नहीं।

Answer 2

आप का उपयोग std::remove के साथ संयोजन में कर सकते हैं। Erase - Remove idiom नामक एक सी ++ मुहावरे है, जो इसे पूरा करने में आपकी सहायता करने जा रहा है।

Answer 3

मान लें कि आप दो सेट, A और B है, और आप (A,B) ऐसी है कि I = A^B की, B, चौराहे, I से निकालना चाहते हैं, अपने अंतिम परिणाम हो जाएगा: A (बाएं बरकरार)
B' = B-I

पूर्ण सिद्धांत:
http://math.comsci.us/sets/difference.html

यह काफी सरल है।

1. I
2. में I
3. कॉपी B की सामग्री बनाएँ और पॉप्युलेट A और B
4. एक तिहाई मध्यवर्ती वेक्टर बनाएँ, प्रत्येक तत्व A की a_j, जो j तत्व शामिल हैं, खोज I के लिए के लिए तत्व a_j; तत्व I में पाया जाता है, को दूर यह

अंत में, एक व्यक्ति तत्व दूर करने के लिए कोड यहां पाया जा सकता:
How do I remove an item from a stl vector with a certain value?

और किसी आइटम के लिए खोज करने के लिए कोड यहाँ है:
How to find if an item is present in a std::vector?

शुभकामनाएं!

Answer 4

व्यक्तिगत रूप से, मैं इसके लिए छोटे सहायकों को बनाना पसंद करता हूं (कि मैं भारी उपयोग करता हूं)।

template <typename Container> 
class InPredicate { 
public: 
    InPredicate(Container const& c): _c(c) {} 

    template <typename U> 
    bool operator()(U const& u) { 
     return std::find(_c.begin(), _c.end(), u) != _c.end(); 
    } 

private: 
    Container const& _c; 
}; 

// Typical builder for automatic type deduction 
template <typename Container> 
InPredicate<Container> in(Container const& c) { 
    return InPredicate<Container>(c); 
} 

यह भी एक सच erase_if एल्गोरिथ्म

template <typename Container, typename Predicate> 
void erase_if(Container& c, Predicate p) { 
    c.erase(std::remove_if(c.begin(), c.end(), p), c.end()); 
} 

और फिर करने में मदद करता: जो बहुत पठनीय :) है

erase_if(items, in(items_to_remove)); 

Answer 5

एक और समाधान:

मानक प्रदान किए गए एल्गोरिदम set_difference है जिसका उपयोग इस के लिए किया जा सकता है। लेकिन इसके परिणामस्वरूप अतिरिक्त कंटेनर की आवश्यकता है। मैं व्यक्तिगत रूप से इसे जगह में करना पसंद करता हूं।

std::vector<int> items; 
//say items = [1,2,3,4,5,6,7,8,9] 

std::set<int>items_to_remove; 
//say items_to_remove = <2,4,5> 

std::vector<int>result(items.size()); //as this algorithm uses output 
          //iterator not inserter iterator for result. 

std::vector<int>::iterator new_end = std::set_difference(items.begin(), 
items.end(),items_to_remove.begin(),items_to_remove.end(),result.begin()); 

result.erase(new_end,result.end()); // to erase unwanted elements at the 
            // end. 

Answer 6

यहाँ यथा-स्थान विधि है कि फैंसी कार्यों की आवश्यकता नहीं है और न ही वैक्टर हल हो की जरूरत है "पर हाथ" एक और भी है:

#include <vector> 

template <class TYPE> 
void remove_intersection(std::vector<TYPE> &items, const std::vector<TYPE> &items_to_remove) 
{ 
    for (int i = 0; i < (int)items_to_remove.size(); i++) { 
     for (int j = 0; j < (int)items.size(); j++) { 
      if (items_to_remove[i] == items[j]) { 
       items.erase(items.begin() + j); 
       j--;//Roll back the iterator to prevent skipping over 
      } 
     } 
    } 
} 

यदि आप जानते हैं कि प्रत्येक में बहुलता सेट 1 है (multiset नहीं), तो आप वास्तव में बेहतर प्रदर्शन के लिए break; के साथ j--; लाइन को प्रतिस्थापित कर सकते हैं।