std::midpoint
#новичкам

Простая задача - получить среднее арифметическое двух чисел. Берем и пишем, как на уроке математики:

int avg(int a, int b) {
  return (a + b) / 2;
}

И дело в шляпе. Или нет?

На самом деле это некорректная реализация, потому что не учитывает переполнение целых чисел. Если сумма (a + b) будет больше, чем помещается в int, то произойдет переполнение, а вы в итоге получите неправильный ответ.

Что же делать?

Если несколько способов обойти эту проблему.

❗️ Складываем половинки двух чисел:

int avg(int a, int b) {
  return a/2 + b/2;
}

Даже если a и b - максимальные инты, все будет гуд. Проблему с переполнением решили.

Однако здесь появляются проблемы с двойным отбрасыванием остатка от деления. В случае передачи двух нечетных чисел, результат будет неверный:

avg(5, 7) = 5 что неверно

💥 Первое число складываем с разницей двух чисел:

int avg(int a, int b) {
  return a > b ? b + (a - b) / 2 : a + (b - a) / 2;
}

Если раскрыть скобки, то выходит тоже самое.
И проблем с корректностью нет.

⚡️ std::midpoint. С++20 мы наконец получили стандартную функцию, считающую среднее арифметическое двух объектов. Давайте посмотрим на ее реализацию из gcc:

 // midpoint
#ifdef __cpp_lib_interpolate // C++ >= 20
  template<typename _Tp>
    constexpr
    enable_if_t<__and_v<is_arithmetic<_Tp>, is_same<remove_cv_t<_Tp>, _Tp>,
      _not<is_same<_Tp, bool>>>,
    _Tp>
    midpoint(_Tp __a, _Tp __b) noexcept
    {
      if constexpr (is_integral_v<_Tp>)
  {
    using _Up = make_unsigned_t<_Tp>;

    int __k = 1;
    _Up __m = __a;
    _Up __M = __b;
    if (__a > __b)
      {
        __k = -1;
        __m = __b;
        __M = __a;
      }
    return __a + __k * _Tp(_Up(__M - __m) / 2);
  }
      else // is_floating
  {
    constexpr _Tp __lo = numeric_limits<_Tp>::min() * 2;
    constexpr _Tp __hi = numeric_limits<_Tp>::max() / 2;
    const _Tp __abs_a = __a < 0 ? -__a : __a;
    const _Tp __abs_b = __b < 0 ? -__b : __b;
    if (__abs_a <= __hi && __abs_b <= __hi) [[likely]]
      return (__a + __b) / 2; // always correctly rounded
    if (__abs_a < __lo) // not safe to halve __a
      return __a + __b/2;
    if (__abs_b < __lo) // not safe to halve __b
      return __a/2 + __b;
    return __a/2 + __b/2;      // otherwise correctly rounded
  }
    }

  template<typename _Tp>
    constexpr enable_if_t<is_object_v<_Tp>, _Tp*>
    midpoint(_Tp* __a, _Tp* __b) noexcept
    {
      static_assert( sizeof(_Tp) != 0, "type must be complete" );
      return __a  + (__b - __a) / 2;
    }
#endif // __cpp_lib_interpolate

Не будем вдаваться в подробности, однако стоит заметить, что стандартная функция использует оба подхода в разных ситуациях. Для целых чисел используется второй подход с вычитанием, а для чисел с плавающей точкой - с располовиниваем(так как не теряем остаток) и, даже, оригинальный подход, когда нет риска переполнения.

Да, может быть эта реализация не такая эффективная, зато гарантировано безопасная. Стандарт об этом явно говорит.

К тому же std::midpoint можно использовать для реализации бинарного поиска при нахождении индекса серединного элемента последовательности. Или для реализации алгоритмов «разделяй и властвуй», когда нужно найти индекс элемента, по которому будут разбивать последовательность пополам

В общем, если вы не упарываетесь по перфу, то она станет вашим верным другом.

Stay safe. Stay cool.

#cpp20 #cppcore