Usuwanie duplikatów z nie sortowalnego wektora

Question

Szukam sposobu na usunięcie duplikatów z wektora (pozwala nazywać go GreatVector: D). Nie mogę użyć std :: sort, po którym następuje std :: unique, ponieważ nie ma sposobu na sortowanie moich obiektów.

theGreatVector zawiera kilka vector<Item*> (smallVectors)

mam przeciążenie == dla vector<Item*> więc można go używać

jestem w stanie stworzyć coś de O (n²), ale muszę efektywności czasowej (theGreatVector.size() może być 10⁵ lub 10⁶)

teraz co mam jest coś takiego (wypełniam moje wektorze tylko jeśli smallOne isnt w nim):

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

Jeśli istnieje sposób, aby to zrobić, nawet w nlog (n) + n lub cokolwiek niższym niż n², byłoby świetnie!

Thanks a lot

AZH

Answer 1

Można zawsze std::tie każdy członek danych do std::tuple i używać leksykograficzny zamawianie na tym, by uporządkować wektor wskaźników do swojej wielkiej struktury danych. Następnie możesz wykonać std::unique na tej strukturze danych przed skopiowaniem danych wyjściowych. Dzięki niewielkiej modyfikacji możesz również usunąć duplikaty na miejscu, bezpośrednio sortując duży wektor 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

Spójrz na nieuporządkowanej zestawie: http://www.cplusplus.com/reference/unordered_set/unordered_set/ wydaje się robić to, co chcesz. Wstawienia dla pojedynczych elementów są wykonywane w O (1) średnio, O (n) w najgorszym przypadku, tylko operator równości musi być zapewniony.