I was solving CSES problem-set problem called Concert Ticket under the heading Searching and Sorting. Link to the problem : https://cses.fi/problemset/task/1091/ In this the array of price of ticket was to be stored in a multiset and for each price we needed to find the upper bound of the element in the multiset of ticket. I first used upper_bound(ticket.begin(),ticket.end(),price[i]) but it gave tle on some testcases.
Then I changed it to**ticket.upper_bound(price[i])** it was able to pass all the test case.
If somebody knows the reason kindly tell.
Hope it helps..
set, multiset, map, multimap and a few other special data structures cannot be randomly accessed, using the generic lower_bound function will result in a linear time complexity. There's a reason why the special function exists.
ook thanks
Basically the difference arise due to the implementations of both,
UPPER_BOUND(ticket.begin(), ticket.end(), price[i]) works on the range of iterators i.e it uses binary search to find in a sorted array and gives result in log(n) time complexity. BUT as it works fine on vector in which random access of element is possible but in case of sets, maps where random access is not possible(cause it uses bidirectional iterators) so Binary Search become inefficient in this case as compared to operations provided by containers itself(e.g s.upper_bound).
And s.upper_bound is a member function of the container itself(multiset) and since it is implemented by balanced binary tree(Red Black Tree) so it efficiently perform(cause using tree data structure) and give result in log(n) due to tree traversal.
Hope It Might help.
ok
https://usaco.guide/silver/intro-sorted-sets read sorted sets