Грокаем C++ on Telegram: “Динамический полиморфизм: указатели на функции и…”

Динамический полиморфизм: указатели на функции и void указатели
#новичкам

C++ - разжиревший отпрыск С, поэтому в нем имеется возможность для динамического полиморфизма пользоваться сишными инструментами.

И два основных сишных инструмента дин полиморфизма - указатели на функции и void указатели.

Функции работают с аргументами и каждое имя функции при компиляции соответствует адресу этой функции в памяти. Даже если 2 функции имеют разные адреса, но одинаковый набор и порядок аргументов, в низкоуровневом коде они вызываются абсолютно единообразно. Поэтому есть такая сущность, как указатели на функции. Они могут хранить адреса любых функций с наперед заданной сигнатурой:

int x2(int i) {
  return i * 2;
}
int square(int i) {
  return i * i;
}
using IntFuncPtr = int (*)(int);

IntFuncPtr func_ptr;

// Вызываем x2 через указатель
func_ptr = x2;
std::cout << "x2(5) = " << func_ptr(5) << std::endl;

// Вызываем square через указатель
func_ptr = square;
std::cout << "square(5) = " << func_ptr(5) << std::endl;

В коде выше с помощью одного указателя вызываются 2 разные функции. Полиморфизм? Вполне! Только вот примерчик давайте по-серьезнее возьмем:

void *bsearch(const void *key, const void *ptr, std::size_t count,
        std::size_t size, /* c-compare-pred */ *comp);

void *bsearch(const void *key, const void *ptr, std::size_t count,
        std::size_t size, /* compare-pred */ *comp);

extern "C" using /* c-compare-pred */ = int(const void*, const void*);  
extern "C++" using /* compare-pred */ = int(const void*, const void*);

std::bsearch - функция, которая выполняет алгоритм бинарного поиска и возвращает либо найденный элемент, либо нулевой указатель, если элемента не было в массиве. Причем он может проводить поиск в массивах разных типов по разным правилам!

Это достигается за счет использования указателя на функцию-компаратор и void указателя. К нему могут неявно приводиться указатели на любые типы, поэтому он не знает, на какой конкретный тип он указывает. Но ему это и не надо. Тот, кто имеет информацию о правильном типе(компаратор) может обратно привести void * к указателю на этот тип и работать уже с нормальным объектом.

Единственная сложность - нужен дополнительный параметр size, с помощью которого задается байтовый размер типа элемента массива.

Ну и давайте все это применим:

int compare_doubles(const void *a, const void *b) {
  static constexpr double EPSILON = 1e-9;
  double diff = *(double *)b - *(double *)a;
  if (std::fabs(diff) < EPSILON) {
    return 0;
  }
  return (diff > 0) ? 1 : -1;
}

int compare_ints(const void *a, const void *b) {
  return (*(int *)a - *(int *)b);
}

double double_arr[] = {5.5, 4.4, 3.3, 2.2, 1.1};
size_t double_size = sizeof(double_arr) / sizeof(double_arr[0]);

int int_arr[] = {10, 20, 30, 40, 50};
size_t int_size = sizeof(int_arr) / sizeof(int_arr[0]);

  

// Поиск в массиве double
double double_key = 3.30000000001; // Почти 3.3
double *double_res = (double *)std::bsearch(
          &double_key, double_arr, double_size,
          sizeof(double), compare_doubles);
// тут надо проверить на nullptr, но опустим это  
std::cout << "Found double: " << *double_res << std::endl;

// Поиск в массиве int
int int_key = 30;
int *int_res =
    (int *)std::bsearch(&int_key, int_arr, int_size,
        sizeof(int), compare_ints);

std::cout << "Found int: " << *int_res << std::endl;

Есть два массива: интов и даблов. Для выполнения бинарного поиска для этих типов нужны абсолютно разные компараторы: как минимум даблы нельзя сравнивать втупую.

std::bsearch на этапе компиляции не знает, с какими типами и компараторами он будет работать. Все решения принимаются в рантайме. Но он умеет по-разному находить элементы в массивах разных типов. Именно поэтому bsearch использует инструменты именно динамического полиморфизма.

Act independently of input. Stay cool.

#cppcore #goodoldc