Смежное хранилище полиморфных типов

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

Например, учитывая следующие классы:

struct B {
int common;
int getCommon() { return common; }
virtual int getVirtual() const = 0;
}

struct D1 : B {
virtual int getVirtual final const { return 5 };
}

struct D2 : B {
int d2int;
virtual int getVirtual final const { return d2int };
}

Я хотел бы выделить непрерывный массив объектов D1 и D2 и рассматривать их как B объекты, включая вызов getVirtual() который делегирует соответствующий метод в зависимости от типа объекта. Концептуально это кажется возможным: каждый объект знает его тип, обычно через встроенный виртуальные таблицы указатель, чтобы вы могли себе представить, храня N объекты в массиве n * max(sizeof(D1), sizeof(D2)) unsigned charи используя размещение new а также delete инициализировать объекты и приведение unsigned char указатель на B*, Однако я уверен, что актеры не законны.

Можно также представить себе создание союза, как:

union Both {
D1 d1;
D2 d2;
}

а затем создать массив Bothи используя размещение new для создания объектов соответствующего типа. Это опять-таки не предлагает способ на самом деле позвонить B::getVirtual() безопасно, однако. Вы не знаете последний сохраненный тип для элементов, так как вы собираетесь получить B*? Вам нужно использовать или &u.d1 или же &u.d2 но ты не знаешь какой! Есть на самом деле специальные правила о «начальных общих подпоследовательностях», которые позволяют вам делать некоторые вещи в профсоюзах, где элементы имеют некоторые общие черты, но это применяется только к стандартным типам макетов. Классы с виртуальными методами не являются стандартными типами макетов.

Есть ли способ продолжить? В идеале решение должно выглядеть как нерезка std::vector<B> которые на самом деле могут содержать полиморфные подклассы B, Да, если требуется, можно предусмотреть, что все возможные подклассы известны заранее, но лучшее решение должно было бы знать только максимально вероятный размер любого подкласса (и потерпеть неудачу во время компиляции, если кто-то пытается добавить «слишком большой» объект) ,

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

Фон

Без сомнения, кто-то спросит «почему», так что вот немного мотивации:

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

Однако не так часто обсуждается тот факт, что использование классов с виртуальными методами для реализации полиморфизма обычно подразумевает совершенно иной способ управления памятью для базовых объектов. Вы не можете просто добавить объекты разных типов (но с общей базой) в стандартный контейнер: если у вас есть подклассы D1 а также D2оба получены из базы B, std::vector<B> отрезал бы любой D1 или же D2 объекты добавлены. Аналогично для массивов таких объектов.

Обычное решение состоит в том, чтобы вместо этого использовать контейнеры или массивы указатели в базовый класс, как std::vector<B*> или возможно std::vector<unique_ptr<B>> или же std::vector<shared_ptr<B>>, Как минимум, это добавляет дополнительную косвенность при доступе к каждому элементу.1, а в случае умных указателей он ломается общие оптимизации контейнеров. Если вы на самом деле выделяете каждый объект через new а также delete (в том числе косвенно), тогда затраты времени и памяти на хранение ваших объектов просто увеличились на большую сумму.

Концептуально кажется, что различные подклассы общей базы могут храниться последовательно (каждый объект будет занимать одинаковое количество места: пространство самого большого поддерживаемого объекта), и что указатель на объект может рассматриваться как указатель базового класса. В некоторых случаях это может значительно упростить и ускорить использование таких полиморфных объектов. Конечно, в общем, это, вероятно, ужасная идея, но для целей этого вопроса давайте предположим, что она имеет какое-то нишевое применение.


1 Помимо прочего, это косвенное обращение в значительной степени предотвращает любую векторизацию одной и той же операции, применяемой ко всем элементам, и наносит ущерб локальности ссылок с последствиями как для кэширования, так и для предварительной выборки.

12

Решение

Вы были почти там с вашим союзом. Вы можете использовать помеченный союз (добавить if различать в своей петле) или std::variant (вводится своего рода двойная диспетчеризация через std::find чтобы получить объект из этого), чтобы сделать это. Ни в том, ни в другом случае у вас нет выделения в динамическом хранилище, поэтому локальность данных гарантирована.
В любом случае, как вы можете видеть, в любом случае вы можете заменить дополнительный уровень косвенного обращения (виртуальный вызов) простым прямым вызовом. Вам нужно стирать как-то типа (полиморфизм — не что иное, как стирание типа, подумайте об этом), и вы не можете выбраться непосредственно из стертого объекта с просто вызов. ifs или дополнительные вызовы, чтобы заполнить пробел дополнительного уровня косвенности требуются.

Вот пример, который использует std::variant а также std::find:

#include<vector>
#include<variant>

struct B { virtual void f() = 0; };
struct D1: B { void f() override {} };
struct D2: B { void f() override {} };

void f(std::vector<std::variant<D1, D2>> &vec) {
for(auto &&v: vec) {
std::visit([](B &b) { b.f(); }, v);
}
}

int main() {
std::vector<std::variant<D1, D2>> vec;
vec.push_back(D1{});
vec.push_back(D2{});
f(vec);
}

Поскольку это действительно близко, это не стоит того, чтобы публиковать также пример, который использует тегированные союзы.


