相关疑难解决方法(0)

C++ 11标准保证在最坏的情况下std::sort具有O(n logn)复杂度 .这与C++ 98/03中的平均情况保证不同,可以使用Quicksort实现(可能与小n的插入排序结合使用),在最坏的情况下具有O(n ^ 2)(对于某些特定情况)输入,例如排序输入).std::sort

std::sort不同的STL库中的实现是否有任何变化？C++ 11如何std::sort在不同的STL中实现？

分析我的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)时间.

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