In recent Div4 contest, I was going through PBDS, and was using less_equal PBDS, where I found out that lower Bound shows result for the upper bound and vice versa. Here's the code for the following.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
int main()
{
tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> s;
s.insert(4);
s.insert(6);
cout<<*s.upper_bound(4)<<" ";
cout<<*s.lower_bound(4);
};
Result: 4 6
Also If I use less instead of less_equal, it shows correct output.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
int main()
{
tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> s;
s.insert(4);
s.insert(6);
cout<<*s.upper_bound(4)<<" ";
cout<<*s.lower_bound(4);
};
Result: 6 4
Help me if I am wrong.
This is because in less equal your less operator (<) become less than equal to (<=), so because of that the lower bound works as upper bound and vice versa and it's not only with pbds, it's with set too
oh, okkk. Thanks for the reply. so because of operator overloading, right? also, you said, this happens with set too, I dont understand that, I have used lower bound on set, and it works fine, so what am I missing here?
You should not be using
less_equal, it is not a real comparator. It works as multiset, only because of how it is implemented, which could reasonably be changed, and your code would stop working. In debug mode using#define _GLIBCXX_DEBUG, you will occassionally notice an internal check failed, because it is a wrong comparator. You should use either pairs, or bit packed long longs.Just wanna know if my ordered set looks like this [2,3,3,4,4,4,5] then how can I erase only one occurrence of an element.