我正在制作一个程序来分析“道路”（图形的边缘）和“城市”（图形中的节点），然后为图形的每个连接子组件打印出最小生成树。
我不允许使用 STL 库，所以我必须实现自己的最小堆。我实现了一个模板最小堆，所以我可以创建一个最低成本道路的优先级队列。在堆的弹出操作中，它还对树进行重组，使顶部最小。当我制作一个 minHeap 时它工作得很好，但是现在我试图制作一个 minHeap 的道路，它给了我以下错误：
error: no match for 'operator<=' in 'lastE <= *(((minHeap<Road>*)this)->minHeap<Road>::heap + ((sizetype)(((unsigned int)child) * 16u)))'|
以及大量警告（见下文）。
下面是 minHeap 的代码：
#ifndef MIN_HEAP
#define MIN_HEAP
template<class T>
class minHeap{
public:
minHeap(int);
void push(const T&);
void pop();
T top();
void doubleHeapCap();
bool isEmpty();
T *heap;
int heapSize;
int capacity;
};
#endif
template<class T>
minHeap<T>::minHeap(int theCapacity = 10){
if(theCapacity < 1) throw "Capacity must be >=1.";
capacity = theCapacity;
heapSize = 0;
heap = new T[capacity + 1]; //heap [0] is not used
}
template<class T>
void minHeap<T>::push(const T& e){
//inserts e into min heap
if(heapSize == capacity){ //doubles capacity if Heap is too small
this->doubleHeapCap();
this->capacity *=2;
}
int currentNode = ++heapSize;
while(currentNode != 1 && heap[currentNode/2] > e){
//bubble up node
heap[currentNode] = heap[currentNode/2]; //moves parent down
currentNode /= 2; //moves current node
}
heap[currentNode] = e;
}
template<class T>
void minHeap<T>::pop(){
//Deletes smallest element from heap and restructures heap
if(isEmpty()) throw "Heap is empty. Cannot delete.";
//deelt smallest element
heap[1].~T();
//remove last element from heap
T lastE = heap[heapSize--];
//trickle down to restructure heap
int currentNode = 1; //root of heap
int child = 2; // first child of heap
while(child <= heapSize){
//set child to smaller child of currentNode
if(child < heapSize && heap[child] > heap[child+1]) child++;
//can we put lastE in currenNode?
if(lastE <= heap[child]) break; //yes we can
//no we can't, Obama
heap[currentNode] = heap[child]; //move child up
currentNode = child; child *= 2; // move a level down
}
//after you finally find one, place the node in the corrent position
heap[currentNode] = lastE;
}
template<class T>
T minHeap<T>::top(){
return heap[1];
}
template<class T>
bool minHeap<T>::isEmpty(){
//says whether or not hear is empty
if(heapSize == 0) return 1;
else return 0;
}
template<class T>
void minHeap<T>::doubleHeapCap(){
int currentcapacity = this->capacity;
int newCapacity = (this->capacity)*2;
T *temp;
T *newHeap;
//create a new heap with twic the size
newHeap = new T[newCapacity + 1];
//copy elements over
for(int i=0; i<=capacity; i++){
newHeap[i] = this->heap[i];
}
//delete the old heap
temp = heap;
heap = newHeap;
newHeap = 0;
delete[] temp;
}
这是 main.cpp 的代码：
#include <iostream>
#include"road.h"
#include"region.h"
#include"minHeap.h"
using namespace std;
int main()
{
int numCities;
int numOldRoads;
cin >> numCities;
cin >> numOldRoads;
minHeap<Road> roadHeap(numOldRoads);
minHeap<Region> regionHeap(numCities);
for(int i=0; i<numOldRoads; i++){
int tempCityA, tempCityB;
double tempLength;
cin >> tempCityA;
cin >> tempCityB;
cin >> tempLength;
cout << "NEW ROAD: " << tempCityA << " " << tempLength << " " << tempCityB << endl;
Road *road = new Road;
road->setCityA(tempCityA);
road->setLength(tempLength);
road->setCityB(tempCityB);
roadHeap.push(*road);
}
for(int i=1; i<=roadHeap.heapSize; i++){
Road tempRoad;
tempRoad = roadHeap.top();
roadHeap.pop();
cout << "ROAD: " << tempRoad.getCityA() << " " << tempRoad.getLength() << " " << tempRoad.getCityB();
}
return 0;
}
这是 road.h 的代码：
#ifndef ROAD_H
#define ROAD_H
class Road{
public:
void setCityA(int);
const int getCityA() const;
void setCityB(int);
const int getCityB() const;
void setLength(double);
const double getLength() const;
friend bool operator<(const Road&, const Road&);
friend bool operator>(const Road&, const Road&);
friend bool operator>=(const Road&, const Road&);
friend bool operator>=(const Road&, const Road&);
private:
int cityA;
int cityB;
double length;
};
#endif
这是 road.cpp 的代码（我重载了它说我没有的运算符）：
#include"road.h"
void Road::setCityA(int x){
this->cityA = x;
}
const int Road::getCityA() const{
return this->cityA;
}
void Road::setCityB(int x){
this->cityB = x;
}
const int Road::getCityB() const{
return this->cityB;
}
void Road::setLength(double x){
this->length = x;
}
const double Road::getLength() const{
return this->length;
}
bool operator<(const Road &lhs, const Road &rhs)
{
if(lhs.getLength() < rhs.getLength()) return 1;
else return 0;
}
bool operator>(const Road &lhs, const Road &rhs)
{
if(lhs.getLength() > rhs.getLength()) return 1;
else return 0;
}
bool operator<=(const Road &lhs, const Road &rhs)
{
if(lhs.getLength() <= rhs.getLength()) return 1;
else return 0;
}
bool operator>=(const Road &lhs, const Road &rhs)
{
if(lhs.getLength() >= rhs.getLength()) return 1;
else return 0;
}
我只是努力让操作员工作（不得不处理 const 错误和诸如“cv-qualifiers and junk”之类的东西）。无论如何，在最终让它工作之后，我认为这将是复制、粘贴和修改的问题在长度上操作的运算符，但它给了我这个奇怪的错误，说我没有定义 <= 运算符
它似乎也奇怪地引用了右手边，为什么它会这样引用它？
*(((minHeap<Road>*)this)->minHeap<Road>::heap + ((sizetype)(((unsigned int)child) * 16u)))
最后这里是完整的构建消息，我觉得这里有很多信息，但是太新了，我似乎无法解析它：
warning: 'bool operator>=(const Road&, const Road&)' is already a friend of class 'Road' [enabled by default]
In instantiation of 'void minHeap<T>::pop() [with T = Road]':
|required from here
error: no match for 'operator<=' in 'lastE <= *(((minHeap<Road>*)this)->minHeap<Road>::heap + ((sizetype)(((unsigned int)child) * 16u)))'
note: candidates are:
note: template<class _T1, class _T2> bool std::operator<=(const std::pair<_T1, _T2>&, const std::pair<_T1, _T2>&)
note: template argument deduction/substitution failed:
note: 'Road' is not derived from 'const std::pair<_T1, _T2>'
note: template<class _Iterator> bool std::operator<=(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&)
note: template argument deduction/substitution failed:
note: 'Road' is not derived from 'const std::reverse_iterator<_Iterator>'
note: template<class _IteratorL, class _IteratorR> bool std::operator<=(const std::reverse_iterator<_IteratorL>&, const std::reverse_iterator<_IteratorR>&)
note: template argument deduction/substitution failed:
note: 'Road' is not derived from 'const std::reverse_iterator<_IteratorL>'
note: template<class _CharT, class _Traits, class _Alloc> bool std::operator<=(const std::basic_string<_CharT, _Traits, _Alloc>&, const std::basic_string<_CharT, _Traits, _Alloc>&)
note: template argument deduction/substitution failed:
note: 'Road' is not derived from 'const std::basic_string<_CharT, _Traits, _Alloc>'
note: template<class _CharT, class _Traits, class _Alloc> bool std::operator<=(const std::basic_string<_CharT, _Traits, _Alloc>&, const _CharT*)
note: template argument deduction/substitution failed:
note: 'Road' is not derived from 'const std::basic_string<_CharT, _Traits, _Alloc>'
note: template<class _CharT, class _Traits, class _Alloc> bool std::operator<=(const _CharT*, const std::basic_string<_CharT, _Traits, _Alloc>&)
note: template argument deduction/substitution failed:
note: mismatched types 'const _CharT*' and 'Road'
In instantiation of 'void minHeap<T>::doubleHeapCap() [with T = Road]':
required from 'void minHeap<T>::push(const T&) [with T = Road]'
required from here
warning: unused variable 'currentcapacity' [-Wunused-variable]