最小共通祖先アルゴリズムに関する質問は山ほどあるが、これはコンパイル時にLCAを決定しようとしている点で異なっており、私の木はどちらでもないバイナリまたは検索ツリー私の簡略版はそう見えるかもしれませんが。
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が望ましいです。
ベストアンサー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
これはおそらく改善される可能性がありますが、出発点として使用できます。