Operator overloading inside struct in cpp

Question

0.00/5 (No votes)

See more:

I was reading Minimum spanning tree - Kruskal with Disjoint Set Union - Competitive Programming Algorithms[^] and I am confused in below operator overloading part used in above implementation,here how we can sort without defining the comparator.

How is sorting taking Place over two structure without defining any comparator,how compiler get to know on what basis it has two sort?
When we are going to use when e1<e2 then who will call the operator overloaded <pre>+</pre>that is e1 or e2.

suppose the default comparator of STL sort using something like this
<pre> e1<e2 </pre> (e1 and e2 are of Edge type) then how are parameters passed to `bool operator<(Edge const& other)` inside struct.

What I have tried:

C++

struct Edge {
    int u, v, weight;
    bool operator<(Edge const& other) {
        return weight < other.weight;
    }
};
vector<Edge> edges;
sort(edges.begin(), edges.end());

Posted 7-Mar-19 23:44pm

kavinderrana121

Updated 16-Jan-22 22:40pm

Richard MacCutchan

v2

Add a Solution

4 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Richard MacCutchan · Answer 1 · 2019-03-08T00:14:00

The definition of the operator < allows the sort method to compare two Edge elements. The sort call takes the elements of the vector from first to last, and uses the overloaded comparator as defined in the struct, to decide which order they should be saved in. Because the less than operator is defined for the Edge type, that is the method that will be used when sort does something like:

C++

if (elem1 < elem2)
{
    // ...
}

CPallini · Answer 2 · 2019-03-08T11:51:00

Solution 2

Richard already gave you the correct answer.

As an addendum, looking at the documentation std::sort - cppreference.com[^], note the first overload of std::sort is used.

Moreover, reading this article: "Sorting a vector of custom objects in C++"[^], could be helpful.

Posted 8-Mar-19 11:51am

CPallini

Member 15502389 · Answer 3 · 2022-01-16T22:25:00

Hello, there is another method to sort vector of edges:

C++

struct Edge {
    int u, v, weight;
};

bool comp(Edge e, Edge f) {
    return e.weight < f.weight;
}

vector<Edge> edges;
sort(edges.begin(), edges.end(), comp);

After you define struct, you can use comparison function (comp) to let std::sort know how to compare your structs.

I hope this is the best solution for your problem, especially in competetive programing.

Member 15502389 · Answer 4 · 2022-01-16T22:40:00

And that's already working code for Kruskal algorithm for finding MST (obviously using Disjoint Set Union)

C++

struct Edge {
    int u, v, weight;
};

bool comp(Edge e, Edge f) {
    return e.weight < f.weight;
}

vector<Edge> edges;
int n, m, rep[n];

int Find(int v) {
    if (rep[v] == v) return v;
    return rep[v] = Find(rep[v]);
}

void Union(int u, int v) {
    rep[Find(u)] = Find(v);
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) rep[i] = i;
    for (int i = 1; i <= m; i++) {
        int u, v, weight;
        cin >> u >> v >> weight;
        edges.push_back({u, v, weight});
    }
    sort(edges.begin(), edges.end(), comp);
    for (Edge e : edges)
        if (Find(e.u) != Find(e.v))
            Union(e.u, e.v);
}

Enjoy!

Operator overloading inside struct in cpp

4 solutions

Solution 1

Solution 2

Solution 3

Solution 4

Add your solution here

Preview 0