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:
As you can see, here the lower bound and upper bounds are flipped. Erase doesn't work either.
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.
Note: If there are any problems please let me know.
Not sorry for my poor English.
(^ヮ^)/
You've already known the problem, so why you still use "why...?" in your blog title?
thanks.. fixed it..
handsome solution! now use
less_equal
also work fine, thanks