c++ - 如何减少 C++ 中多重集中元素的数量？

Question

我在 C++ 中使用了一个多集，我相信它存储了一个元素和它在插入时的相应计数。

这里，当我想删除一个元素时，我只想将该元素在集合中的计数减1，直到它大于0。

示例 C++ 代码:

    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 .

有什么方法可以实现吗？还是我应该删除它并按要求的(count-1)次插入元素 2？

Answer 1

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

不，你不是。您正在使用一个多集，它存储 n 个插入 n 次的值的拷贝。

如果您想存储与计数相关的值，请使用关联容器，如 std::map<int, int> ，并使用 map[X]++增加 X 的数量。

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

两者都是 map和 set仅找到您要更改的元素就具有 O(log N) 的复杂性，因此这对他们来说是不可能的。使用 std::unordered_map/set得到 O(1) 复杂度。

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

我不确定那是什么意思。

• 一组:

  • 要从集合中删除一个元素的所有 拷贝，使用equal_range获取一个范围(一对迭代器)，然后删除该范围
  • 要删除非空范围内的所有拷贝，只需递增该对中的第一个迭代器并在删除新范围之前检查它仍然不等于第二个迭代器。

  它们都有一个 O(log N) 查找 ( equal_range ) 步骤，然后是一个线性时间删除步骤(尽管它与具有相同键的元素数量成线性关系，而不是 N)。

• map :

  • 要从 map 中删除计数，只需删除键
  • 要将计数设置为 1，只需使用 map[key]=1;

  这两个都有一个 O(log N) 查找，然后是一个恒定时间删除

• 使用无序映射...出于您的目的，它与上面的映射相同，除了复杂度为 O(1)。

这是一个使用 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;
    }
};

然后像这样使用它:

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