Problem with operator <

Question

Hi , I have a problem with the operator < that i wrote:

in Node.h :

.
..
bool operator<(const Node<T>& other) const;
const T& GetData ();
.
..
template <class T>
const T& Node<T>::GetData () {
 return m_data;
}

template <class T>
bool Node<T>:: operator<(const Node<T>& other) const
{
 return (*(this->GetData()) < *(other.GetData()));
}

in Heap.h :

template<class T>
void Heap<T>::Insert(Node<T>* newNode) {
 if (m_heap.size() == 0) {
  m_heap.push_back(newNode);
 }
 else
  DecreaseKey(newNode);  
}

template<class T>
void Heap<T>::DecreaseKey(Node<T>* newNode) {
 m_heap.push_back(newNode);
 int index = m_heap.size();
 while ((index > 1) && (m_heap[(index/2)-1] < (m_heap[index-1]))) { // doen't do the operator < !
  Exchange(index,index/2);
  index = index/2;
 }
}

in Vehicle.h:

bool operator< (const Vehicle& otherVehicle) const;

in Vehicle.cpp:

bool Vehicle::operator<(const Vehicle& otherVehicle) const {
 return (GetDistance() > otherVehicle.GetDistance());
}

in main.cpp: .

..
 Node<Vehicle*> a(car1);
 Node<Vehicle*> b(car2);
 Heap<Vehicle*> heap;
 Node<Vehicle*>* p = &a;
 Node<Vehicle*>* q = &b;
 heap.Insert(p);
 heap.Insert(q);
 heap.ExtractMin()->GetData()->Show();
.
..

Why it doen't do the compeare ? with opeartor < , note: it pass the compiler.

Answer 1

Because you used Vehicle*, not Vehicle.

Answer 2

But i must to use Vehicle* . How I make it work (that operator < work) with Vehicle* ?

Answer 3

Use std::priority_queue instead of Heap, or any other heap that allows you to define custom comparison predicate.

Answer 4

From what I see m_heap stores pointer to Node

 while ((index > 1) && (m_heap[(index/2)-1] < (m_heap[index-1]))) { // doen't do the operator < 

I guess this should do

while ((index > 1) && (*(m_heap[(index/2)-1]) < *(m_heap[index-1]))) {

Answer 5

m_heap is a container of pointers. In this case you should dereference the node pointers:

while ((index > 1) && (*m_heap[(index/2)-1] < (*m_heap[index-1])))

This should now call operator< for Nodes, which in turn calls operator< for Vehicles.

Answer 6

Short answer: don't use pointers. You probably don't need them.

If possible, it's much easier to get this kind of code correct if you use plain objects. If you need to use the concept of a pointer, use a pointer-container class, i.e. a wrapper that is passed around as a plain object with value semantics and potentially custom overloads such as the operator< you're using, but which hides the implementation pointer internally.

That way, you don't need to deal with pointers all over your app, but only where semantically relevant.