c++ - 确定无序 vector<T> 是否具有所有唯一元素

Question

分析我的 cpu 绑定(bind)代码建议我花很长时间检查容器是否包含完全独特的元素。假设我有一些未排序元素的大型容器(定义了 < 和 =)，我对如何做到这一点有两个想法:

第一次使用集合:

template <class T>
bool is_unique(vector<T> X) {
  set<T> Y(X.begin(), X.end());
  return X.size() == Y.size();
}

第二次循环遍历元素:

template <class T>
bool is_unique2(vector<T> X) {
  typename vector<T>::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;
}

我已经尽我所能对它们进行了测试，从阅读有关 STL 的文档中收集到的信息，答案是(像往常一样)，这取决于。我认为在第一种情况下，如果所有元素都是唯一的，它会非常快，但如果退化很大，则操作似乎需要 O(N^2) 时间。对于嵌套迭代器方法，相反的情况似乎是正确的，如果 X[0]==X[1]但如果所有元素都是唯一的，则需要(可以理解的)O(N^2) 时间。

有没有更好的方法来做到这一点，也许是为此目的而构建的 STL 算法？如果没有，有什么建议可以提高效率吗？

Answer 1

您的第一个示例应该是 O(N log N)，因为 set 每次插入都需要 log N 时间。我认为更快的 O 是不可能的。

第二个例子显然是O(N^2)。系数和内存使用率较低，因此在某些情况下可能会更快(甚至最快)。

这取决于 T 是什么，但为了通用性能，我建议对指向对象的指针 vector 进行排序。

template< class T >
bool dereference_less( T const *l, T const *r )
 { return *l < *r; } 

template <class T>
bool is_unique(vector<T> const &x) {
    vector< T const * > vp;
    vp.reserve( x.size() );
    for ( size_t i = 0; i < x.size(); ++ i ) vp.push_back( &x[i] );
    sort( vp.begin(), vp.end(), ptr_fun( &dereference_less<T> ) ); // O(N log N)
    return adjacent_find( vp.begin(), vp.end(),
           not2( ptr_fun( &dereference_less<T> ) ) ) // "opposite functor"
        == vp.end(); // if no adjacent pair (vp_n,vp_n+1) has *vp_n < *vp_n+1
}

或采用 STL 风格，

template <class I>
bool is_unique(I first, I last) {
    typedef typename iterator_traits<I>::value_type T;
    …

---

如果你可以重新排序原始 vector ，当然，

template <class T>
bool is_unique(vector<T> &x) {
    sort( x.begin(), x.end() ); // O(N log N)
    return adjacent_find( x.begin(), x.end() ) == x.end();
}