c++ - 在编译时确定最小共同祖先

Question

关于最小共同祖先算法有很多问题，但这个不同，因为我试图在编译时确定 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

最好的方法是什么？

我不关心算法的复杂性，特别是因为树的深度很小，我正在寻找最简单的元程序，它会得到正确的答案。

编辑:我需要能够使用 msvc2013 以及其他编译器构建解决方案，因此首选没有 constexpr 的答案。

Answer 1

这可能会有所改进，但您可以先计算您的类型的深度，然后使用此信息向上一个或另一个分支:

template <typename U, typename = typename U::parent>
struct depth {
    static const int value = depth<typename U::parent>::value + 1;
};

template <typename U>
struct depth<U, U> {
    static const int value = 0;
};

上面将基本上计算你的类型在你的树中的深度。

那么你可以使用 std::enable_if :

template <typename U, typename V, typename Enabler = void>
struct least_common_ancestor;

template <typename U>
struct least_common_ancestor<U, U> {
    using type = U;
};

template <typename U, typename V>
struct least_common_ancestor<U, V,
                             typename std::enable_if<(depth<U>::value < depth<V>::value)>::type> {
    using type = typename least_common_ancestor<U, typename V::parent>::type;
};

template <typename U, typename V>
struct least_common_ancestor<U, V,
                             typename std::enable_if<(depth<V>::value < depth<U>::value)>::type> {
    using type = typename least_common_ancestor<V, typename U::parent>::type;
};

template <typename U, typename V>
struct least_common_ancestor<U, V,
                             typename std::enable_if<!std::is_same<U, V>::value && (depth<V>::value == depth<U>::value)>::type> {
    using type = typename least_common_ancestor<typename V::parent, typename U::parent>::type;
};

输出:

int main(int, char *[]) {

    std::cout << std::is_same<least_common_ancestor<A, B>::type, E>::value << std::endl;
    std::cout << std::is_same<least_common_ancestor<C, D>::type, F>::value << std::endl;
    std::cout << std::is_same<least_common_ancestor<A, E>::type, E>::value << std::endl;
    std::cout << std::is_same<least_common_ancestor<A, F>::type, G>::value << std::endl;
    std::cout << std::is_same<least_common_ancestor<A, A>::type, A>::value << std::endl;

    return 0;
}

给予:

1 1 1 1 1

这可能会有所改进，但可以作为起点。