Unable to erase from libstdc++ Policy based data structure

Question

There is an associated container in C++ which is actually a set (multiset) which can give the order of an element in it in.

Here is how I use the container:

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template <typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag,
                              tree_order_statistics_node_update>;

The problem is, I am not able to erase an element from it:

ordered_multiset<int> s;
s.insert(0);
s.erase(0);

cout << s.order_of_key(1); // returns number of elements less than x

// Outputs: 1

The strange part is that if you replace less_equal with less, then you would be able to do the job without a problem, actually if you use the container as a multiset, then you won't be able to erase elements from it, but there is no problem when you use it as a set.

• What is causing the problem?
• How can I solve the problem?

Note: Please don't suggest solving the problem in way of using another container. That's not a solution.

Answer 1

Using std::less_equal, there's no way to know if two elements are equivalent. std::set uses the expression !comp(a, b) && !comp(b, a) to determine whether a and b are equivalent. This works if you use a strict weak ordering like std::less but fails when you use std::less_equal. 5 and 5 are equivalent but !(5 <= 5) && !(5 <= 5) is false. So the erase fails.

In short, you can't just turn a set into a multiset using std::less_equal.

---

@Caleth has described a way of using std::multiset and doing the search in linear time. You can determine the order in logarithmic time by keeping the order for each element.

template <typename Value>
struct ordered_value {
  size_t order;
  Value value;
};

template <typename Value>
using ordered_multiset = std::multiset<ordered_value<Value>>;

The problem with this is that you have to update the order each time you insert or erase (which is linear). Are you sure that the container you're using does the operation in constant time? That kind of seems impossible to me.

The way that the ordering statistic is implemented in a red-black tree is actually pretty similar. There's some extra information in each node that is updated whenever you insert or erase. The point is, this is pretty close to the best you can do without going to all the trouble of making your own red-black tree.

Answer 2

I was struggling with the same problem and think I found a not so elegant but useful solution.

You can make your own erase function like this:

void myerase(ordered_set &t, int v){
    int rank = t.order_of_key(v);//Number of elements that are less than v in t
    ordered_set::iterator it = t.find_by_order(rank); //Iterator that points to the (rank+1)th element in t
    t.erase(it);
}

Since order_of_key, find_by_order and the standard erase are all O(log(N)), myerase should also be O(log(N)). Someone correct me if I'm wrong.

Here is the code snippet I used to test it:

#include<iostream>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

using namespace __gnu_pbds; 
using namespace std;

typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

void myerase(ordered_set &t, int v){
    int rank = t.order_of_key(v);//Number of elements that are less than v in t
    ordered_set::iterator it = t.find_by_order(rank); //Iterator that points to the (rank+1)th element in t
    t.erase(it);
}

void printOrderedSet(ordered_set s){
    //Function to show the contents of the set
    for(auto it=s.begin(); it!=s.end(); it++){
        cout<<*it<<" ";
    }cout<<endl;
}

int main(){
    //Create an ordered_set t with the numbers 0,0,1,1,2,2,3,3,4,4
    ordered_set t;
    for(int i=0; i<10;i++){
        t.insert(i/2);
    }
    printOrderedSet(t); //output: 0 0 1 1 2 2 3 3 4 4
    
    myerase(t, 3);
    printOrderedSet(t); //output: 0 0 1 1 2 2 3 4 4

    myerase(t, 3);
    printOrderedSet(t); //output: 0 0 1 1 2 2 4 4

    myerase(t, 0);
    printOrderedSet(t); //output: 0 1 1 2 2 4 4

    myerase(t, 1);
    printOrderedSet(t); //output: 0 1 2 2 4 4
}

Answer 3

What is causing the problem?

You haven't supplied a Compare to tree. Your program is ill-formed.

How can I solve the problem?

Use std::multiset<T> and

template<typename Set, typename Key>
size_t order_of_key(const Set & set, const Key & key)
{
    return std::distance(set.begin(), set.lower_bound(key));
}