std::lower_bound, but returns index (tools/lower_bound.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2022-05-30 15:17:45+09:00
• Include: #include "tools/lower_bound.hpp"

template <class ForwardIterator, class T>
typename ::std::iterator_traits<ForwardIterator>::difference_type lower_bound(ForwardIterator first, ForwardIterator last, T value);

It is identical to std::distance(first, std::lower_bound(first, last, value)).

Constraints

• None

Time Complexity

• Same as that of std::distance(first, std::lower_bound(first, last, value)).

License

• CC0

Author

• anqooqie

Required by

• Compress values (tools/compress.hpp)
• Compress values (for more complicated cases) (tools/compressor.hpp)
• The number of inversions (tools/inversion_number.hpp)
• Li Chao segment tree (tools/li_chao_segtree.hpp)
• Range count distinct (tools/range_count_distinct.hpp)
• Area of union of rectangles (tools/rectangle_union_area.hpp)
• Wavelet matrix (tools/wavelet_matrix.hpp)

Verified with

• tests/inversion_number.test.cpp
• tests/lazy_segtree/lazy_segtree/binary_search.test.cpp
• tests/lazy_sparse_segtree/binary_search.test.cpp
• tests/li_chao_segtree/line.test.cpp
• tests/li_chao_segtree/segment.test.cpp
• tests/persistent_lazy_segtree/binary_search.test.cpp
• tests/range_count_distinct.test.cpp
• tests/rectangle_union_area.test.cpp
• tests/wavelet_matrix/kth_smallest.test.cpp
• tests/wavelet_matrix/next_points.test.cpp
• tests/wavelet_matrix/prev_points.test.cpp
• tests/wavelet_matrix/range_freq.test.cpp
• tests/wavelet_matrix/range_prod.test.cpp

Code

#ifndef TOOLS_LOWER_BOUND_HPP
#define TOOLS_LOWER_BOUND_HPP

#include <iterator>
#include <algorithm>

namespace tools {

  template <class ForwardIterator, class T>
  auto lower_bound(ForwardIterator first, ForwardIterator last, const T& value) {
    return ::std::distance(first, ::std::lower_bound(first, last, value));
  }

  template <class ForwardIterator, class T, class Compare>
  auto lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp) {
    return ::std::distance(first, ::std::lower_bound(first, last, value, comp));
  }
}

#endif

#line 1 "tools/lower_bound.hpp"



#include <iterator>
#include <algorithm>

namespace tools {

  template <class ForwardIterator, class T>
  auto lower_bound(ForwardIterator first, ForwardIterator last, const T& value) {
    return ::std::distance(first, ::std::lower_bound(first, last, value));
  }

  template <class ForwardIterator, class T, class Compare>
  auto lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp) {
    return ::std::distance(first, ::std::lower_bound(first, last, value, comp));
  }
}

Back to top page