CRTP, чтобы избежать динамического полиморфизма

Question

CRTP, чтобы избежать динамического полиморфизма

Как я могу использовать CRTP в C++, чтобы избежать накладных расходов на виртуальные функции-члены?

94

c++ templates virtual crtp

Источник

04 ноя '08 в 16:07

5 ответов

Другие вопросы по тегам c++ templates virtual crtp

user11274 04 ноя '08 в 19:02 2008-11-04 19:02 · Answer 1 · 2008-11-04 19:02

Есть два способа.

Первый заключается в статическом указании интерфейса для структуры типов:

template <class Derived>
struct base {
  void foo() {
    static_cast<Derived *>(this)->foo();
  };
};

struct my_type : base<my_type> {
  void foo(); // required to compile.
};

struct your_type : base<your_type> {
  void foo(); // required to compile.
};

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

template <class T> // T is deduced at compile-time
void bar(base<T> & obj) {
  obj.foo(); // will do static dispatch
}

struct not_derived_from_base { }; // notice, not derived from base

// ...
my_type my_instance;
your_type your_instance;
not_derived_from_base invalid_instance;
bar(my_instance); // will call my_instance.foo()
bar(your_instance); // will call your_instance.foo()
bar(invalid_instance); // compile error, cannot deduce correct overload

Таким образом, объединение определения структуры / интерфейса и вывода типов во время компиляции в ваших функциях позволяет выполнять статическую диспетчеризацию вместо динамической диспетчеризации. Это суть статического полиморфизма.

user18167 04 ноя '08 в 17:49 2008-11-04 17:49 · Answer 2 · 2008-11-04 17:49

Я искал достойные обсуждения CRTP сам. Методика Тодда Велдхейзена для Scientific C++ - отличный ресурс для этого (1.3) и многих других продвинутых техник, таких как шаблоны выражений.

Кроме того, я обнаружил, что вы можете прочитать большую часть оригинальной статьи Коплиена о C++ Gems в книгах Google. Может быть, это все еще так.

user8446 04 ноя '08 в 16:11 2008-11-04 16:11 · Answer 3 · 2008-11-04 16:11

Я должен был искать CRTP. Сделав это, я нашел кое-что о статическом полиморфизме. Я подозреваю, что это ответ на ваш вопрос.

Оказывается, ATL использует этот паттерн довольно широко.

1

Источник

user8446 04 ноя '08 в 16:11

user15013600 29 янв '21 в 23:12 2021-01-29 23:12 · Answer 4 · 2021-01-29 23:12

Статическая рассылка CRTP / SFINAE со строгой проверкой подписи

Это решение для статической диспетчеризации использует CRTP и SFINAE, что не ново. Уникальность этого решения заключается в том, что оно также обеспечивает строгую проверку подписи, что позволяет нам статически отправлять перегруженные методы таким же образом, как динамическая диспетчеризация работает для виртуальных функций.

Для начала давайте сначала рассмотрим ограничения традиционного решения, использующего SFINAE. Следующее было взято из выступления Бена Дина на CppCon 2016 Lightning Talk «Статическая альтернатива виртуальным функциям с использованием выражения SFINAE».

      #define SFINAE_DETECT(name, expr)                                       \
  template <typename T>                                                 \
  using name##_t = decltype(expr);                                      \
  template <typename T, typename = void>                                \
  struct has_##name : public std::false_type {};                        \
  template <typename T>                                                 \
  struct has_##name<T, void_t<name##_t<T>>> : public std::true_type {};

// detect CommonPrefix(string)
SFINAE_DETECT(common_prefix,
              declval<T>().CommonPrefix(std::string()))

Используя приведенный выше код, создание экземпляра шаблона has_complete<DerivedClass>будет, в общем, делать то, что вы ожидаете. Если DerivedClass имеет метод с именем Complete который принимает std::string, результирующий тип будет.

Что происходит, когда вы хотите перегрузить функцию?

      template <class Derived>
struct Base {
    std::string foo(bool);
    std::string foo(int);
    ...
};

struct Derived : public Base<Derived>
{
    std::string foo(int);
};

В таком случае, Derived действительно имеет метод с именем foo который принимает потому что bool неявно конвертируется в int. Следовательно, даже если мы настроим отправку только для подписи, которая принимает логическое значение, has_foo<Derived> решит std::true_type, и звонок будет отправлен на Derived::foo(int). Мы этого хотим? Вероятно, нет, потому что виртуальные функции работают не так. Функция может переопределить виртуальную функцию только в том случае, если две подписи точно совпадают. Предлагаю создать такой же статический механизм диспетчеризации.

      template <template <class...> class Op, class... Types>
