我在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吗?
。。。我在c++中使用了一个多集,它存储一个元素和它各自的计数。。。
不,你不是。您使用的是一个多集,它存储插入n次的值的n个副本。
如果要存储将值与计数相关联的内容,请使用类似std::map<int, int>
的关联容器,并使用map[X]++
来增加X的数量。
。。。我需要一个O(1)常数时间函数。。。减少计数。。。
map
和set
都有O(log N)复杂性,只是为了找到要更改的元素,所以这对它们来说是不可能的。用std::unordered_map
/set
求O(1)的复杂度。
。。。我只想把集合中那个元素的计数减少1,直到它>0
我不知道这意味着什么。
-
带有一个集合:
- 要从集合中删除元素的所有副本,请使用
equal_range
获取一个范围(迭代器对),然后擦除该范围 - 要删除非空范围中除一个副本外的所有副本,只需增加对中的第一个迭代器,并在擦除新范围之前检查它是否仍不等于第二个迭代者
这两者都有一个O(log N)查找(
equal_range
)步骤,然后是一个线性时间擦除步骤(尽管它与具有相同密钥的元素数量而不是N是线性的)。 - 要从集合中删除元素的所有副本,请使用
-
带地图:
- 要从地图中删除计数,只需擦除键
- 要将计数设置为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);
}