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.

Joubert

Why not use std::multiset? – Kumasi

@Kerndog73 Because of the use of function order_of_key. In multiset doing this job is O(n). – Joubert

Why are you using std::less_equal when std::less is expected (it's the default)? – Kumasi

@Kerndog73 Because I need a multiset, not a set. Duplication of number in the container. – Joubert

So the data structure you're using is actually a set but you're using std::less_equal to fake a multiset? That doesn't sound safe – Kumasi

@Kerndog73 I would be happy if you provide an alternative. – Joubert

Let us continue this discussion in chat. – Joubert

rather than rely on using namespace std;using namespace __gnu_pbds;, be explicit about the namespace your are talking about. ordered_multiset is not part of c++, but of some non-common extension – Matrices

@Matrices ordered_multiset is defined on the first code. – Joubert

The problem is, I am not able to erase an element from it. People cannot answer this question if they can't find the reference. – Matrices

"Note: Please don't suggest solving the problem in way of using another container. That's not a solution." any solution is going to involve a different container, even if its some other instantiation of tree – Juarez

@Matrices Have you read the line using ordered_multiset = tree< ... on my first code in the question? – Joubert

@Juarez It's ok to provide an alternative which does the job of order_of_key in O(1). – Joubert

I can't find where the claim of O(1) comes from for order_of_key, but I am very suspicious of it, given that lookup is O(log(n)) – Juarez

I have. But there are conflicting statements in your question, and the simple insert-erase should have worked. but it doesn't. So you broke the library contract in some way, and to be able to say in which way we need the library contract. which is not the standard library. As @Juarez said, the complexity claim seems wrong. – Matrices

@Juarez I don't know, it may be logarithmic. I have heard that it works in constant time but I am not able to find any reliable source which says that. – Joubert

Not being able to find documentation is another reason not to use this library and instead using the standard library – Kumasi

@Juarez Even if it is logarithmic, it is much better than linear. That's way I'm not using std::multiset. – Joubert

linear is still better than unimplemented, which is better than unimplementable – Juarez

@Juarez You're right about the complexity of order_of_key, it's logarithmic. – Joubert

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.

Kumasi

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

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
}

Salute

Answer 3

Well, the real problem was already pointed out (you shouldn't use less_equal as a comparator). However, recently I had a similar problem, when I was solving the problems from the CSES problemset. I found a pretty simple, but working solution (replace int with integer type that can hold enough elements):

template <typename T>
using ordered_multiset = tree<pair<T, int>, null_type, less_equal<T>, rb_tree_tag,
                          tree_order_statistics_node_update>;
int timer = 0; // the number of elements inserted

ordered_multiset<int> st;
// to insert do
st.insert({value, timer});
timer++;

// to erase elements you can do this
auto it = st.lower_bound({value, 0});
if (it != st.end() && it->first == value)
    st.erase(it);

What's more, in a lot of competitive programming related problems you usually insert elements from an array, so you can take the indexes from the position in array, and erasing them becomes easier

Hefter

Answer 4

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));
}

Juarez

If you mean std::multiset, then I can't use a multiset becuase I need the function order_of_key which is not available in multiset container. – Joubert

std::distance is in O(n), n = distance of the two element. – Joubert

Would it actually have to be upper_bound to get the first element greater than the one searched for? The question is a little unclear in that regard. – Kumasi

Answer 5

Passing an iterator to the erase function worked for me.
If it is not convenient to find the iterator, I believe pbds.erase(pbds.find_by_order(your_order) should work.
If you do not know the order a priori, you can do something like pbds.erase(pbds.find_by_order(pbds.order_of_key(your_key)))

Shote

All of these options work in O(log (size of pbds) ). – Shote

Answer 6

you can use mt.erase(mt.upper_bound(x)) instead of mt.erase(x)

sample cpp with less_equal:

#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) {
         mt.insert(x);
      }
      if (op == 2) {
         mt.erase(mt.upper_bound(x));
      }
      if (op == 3) {
         cout << mt.order_of_key(x) + 1 << endl;
      }
      if (op == 4) {
         cout << *mt.find_by_order(x - 1) << endl;
      }
      if (op == 5) {
         cout << *--mt.upper_bound(x) << endl;
      }
      if (op == 6) {
         cout << *mt.lower_bound(x) << endl;
      }
   }
   return 0;
}

test input:

10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598

work fine!

106465
84185
492737

Halter

upper_bound and lower_bound filp, and use a new version of erase code from : codeforces.com/blog/entry/127634 – Halter

Answer 7

**We can erase by passing an iterator in erase function ** Here is my snapped: code

Pickup

Please do not upload images of code or errors. – Leatherwood