我对在size n的多集合中为某些element x调用count（x）时发生的操作数量感到困惑。
我是否纠正为操作数为log（n）+ #_of_matches_of_x，这意味着多集中元素数的对数加上多集中所有元素中目标元素x的匹配数？
感谢您的时间！
此site明确指出multiset :: count的复杂度为
大小为对数，匹配数为线性。
或者您可以签出此one。
容器大小的对数加上找到的元素数的线性。
好吧，我为您准备了一篇有趣的文章。 （Link）
正如参考链接所提到的，计数的复杂度在容器的大小上是对数的，在找到的元素数量上是线性的。
原因是多图是一个树状数据结构，每个树节点处都有一个容器。因此，为了计数，您应该首先在树O（log（All elements））中找到键，然后对那个节点中的元素（O（found elements））进行计数。