Some tips regarding sets and multisets

#	User	Rating
1	tourist	3757
2	jiangly	3647
3	Benq	3581
4	orzdevinwang	3570
5	Geothermal	3569
5	cnnfls_csy	3569
7	Radewoosh	3509
8	ecnerwala	3486
9	jqdai0815	3474
10	gyh20	3447

#	User	Contrib.
1	maomao90	171
2	adamant	164
3	awoo	163
4	TheScrasse	159
5	nor	155
6	maroonrk	154
7	-is-this-fft-	152
8	Petr	147
9	orz	146
10	pajenegod	145

I actually thought I had a quite good understanding of std::set and std::multiset until D of the last Div. 2 contest taught me a lesson (you can tell from my submissions on D). So I decided to write this blog to prevent other people from making similar mistakes when overloading the < operator in sets (if these are just common sense then it's probably just my skill issue). If there exists a blog that talks about similar things please do inform me.

Try to think of the output for each of the following codes.

1) (with std::set)

Code 1

#include <bits/stdc++.h>
using namespace std;

struct node{
    int l, r;
    bool operator < (node t) const& {
        return r - l < t.r - t.l;
    }
};

int main(){
    set <node> st;
    st.insert({1, 2});
    st.insert({3, 5});
    st.insert({6, 7});
    cout << st.size() << "\n";
    return 0;
}

Explanation 1

The output is 2 instead of 3 because {1, 2} and {6, 7} have the same (r-l) value. Since sets only store unique values, when we are to insert {6, 7}, the compiler thinks that the value already exists so just does nothing on this line.

What should we do if we want to store all values in the set then? Just change the operator overloading to

bool operator < (node t) const& {
    if(r - l == t.r - t.l) return l < t.l;
    return r - l < t.r - t.l;
}

That is, we would want to make sure that no two "different" elements have the same value in the < operator overloading.

2) (with std::multiset)

Code 2

#include <bits/stdc++.h>
using namespace std;

struct node{
    int l, r;
    bool operator < (node t) const& {
 return r - l < t.r - t.l;
    }
};

int main(){
    multiset <node> st;
    st.insert({6, 7});
    st.insert({3, 5});
    st.insert({1, 2});
    cout << st.size() << " ";
    st.erase({1, 2});
    cout << st.size() << "\n";
    
    return 0;
}

Explanation 2

3) (with std::multiset, very similar to (2))

Code 3

#include <bits/stdc++.h>
using namespace std;

struct node{
    int l, r;
    bool operator < (node t) const& {
	return r - l < t.r - t.l;
    }
};

int main(){
    multiset <node> st;
    st.insert({1, 2});
    st.insert({2, 3});
    st.insert({3, 4});
    cout << st.size() << "\n";
    st.extract({4, 5});
    cout << st.size() << "\n";
    return 0;
}

Explanation 3

These tips are really about the same core idea, but I decided to write three tips because I actually made all these three mistakes (which made my debugging life despairing). Hope these are helpful to you!

(PS: I love how the name of the problem is literally "More Wrong" xd)

Comments (6)

Write comment?

zip_demon

10 months ago, # |

From where I can learn this Operator Overloading ? Like in Sets and Multisets (because I couldn't understand this return (r — l < t.r — t.l)

→ Reply

TKTO

10 months ago, # ^ |

← Rev. 3 →

It basically means the rules when it comes to compare two structs. Here, the author defines node a is less than node b if a.r-a.l is less than b.r — b.l. Another approach would be using the "friend" key word:

struct node{
    int l, r;
    friend bool operator < (const node &a, const node &b){
        return a.r - a.l< b.r - b.l;
    }
};

My understanding of the differences of whether or not using the "friend" keyword is third person or first person point of view. Without friend, you simply compare current node's attribute with another node-type variable and calling that variables attributes. USACO guide explained some sorting techniques, you can check it out. Cuz I don't think I have explained it very well

Thanks

AbsurdMan

-14

Yes. There exists a similar blog regarding this particular topic. Please, do read it!

debugging_since_epoch

I really wonder how the builtin std::set can think two elements are some just only from a < operator , I think it should be that you need to define a == operator too for sets to avoid confusions like this

vgtcross

+11

For any c++ STL class or function, the provided comparator must conform to a Strictly Weak Ordering, which you can read about here.

TL;DR: (answer to your question)

A Strictly Weak Ordering doesn't allow two elements $$$a$$$ and $$$b$$$, where $$$a$$$ is not less than $$$b$$$, $$$a$$$ is not greater than $$$b$$$ but also $$$a$$$ is not equal to $$$b$$$.

A strictly weak ordering defines equality as follows: If $$$a$$$ is not less than $$$b$$$ and $$$a$$$ is not greater than $$$b$$$, then $$$a$$$ is equal to $$$b$$$. In code, the condition a == b is equivalent to the condition !(a < b) && !(b < a) for any Strictly Weak Ordering.

Mkswll's blog