make_heap 和对比较器的 C++ 编译错误

Question

我正在尝试在 C++ 中的 class 中的邻接矩阵旁边构建一个邻居列表。我正在尝试使用 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 studio17\community\vc\tools\msvc.12.25827\include\xutility(1017): error C2064: term does not evaluate to a function taking 2 arguments
1>c:\program files (x86)\microsoft visual studio17\community\vc\tools\msvc.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 studio17\community\vc\tools\msvc.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 studio17\community\vc\tools\msvc.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 studio17\community\vc\tools\msvc.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

根据 STL，您必须提供带有签名的比较函数

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

但是你指定了一个带有签名的函数

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

你看出区别了吗？

Answer 2

您的比较器函数需要是静态的。非静态成员函数有一个隐式参数传递给它。（this 指针）。

在您的情况下，您实际上不需要 this 指针，因为您没有在比较器函数中引用任何成员变量。

make_heap 和对比较器的 C++ 编译错误

C++ compile errors with make_heap and pair comparator

c++

stl

std-pair