Rimozione di duplicati da un vettore non ordinabile

Question

Sto cercando un modo per rimuovere i duplicati da un vettore (chiamiamolo theGreatVector: D). Non riesco a usare std :: sort seguito da std :: unique perché non c'è modo di ordinare i miei oggetti.

theGreatVector contiene alcuni vector<Item*> (smallVectors)

ho avuto un sovraccarico di == per vector<Item*> così posso usarlo

sono in grado di creare qualcosa in O (n²), ma ho bisogno di tempo l'efficienza (theGreatVector.size() potrebbe essere 10⁵ o 10⁶)

in questo momento quello che ho ottenuto è qualcosa di simile (riempio il mio vettore solo se smallOne isnt in esso):

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

Se c'è un modo per farlo anche in nlog (n) + n o qualcosa di inferiore a n², sarebbe fantastico!

Grazie mille

AZH

Answer 1

Si può sempre std::tie ogni membro dati in un std::tuple e utilizzare ordinamento lessicografico da quello di ordinare un vettore di puntatori per la struttura Big Data. È quindi possibile fare std::unique su quella struttura dati prima di copiare l'output. Con una piccola modifica è anche possibile rimuovere i duplicati in posizione ordinando direttamente il grande vettore 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

Date un'occhiata a insieme non ordinato: http://www.cplusplus.com/reference/unordered_set/unordered_set/ sembra di fare quello che vuoi. Gli inserimenti per singoli elementi vengono eseguiti in O (1) in media, O (n) nel peggiore dei casi, solo l'operatore di uguaglianza deve essere fornito.