bazsi700's blog

std::lower_bound vs std::set::lower_bound
By bazsi700, history, 7 years ago, In English

I have just discovered, that std::set::lower_bound for larger sets is much-much faster than std::lower_bound.

Can anyone give explanation why does this happen?

Also, use std::set::lower_bound instead of std::lower_bound, I struggled on a problem for like 2 hours because of getting TLE for this.

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +24 Vote: I do not like it

http://www.cplusplus.com/reference/algorithm/lower_bound/:

On non-random-access iterators, the iterator advances produce themselves an additional linear complexity in N on average.

http://www.cplusplus.com/reference/set/set/:

iterator — a bidirectional iterator to const value_type

→ Reply
»
7 years ago, # |
  Vote: I like it -15 Vote: I do not like it

As far as i know std::lower_bound works with complexity O(log n) * O(access_of_element), it is O(log n) for vectors, arrays, but for sets it is something like O(n * log^2 n) (because you can get element in set in O(n log n)). std::set::lower_bound is function specified for using in sets, it has complexity O(log n).

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Actually, std::lower_bound on a set is (not much better anyway). See this StackOverflow question and, especially, WaltK's comment.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, i just thought that we need about O(log n) operations to go to the next element in rb-tree every time, but it is O(n) in total, so final complexity is O(n * log n).

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +46 Vote: I do not like it

      I'm pretty sure it's implemented in O(n)

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        I'm not so sure.

        Performs approximately log2(N)+1 element comparisons (where N is this distance).

        It is a binary search, after all, and generally cannot be replaced with a linear one, because the comparison function might have insanely huge complexity.

        In my STL implementation:

        template<typename _ForwardIterator, typename _Tp, typename _Compare>
  _ForwardIterator
  __lower_bound(_ForwardIterator __first, _ForwardIterator __last,
        const _Tp& __val, _Compare __comp)
  {
    typedef typename iterator_traits<_ForwardIterator>::difference_type
  _DistanceType;

    _DistanceType __len = std::distance(__first, __last);

    while (__len > 0)
  {
    _DistanceType __half = __len >> 1;
    _ForwardIterator __middle = __first;
    std::advance(__middle, __half);
    if (__comp(__middle, __val))
      {
        __first = __middle;
        ++__first;
        __len = __len - __half - 1;
      }
    else
      __len = __half;
  }
    return __first;
  }
        → Reply