Soru Derleme zamanında en az kullanılan atayı belirle


En az görülen atası algoritması hakkında tonlarca soru vardır, fakat bu farklıdır çünkü derleme zamanında LCA'yı belirlemeye çalışıyorum ve benim ağacım ne ikili ne de bir arama ağacıBasitleştirilmiş versiyonumun bir tane gibi görünmesine rağmen.

Bir üye typedef içeren bir dizi yapı olduğunu varsayalım parentBaşka benzer bir yapıdır:

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;
};

birlikte bir ağaç gibi

A    B    C    D
 \  /      \  /
  E         F
   \       /
    \     /
     \   /
       G

NOT: Yapılar arasında kalıtım ilişkisi yoktur.

Yapmak istediğim şey tür özelliği oluşturmak least_common_ancestor öyle ki:

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

Bunu yapmanın en iyi yolu nedir?

Özellikle ağaç derinliği küçük olduğundan algoritmik karmaşıklıkla ilgilenmiyorum, doğru cevaba ulaşacak en basit meta programı arıyorum.

DÜZENLE: Diğer derleyiciler arasında msvc2013 ile çözümü yapabilmem gerekiyor, constexpr tercih edilir.


18
2018-04-11 14:48


Menşei




Cevaplar:


Bu muhtemelen geliştirilebilir, ancak önce türünüzün derinliğini hesaplayabilir ve ardından bu bilgiyi bir şube veya diğerine gitmek için kullanabilirsiniz:

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;
};

Yukarıdaki temelde temelde hesaplayacaktır. derinlik senin ağacında senin tipin.

Sonra kullanabilirsiniz 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;
};

Çıktı:

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;
}

verir:

1 1 1 1 1

Bu muhtemelen geliştirilebilir, ancak başlangıç ​​noktası olarak kullanılabilir.


11
2018-04-11 15:11



Üzgünüm, desteklemediğim msvc2013 üzerinde çalıştığımı belirtmeliydim constexpr. - Nicolas Holthaus
@NicolasHolthaus Değiştirebilirsiniz constexpr ile const Bu durumda, benim için sadece daha temiz oldu. Cevabı güncelledim. - Holt
Teşekkürler, test ediyorum. Visual Studio, iki aşamalı arama yapmadığı için şablon uzmanlıklarını nasıl seçtiği konusunda da tuhaftır, bu yüzden muhtemelen yeniden değerlendirmem gerekecek. enable_if işe yarayıp yaramadığını bildirmeden önce. - Nicolas Holthaus
@NicolasHolthaus Ben şimdi msvc 2013 ile test edemem, ama msvc 2015 ile çalışır gibi görünüyor (rextester.com/l/cpp_online_compiler_visual). - Holt
Kutudan çıktı. Teşekkürler! - Nicolas Holthaus


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>;

DEMO


  1. Alttan yukarı: Form yolları (path::typeHer seviyeden bir tip listesi hazırlayarak her iki düğümden kökepath<?, T, Ts...>), a kadar parent şu anda işlenen düğüme eşittir (<T, T, ?...>). Yukarı doğru hareket etmek yerine geçmek T tarafından T::parent.

  2. Yukarıdan aşağıya doğru: İki yazmayı aynı anda (least), karşılık gelen pozisyonlarda bir uyumsuzluk olana kadarVs..., Us...); eğer öyleyse, son ortak düğüm ortak atandır (T); aksi takdirde (<T, W, ?...>, <T, W, ?...>), eşleşen düğümü kaldırın (T) ve bir adım aşağı (şimdi W en son bilinen ortak düğümdür.


9
2018-04-11 15:31



Belki de kısa bir açıklama yardımcı olabilir, ama bu iyidir. - skypjack


Bu muhtemelen algoritmik olarak en etkili yaklaşım değildir, ancak işlevseldir.

İlk olarak, her türün atalarından listeler oluşturacağız. İçin böylece A bu olabilir <A,E,G> ve için G bu olabilir <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;

Sonra, iki düğümün en az rastlanan ataları, diğer düğümün atalarında yer alan bir düğümün atalarının ilk düğümüdür.

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;

beklediğiniz davranışa sahip olan:

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

5
2018-04-11 15:17



@Downvoter Ne var ne yok? Bu işe yarıyor. - Barry