确定的无序矢量＆lt; T＆GT;拥有各种独特的元素 [英] Determining if an unordered vector<T> has all unique elements

问题描述

剖析我的CPU绑定的code已建议我是花很长的时间来检查，看是否有容器包含完全独特的元素。假设我有无序的元素一些大型集装箱（与＆LT; 和 = 中定义），我有两个想法这是如何完成：

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 < and = defined), I have two ideas on how this might be done:

在使用一组第一：

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

第二个循环过的元素：

The second looping over the elements:

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 ）时间，如果所有的元素都是唯一的。

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 X[0]==X[1] but takes (understandably) O(N^2) time if all the elements are unique.

有没有更好的方式来做到这一点，也许是专为这个目的一个STL的算法？如果不是，是否有什么建议伊克出多一点的效率？

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?

推荐答案

您第一个例子应该是O（N日志N）的设置需要日志N时间为每个插入。我不认为一个更快的O的可能。

Your first example should be O(N log N) as set takes log N time for each insertion. I don't think a faster O is possible.

第二个例子显然是O（N ^ 2）。系数和存储器使用率较低，所以它可能是快（或即使是最快的）在一些情况下

The second example is obviously O(N^2). The coefficient and memory usage are low, so it might be faster (or even the fastest) in some cases.

这要看是什么 T 是，但是对于一般的表现，我建议你整理指针向量的对象。

It depends what T is, but for generic performance, I'd recommend sorting a vector of pointers to the objects.

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风格，

or in STL style,

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

---

如果你可以重排原有的载体，当然，

---

And if you can reorder the original vector, of course,

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

这篇关于确定的无序矢量＆lt; T＆GT;拥有各种独特的元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！