The best way to count a unique item

Question

I just find a way to count the number of unique elements in a vector. This is my most naive approach.

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

Is it the only one with or is it better in the standard library?

Answer 1

It may depend on what you mean by “better,” but of course there are ways that are simpler and other ways that are probably faster.

The easiest way is to insert elements into std::set or std::unordered_set . When you inserted all of them, the size of the set will be the number of unique elements.

Probably a faster method is to use std::sort and std::unique to find unique elements in place instead of copying them. This is pretty much what std::unique_copy will usually do internally, but doing it in place saves a fair amount of distribution and copying.

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

here I create a hash on vector iterators that hash and compare with the underlying elements (do not pass it to the .end() iterator).

Then I insert the iterators from the set into it and ask it how big it is.

Instead, we could use std::set<Iterator, iterator_less> or something if you prefer.