relational operator overloading not working in C++

Question

I am trying to implement Huffman encoding in C++ using custom made priority_queue. I am storing the information in structure named Node. Here is the code

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
//two same name functions are for min heap and max heap(Function overloading)
struct Node{
    char letter;
    int value;
    Node* left;
    Node* right;
    Node(char letter,int value, Node* left,Node* right){
        this->letter = letter;
        this->value = value;
        this->left = left;
        this->right = right;
    }

    bool operator < (const Node* &a){//HERE IS THE PROBLEM
        if((this->value) < (a->value))
            return true;
        else
            return false;
    }

    bool operator > (const Node* &a){//HERE IS THE PROBLEM
        if((this->value) > (a->value))
            return true;
        else
            return false;
    }
};

template <class T>
class Priority_Queue{

    public:
    int k;
    int sz;
    vector<T> v;

    Priority_Queue(int k){
        sz = 0;
        this->k = k;
    }

    void heapify(int index,int n){
        int max_index = index;
        for(int i = index*k+1;i <= min(n-1,index*k+k);++i){
            if(v[i] > v[max_index])
                max_index = i;
        }
        if(index != max_index){
            swap(v[max_index],v[index]);
            heapify(v,max_index,n);
        }
    }

    void heapify(vector<int> &v,int index,int n,bool trigger){
        //for calling min_heapify using function overloading
        int min_index = index;
        for(int i = index*k+1;i <= min(n-1,index*k+k);++i){
            if(v[i] < v[min_index])
                min_index = i;
        }
        if(index != min_index){
            swap(v[min_index],v[index]);
            heapify(v,min_index,n,trigger);
        }
    }   

    void Insert(T val){
        if(sz == (int)v.size()){
            v.push_back(val);
            ++sz;
        }
        else
            v[sz++] = val;
        int parent = (sz-1)/k;
        int node = sz-1;
        while(node >= 1){
            int parent = (node-1)/k;
            if(v[parent] < v[node]){
                swap(v[parent],v[node]);
                node = parent;
                parent = (parent-1)/k;
            }
            else
                break;
        }
    }

    void Insert(T val, bool trigger){
        if(sz == (int)v.size()){
            v.push_back(val);
            ++sz;
        }
        else
            v[sz++] = val;
        int parent = (sz-1)/k;
        int node = sz-1;
        while(node >= 1){
            int parent = (node-1)/k;
            if(v[parent] > v[node]){// IF CONDITION DOESN'T WORK
                swap(v[parent],v[node]);
                node = parent;
                parent = (parent-1)/k;
            }
            else
                break;
        }
    }

    void Pop(){
    if(sz == 0){
            cout << "Heap Underflow\n";
            return;
        }
        swap(v[0],v[sz-1]);
        --sz;
        heapify(0,sz);

    }

    void Pop(bool trigger){
        if(sz == 0){
            cout << "Heap Underflow\n";
            return;
        }
        swap(v[0],v[sz-1]);
        --sz;
        heapify(0,sz,trigger);
    }

    T Top(){
        return v[0];
    }

    void printHeap(){
        for(int i = 0; i < sz;++i){
            cout << v[i]->value << " ";
        }
        cout << "\n";
    }

};

int main()
{
    string s;
    cin >> s;
    int n = s.length();
    vector<int> freq(26,0);
    for(int i = 0; i < n;++i){
        ++freq[s[i]-'a'];
    }
    Priority_Queue<Node*> pq(2);
    for(int i = 0; i < 26;++i){
        if(freq[i] == 0)
            continue;
        pq.Insert(new Node(char(i+'a'),freq[i],NULL,NULL),true);
    }
    pq.printHeap();
}

I don't have much experience with C++ and I am having trouble overloading relational operators where I want to compare two structure pointers based on the value parameter.For example: if I enter aab , the if condition in Insert function should be executed but it never happens. I searched up a lot regarding overloading of relational operators but none of them seem to fix the issue I am facing. Can someone please help me ? What am I doing wrong while overloading the operator?

