Почему я получаю квадратичную сортировку по времени с помощью 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, это занимает около 1 с, 4 с, 18 с соответственно. Как это возможно? Почему я не получаю ожидаемую зависимость imax*log(imax)? У меня ограниченный опыт работы с C++, пожалуйста, помогите! Спасибо!

Обновление: спасибо Ксео, Рик и всем, кто откликнулся. Как объясняли Ксео и Рик, проблема в том, что компаратор (в моем случае 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 Вероятно, основано на быстрой сортировке, производительность которой в худшем случае - предварительная сортировка входных данных.