在编译时确定最近公共祖先

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。

- Nicolas Holthaus

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

这可能还有改进的空间，但可以用作起点。

- Holt

---

抱歉，我应该提到我正在使用不支持 constexpr 的 msvc2013 进行构建。 - Nicolas Holthaus

@NicolasHolthaus 在这种情况下，您可以将constexpr替换为const，这只是对我来说更加简洁。我已经更新了答案。 - Holt

谢谢，我正在测试它。Visual Studio 在选择模板特化方面也很奇怪，因为它不执行两阶段查找，所以在我知道它是否有效之前，我可能需要重新设计 enable_if 语句。 - Nicolas Holthaus

@NicolasHolthaus 我现在无法使用 msvc 2013 进行测试，但看起来它可以在 msvc 2015 上运行（http://rextester.com/l/cpp_online_compiler_visual）。 - Holt

Answer 2

template <typename...> struct typelist {};

template <typename T, typename... Ts>
struct path : path<typename T::parent, T, Ts...> {};

template <typename T, typename... Ts>
struct path<T, T, Ts...> { using type = typelist<T, Ts...>; };

template <typename T, typename U>
struct least;

template <typename T, typename... Vs, typename... Us>
struct least<typelist<T, Vs...>, typelist<T, Us...>> { using type = T; };

template <typename T, typename W, typename... Vs, typename... Us>
struct least<typelist<T, W, Vs...>, typelist<T, W, Us...>>
    : least<typelist<W, Vs...>, typelist<W, Us...>> {};

template <typename V, typename U>
using least_common_ancestor = least<typename path<V>::type, typename path<U>::type>;

演示

---

1. 自下而上：从两个节点到根节点，通过在每个级别前面添加一个类型列表（path<?, T, Ts...>）来形成路径（path::type），直到parent等于当前处理的节点（<T, T, ?...>）。向上移动是通过将T替换为T::parent来完成的。

2. 自上而下：同时遍历这两个类型列表（least），直到在相应位置出现不匹配的地方（Vs..., Us...）；如果出现不匹配，则最后一个公共节点是共同的祖先（T）；否则，删除匹配节点（T）并向下移动一层（现在W是最后一个已知的公共节点）。

- Piotr Skotnicki

Answer 3

这可能不是最算法效率高的方法，但它是有效的。

首先，我们要根据每种类型的祖先创建列表。所以对于 A，这将是 <A,E,G>，对于 G，这将是 <G>：

template <class X>
using parent_t = typename X::parent;

template <class... > struct typelist {}; 
template <class T> struct tag_t { using type = T; };

template <class, class> struct concat;
template <class X, class Y> using concat_t = typename concat<X, Y>::type;

template <class... Xs, class... Ys> 
struct concat<typelist<Xs...>, typelist<Ys...>>
: tag_t<typelist<Xs..., Ys...>>
{ };

template <class X, class = parent_t<X>>
struct ancestors
    : tag_t<concat_t<typelist<X>, typename ancestors<parent_t<X>>::type>>
{ };

template <class X>
struct ancestors<X, X>
    : tag_t<typelist<X>>
{ };

template <class X>
using ancestors_t = typename ancestors<X>::type;

那么两个节点的最近公共祖先将是一个节点的祖先中第一个出现在另一个节点的祖先中的节点：

template <class X, class TL> struct contains;
template <class X, class TL> using contains_t = typename contains<X, TL>::type;

template <class X, class... Xs>
struct contains<X, typelist<X, Xs...>> : std::true_type { };

template <class X, class Y, class... Xs>
struct contains<X, typelist<Y, Xs...>> : contains_t<X, typelist<Xs...>> { };

template <class X>
struct contains<X, typelist<>> : std::false_type { };

template <class X, class Y>
struct lca_impl;

template <class X, class Y>
struct lca : lca_impl<ancestors_t<X>, ancestors_t<Y>> { };

template <class X, class... Xs, class TL>
struct lca_impl<typelist<X, Xs...>, TL>
    : tag_t<
        typename std::conditional_t<contains_t<X, TL>::value,
            tag_t<X>,
            lca_impl<typelist<Xs...>, TL>
            >::type
        >
{ };


template <class X, class Y>
using lca_t = typename lca<X, Y>::type;

这个功能的行为符合您的预期：

static_assert(std::is_same<lca_t<A, E>, E>{}, "!");
static_assert(std::is_same<lca_t<A, D>, G>{}, "!");

- Barry