less_equal
PBDS set has certain problems:
- Erase doesn’t work (if the value is sent)
- upper_bound gives lower_bound
- and lower_bound gives upper_bound
To demonstrate this problem, let's see a code and it's output:
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
void print(auto& s) {
cout << "s = ";
for (auto& x : s)
cout << x << " ";
cout << '\n';
}
int main()
{
tree<int, null_type, less_equal<int>, rb_tree_tag,
tree_order_statistics_node_update> s;
s.insert(1);
s.insert(2);
s.insert(4);
s.insert(4);
s.insert(6);
s.insert(7);
cout << "s.lower_bound(4) = " << *s.lower_bound(4) << endl;
cout << "s.upper_bound(4) = " << *s.upper_bound(4) << endl;
s.erase(6);
cout << "After s.erase(6),\n";
print(s);
};
s.lower_bound(4) = 6
s.upper_bound(4) = 4
After s.erase(6),
s = 1 2 4 4 6 7
In short, PBDS uses the same comparator for sorting, equality check, upper bound, and lower bound. less_equal just replaces < sign with <= sign. Nothing else.
Let’s see what kind of problem it arises:
Sorting comparator: No problem. It is the order we want the elements to follow.
Equality Check:
In std::set, !comp(a, b) && !comp(b, a) is used. Which works for strictly increasing/decreasing order like set.
But, if a = 5 and b = 5 Then !(5 <= 5) and !(5 <= 5) returns false.
That’s why erase doesn’t work if only value is passed.
But if the iterator is provided, it will work. So, always do this: s.erase(s.find_by_order(5));
Lower bound and Upper bound: Lower bound is the first element that is not less than a given key
normal lower = !(value < target) here comp = !(value <= target)
Elements = 1 2 3 3 4 5 Normal = F F T Here = F F F F T
Upper bound is the smallest element greater than the given value
normal upper = (value > target) here comp = (value >= target)
Elements = 1 2 3 3 4 5 Normal = F F F F T Here = F F T
As you can see, how upper and lower bound flips here.