Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

ArPiT_PanDeY's blog

By ArPiT_PanDeY, history, 20 months 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.

Full text and comments »

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