Why upper bound and lower bound flips and erase doesn't work in less_equal PBDS?

Revision en2, by maharun, 2024-03-27 15:13:27
less_equal PBDS set has certain problems:
  1. Erase doesn’t work (if the value is sent)
  2. upper_bound gives lower_bound
  3. and lower_bound gives upper_bound
To demonstrate this problem, let's see a code and it's output:
Code
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.
(^ヮ^)/

Tags pbds

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English maharun 2024-03-27 16:03:38 9
en2 English maharun 2024-03-27 15:13:27 655 Tiny change: 'sh. <br>\nദ്ദി(˵ •̀ ᴗ - ˵ ) ✧\n</p>' -> 'sh. <br>\n(^ヮ^)/\n</p>' (published)
en1 English maharun 2024-03-27 15:06:11 2229 Initial revision (saved to drafts)