title: Determining if an unordered vector<T> has all unique elements
body: <p>Profiling my cpu-bound code has suggested I that spend a long time checking to see if a container contains completely unique elements. Assuming that I have some large container of unsorted elements (with <code>&lt;</code> and <code>=</code> defined), I have two ideas on how this might be done:</p>
  
  <p>The first using a set:</p>
  
  <pre><code>template &lt;class T&gt;
  bool is_unique(vector&lt;T&gt; X) {
    set&lt;T&gt; Y(X.begin(), X.end());
    return X.size() == Y.size();
  }
  </code></pre>
  
  <p>The second looping over the elements:</p>
  
  <pre><code>template &lt;class T&gt;
  bool is_unique2(vector&lt;T&gt; X) {
    typename vector&lt;T&gt;::iterator i,j;
    for(i=X.begin();i!=X.end();++i) {
      for(j=i+1;j!=X.end();++j) {
        if(*i == *j) return 0;
      }
    }
    return 1;
  }
  </code></pre>
  
  <p>I've tested them the best I can, and from what I can gather from reading the documentation about STL, the answer is (as usual), it depends. I think that in the first case, if all the elements are unique it is very quick, but if there is a large degeneracy the operation seems to take O(N^2) time. For the nested iterator approach the opposite seems to be true, it is lighting fast if <code>X[0]==X[1]</code> but takes (understandably) O(N^2) time if all the elements are unique.</p>
  
  <p>Is there a better way to do this, perhaps a STL algorithm built for this very purpose? If not, are there any suggestions eek out a bit more efficiency?</p>