bazsi700's blog

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

»
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).

  • »
    »
    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.

    • »
      »
      »
      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).

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

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

      • »
        »
        »
        »
        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;
          }