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

89

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

Гонки легкости на орбите
источник

Ответы:

141

Есть два пути.

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

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

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

Дин Майкл
источник
15
Отличный ответ
Эли Бендерски
5
Я хотел бы подчеркнуть, что not_derived_from_baseэто не производное baseи не производное от base...
leftaroundabout
3
На самом деле объявление foo () внутри my_type / your_type не требуется. codepad.org/ylpEm1up (вызывает переполнение стека) - есть ли способ обеспечить определение foo во время компиляции? - Хорошо, нашел решение: ideone.com/C6Oz9 - Возможно, вы захотите исправить это в своем ответе.
cooky451 03
3
Не могли бы вы объяснить мне, какова мотивация использовать CRTP в этом примере? Если бы bar был определен как шаблон <class T> void bar (T & obj) {obj.foo (); }, тогда подойдет любой класс, предоставляющий foo. Итак, исходя из вашего примера, похоже, что единственное использование CRTP - это указать интерфейс во время компиляции. Это зачем?
Антон Данейко
1
@Dean Michael Действительно, код в примере компилируется, даже если foo не определен в my_type и your_type. Без этих переопределений рекурсивно вызывается base :: foo (и stackoverflows). Так что, может быть, вы хотите исправить свой ответ, как показал cooky451?
Антон Данейко
18

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

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

шипучка
источник
@fizzer Я прочитал предложенную вами часть, но все еще не понимаю, что означает двойная сумма шаблона <class T_leaftype> (Matrix <T_leaftype> & A); покупает вас по сравнению с шаблоном <class Whatever> с двойной суммой (Whatever & A);
Антон Данейко
@AntonDaneyko При вызове в базовом экземпляре вызывается сумма базового класса, например, «площадь формы» с реализацией по умолчанию, как если бы это был квадрат. Цель CRTP в этом случае состоит в том, чтобы разрешить наиболее производную реализацию, «область трапеции» и т. Д., Сохраняя при этом возможность ссылаться на трапецию как на форму, пока не потребуется производное поведение. В основном, когда вам обычно нужны dynamic_castвиртуальные методы.
John P
1

Пришлось искать CRTP . Однако, сделав это, я нашел кое-что о статическом полиморфизме . Подозреваю, что это ответ на ваш вопрос.

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

Роджер Липскомб
источник
-5

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

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
user23167
источник
4
Фактически, дублирование Base для экземпляра шаблона является иллюзией, потому что (если у вас все еще нет vtable) компилятор объединит хранилище базы и производного в единую структуру для вас. Вызов указателя функции также оптимизируется компилятором (часть static_cast).
Дин Майкл
19
Кстати, ваш анализ CRTP неверен. Должно быть: Память: Ничего, как сказал Дин Майкл. Время выполнения: один (более быстрый) вызов статической функции, а не виртуальной, и в этом весь смысл упражнения. static_cast ничего не делает, он просто позволяет коду компилироваться.
Frederik Slijkerman 05
2
Я хочу сказать, что базовый код будет дублироваться во всех экземплярах шаблона (то самое слияние, о котором вы говорите). Это похоже на наличие в шаблоне только одного метода, основанного на параметре шаблона; все остальное лучше в базовом классе, иначе он втягивается («объединяется») несколько раз.
user23167 05
1
Каждый метод в базе будет компилироваться заново для каждого производного. В (ожидаемом) случае, когда каждый экземпляр метода отличается (из-за того, что свойства Derived различны), это не обязательно может считаться накладными расходами. Но это может привести к увеличению общего размера кода по сравнению с ситуацией, когда сложный метод в (нормальном) базовом классе вызывает виртуальные методы подклассов. Кроме того, если вы поместите служебные методы в Base <Derived>, которые на самом деле вообще не зависят от <Derived>, они все равно будут созданы. Может быть, глобальная оптимизация несколько это исправит.
greggo 01
Вызов, который проходит через несколько уровней CRTP, будет расширяться в памяти во время компиляции, но может легко сжиматься через TCO и встраивание. Тогда CRTP сам по себе не виноват, верно?
Джон П.