Ошибки компиляции C++ с make_heap и компаратором пар

Question

Я пытаюсь построить список соседей рядом с матрицей смежности внутри класса в C++. Я пытаюсь взять vector<pair<int,int>> и создание кучи с помощью make_heap, но это не работает.

void Tour::buildMatrix() {
   matrix.reserve(size);
   neighborList.reserve(size);
   for (int i = 0; i < size; i++) {
      matrix.push_back(vector<int>(size));
      neighborList.push_back(vector<pair<int,int>>(size));
   }

   int distance;
   for (int i = 0; i < size; i++) {
      for (int k = i + 1; k < size; k++)
      {
         distance = calcDistance(cities[i], cities[k]);
         matrix[i][k] = matrix[k][i] = distance;
         neighborList[i][k] = (make_pair(distance, k));
         neighborList[k][i] = (make_pair(distance, i));
      }
   }

   for (int i = 0; i < size; i++) {
      make_heap(neighborList[i].begin(), neighborList[i].end(), &Tour::compare);
   }

   cout << "Done";
}

bool Tour::compare(const pair<int, int>& left, const pair<int, int>& right) {
   return left.first > right.first;
}

Я использую указатель функции для функции сравнения, и код кажется разумным, но не компилируется в Visual Studio.

Я не могу использовать функцию сравнения, и она будет работать, но не сортируется должным образом. Любая помощь будет оценена. Спасибо.

Журнал ошибок Visual Studio:

1>------ Build started: Project: TSP_Project, Configuration: Debug Win32 ------
1>Tour.cpp
1>c:\program files (x86)\microsoft visual studio\2017\community\vc\tools\msvc\14.12.25827\include\xutility(1017): error C2064: term does not evaluate to a function taking 2 arguments
1>c:\program files (x86)\microsoft visual studio\2017\community\vc\tools\msvc\14.12.25827\include\xutility(1014): note: see reference to function template instantiation 'bool std::_Debug_lt_pred<_Pr&,std::pair<int,int>&,std::pair<int,int>&>(bool(__thiscall Tour::* &)(const std::pair<int,int> &,const std::pair<int,int> &),_Ty1,_Ty2,std::_Dbfile_t,std::_Dbline_t) noexcept(<expr>)' being compiled
1>        with
1>        [
1>            _Pr=bool (__thiscall Tour::* )(const std::pair<int,int> &,const std::pair<int,int> &),
1>            _Ty1=std::pair<int,int> &,
1>            _Ty2=std::pair<int,int> &
1>        ]
1>c:\program files (x86)\microsoft visual studio\2017\community\vc\tools\msvc\14.12.25827\include\algorithm(2301): note: see reference to function template instantiation 'void std::_Pop_heap_hole_by_index<_RanIt,int,std::pair<int,int>,_Pr>(_RanIt,_Diff,_Diff,_Ty &&,_Pr)' being compiled
1>        with
1>        [
1>            _RanIt=std::pair<int,int> *,
1>            _Pr=bool (__thiscall Tour::* )(const std::pair<int,int> &,const std::pair<int,int> &),
1>            _Diff=int,
1>            _Ty=std::pair<int,int>
1>        ]
1>c:\program files (x86)\microsoft visual studio\2017\community\vc\tools\msvc\14.12.25827\include\algorithm(2310): note: see reference to function template instantiation 'void std::_Make_heap_unchecked<std::pair<int,int>*,_Fn>(_RanIt,_RanIt,_Pr)' being compiled
1>        with
1>        [
1>            _Fn=bool (__thiscall Tour::* )(const std::pair<int,int> &,const std::pair<int,int> &),
1>            _RanIt=std::pair<int,int> *,
1>            _Pr=bool (__thiscall Tour::* )(const std::pair<int,int> &,const std::pair<int,int> &)
1>        ]
1>c:\dropbox\dev\_osu\cs325\project\tsp_project\tour.cpp(64): note: see reference to function template instantiation 'void std::make_heap<std::_Vector_iterator<std::_Vector_val<std::_Simple_types<_Ty>>>,bool(__thiscall Tour::* )(const std::pair<int,int> &,const std::pair<int,int> &)>(_RanIt,_RanIt,_Pr)' being compiled
1>        with
1>        [
1>            _Ty=std::pair<int,int>,
1>            _RanIt=std::_Vector_iterator<std::_Vector_val<std::_Simple_types<std::pair<int,int>>>>,
1>            _Pr=bool (__thiscall Tour::* )(const std::pair<int,int> &,const std::pair<int,int> &)
1>        ]
1>c:\program files (x86)\microsoft visual studio\2017\community\vc\tools\msvc\14.12.25827\include\xutility(1017): error C2056: illegal expression
1>Generating Code...
1>Compiling...
1>main.cpp
1>Generating Code...
1>Done building project "Project.vcxproj" -- FAILED.
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========

Журнал ошибок g++:

In file included from /usr/include/c++/4.8.2/bits/stl_algo.h:61:0,
                 from /usr/include/c++/4.8.2/algorithm:62,
                 from Tour.hpp:16,
                 from Tour.cpp:6:
/usr/include/c++/4.8.2/bits/stl_heap.h: In instantiation of ‘void std::__adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >; _Distance = long int; _Tp = std::pair<int, int>; _Compare = bool (Tour::*)(const std::pair<int, int>&, const std::pair<int, int>&)]’:
/usr/include/c++/4.8.2/bits/stl_heap.h:448:15:   required from ‘void std::make_heap(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >; _Compare = bool (Tour::*)(const std::pair<int, int>&, const std::pair<int, int>&)]’
Tour.cpp:64:79:   required from here
/usr/include/c++/4.8.2/bits/stl_heap.h:313:40: error: must use ‘.*’ or ‘->*’ to call pointer-to-member function in ‘__comp (...)’, e.g. ‘(... ->* __comp) (...)’
        *(__first + (__secondChild - 1))))

Answer 1

Ваша функция компаратора должна быть статической. Нестатическая функция-член имеет неявный параметр, переданный ей. (The this указатель).

В вашем случае вам на самом деле не нужно this указатель, так как вы не ссылаетесь ни на одну переменную-член внутри функции сравнения.

Answer 2

Согласно STL вы должны предоставить функцию сравнения с подписью

bool cmp(const Type1 &a, const Type2 &b);

Но вы указываете функцию с подписью

bool cmp(Type1 *a, Type2 *b);

Вы видите различия?