-2

I am trying to write a templated function named unique() that detects if a std::vector only has unique elements, using only the <vector>, <set> and <iostream> headers. 

template <typename T>
bool unique(const std::vector<T>& container){}

How can I manage to do this?

Remy Lebeau
  • 555,201
  • 31
  • 458
  • 770
cppp2020
  • 7
  • 1

2 Answers2

5

This is actually quite easy if you can use std::set. Since std::set will only store unique items you can create a std::set from the std::vector and compare their sizes. If they match then the vector has unique elements. That would look like

template <typename T>
bool unique(const std::vector<T>& container)
{
    return container.size() == std::set<T>{container.begin(), container.end()}.size();
}
NathanOliver
  • 171,901
  • 28
  • 288
  • 402
  • Oh I got it now. The set stream is quite useful – cppp2020 Jan 30 '20 at 20:22
  • @cppp2020 Yes, the iterator pair constructor can be quite useful. It should be noted that this is O(NlogN) complexity and uses O(N) space. Not exactly efficient, but it does pretty well. A `std::unordered_set` takes it down to O(N) complexity. – NathanOliver Jan 30 '20 at 20:30
  • The question is almost a duplicate. At lease the answer certainly is: [What's the most efficient way to erase duplicates and sort a vector?](https://stackoverflow.com/q/1041620/10147399) – Aykhan Hagverdili Jan 30 '20 at 20:40
  • Note that set's require that the objects are less than comparable. So you need to provide this for T's that don't have it. Might be faster to copy the vector, sort it, and look for sequential matches. sets do a lot of heap allocation. – doug Jan 30 '20 at 23:26
2
std::set<T> other{ container.begin(), container.end() );
return other.size() < container.size();

You can also break out early.

std::set<T> other;
for (auto&& e:container)
  if (!other.insert( e ).second)
    return false;
return true;
Yakk - Adam Nevraumont
  • 262,606
  • 27
  • 330
  • 524