Entfernen von Duplikaten aus einem nicht sortierbaren Vektor

Question

Ich bin auf der Suche nach einer Möglichkeit, Duplikate aus einem Vektor zu entfernen (nennen wir ihn den GroßenVektor: D). Ich kann nicht std :: sort gefolgt von std :: unique verwenden, da es keine Möglichkeit gibt, meine Objekte zu sortieren.

theGreatVector enthält einige vector<Item*> (smallVectors)

ich eine Überlastung von == bekam für vector<Item*>, so kann ich es verwenden

Ich bin in der Lage de etwas in O (n²) erstellen, aber ich brauche Zeiteffizienz (theGreatVector.size() könnte 10⁵ oder 10⁶)

Gerade jetzt, was ich habe ist etwas wie das (i füllen mein Vektor nur, wenn smallOne ist nicht drin):

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); 
    } 
} 

Wenn es eine Möglichkeit gibt, das auch in nlog (n) + n oder etwas niedriger als n² zu tun, wäre das großartig!

Vielen Dank

Azh

Answer 1

Sie können immer std::tie jedes Datenelement in eine std::tuple und lexikographische Ordnung auf, dass verwenden, um einen Vektor von Zeigern auf Ihre große Datenstruktur zu sortieren. Sie können dann std::unique auf dieser Datenstruktur vor dem Kopieren der Ausgabe tun. Mit einer kleinen Modifikation können Sie die Duplikate auch entfernen, indem Sie den großen Item Vektor direkt sortieren.

#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

einen Blick auf ungeordnete Menge Nehmen: http://www.cplusplus.com/reference/unordered_set/unordered_set/ es, was Sie wollen zu tun scheint. Einfügungen für einzelne Elemente werden im Durchschnitt in O (1) durchgeführt, O (n) im schlechtesten Fall muss nur ein Gleichheitsoperator bereitgestellt werden.