struct dispatcher;

template <template <class...> class Op, class T>
struct dispatcher<Op, T> : std::experimental::detected_t<Op, T> {};

template <template <class...> class Op, class T, class... Types>
struct dispatcher<Op, T, Types...>
  : std::experimental::detected_or_t<
    typename dispatcher<Op, Types...>::type, Op, T> {};

template <template <class...> class Op, class... Types>
using dispatcher_t = typename dispatcher<Op, Types...>::type;

Это хорошо, но одно это не требует проверки подписи. Чтобы выполнить строгую проверку подписи, мы должны правильно определить параметр шаблона шаблона. Для этого мы воспользуемся std::integral_constantуказателя на функцию-член. Вот как это выглядит:

      template <class T>
using foo_op_b = std::integral_constant<std::string(T::*)(bool), &T::foo>;

template <class T>
using foo_op_i = std::integral_constant<std::string(T::*)(int), &T::foo>

Определение наших Ops таким образом позволяет нам отправлять только методы с точным совпадением сигнатур.

      // Resolves to std::integral_constant<std::string(T::*)(bool), &Derived::foo>
using foo_bool_ic = dispatcher_t<foo_op_b, Derived, Defaults>;

// Resolves to std::integral_constant<std::string(T::*)(int), &Defaults::foo>
using foo_int_ic = dispatcher_t<foo_op_i, Derived, Defaults>;

А теперь давайте все вместе.

      #include <iostream>
#include <experimental/type_traits>
#include <string>

template <template <class...> class Op, class... Types>
struct dispatcher;

template <template <class...> class Op, class T>
struct dispatcher<Op, T> : std::experimental::detected_t<Op, T> {};

template <template <class...> class Op, class T, class... Types>
struct dispatcher<Op, T, Types...>
  : std::experimental::detected_or_t<
    typename dispatcher<Op, Types...>::type, Op, T> {};

template <template <class...> class Op, class... Types>
using dispatcher_t = typename dispatcher<Op, Types...>::type;


// Used to deduce class type from a member function pointer
template <class R, class T, class... Args>
auto method_cls(R(T::*)(Args...)) -> T;


struct Defaults {
    std::string foo(bool value) { return value ? "true" : "false"; }
    std::string foo(int  value) { return value ? "true" : "false"; }

    // Ensure that the class is polymorphic so we can use dynamic_cast
    virtual ~Defaults() {};
};

template <class Derived>
struct Base : Defaults {
    template <class T>
    using foo_op_b = std::integral_constant<std::string(T::*)(bool), &T::foo>;

    template <class T>
    using foo_op_i = std::integral_constant<std::string(T::*)(int), &T::foo>;

    std::string foo(bool value) {
        auto method = dispatcher_t<foo_op_b, Derived, Defaults>::value;
        auto *target = dynamic_cast<decltype(method_cls(method)) *>(this);
        return (target->*method)(value);
    }

    std::string foo(int value) {
        auto method = dispatcher_t<foo_op_i, Derived, Defaults>::value;
        auto *target = dynamic_cast<decltype(method_cls(method)) *>(this);
        return (target->*method)(value);
    }
};

struct Derived : Base<Derived> {
    std::string foo(bool value) { return value ? "TRUE" : "FALSE"; }
};

int main() {
    Derived d;
    std::cout << dynamic_cast<Base<Derived> *>(&d)->foo(true) << std::endl; // TRUE
    std::cout << dynamic_cast<Base<Derived> *>(&d)->foo(1) << std::endl;    // true
}

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

user23167 04 ноя '08 в 16:12 2008-11-04 16:12 · Answer 5 · 2008-11-04 16:12

Этот ответ Википедии имеет все, что вам нужно. А именно:

template <class Derived> struct Base
{
    void interface()
    {
        // ...
        static_cast<Derived*>(this)->implementation();
        // ...
    }

    static void static_func()
    {
        // ...
        Derived::static_sub_func();
        // ...
    }
};

struct Derived : Base<Derived>
{
    void implementation();
    static void static_sub_func();
};

Хотя я не знаю, сколько это на самом деле покупает. Затраты на вызов виртуальной функции (конечно, зависят от компилятора):

Память: один указатель на виртуальную функцию
Время выполнения: один вызов указателя функции

В то время как издержки статического полиморфизма CRTP составляют:

Память: дублирование базы на каждый экземпляр шаблона
Время выполнения: один вызов указателя функции + все, что делает static_cast