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

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运行它时，它分别需要大约1、4、18秒。这怎么可能？为什么我不能得到预期的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)来解决此问题。

Answer 2

映射已排序。std::sort可能是基于Quicksort的，其最坏的性能是当输入被预排序时。