0

We have STL (Standard Template Library) multiset, we want to implement a binary search that will give us the first less-or-equal element compared to some value x

From this post: lower_bound == upper_bound, we see that we can use the standar lower_bound and upper_bound to find greater values compared to x, what about finding smaller or equal.

Is it possible to do such thing?

5
  • Binary search doesn't work with multiset or any other associative container. May 21, 2018 at 18:48
  • "first less-or-equal element" -- This would always be the first element of the range (i.e. set.begin()) except in the case that all the elements are greater than x, in which case it's not clear what you would want returned. May 21, 2018 at 18:49
  • @n.m. where are you getting that from? According to this, they are commonly implemented as binary search trees. And they have a logarithmic complexity find method. Perhaps you were thinking of an unordered_multiset? May 21, 2018 at 18:54
  • @Helium_1s2 Binary search doesn't work with associative containers. whatever their implementation is and whatever its underlying complexity is. They may well be using binary search as internal implementation technique, it is immaterial. You can't use binary search with them. They simply don't have an API that would support binary search. May 21, 2018 at 19:00
  • @Bejamin Lindley, I wasn't thinking of that, I mean the greatest less-or-equal element. BTW, multiset is some type of binary tree that supports the standard lower_bound and upper_bound. More reference: cplusplus.com/reference/set/multiset/lower_bound May 21, 2018 at 19:04

1 Answer 1

5

Just use the upper_bound member function of the multiset. upper_bound will return the first element that is grater than the value you are searching for. That means the iterator before that will be the first element that is equal to or smaller than the value. So in

int main()
{
    std::multiset<int> ms = {1,1,2,2,3,3,4,4,5,5};
    auto end = ms.upper_bound(3);
    for (auto it = ms.begin(); it != end; ++it)
        std::cout << *it;
}

It will print 112233 since that is all the element less than or equal to 3.


Of course you will need to make sure upper_bound does not return begin() which would mean there are no elements less than or equal to what you are searching for.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.