Although multiset count() is linear in the number of matches, it’s logarithmic in the size of the multiset. I think only random access iterators can be subtracted; multiset upper/lower bound return a bidirectional iterator.

Something like this would work,

multiset<int> ms;
int x; cin >> x;
auto ub = ms.upper_bound(x);
auto lb = ms.lower_bound(x);
cout << distance(lb, ub) << '\n';

where distance() is linear in the distance. This makes the time complexity the same as multiset count().

That makes sense. It’s logarithmic in terms of finding lower_bound and upper_bound. To find the distance between the two iterators, distance(lb, ub) actually iterates through everything between lb and ub. Thank you for mentioning the difference between random access iterators and bidirectional iterators as well.