对我的cpu绑定代码进行分析表明，我花了很长时间检查容器是否包含完全唯一的元素。假设我有一些未分类的元素（带有<和=定义），那么我对如何实现有两个想法：
<
=
首先使用一套：
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）时间。
X[0]==X[1]
有没有更好的方法可以这样做，也许是为此目的而构建的STL算法？如果没有，有什么建议可以提高效率吗？
您的第一个示例应为O（N log N），set因为每次插入都需要log N时间。我认为更快的O是不可能的。
set
第二个例子显然是O（N ^ 2）。系数和内存使用率很低，因此在某些情况下可能会更快（甚至最快）。
这取决于什么T，但是为了获得通用性能，我建议对指向对象的指针向量进行排序。
T
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; …
当然，如果您可以重新排序原始向量，
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(); }
