为什么我使用STL sort()进行二次时间排序？

Question

我试图使用STL sort()函数按照存储在地图中的值对对象矢量进行排序.令我惊讶的是,我的算法在二次时运行.我尽可能地简化它,试图找出一个明显的错误,但无济于事.这是简化版本:

#include <map>
#include <vector>
#include <algorithm>

using namespace std;

struct a{
  map<a*,float> vals;
  bool operator()(a* a1, a* a2){return (vals[a1]>vals[a2]);}
  void asort();
};

void a::asort(){
  vector<a*> v;
  map<a*,float>::iterator it = vals.begin();
  for(;it!=vals.end();it++){v.push_back((*it).first);}
  sort(v.begin(),v.end(),*this);
}

int main(){
  a a0;
  int imax=8000;
  for(int i=0;i<imax;i++){a0.vals[new a]=rand();}
  a0.asort();
}

当我为imax = 2000,4000,8000运行它时,它分别需要大约1s,4s,18s.这怎么可能？为什么我没有得到预期的imax*log(imax)依赖？我对C++的经验有限,请帮忙!谢谢!

更新:谢谢Xeo,Rick和所有回复的人.正如Xeo和Rick所解释的那样,问题在于比较器(在我的情况下struct a,包含值的映射)会在每次比较时被复制,因此计算复杂性O(imax^2 log(imax)).我可以看到的一种解决方法(使我的代码更改最小)是使用指向地图的指针,即map<a*,float>* vals代替map<a*,float> vals.然后避免地图复制,并且复杂性又回到了O(imax log(imax)).非常感谢!

Answer 1

std::sort以价值来表达其谓词

sort(v.begin(),v.end(),*this);
//                     ^^^^^

将复制包含的地图.

接下来,您在比较期间进行了两次地图查找,即O(log N)预期这pred(a,b)是一个常量操作.

可以通过定义一个单独的比较器,用于解决此问题std::sort,并使用std::unordered_map(C++ 11).