Some tips regarding sets and multisets

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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)

Комментарии (5)

Показать архивные | Написать комментарий?

zip_demon

16 месяцев назад, # |

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)

→ Ответить

TKTO

16 месяцев назад, # ^ |

← 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

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