std::ranges::upper_bound(3)

🦋 std::ranges::upper_bound(3) 🦋

C++ Standard Libary, bestie — we’re deep in std::ranges::upper_bound territory. No cap, this one is the “first element that’s greater than value” girlie, and she’s got some very specific partition rules you gotta respect. 💅

💖 NAME 💖

std::ranges::upper_bound — std::ranges::upper_bound.

🌸 Synopsis 🌸

Here’s the header tea, exactly as it’s written:

          Defined in header <algorithm>
          Call signature
          template< std::forward_iterator I, std::sentinel_for<I> S,

                    class T, class Proj = std::identity,
       (since
                    std::indirect_strict_weak_order
       C++20)
                        <const T*, std::projected<I, Proj>> Comp =
       (until
          ranges::less >
       C++26)
          constexpr I upper_bound( I first, S last, const T& value,

                                   Comp comp = {}, Proj proj = {} );
          template< std::forward_iterator I, std::sentinel_for<I> S,

                    class Proj = std::identity,
                    class T = std::projected_value_t<I, Proj>,
                    std::indirect_strict_weak_order
       (since
                        <const T*, std::projected<I, Proj>> Comp =
       C++26)
          ranges::less >
          constexpr I upper_bound( I first, S last, const T& value,

                                   Comp comp = {}, Proj proj = {} );
          template< ranges::forward_range R,

                    class T, class Proj = std::identity,
                    std::indirect_strict_weak_order                    (1)
                        <const T*,
       (since
          std::projected<ranges::iterator_t<R>,
       C++20)
                                                  Proj>> Comp =
       (until
          ranges::less >
       C++26)
          constexpr ranges::borrowed_iterator_t<R>

              upper_bound( R&& r, const T& value, Comp comp = {}, Proj
          proj = {} );
          template< ranges::forward_range R,                               (2)

                    class Proj = std::identity,
                    class T =
          std::projected_value_t<ranges::iterator_t<R>, Proj>,
                    std::indirect_strict_weak_order
                        <const T*,
       (since
          std::projected<ranges::iterator_t<R>,
       C++26)
                                                  Proj>> Comp =
          ranges::less >
          constexpr ranges::borrowed_iterator_t<R>

              upper_bound( R&& r, const T& value, Comp comp = {}, Proj
          proj = {} );

1) Returns an iterator pointing to the first element in the range [first, last) that is greater than value, or last if no such element is found. The range [first, last) must be partitioned with respect to the expression or !comp(value, element), i.e., all elements for which the expression is true must precede all elements for which the expression is false. A fully-sorted range meets this criterion.

2) Same as (1), but uses r as the source range, as if using ranges::begin(r) as first and ranges::end(r) as last.

Okay so the function-like entities described on this page are niebloids, that is:

• Explicit template argument lists cannot be specified when calling any of them.
• None of them are visible to argument-dependent lookup.
• When any of them are found by normal unqualified lookup as the name to the left of the function-call operator, argument-dependent lookup is inhibited.

In practice, they may be implemented as function objects, or with special compiler extensions. 🧚

🎀 Parameters 🎀

• first, last — iterator-sentinel defining the partially-ordered range to examine.
• r — the partially-ordered range to examine.
• value — value to compare the elements to.
• pred — predicate to apply to the projected elements.
• proj — projection to apply to the elements.

💫 Return value 💫

Iterator pointing to the first element that is greater than value, or last if no such element is found. Slay.

🔥 Complexity 🔥

The number of comparisons and applications of the projection performed are logarithmic in the distance between first and last (at most log 2(last - first) + O(1) comparisons and applications of the projection). However, for an iterator that does not model random_access_iterator, the number of iterator increments is linear. iykyk

🧚 Possible implementation 🧚

No cap, here’s the possible implementation in full:

          struct upper_bound_fn
          {
              template<std::forward_iterator I, std::sentinel_for<I> S,
                       class Proj = std::identity, class T =
       std::projected_value_t<I, Proj>,
                       std::indirect_strict_weak_order
                           <const T*, std::projected<I, Proj>> Comp =
       ranges::less>
              constexpr I operator()(I first, S last, const T& value,
                                     Comp comp = {}, Proj proj = {}) const
              {
                  I it;
                  std::iter_difference_t<I> count, step;
                  count = ranges::distance(first, last);

                  while (count > 0)
                  {
                      it = first;
                      step = count / 2;
                      ranges::advance(it, step, last);
                      if (!comp(value, std::invoke(proj, *it)))
                      {
                          first = ++it;
                          count -= step + 1;
                      }
                      else
                          count = step;
                  }
                  return first;
              }

              template<ranges::forward_range R, class Proj = std::identity,
                       class T = std::projected_value_t<ranges::iterator_t<R>,
       Proj>,
                       std::indirect_strict_weak_order
                           <const T*, std::projected<ranges::iterator_t<R>,
                                                     Proj>> Comp =
       ranges::less>
              constexpr ranges::borrowed_iterator_t<R>
                  operator()(R&& r, const T& value, Comp comp = {}, Proj proj =
       {}) const
              {
                  return (*this)(ranges::begin(r), ranges::end(r), value,
                                 std::ref(comp), std::ref(proj));
              }
          };

          inline constexpr upper_bound_fn upper_bound;

📝 Notes 📝

• Feature-test macro __cpp_lib_algorithm_default_value_type — value 202403, std (C++26), feature: List-initialization for algorithms (1,2).

🍓 Example 🍓

        // Run this code

        #include <algorithm>
        #include <cassert>
        #include <complex>
        #include <iostream>
        #include <iterator>
        #include <vector>

        int main()
        {
            namespace ranges = std::ranges;

            std::vector<int> data{1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6};

            {
                auto lower = ranges::lower_bound(data.begin(), data.end(), 4);
                auto upper = ranges::upper_bound(data.begin(), data.end(), 4);

                ranges::copy(lower, upper,
       std::ostream_iterator<int>(std::cout, " "));
                std::cout << '\n';
            }
            {
                auto lower = ranges::lower_bound(data, 3);
                auto upper = ranges::upper_bound(data, 3);

                ranges::copy(lower, upper,
       std::ostream_iterator<int>(std::cout, " "));
                std::cout << '\n';
            }

            using CD = std::complex<double>;
            std::vector<CD> nums{{1, 0}, {2, 2}, {2, 1}, {3, 0}, {3, 1}};
            auto cmpz = [](CD x, CD y) { return x.real() < y.real(); };
            #ifdef __cpp_lib_algorithm_default_value_type
                auto it = ranges::upper_bound(nums, {2, 0}, cmpz);
            #else
                auto it = ranges::upper_bound(nums, CD{2, 0}, cmpz);
            #endif
            assert((*it == CD{3, 0}));
        }

Output:

        4 4 4
        3 3 3 3

👀 See also 👀

• ranges::equal_range (C++20) (niebloid) — returns range of elements matching a specific key.
• ranges::lower_bound (C++20) (niebloid) — returns an iterator to the first element not less than the given value.
• ranges::partition (C++20) (niebloid) — divides a range of elements into two groups.
• upper_bound (function template) — returns an iterator to the first element greater than a certain value.

---

Signed off with cppreference.com source love, version/date 2024.06.10 — std::ranges::upper_bound(3) 🫶✨