एक गैर-क्रमबद्ध वेक्टर

Question

से डुप्लिकेट को हटा रहा है मैं एक वेक्टर से डुप्लिकेट को हटाने का एक तरीका ढूंढ रहा हूं (उसे उसे GreatVector: D) कहें। मैं std :: sort का उपयोग नहीं कर सकता, इसके बाद std :: अद्वितीय है क्योंकि मेरी ऑब्जेक्ट्स को सॉर्ट करने का कोई तरीका नहीं है।

theGreatVector कुछ vector<Item*> (smallVectors)

मैं vector<Item*> के लिए == की एक अधिभार मिला तो मैं उपयोग कर सकते हैं

मैं सक्षम डी ओ (n²) में कुछ बनाना चाहता हूँ होता है, लेकिन मैं समय दक्षता की जरूरत है (theGreatVector.size() 10⁵ हो सकता है या 10⁶)

अभी मैं क्या मिल गया है कि की तरह कुछ है (मेरे वेक्टर मैं भरने केवल अगर यह में smallOne नहीं है):

for(i=0;i<size;i++) 
{ 
    vector<Item*>smallOne = FindFacets(i) 
    if(smallOne doesnt belong to GreatOne) // this line already in O(n) :/ 
    { 
    theGreatOne.push_back(smallOne); 
    } 
} 

यदि नलॉग (एन) + एन या एन² से कम कुछ भी करने के लिए ऐसा कोई तरीका है, तो यह बहुत अच्छा होगा!

धन्यवाद एक बहुत

Azh

Answer 1

आप कर सकते हैं हमेशा std::tie में हर डेटा सदस्य एक std::tuple और अपने बड़े डेटा संरचना की ओर इशारा का एक वेक्टर सॉर्ट करने के लिए उस पर कोषगत आदेश का उपयोग करें। आउटपुट की प्रतिलिपि बनाने से पहले आप उस डेटा संरचना पर std::unique कर सकते हैं। एक छोटे से संशोधन के साथ आप बड़े Item वेक्टर को सीधे क्रमबद्ध करके डुप्लीकेट को भी हटा सकते हैं।

#include <tuple> 
#include <memory> 
#include <vector> 

// tuples have builtin lexicographic ordering, 
// I'm assuming all your Item's data members also have operator< 
bool operator<(Item const& lhs, Item const& rhs) 
{ 
    return std::tie(lhs.first_data, /*...*/ lhs.last_data) < std::tie(rhs.first_data, /*...*/ rhs.last_Data); 
} 

int main() 
{ 
    // In the Beginning, there was some data 
    std::vector<Item> vec; 
    // fill it 

    // init helper vector with addresses of vec, complexity O(N) 
    std::vector<Item*> pvec; 
    pvec.reserve(vec.size()); 
    std::transform(std::begin(vec), std::end(vec), std::back_inserter(pvec), std::addressof<Item>); 

    // sort to put duplicates in adjecent positions, complexity O(N log N) 
    std::sort(std::begin(pvec), std::end(pvec), [](Item const* lhs, Item const* rhs){ 
     return *lhs < *rhs; // delegates to operator< for Item 
    });  

    // remove duplicates, complexity O(N) 
    auto it = std::unique(std::begin(pvec), std::end(pvec), [](Item const* lhs, Item const* rhs){ 
     return *lhs == *rhs; // assumes Item has operator==, if not use std::tuple::operator== 
    }); 
    pvec.erase(it, std::end(pvec)); 

    // copy result, complexity O(N) 
    std::vector<Item> result; 
    result.reserve(pvec.size()); 
    std::transform(std::begin(pvec), std::end(pvec), std::back_inserter(result), [](Item const* pelem){ 
     return *pelem; 
    }); 

    // And it was good, and done in O(N log N) complexity 
} 

Answer 2

अव्यवस्थित सेट पर एक नज़र डालें: http://www.cplusplus.com/reference/unordered_set/unordered_set/ यह है कि तुम क्या चाहते हो रहा है। एकल तत्वों के लिए सम्मिलन औसतन (1) में किया जाता है, ओ (एन) सबसे खराब मामले में, केवल समानता ऑपरेटर को प्रदान करने की आवश्यकता होती है।