ArPiT_PanDeY's blog

Policy Based Datastructure in C++, ordered_multiset. Is this the correct way of implementing it?
By ArPiT_PanDeY, history, 2 years ago, In English

I saw this template somewhere for implementing ordered_multiset:

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

But in this template, both find function and erase function are completely broken (when argument is not an iterator, but a key instead). So i was wondering what's the correct way of ensuring these functions work correctly, while keeping the interface feel "normal". I came up with something like this:

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

template <typename T>
class ordered_multiset : public oms<T> {
   public:
    oms<T>::iterator find(T k) {
        int order = this->order_of_key(k);
        return this->find_by_order(order);
    }
    template <typename U>
    void erase(U it) { //erases key where 'it' is pointing currently
        oms<T>::erase(it);
    }
    void erase(T k) {  // erases first entity of key = k
        auto it = this->find(k);
        this->erase(it);
    }
};

But i once read somewhere that STL containers should never be inherited, so is this method of overloading in-built functions any good? I am a complete noob in modern C++ and Object Oriented Design, so please go easy on me.

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

»
2 years ago, # |
  Vote: I like it +9 Vote: I do not like it

I think erase(T k) could give runtime error if the value isn't found, maybe replace find with upper_bound (because upper and lower bound get swapped with less_equal) and check if the value is equal to k before calling the erase(U it) inside erase(T k)

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 3   Vote: I like it +9 Vote: I do not like it 
    template <typename T>
using oms = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T>
class ordered_multiset : public oms<T> {
   public:
    oms<T>::iterator find(T k) {
        auto ret = this->upper_bound(k);
        return ret != this->end() and *ret == k ? ret : this->end();
    }
    void erase(T k) {  // erases first entity of key = k
        auto it = this->find(k);
        if(it != this->end() and *it == k) this->erase(it);
    }
};

    I'm not sure but something like this maybe

    → Reply