Есть тонны вопросов о алгоритме наименьшего общего предка, но это другое, потому что я пытаюсь определить LCA во время компиляции, а мое дерево ни двоичное ни дерево поиска, хотя моя упрощенная версия может выглядеть как.
Предположим, что у вас есть куча структур, которые содержат член typedef parent
, что является другой подобной структурой:
struct G
{
typedef G parent; // 'root' node has itself as parent
};
struct F
{
typedef G parent;
};
struct E
{
typedef G parent;
};
struct D
{
typedef F parent;
};
struct C
{
typedef F parent;
};
struct B
{
typedef E parent;
};
struct A
{
typedef E parent;
};
которые вместе образуют дерево, такое как
A B C D
\ / \ /
E F
\ /
\ /
\ /
G
ПРИМЕЧАНИЕ: между структурами нет отношения наследования.
Мне бы хотелось создать тип-характер least_common_ancestor
, который:
least_common_ancestor<A, B>::type; // E
least_common_ancestor<C, D>::type; // F
least_common_ancestor<A, E>::type; // E
least_common_ancestor<A, F>::type; // G
Какой лучший способ сделать это?
Я не занимаюсь алгоритмической сложностью, особенно потому, что глубина дерева мала, а я ищу простую метапрограмму, которая дойдет до правильного ответа.
EDIT: Мне нужно иметь возможность создавать решение с помощью msvc2013 среди других компиляторов, поэтому предпочтительны ответы без constexpr
.