dsfds

Revision en1, by maharun, 2024-03-27 15:06:11

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:

#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.

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)