किसी अन्य वेक्टर

Question

दिए गए वेक्टर से तत्वों को कुशलता से कैसे हटाएं एक वेक्टर से तत्वों को हटाने के लिए सबसे अच्छा तरीका क्या है?

मैं निम्नलिखित कोड के साथ आए हैं:

#include <iostream> 
#include <vector> 
#include <algorithm> 
using namespace std; 

void remove_elements(vector<int>& vDestination, const vector<int>& vSource) 
{ 
    if(!vDestination.empty() && !vSource.empty()) 
    { 
     for(auto i: vSource) { 
      vDestination.erase(std::remove(vDestination.begin(), vDestination.end(), i), vDestination.end()); 
     } 
    } 
} 

int main() 
{ 
    vector<int> v1={1,2,3}; 
    vector<int> v2={4,5,6}; 
    vector<int> v3={1,2,3,4,5,6,7,8,9}; 
    remove_elements(v3,v1); 
    remove_elements(v3,v2); 
    for(auto i:v3) 
     cout << i << endl; 
    return 0; 
} 

यहाँ उत्पादन होगा:

7 
8 
9 

Answer 1

मेरे संस्करण निम्नलिखित है, मैं केवल वेक्टर vSource से सभी तत्वों के बाद erase लागू std::remove द्वारा अंत में स्थानांतरित कर दिया गया है और वेक्टर vDestination के अंत तक पॉइंटर का ट्रैक रखें ताकि इसे किसी भी चीज़ के लिए फिर से चालू न किया जा सके।

void remove_elements(vector<int>& vDestination, const vector<int>& vSource) 
{ 
    auto last = std::end(vDestination); 
    std::for_each(std::begin(vSource), std::end(vSource), [&](const int & val) { 
     last = std::remove(std::begin(vDestination), last, val); 
    }); 
    vDestination.erase(last, std::end(vDestination)); 
} 

coliru पर देखें: http://coliru.stacked-crooked.com/a/6e86893babb6759c

---

अद्यतन

यहाँ एक टेम्पलेट संस्करण है, तो आप कंटेनर प्रकार के बारे में परवाह नहीं है:

template <class ContainerA, class ContainerB> 
void remove_elements(ContainerA & vDestination, const ContainerB & vSource) 
{ 
    auto last = std::end(vDestination); 
    std::for_each(std::begin(vSource), std::end(vSource), [&](typename ContainerB::const_reference val) { 
     last = std::remove(std::begin(vDestination), last, val); 
    }); 
    vDestination.erase(last, std::end(vDestination)); 
} 

---

नोट

इस संस्करण में किसी भी बाधाओं के बिना वैक्टर लिए काम करता है, अगर आपके वैक्टर हल कर रहे हैं आप कुछ शॉर्टकट लेने के लिए और अधिक और प्रत्येक तत्व नष्ट करने के लिए वेक्टर से अधिक बार-बार दोहराना बच सकते हैं।

Answer 2

के रूप में एसटीएल के साथ लिखा जा सकता है:

void remove_elements(vector<int>& vDestination, const vector<int>& vSource) 
{ 
    const auto isInSource = [&](int e) { 
     return std::find(vSource.begin(), vSource.end(), e) != vSource.end(); 
    }; 
    vDestination.erase(
     std::remove_if(vDestination.begin(), vDestination.end(), isInSource), 
     vDestination.end()); 
} 

अगर vSource क्रमबद्ध हो जाता है, तो आप std::binary_search द्वारा std::find जगह ले सकती।

Answer 3

अपने वैक्टर हमेशा हल कर रहे हैं, तो आप set_difference उपयोग कर सकते हैं:

#include <iostream> 
#include <vector> 
#include <algorithm> 
#include <iterator> 

void remove_elements(std::vector<int>& vDestination, const std::vector<int>& vSource) 
{ 
    std::vector<int> result; 
    std::set_difference(vDestination.begin(), vDestination.end(), vSource.begin(), vSource.end(), std::back_inserter(result)); 
    vDestination.swap(result); 
} 

int main() 
{ 
    std::vector<int> v1={1,2,3}; 
    std::vector<int> v2={4,5,6}; 
    std::vector<int> v3={1,2,3,4,5,6,7,8,9}; 
    remove_elements(v3,v1); 
    remove_elements(v3,v2); 
    for(auto i:v3) 
     std::cout << i << '\n'; 
} 

नहीं reqirement के लिए, कि उत्पादन रेंज किसी भी इनपुट रेंज के साथ ovelap नहीं करना चाहिए, तो हम भी अतिरिक्त वेक्टर से बच सकते हैं। संभावित रूप से आप set_difference का अपना संस्करण रोल कर सकते हैं जिसे vDestination.begin() से शुरू होने वाली सीमा में आउटपुट करने की अनुमति है, लेकिन यह इस उत्तर के दायरे से बाहर है।

Answer 4

मुझे लगता है कि सर्वोत्तम का मतलब है कि सबसे तेज़ है जो काम करता है। चूंकि यह दक्षता के बारे में एक सवाल है, इसलिए मैंने कई एल्गोरिदम की दक्षता की तुलना करने के लिए एक सरल बेंचमार्क किया है। ध्यान दें कि वे एक छोटे से अलग के बाद से समस्या एक सा underspecified है - सवाल उठता है कि (और मान्यताओं बेंचमार्क के लिए लिया गया) कर रहे हैं:

