Общий Quadtree
Я пишу класс quadtree как часть графической библиотеки и столкнулся с проблемой дизайна.
Основная цель — позволить пользователю библиотеки легко расширять quadtree своими собственными типами узлов. Каждый узел имеет указатель на первый из его четырех дочерних элементов. Я использую шаблон прототипа для «клонирования» родительского узла (его реальный тип неизвестен библиотеке) четыре раза, когда он разделяется. Итак, вот класс Node:
class CNode {
public:
virtual CNode* clone();
protected:
CNode* pChilds;
}
Пользователь библиотеки теперь может определить свой собственный узел и добавить метод перемещения:
class MyNode : public CNode {
public:
virtual CNode* clone() {
return new MyNode;
}
void myTraverse() {
if(pChilds[0] != nullptr)
static_cast<MyNode*>(pChilds[0])->traverse();
}
}
Как видно, я должен выполнить приведение из базового класса к производному классу. В качестве альтернативы я мог бы создать все шаблоны классов, связанных с квадродеревом, но я действительно не хочу этого делать.
Я также не могу использовать повышение. Кроме того, boost :: any и аналогичные решения с RTTI или динамическим преобразованием должны быть медленными, поскольку квадродерево является критически важным компонентом производительности и должно работать как можно быстрее!
Есть ли возможность поддерживать скорость static_cast при добавлении безопасности типов? (дерево quadtree будет содержать только узлы одного типа).
Решение
Я знаю, что вы сказали, что не хотите использовать шаблоны, но такого рода вещи именно так для чего нужны шаблоны Делая ваш класс узла виртуальным классом, вы накладываете дополнительные издержки на каждую конструкцию и разрушение, а также увеличиваете размер структуры узла по крайней мере на один указатель, что снизит когерентность кэша.
Кроме того, отказ от использования шаблонов приведет вас в бешенство static_casts и небезопасный код. Обратите внимание, например, что если pChilds указывает на массив MyNode а также MyNode имеет какие-либо переменные-члены, тогда оператор индекса не будет работать должным образом.
Другие решения
Так как вы сказали
квадродерево будет содержать только узлы одного типа
тогда вы можете использовать это предположение для оптимизации вашего кода. Как в, вы можете предположить, в теле MyNode::myTraverse() тот thisдети все будут MyNode и вы можете безопасно static_cast любые дети в MyNodes.
Однако вы можете беспокоиться о том, что произойдет, если ошибка в вашем коде нарушает инвариант вашей структуры данных о том, что она может содержать только элементы одного типа. Здесь условная компиляция может пригодиться. Принимая символ DEBUG определяется в отладочных сборках:
#ifdef DEBUG
#define my_cast dynamic_cast
#else
#define my_cast static_cast
#endif
...
void MyNode::myTraverse() {
if(pChilds[0] != nullptr)
my_cast<MyNode*>(pChilds[0])->traverse();
}
Это даст вам скорость static_cast в ваших сборках релиза и проверки типов во время выполнения dynamic_cast в ваших отладочных сборках, где скорость не так важна. И есть вероятность, что если вы нарушаете инвариант вашей структуры в ваших сборках релиза, вы также будете делать это в ваших отладочных сборках, и ваши отладочные сборки, вероятно, будут аварийно завершаться (на самом деле это будет неопределенное поведение, но большинство платформ будут аварийно завершать работу). когда вы разыменовываете нулевой указатель) с исключениями / segfaults нарушения прав доступа.
В качестве альтернативы, вы можете придерживаться dynamic_cast на данный момент, и переключиться на static_cast как только вы будете готовы выпустить и / или вы сделали тестирование, которое показывает, что с помощью dynamic_cast вместо static_cast приводит к недопустимому снижению производительности.
Изменить: И так как вы создаете библиотеку, убедитесь, что она очень ясно, что ваши пользователи clone() должен возвращать объект того же типа, к которому он был вызван, с некоторыми примерами. Это одна из тех ситуаций, когда вы не можете быть уверены, что другой программист не допустит ошибок, и вы просто должны поверить, что он может читать комментарии или документацию.