确定无序向量是否具有所有唯一元素

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

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

这取决于什么 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();
}

如果要快速确定向量是否只有唯一元素,则必须对向量进行排序。否则,最好是O(n^2)运行时或O(n Log n)运行时带O(n)空间。我认为最好编写一个假设输入已排序的函数。

template<class Fwd>
bool is_unique(In first, In last)
{
    return adjacent_find(first, last) == last;
}

然后让客户机对向量进行排序,或者制作向量的排序副本。这将为动态编程打开一扇门。也就是说,如果客户机在过去对向量进行了排序,那么他们可以选择保留并引用排序后的向量,这样他们就可以为O(N)运行时重复此操作。

标准库有 std::unique ,但这需要您复制整个容器(注意,在两个示例中,您也复制了整个向量,因为不必要地按值传递向量)。

template <typename T>
bool is_unique(std::vector<T> vec)
{
    std::sort(vec.begin(), vec.end());
    return std::unique(vec.begin(), vec.end()) == vec.end();
}

这是否比使用 std::set 如你所知,将取决于:—)。

仅仅使用一个提供这种“保证”的容器是不可行的吗?在插入时而不是将来某个时候标记一个副本是否有用?当我想做这样的事情时,这就是我前进的方向;仅仅使用集合作为“主”容器,如果我需要保持原始顺序,可以构建一个并行向量,但是当然,这对内存和CPU可用性做了一些假设…

一方面,您可以将两者的优点结合起来:如果已经发现了一个副本,请停止构建集合:

template <class T>
bool is_unique(const std::vector<T>& vec)
{
    std::set<T> test;
    for (typename std::vector<T>::const_iterator it = vec.begin(); it != vec.end(); ++it) {
        if (!test.insert(*it).second) {
            return false;
        }
    }
    return true;
}

顺便说一句, Potatoswatter 很好地指出,在一般情况下,您可能希望避免复制t,在这种情况下,您可能会使用 std::set<const T*, dereference_less> 相反。

当然,如果它不是通用的,您可能会做得更好。例如,如果你有一个已知范围的整数向量,如果一个元素存在,你可以在一个数组(甚至是位集)中进行标记。

你可以使用 std::unique ,但它要求首先对范围进行排序:

template <class T>
bool is_unique(vector<T> X) {
  std::sort(X.begin(), X.end());
  return std::unique(X.begin(), X.end()) == X.end();
}

STD:独特的 修改序列并将迭代器返回到唯一集的结尾,因此如果这仍然是向量的结尾,那么它必须是唯一的。

它以nlog(n)运行;与您的设置示例相同。虽然使用C++ 0x,但我认为理论上不能保证更快地完成它。 std::unordered_set 而不是 std::set 将在预期的线性时间内完成这项工作-但这要求您的元素不仅具有 operator == 定义,这可能不那么容易。

另外,如果您没有在示例中修改向量,那么您可以通过传递const reference来提高性能,这样就不会对它进行不必要的复制。

如果我可以自己加2美分。

首先,作为 @Potatoswatter 注意,除非您的元素的复制成本很低(内置/小豆荚),否则您将希望使用指向原始元素的指针,而不是复制它们。

第二,有两种策略可用。

1. 只需确保在第一个位置没有插入副本。当然,这意味着控制插入,这通常是通过创建一个专用类(以向量作为属性)来实现的。
2. 每当需要属性时,检查是否有重复项

我必须承认我会倾向于第一个。封装,明确职责分离等等。

不管怎样,根据需求有很多种方法。第一个问题是:

• 我们必须让元素 vector 在一个特定的秩序,还是我们可以“混乱”与他们?

如果我们能搞砸他们,我建议 矢量 排序: Loki::AssocVector 你应该开始了。 如果不是,那么我们需要在结构上保留一个索引来确保这个属性…等一下: Boost.MultiIndex 救援?

第三:正如你所说,一个简单的线性搜索加倍得到O(N ^二 )平均来说,这是不好的。

如果 < 已经定义了,那么排序是显而易见的,具有O(n log n)复杂性。 这也可能是值得的 T hashable,因为 std::tr1::hash_set 可能会有更好的时间(我知道,你需要一个RandoAccessIterator,但是如果 T 是可哈希的,那么很容易拥有 T* 可哈希到;()

但归根结底,真正的问题是,我们的建议是必要的一般性的,因为我们缺乏数据。

• 是什么 T ,是否希望该算法是通用的?
• 元素的数量是多少?10,100,10.000,1.000.000?因为在处理几百个问题时,渐进复杂性是没有意义的。
• 当然:您能确保插入时的唯一性吗?你能修改向量本身吗?

嗯,你的第一个应该只吃 N log(N) 因此,对于这个应用程序来说,这显然是更好更糟的情况。

但是,如果在向集合中添加内容时进行检查,则应该能够获得更好的最佳情况:

template <class T>
bool is_unique3(vector<T> X) {
  set<T> Y;
  typename vector<T>::const_iterator i;
  for(i=X.begin(); i!=X.end(); ++i) {
    if (Y.find(*i) != Y.end()) {
      return false;
    }
    Y.insert(*i);
  }
  return true;
}

这个应该有 O(1) 最佳案例, O(N log(N)) 最坏情况和平均情况取决于输入的分布。

如果存储在向量中的类型t很大,并且复制它的成本很高,那么可以考虑为向量元素创建指针或迭代器的向量。根据指向的元素对其进行排序,然后检查其唯一性。

您也可以使用std::set。模板如下

template <class Key,class Traits=less<Key>,class Allocator=allocator<Key> > class set

我认为您可以提供适当的traits参数并为speed插入原始指针,或者使用<运算符为指针实现一个简单的包装类。

不要使用构造函数插入到集合中。使用插入方法。方法(重载之一)具有签名

pair <iterator, bool> insert(const value_type& _Val);

通过检查结果(第二个成员),通常可以比插入所有元素更快地检测重复的元素。

在(非常)特殊的情况下,用已知的、不太大的、最大值n对离散值进行排序。
您应该能够开始一个bucket排序,并简单地检查每个bucket中的值的数量是否低于2。

bool is_unique(const vector<int>& X, int N)
{
  vector<int> buckets(N,0);
  typename vector<int>::const_iterator i;
  for(i = X.begin(); i != X.end(); ++i)
    if(++buckets[*i] > 1)
      return false;
  return true;
}

这样做的复杂性是O(n)。

使用当前的C++标准容器,在第一个示例中有一个很好的解决方案。但是如果您可以使用散列容器,您可能会做得更好,因为散列集将是n O(1)而不是N o(对数n)表示标准集。当然,一切都将取决于n的大小和特定的库实现。