• यह गारंटी है कि vDestinationvSource से सभी तत्व शामिल हैं है? (धारणा: नहीं)
• या तो vDestination या vSource में डुप्लिकेट की अनुमति है?(धारणा: हाँ, दोनों में)
• परिणाम वेक्टर पदार्थ में तत्वों का क्रम करता है? (दोनों मामलों के परीक्षण के लिए एल्गोरिदम)
• vDestination से प्रत्येक तत्व को हटाया जाना चाहिए यदि यह vSource से किसी भी तत्व के बराबर है, या केवल एक-एक के लिए है? (धारणा: हाँ, दोनों में)
• vDestination और vSource के आकार किसी भी तरह से बंधे हैं? उनमें से एक हमेशा बड़ा है या अधिक बड़ा है? (कई मामलों का परीक्षण किया गया)
• टिप्पणियों में यह पहले से ही समझाया गया है कि वैक्टर को क्रमबद्ध करने की आवश्यकता नहीं है, लेकिन मैंने इस बिंदु को शामिल किया है, क्योंकि यह तुरंत प्रश्न से दिखाई नहीं दे रहा है (वेक्टरों में से कोई भी सॉर्टिंग नहीं)

जैसा कि आप देखते हैं, कुछ बिंदुएं हैं जिनमें एल्गोरिदम अलग-अलग होंगे और परिणामस्वरूप, जैसा कि आप अनुमान लगा सकते हैं, सर्वोत्तम एल्गोरिदम आपके उपयोग के मामले पर निर्भर करेगा। तुलना एल्गोरिदम में शामिल हैं:

1. मूल एक (प्रश्न में प्रस्तावित) - आधारभूत
2. @dkg जवाब में प्रस्तावित
3. @Revolver_Ocelot जवाब + अतिरिक्त छंटाई (कलन विधि के लिए आवश्यक) और अंतरिक्ष के पूर्व आरक्षण में प्रस्तावित परिणाम वेक्टर के लिए
4. @ Jarod42 में प्रस्तावित का जवाब
5. सेट आधारित एल्गोरिथ्म (नीचे प्रस्तुत - ज्यादातर @ Jarod42 एल्गोरिथ्म के अनुकूलन)
6. गिनती एल्गोरिथ्म (पी नीचे resended)

सेट आधारित एल्गोरिथ्म:

std::unordered_set<int> elems(vSource.begin(), vSource.end()); 
auto i = destination.begin(); 
auto target = destination.end(); 
while(i <= target) { 
    if(elems.count(*i) > 0) 
     std::swap(*i, *(--target)); 
    else 
     i++; 
} 
destination.erase(target, destination.end()); 

गिनती एल्गोरिथ्म:

std::unordered_map<int, int> counts;  
counts.max_load_factor(0.3);  
counts.reserve(destination.size());  

for(auto v: destination) {  
    counts[v]++;  
}  

for(auto v: source) {  
    counts[v]--;  
}  

auto i = destination.begin();  
for(auto k: counts) {  
    if(k.second < 1) continue;    
    i = std::fill_n(i, k.second, k.first);  
}  
destination.resize(std::distance(destination.begin(), i));  

बेंचमार्किंग प्रक्रिया Celero लाइब्रेरी का उपयोग कर मार डाला गया था और पीछा कर रहा था:

1. उत्पन्न n छद्म-यादृच्छिक int रों (सेट {10,100,1000,10000, 20000, 200000} में n) और एक vector
2. कॉपी करने के लिए उन्हें डाल सेट {0.01, 0.1, 0.2, 0.4, 0.6, 0.8}, मिनट से दूसरे vector (अंशों करने के लिए इन ints का एक अंश (m)। 1 तत्व)
3. प्रारंभ टाइमर
4. निष्पादित हटाने की प्रक्रिया
5. टाइमर बंद करें

केवल एल्गोरिदम 3, 5 और 6 उनमें से बाकी के रूप में 10 000 तत्वों की तुलना में बड़े डेटासेट पर मार डाला गया के लिए लंबे समय तक ले गए मुझे आराम से मापने के लिए (इसे स्वयं करने के लिए स्वतंत्र महसूस करें)।

लंबी कहानी छोटी: यदि आपके वैक्टर में 1000 से कम तत्व होते हैं, तो आप जो चाहें उसे चुनें। यदि वे लंबे समय तक हैं - vSource के आकार पर भरोसा करें। यदि यह vDestination का 50% से कम है - सेट-आधारित एल्गोरिदम चुनें, यदि यह अधिक है - उन्हें क्रमबद्ध करें और @ Revolver_Ocelot का समाधान चुनें (वे लगभग 60% बांधते हैं, vSource के लिए सेट-आधारित 2x तेज से vDestination का 1% आकार है) ।कृपया आदेश पर भरोसा न करें या शुरुआत से क्रमबद्ध वेक्टर प्रदान करें - ऑर्डर करने की आवश्यकता समान है, प्रक्रिया को नाटकीय रूप से धीमा कर दें। अपने उपयोग के मामले, अपने कंपाइलर, अपने झंडे और अपने हार्डवेयर पर बेंचमार्क। यदि आप उन्हें पुन: पेश करना चाहते हैं, तो मैंने अपने बेंचमार्क से लिंक संलग्न किया है।

पूर्ण परिणाम (फ़ाइल vector-benchmarks.csv) बेंचमार्किंग कोड (फ़ाइल tests/benchmarks/vectorRemoval.cpp) here के साथ गिटहब पर उपलब्ध हैं।

कृपया ध्यान रखें कि ये परिणाम मेरे कंप्यूटर, मेरे कंपाइलर आदि पर प्राप्त हुए हैं - आपके मामले में वे अलग-अलग होंगे (विशेष रूप से जब यह उस बिंदु पर आता है जिसमें एक एल्गोरिदम दूसरे से बेहतर होता है)।

मैंने वर्चुअलबॉक्स के शीर्ष पर फेडोरा 24 पर -O3 के साथ जीसीसी 6.1.1 का उपयोग किया है।