What exactly is the problem? Are you getting an error? The wrong result? — Mureinik, Feb 19 '21 at 14:19
Your overloading is about comparing `Node` and `const Node*`. Your `Priority_Queue` should accept comparator like [`std::priority_queue`](https://en.cppreference.com/w/cpp/container/priority_queue). — MikeCAT, Feb 19 '21 at 14:19
Pointers are not objects, Node and const Node* are different things. — john, Feb 19 '21 at 14:20
I am getting wrong answer. As I said, the if condition in the Insert function doesn't become true for the example I wrote . I am sure the operator overloading is at fault. Removing const keyword also doesn't help :( — nmnsharma007, Feb 19 '21 at 14:21
I don't know how I would accept comparators .I searched up that too :( — nmnsharma007, Feb 19 '21 at 14:23
You have written operators that compare `Node` to `Node*`. Your priority queue compares `Node*` to `Node*`. — molbdnilo, Feb 19 '21 at 14:24
So, I should write the overload function outside the structure? — nmnsharma007, Feb 19 '21 at 14:25
@nmnsharma007 No, you cannot change the way C++ compares pointers. You have two choices, stop using pointers, or write your code to accept a custom comparator object. — john, Feb 19 '21 at 14:27
No, you should overload for comparison between two `Node`s, and use a `Priority_Queue`. — molbdnilo, Feb 19 '21 at 14:27
Oh ! So, relational operators cannot be overloaded for pointers , right? And how can I pass a comparator to a function like STL priority queue does? — nmnsharma007, Feb 19 '21 at 14:29
not sure if it will help, but here you can find a nice overview for operator overloading https://stackoverflow.com/questions/4421706/what-are-the-basic-rules-and-idioms-for-operator-overloading — 463035818_is_not_an_ai, Feb 19 '21 at 14:29
@nmnsharma007 It's not possible to overload any operator for built in types (including pointers). You can't fundamentally change the language like that. — john, Feb 19 '21 at 14:33
Ah ok. that makes sense . So it means, pointers have some default way of being compared right? — nmnsharma007, Feb 19 '21 at 14:35
@nmnsharma007 Yes, essentially the addresses of the two pointers are compared. i.e. it is the pointers themselves that are being compared, not what they are pointing to. — john, Feb 19 '21 at 14:43
Oh OK. Thanks . Apparently, overload didn't work at all and neither gave an error for comparing builtin types. Can u tell me how would I pass a comparator object to a function like STL priority queue does?Do I need to make an object or a just a comparator like I made above? — nmnsharma007, Feb 19 '21 at 14:45
Your code was just using the default pointer comparison, which is why you got no error, but also it didn't work. It would take a little bit too long to explain how to pass a comparator like the STL. These objects are generally knowns as *functors*, maybe you could google that. — john, Feb 19 '21 at 14:52
Yea sure, I heard about functors once but they looked scary. Maybe it's time to learn them finally. Thanks a lot for your help . I really appreciate it ^_^ — nmnsharma007, Feb 19 '21 at 14:54
@nmnsharma007 To be precise your overload was comparing a `Node` with a `Node*`. That is legal (but fairly useless), two pointers would have been illegal however. — john, Feb 19 '21 at 14:54
So, a structure and a pointer can be compared ? On what basis? The address they hold? — nmnsharma007, Feb 19 '21 at 14:56

Joseph Larson · Accepted Answer · 2021-02-19T14:33:24.707

1

You probably should make your method look like this:

bool operator<(const Node &node) const {
   return value < node.value;
}

Notice the slightly different method signature. And then you should test it with an absolutely minimal method.

int main(int, char **) {
     Node first{'a', 10, nullptr, nullptr};
     Node second{'b', 5, nullptr, nullptr};

     cout << "first < second: " << (first < second) << endl;
     cout << "second < first: " << (second < first) << endl;
}

In your code, you might have to do this:

if (*v[index] < *v[otherIndex)

Another comment: don't name variables like v. That's going to bite you in the backside as your programs get bigger. Give them longer names that are more searchable and descriptive. vec is better than v.

edited Feb 19 '21 at 14:33

answered Feb 19 '21 at 14:30

Joseph Larson

8,530
1
19
36

OPs priority queue holds a vector of `Node*` not a vector of `Node`s – 463035818_is_not_an_ai Feb 19 '21 at 14:31
Ah, you're right. I'll modify the answer slightly. – Joseph Larson Feb 19 '21 at 14:32
Your overload method should be const. – john Feb 19 '21 at 14:32
why use abbreviations? How is `vec` better than `v`? I'd vote for `data`, at least make it a name, not the abbreviation of the actual name – 463035818_is_not_an_ai Feb 19 '21 at 14:33
@largest_prime_is_463035818 Vec is at least a LITTLE more searchable than v. And everyone has opinions on naming conventions. Note that I wouldn't necessarily use vec, either, but I was just trying to illustrate what I was trying to say. – Joseph Larson Feb 19 '21 at 14:34
hm ok. opinion based. But consider that `vec` isnt that searchable when the code uses `vector`s – 463035818_is_not_an_ai Feb 19 '21 at 14:35
1

I will improve my variable names . I agree with u on that :) – nmnsharma007 Feb 19 '21 at 14:36
@largest_prime_is_463035818 It's still better than v. As we don't really know what the data really is, coming up with a better name is trick. Data isn't that great, either. nodeVector is probably better than any of the above. – Joseph Larson Feb 19 '21 at 14:37

relational operator overloading not working in C++

1 Answers1