modo migliore per contare un articolo unico

Question

Ho appena trovato un modo per contare quel numero di elementi unici in un vettore. Questo è il mio approccio più ingenuo.

std::vector<Items> v; 

// some other work 
std::vector<Items> unique_Count; 
unique_Count.clear(); 
std::unique_copy(v.begin, v.end(), std::back_inserter(unique_Count); 
int uniqueCount = unique_Count.size(); 

È questo l'unico con o questo c'è un modo migliore nella libreria standard?

Answer 1

Può dipendere da cosa si intende per "migliore", ma ci sono sicuramente modi che sono più semplici, e altri modi che sono probabilmente più veloce.

Il modo più semplice sarebbe inserire gli articoli in std::set o std::unordered_set. Quando li hai inseriti tutti, la dimensione del set sarà il numero di oggetti unici.

Il metodo probabilmente più veloce sarebbe quella di utilizzare std::sort e std::unique per trovare gli oggetti unici "in luogo", invece che copiarli. Questo è piuttosto molto che cosa lo std::unique_copy normalmente farà internamente in ogni caso, ma farlo sul posto salva una quantità equa su allocazione e copia.

std::vector<Items> v; 

// populate v with data 

std::sort(v.begin(), v.end()); 
int uniqueCount = std::unique(v.begin(), v.end()) - v.begin(); 

Answer 2

struct iterator_hash { 
    template<class Iterator> 
    size_t operator()(Iterator it) const { 
    using value_type = typename std::decay< decltype(*it) >::type; 
    return std::hash<value_type>{}(*it); 
    } 
}; 
struct iterator_element_equals { 
    template<class Iterator> 
    size_t operator()(Iterator lhs, Iterator rhs) const { 
    return *lhs == *rhs; 
    } 
}; 
std::vector<Items> v; 
std::unordered_set<std::vector<Items>::iterator, iterator_hash, iterator_element_equals> s; 
for(auto it = v.begin(); it != v.end(); ++it) { 
    s.insert(it); // not *it 
} 
size_t uniqueCount = s.size(); 

qui crea un hash su iteratori vettoriali che hash e mette a confronto sugli elementi sottostanti (Non lo dia il .end() iteratore).

Quindi inserisco gli iteratori dal set e lo chiedo quanto è grande.

Si potrebbe invece utilizzare un std::set<Iterator, iterator_less> o qualcosa, se si preferisce.