Сложность времени для вызова виртуальных функций в переполнении стека
Предположим иерархию наследования с типом Base, имеющим F виртуальных функций, D различных производных типов и предполагающих, что каждый производный тип переопределяет все виртуальные функции.
Какова временная сложность вызова одной из виртуальных функций для указателя p типа Base *?
Кроме того, какова сложность пространства системы, если общее количество объектов O (поровну разделено между типами) и все объекты имеют одинаковые элементы данных?
Решение
Временная сложность вызова функции составляет O (1). У каждого класса есть «vtable», который по сути является структурой указателей на функции — у каждого объекта есть указатель на эту vtable, поэтому вызов виртуальной функции — это просто поиск указателя функции в vtable и его вызов.
Полнота пространства объектов O равна O (O), поскольку она линейна по количеству объектов.
Другие решения
Размер объекта рассчитывается как общая сумма атрибутов, размер этого объекта + размер указателя на виртуальную таблицу
так что если
class Base {
int a;
char b;
virtual void f();
virtual void g();
};
это означает, что размер Base b это sizeof (int) + sizeof (b) + size of vtable ptr.
Если вы говорите, что все объекты (производные и не производные) имеют одинаковые члены, их размер одинаков.
Существует один указатель на виртуальную таблицу, которая содержит все виртуальные функции, поэтому доступ к ней и разыменование функции — это O (1).
Сложность пространства равна O (F) (или O (1), если F — константа), поскольку существует одна таблица адресов для всех объектов одного и того же класса.
Цитата из Википедии:
Таблица диспетчеризации объекта будет содержать адреса динамически связанных методов объекта. Вызовы метода выполняются путем извлечения адреса метода из таблицы диспетчеризации объекта. Таблица диспетчеризации одинакова для всех объектов, принадлежащих к одному и тому же классу, и поэтому, как правило, используется совместно ими. Объекты, принадлежащие классам, совместимым с типами (например, братья и сестры в иерархии наследования), будут иметь таблицы диспетчеризации с одинаковым расположением: адрес данного метода будет отображаться с одинаковым смещением для всех классов, совместимых с типами. Таким образом, выборка адреса метода из заданного смещения таблицы диспетчеризации получит метод, соответствующий фактическому классу объекта.