maharun's blog

Reason why upper bound and lower bound flips and erase doesn't work in less_equal PBDS?
By maharun, history, 8 months ago, In English
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.
(^ヮ^)/

  • Vote: I like it
  • +16
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You've already known the problem, so why you still use "why...?" in your blog title?

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

handsome solution! now use less_equal also work fine, thanks

#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>   // Common file
#include <ext/pb_ds/tree_policy.hpp>       // Including tree_order_statistics_node_update
using namespace __gnu_pbds;

template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T> 
using MultiTree = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;


/*
If using MultiTree:
   Ranking of x:                                                mt.order_of_key(x) + 1
   Find the number with rank idx:                               *mt.find_by_order(idx)
   To delete only one of multiple identical numbers:            mt.erase(st.upper_bound(x));
   Predecessor is defined as the largest number less than x:    *--mt.upper_bound(x)
   Successor is defined as the smallest number greater than x:  *mt.lower_bound(x)
*/

int main() {
   MultiTree<int> mt;
   int n = 0;
   cin >> n;
   while (n--) {
      int op, x;
      cin >> op >> x;
      if (op == 1) { // insert 
         mt.insert(x);
      }
      if (op == 2) { // erase 
         mt.erase(mt.upper_bound(x));
      }
      if (op == 3) { // rank
         cout << mt.order_of_key(x) + 1 << endl;
      }
      if (op == 4) { // rank val
         cout << *mt.find_by_order(x - 1) << endl;
      }
      if (op == 5) { // pre
         cout << *--mt.upper_bound(x) << endl;
      }
      if (op == 6) { // suf
         cout << *mt.lower_bound(x) << endl;
      }
   }
   return 0;
}
→ Reply