Difference between std::lower_bound and set::lower_bound

Правка en2, от ghost1733, 2021-06-01 11:59:58

So today I learnt a new thing, which I think will be useful for beginners. I thought that both of the lines are equivalent. However when I found out that the latter is more efficient in case of sets.

set set1;

auto ite = upper_bound(set1.begin(), set1.end(), val); // O(n) // O(log n) in case of random access container. auto ite = set1.upper_bound(val);//O(log n) // binary search, uses set property

Hope this helps; return 0;

Теги c++ stl, #time complexity, #beginners, #for_beginners

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский ghost1733 2021-06-01 11:59:58 1 Tiny change: 'at the later is mor' -> 'at the latter is mor'
en1 Английский ghost1733 2021-06-01 11:59:12 505 Initial revision (published)