How do I decrease the count of an element in a multiset in C++?

Question

I am using a multi-set in c++, which I believe stores an element and the respective count of it when it is inserted.

Here, when I want to delete an element, I just want to decrease the count of that element in the set by 1 till it is greater than 0.

Example C++ code:

    multiset<int>mset;
    mset.insert(2);
    mset.insert(2);
    printf("%d ",mset.count(2)); //this returns 2
    // here I need an O(1) constant time function (in-built or whatever )
    // to decrease the count of 2 in the set without deleting it 
    // Remember constant time only

      -> Function and its specifications

    printf("%d ",mset.count(2)); // it should print 1 now .

Is there any way to achieve that or should i go by deleting that and inserting the element 2 by the required (count-1) times?

Answer 1

... I am using a multi-set in c++, which stores an element and the respective count of it ...

No you aren't. You're using a multi-set which stores n copies of a value which was inserted n times.

If you want to store something relating a value to a count, use an associative container like std::map<int, int>, and use map[X]++ to increment the number of Xs.

... i need an O(1) constant time function ... to decrease the count ...

Both map and set have O(log N) complexity just to find the element you want to alter, so this is impossible with them. Use std::unordered_map/set to get O(1) complexity.

... I just want to decrease the count of that element in the set by 1 till it is >0

I'm not sure what that means.

• with a set:

  • to remove all copies of an element from the set, use equal_range to get a range (pair of iterators), and then erase that range
  • to remove all-but-one copies in a non-empty range, just increment the first iterator in the pair and check it's still not equal to the second iterator before erasing the new range.

  these both have an O(log N) lookup (equal_range) step followed by a linear-time erase step (although it's linear with the number of elements having the same key, not N).

• with a map:

  • to remove the count from a map, just erase the key
  • to set the count to one, just use map[key]=1;

  both of these have an O(log N) lookup followed by a constant-time erase

• with an unordered map ... for your purposes it's identical to the map above, except with O(1) complexity.

Here's a quick example using unordered_map:

template <typename Key>
class Counter {
    std::unordered_map<Key, unsigned> count_;
public:
    unsigned inc(Key k, unsigned delta = 1) {
        auto result = count_.emplace(k, delta);
        if (result.second) {
            return delta;
        } else {
            unsigned& current = result.first->second;
            current += delta;
            return current;
        }
    }
    unsigned dec(Key k, unsigned delta = 1) {
        auto iter = count_.find(k);
        if (iter == count_.end()) return 0;
        unsigned& current = iter->second;
        if (current > delta) {
            current -= delta;
            return current;
        }
        // else current <= delta means zero
        count_.erase(iter);
        return 0;
    }
    unsigned get(Key k) const {
        auto iter = count_.find(k);
        if (iter == count_.end()) return 0;
        return iter->second;
    }
};

and use it like so:

int main() {
    Counter<int> c;
    // test increment
    assert(c.inc(1) == 1);
    assert(c.inc(2) == 1);
    assert(c.inc(2) == 2);
    // test lookup
    assert(c.get(0) == 0);
    assert(c.get(1) == 1);
    // test simple decrement
    assert(c.get(2) == 2);
    assert(c.dec(2) == 1);
    assert(c.get(2) == 1);
    // test erase and underflow
    assert(c.dec(2) == 0);
    assert(c.dec(2) == 0);
    assert(c.dec(1, 42) == 0);
}