डुप्लिकेट तत्वों को हटाने, एकाधिक एसटीएल कंटेनरों को मर्ज करने का सबसे अच्छा तरीका?

Question

मेरे पास दो एसटीएल कंटेनर हैं जिन्हें मैं एक से अधिक बार दिखाई देने वाले किसी भी तत्व को हटाने, विलय करना चाहता हूं। उदाहरण के लिए:

typedef std::list<int> container; 
container c1; 
container c2; 

c1.push_back(1); 
c1.push_back(2); 
c1.push_back(3); 

c2.push_back(2); 
c2.push_back(3); 
c2.push_back(4); 

container c3 = unique_merge(c1, c2); 
// c3 now contains the following 4 elements: 
// 1, 2, 3, 4 

std :: अद्वितीय केवल आसन्न तत्वों के लिए हो रहा है और मेरे मामले में कंटेनर किसी भी क्रम में हो सकता है।

container unique_merge(const container& c1, const container& c2) 
{ 
    std::set<container::value_type> s; 
    BOOST_FOREACH(const container::value_type& val, c1) 
     s.insert(val); 
    BOOST_FOREACH(const container::value_type& val, c2) 
     s.insert(val); 
    return container(s.begin(), s.end()); 
} 

वहाँ एक बेहतर तरीका है या मैं खून बह रहा है स्पष्ट कुछ छूट गया है: मैं कुछ std :: प्रवंचना सेट मुझे लगता है कि कर सकता है?

Answer 1

एक अनियमित सूचियों के लिए, आपकी सेट चाल शायद सबसे अच्छी है। यह प्रत्येक सम्मिलन ओ (लॉग एन) होना चाहिए, जिसमें एन आवेषण आवश्यक हैं, और ट्रैवर्सिंग ओ (एन) होगी, जो आपको ओ (एन * लॉग एन) देगी। दूसरा विकल्प अलग-अलग सूची में std :: sort को चलाने के लिए है और फिर std::set_union का उपयोग करके समानांतर में उनके माध्यम से चलना है, जो आपके लिए डुप्लीकेट हटा देता है। यह ओ (एन * लॉग एन) भी होगा, इसलिए यदि आप प्रदर्शन के बारे में चिंतित हैं, तो आपको प्रोफ़ाइल करना होगा। यदि आप नहीं हैं, तो जो भी आपको अधिक समझ में आता है।

संपादित करें: set_union तभी मूल सूचियों में कोई डुप्लिकेट हैं काम करेंगे, अन्यथा आप sort, merge, unique और erase साथ जाने के लिए होगा। बड़ा ओ प्रदर्शन अभी भी वही है, प्रोफाइलिंग के बारे में एक ही चेतावनी के साथ।

template <typename container> 
container unique_merge(container c1, container c2) 
{ 
    std::sort(c1.begin(), c1.end()); 
    std::sort(c2.begin(), c2.end()); 
    container mergeTarget; 
    std::merge(c1.begin(), c1.end(), c2.begin(), c2.end(), 
     std::insert_iterator(mergeTarget, mergeTarget.end()) 
    ); 
    std::erase(
     std::unique(mergeTarget.begin(), mergeTarget.end()), 
     mergeTarget.end() 
    ); 

    return mergeTarget; 
} 

Answer 2

क्या आप उन्हें मर्ज करने के लिए std::merge का उपयोग नहीं कर सकते हैं और फिर डुप्लीकेट हटा सकते हैं? हालांकि, कंटेनरों को सॉर्ट करने की आवश्यकता होती है, हालांकि।

Answer 3

एसटीएल से std::set_union algorithm का उपयोग करें। आपको पहले अपनी इनपुट सूचियों को क्रमबद्ध करने की आवश्यकता होगी - या अपनी इनपुट सूचियों की प्रतियां बनाएं, उन्हें सॉर्ट करें, फिर std :: set_union का उपयोग करें।

Answer 4

आपको या तो क्रमबद्ध करने की आवश्यकता होगी (या तो स्पष्ट रूप से, या निश्चित रूप से सेट किए गए सॉर्ट किए गए कंटेनर के माध्यम से)।

एक कंटेनर में अद्वितीय तत्व प्राप्त करने के लिए std :: sort/std :: अद्वितीय/std :: मिटा का उपयोग कर एक सामान्य मुहावरे है।

तो सी 1 की सामग्री के साथ एक कंटेनर बनाएं, सी 2 की सामग्री संलग्न करें, फिर क्रमबद्ध करें, अद्वितीय तत्वों को अंत में ले जाएं, और उन्हें मिटा दें। कुछ ऐसा:

container c(c1.begin(), c1.end()); 
c.insert(c.end(), c2.begin(), c2.end()); 
c.erase(std::unique(c.begin(), c.end()), c.end());