In the module “More operations on ordered sets”, it’s mentioned that a multiset count() operation takes time linear in the number of matches.
Is it possible to count the number of elements in logarithmic time using the following code?
multiset<int> ms;
int x; cin >> x;
int ub = ms.upper_bound(x) - ms.begin();
int lb = ms.lower_bound(x) - ms.begin();
cout << ub - lb << '\n';
In particular, is it allowed to subtract two iterators?
Resolved. Subtraction of iterators only works when binary searching on an array. It doesn’t work with sets.
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.