harshad2112's blog

Lower bound and Upper bound showing opposite result in less_equal PBDS set.
By harshad2112, history, 3 years ago, In English

In recent Div4 contest, I was going through PBDS, and was using less_equal PBDS, where I found out that lower Bound shows result for the upper bound and vice versa. Here's the code for the following.

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;

int main()
{
    tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> s;
    s.insert(4);
    s.insert(6);
    cout<<*s.upper_bound(4)<<" ";
    cout<<*s.lower_bound(4);
};

Result: 4 6

Also If I use less instead of less_equal, it shows correct output.

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;

int main()
{
    tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> s;
    s.insert(4);
    s.insert(6);
    cout<<*s.upper_bound(4)<<" ";
    cout<<*s.lower_bound(4);
};

Result: 6 4

Help me if I am wrong.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This is because in less equal your less operator (<) become less than equal to (<=), so because of that the lower bound works as upper bound and vice versa and it's not only with pbds, it's with set too

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    oh, okkk. Thanks for the reply. so because of operator overloading, right? also, you said, this happens with set too, I dont understand that, I have used lower bound on set, and it works fine, so what am I missing here?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You should not be using less_equal, it is not a real comparator. It works as multiset, only because of how it is implemented, which could reasonably be changed, and your code would stop working. In debug mode using #define _GLIBCXX_DEBUG, you will occassionally notice an internal check failed, because it is a wrong comparator. You should use either pairs, or bit packed long longs.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Just wanna know if my ordered set looks like this [2,3,3,4,4,4,5] then how can I erase only one occurrence of an element.

        → Reply