c++ - コンパイル時に最小共通祖先を決定する

Question

最も一般的でない祖先アルゴリズムについてはたくさんの質問がありますが、コンパイル時に LCA を決定しようとしており、単純化されたバージョンは次のように見えるかもしれませんが、ツリーはバイナリでも検索ツリーでもないため、これは異なります。 1。

parent別の同様の構造であるメンバー typedef を含む一連の構造があるとします。

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

これはおそらく改善される可能性がありますが、出発点として使用できます。

Answer 2

これはおそらくアルゴリズム的に最も効率的なアプローチではありませんが、機能的です。

まず、各型の祖先からリストを作成します。したがって、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;

次に、2 つのノードの最小共通祖先は、一方のノードの祖先の最初のノードであり、もう一方のノードの祖先に含まれています。

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>{}, "!");