Why do two seemingly lower_bound () methods have different processing times

Question

While I am solving the problem with the algorithm, My decision could not be made due to a time problem.
But I realized that the only difference between the past and mine is

bag.lower_bound(jewerly[i].first) != bag.end() //passed lower_bound(bag.begin(), bag.end(), jewerly[i].first) != bag.end() //failed 

I already checked it with clock() , and it was clearly slower than the other.

what makes the difference between the two codes?

 #include <cstdio> #include <set> #include <algorithm> using namespace std; const int MAXN = 300100; bool cmp(pair<int, int> a, pair<int, int> b) { if(a.second != b.second) return a.second > b.second; return a.first < b.first; } pair<int, int> jewerly[MAXN]; multiset<int> bag; int main() { int N, K, M; scanf("%d%d", &N, &K); int w, p; for(int i = 0; i<N; i++) { scanf("%d%d", &w, &p); jewerly[i] = {w, p}; } for(int i = 0; i<K; i++) { scanf("%d", &M); bag.insert(M); } sort(jewerly, jewerly+N, cmp); clock_t begin = clock(); long long sum = 0; for(int i = 0; i<N; i++) // #1 { if( bag.empty() ) break; if( lower_bound(bag.begin(), bag.end(), jewerly[i].first) != bag.end()) { sum += jewerly[i].second; bag.erase(bag.lower_bound(jewerly[i].first)); } } /* for(int i = 0; i<N; i++) //#2 { if( bag.empty() ) break; if( bag.lower_bound(jewerly[i].first) != bag.end()) { sum += jewerly[i].second; bag.erase(bag.lower_bound(jewerly[i].first)); } } */ clock_t end = clock(); printf("%lf\n", double(end-begin)); } 

Test input 10 8 1 65 5 23 1 30 9 40 3 50 2 90 5 30 5 30 7 80 2 99 10 15 12 5 3 5 2 2

Answer 1

std::lower_bound does not have access to the internal structure of std::multiset . This is not O (log N), because the std::multiset iterators are not random access (and you cannot implement it for a random access iterator faster than in Theta (N))

std::multiset::lower_bound has access to the tree structure and can be easily implemented with complexity O (tree height), which is O (log N)