Другой способ сделать это — использовать отдельные векторы для производных классов и опорный вектор для их итерации в правильном порядке.
Вот минимальный пример, который показывает это:

#include<vector>
#include<functional>

struct B { virtual void f() = 0; };
struct D1: B { void f() override {} };
struct D2: B { void f() override {} };

void f(std::vector<std::reference_wrapper<B>> &vec) {
for(auto &w: vec) {
w.get().f();
}
}

int main() {
std::vector<std::reference_wrapper<B>> vec;
std::vector<D1> d1;
std::vector<D2> d2;

d1.push_back({});
vec.push_back(d1.back());
d2.push_back({});
vec.push_back(d2.back());

f(vec);
}
5

Другие решения

Я пытаюсь реализовать то, что вы хотите без памяти:

template <typename Base, std::size_t MaxSize, std::size_t MaxAlignment>
struct PolymorphicStorage
{
public:
template <typename D, typename ...Ts>
D* emplace(Ts&&... args)
{
static_assert(std::is_base_of<Base, D>::value, "Type should inherit from Base");
auto* d = new (&buffer) D(std::forward<Ts>(args)...);
assert(&buffer == reinterpret_cast<void*>(static_cast<Base*>(d)));
return d;
}

void destroy() { get().~Base(); }

const Base& get() const { return *reinterpret_cast<const Base*>(&buffer); }
Base& get() { return *reinterpret_cast<Base*>(&buffer); }

private:
std::aligned_storage_t<MaxSize, MaxAlignment> buffer;
};

демонстрация

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

Я не могу =delete их, иначе вы не можете использовать их в std::vector,

С памятью, variant кажется тогда проще.

4

Итак, это действительно ужасно, но если вы не используете множественное наследование или виртуальное наследование, Derived * в большинстве реализаций будет иметь то же значение уровня битов, что и Base *,

Вы можете проверить это с static_assert так что вещи не скомпилируются, если это не так на конкретной платформе, и используйте ваш union идея.

#include <cstdint>

class Base {
public:
virtual bool my_virtual_func() {
return true;
}
};

class DerivedA : public Base {
};

class DerivedB : public Base {
};

namespace { // Anonymous namespace to hide all these pointless names.
constexpr DerivedA a;
constexpr const Base *bpa = &a;
constexpr DerivedB b;
constexpr const Base *bpb = &b;

constexpr bool test_my_hack()
{
using ::std::uintptr_t;

{
const uintptr_t dpi = reinterpret_cast<uintptr_t>(&a);
const uintptr_t bpi = reinterpret_cast<uintptr_t>(bpa);
static_assert(dpi == bpi, "Base * and Derived * !=");
}
{
const uintptr_t dpi = reinterpret_cast<uintptr_t>(&b);
const uintptr_t bpi = reinterpret_cast<uintptr_t>(bpb);
static_assert(dpi == bpi, "Base * and Derived * !=");
}
// etc...
return true;
}
}

const bool will_the_hack_work = test_my_hack();

Единственная проблема заключается в том, что правила constexpr запрещают вашим объектам иметь виртуальные деструкторы, потому что они будут считаться «нетривиальными». Вам придется уничтожить их, вызвав виртуальную функцию, которая должна быть определена в каждом производном классе, который затем вызывает деструктор напрямую.

Но если этот фрагмент кода успешно компилируется, то не имеет значения, если вы получите Base * от DerivedA или же DerivedB член вашего союза. Они все равно будут одинаковыми.

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

2

Был разговор на CppCon 2017, «Полиморфизм времени выполнения — назад к основам«, который обсуждал делать что-то вроде того, что вы просите. Слайды на GitHub и видео разговора доступно на YouTube.

Говорящий экспериментальный Библиотека для достижения этого, «Dyno», также на GitHub.

2

Мне кажется, что вы ищете variant, который является помеченным союзом с безопасным доступом.

с ++ 17 имеет std::variant, Для предыдущих версий, Boost предлагает версию — boost::variant

Обратите внимание, что полиморфизм больше не нужен. В этом случае я использовал сигнатурно-совместимые методы для обеспечения полиморфизма, но вы также можете предоставить его через сигнатурно-совместимые бесплатные функции и ADL.

#include <variant>   // use boost::variant if you don't have c++17
#include <vector>
#include <algorithm>

struct B {
int common;
int getCommon() const { return common; }
};

struct D1 : B {
int getVirtual() const { return 5; }
};

struct D2 : B {
int d2int;
int getVirtual() const { return d2int; }
};

struct d_like
{
using storage_type = std::variant<D1, D2>;

int get() const {
return std::visit([](auto&& b)
{
return b.getVirtual();
}, store_);
}

int common() const {
return std::visit([](auto&& b)
{
return b.getCommon();
}, store_);
};

storage_type store_;
};

bool operator <(const d_like& l, const d_like& r)
{
return l.get() < r.get();
}

struct by_common
{
bool operator ()(const d_like& l, const d_like& r) const
{
return l.common() < r.common();
}
};

int main()
{
std::vector<d_like> vec;
std::sort(begin(vec), end(vec));
std::sort(begin(vec), end(vec), by_common());
}
1
По вопросам рекламы ammmcru@yandex.ru
Adblock
detector