29
İç içe türdeki bir paketin (örneğin, bir ağaç türü) bir önyüklemesini yapmak ve her yaprakta bir eylem gerçekleştirebilmek için, zaten bir algoritma çalıştım. (ve düzgün çalışması için test):Derleme zamanı sırasında bir ağaç geçme, ziyaret etme eylemleriyle
template <typename...> struct Pack {};
template <typename...> struct Group {};
template <typename...> struct Wrap {};
struct Object {};
int main() {
std::cout << std::boolalpha << std::is_same<
Visit<Pack<Wrap<int, Object, double>, bool, Group<char, Pack<int, double, Pack<char, Wrap<char, long, short>, int, Object>, char>, double>, long>, Pack<>>::type,
Pack<int, Object, double, bool, char, int, double, char, char, long, short, int, Object, char, double, long>
>::value << std::endl; // true
}
Ama benim sorunum artık: benim test gösterdiği gibi
template <typename T>
struct HasChildren : std::false_type {};
template <template <typename...> class P, typename... Types>
struct HasChildren<P<Types...>> : std::true_type {};
template <typename, typename> struct Merge;
template <template <typename...> class P1, template <typename...> class P2, typename... Ts, typename... Us>
struct Merge<P1<Ts...>, P2<Us...>> {
using type = P1<Ts..., Us...>;
};
template <typename, typename> struct Visit;
template <typename, typename, bool> struct VisitHelper;
template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
struct Visit<P1<First, Rest...>, P2<Visited...>> :
VisitHelper<P1<First, Rest...>, P2<Visited...>, HasChildren<First>::value> {};
template <template <typename...> class P1, template <typename...> class P2, typename... Visited>
struct Visit<P1<>, P2<Visited...>> { // End of recursion. Every leaf in the tree visited.
using result = P2<Visited...>;
};
template <typename, typename> struct LeafAction;
// As a simple example, the leaf action is appending its type to P<Visited...>.
template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
struct LeafAction<P1<First, Rest...>, P2<Visited...>> : Visit<P1<Rest...>, P2<Visited..., First>> {}; // Having visited First, now visit Rest...
// Here First has children, so visit its children, after which visit Rest...
template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
struct VisitHelper<P1<First, Rest...>, P2<Visited...>, true> : Visit<typename Merge<First, P1<Rest...>>::type, P2<Visited...>> {};
// Here First has no children, so the "leaf action" is carried out.
template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
struct VisitHelper<P1<First, Rest...>, P2<Visited...>, false> : LeafAction<P1<First, Rest...>, P2<Visited...>> {};
benim "yaprak eylem" burada basitçe, ziyaret edilen her yaprağın türünü depolamak nedir her yapraksızda bir eylem yapılacaksa ve böyle bir "yapraksız eylem" gerçekleştirilir. isited? Yapraksız nasıl hatırlanır? Bir düğümün her çocuk (öncesinde değil ama) ziyaret sonra , yukarıda benim Visit programa değinen olmayan yaprak paketinde ilk türünü ekleyin: Burada
bu gerektirecektir bir örnek görevdir
P<Visited...> paketi. Bir yaprak ziyaret edilirse, orijinal programdaki gibi türünü P<Visited...> paketine ekleyin. Bu özel sipariş nedeniyle, Visit<Pack<Types...>>::type belirli bir siparişe sahip olacak. Bunu çözün ve orijinal soru çözüldü. Bu Yaprak olmayan eylem ziyaret SONRA yapılacak Şimdi eğer çözüm nedir #include <iostream>
#include <type_traits>
#include <typeinfo>
template <typename T>
struct HasChildren : std::false_type {};
template <template <typename...> class P, typename... Types>
struct HasChildren<P<Types...>> : std::true_type {};
template <typename, typename> struct Merge;
template <template <typename...> class P1, template <typename...> class P2, typename... Ts, typename... Us>
struct Merge<P1<Ts...>, P2<Us...>> {
using type = P1<Ts..., Us...>;
};
template <typename> struct FirstType;
template <template <typename...> class P, typename First, typename... Rest>
struct FirstType<P<First, Rest...>> {
using type = First;
};
template <typename, typename> struct Visit;
template <typename, typename, bool> struct VisitHelper;
template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
struct Visit<P1<First, Rest...>, P2<Visited...>> :
VisitHelper<P1<First, Rest...>, P2<Visited...>, HasChildren<First>::value> {};
template <template <typename...> class P1, template <typename...> class P2, typename... Visited>
struct Visit<P1<>, P2<Visited...>> { // End of recursion. Every leaf in the tree visited.
using result = P2<Visited...>;
};
template <typename, typename> struct LeafAction;
template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
struct LeafAction<P1<First, Rest...>, P2<Visited...>> : Visit<P1<Rest...>, P2<Visited..., First>> {};
template <typename, typename> struct NonLeafActionPrevisit;
template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
struct NonLeafActionPrevisit<P1<First, Rest...>, P2<Visited...>> :
Visit<typename Merge<First, P1<Rest...>>::type, P2<Visited..., typename FirstType<First>::type>> {};
// Here First has children, so visit its children, after which visit Rest..., but before doing so carry out the non-leaf action in the inherited struct.
template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
struct VisitHelper<P1<First, Rest...>, P2<Visited...>, true> :
NonLeafActionPrevisit<P1<First, Rest...>, P2<Visited...>> {}; // *** The simple solution here.
// Here First has no children, so the "leaf action" is carried out. In this case, it is appended to P<Visited...> as a simple example.
template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
struct VisitHelper<P1<First, Rest...>, P2<Visited...>, false> : LeafAction<P1<First, Rest...>, P2<Visited...>> {};
template <typename> struct VisitTree;
template <template <typename...> class P, typename... Types>
struct VisitTree<P<Types...>> : Visit<P<Types...>, P<>> {};
// ---------------------------- Testing ----------------------------
template <typename...> struct Pack {};
template <typename...> struct Group {};
template <typename...> struct Wrap {};
struct Object {};
int main() {
std::cout << std::boolalpha << std::is_same<
VisitTree<Pack<Wrap<int, Object, double>, bool, Group<char, Pack<int, double, Pack<char, Wrap<char, long, short>, int, Object>, char>, double>, long>>::result,
Pack<int, int, Object, double, bool, char, char, int, int, double, char, char, char, char, long, short, int, Object, char, double, long>
>::value << std::endl; // true
}
: O Yaprak olmayan eylem onun çocukları ziyaret ÖNCE gerçekleştirilir varsa burada
basit bir çözümdür çocuklar? Bu durumda , çıktı, yani farklı olurdu:Pack<int, Object, double, int, bool, char, int, double, char, char, long, short, char, int, Object, int, char, char, double, long>
Fikir: Birinci gelen son çocuğu alın. Son çocuğu ve ilk olarak bir yere saklayın (ama nerede ???). Bu son çocuk ziyaret edildiğinde, ilk sayfada yaprak olmayan eylemi gerçekleştirin. gibi bir şey:
template <typename, typename, typename> struct Visit;
template <typename, typename, typename, bool> struct VisitHelper;
template <template <typename...> class P1, template <typename...> class P2, template <typename...> class P3, typename First, typename... Rest, typename... ChildAndParent, typename... Visited>
struct Visit<P1<First, Rest...>, P2<ChildAndParent...>, P3<Visited...>> :
VisitHelper<P1<First, Rest...>, P2<ChildAndParent...>, P3<Visited...>, HasChildren<First>::value> {};
template <template <typename...> class P1, template <typename...> class P2, template <typename...> class P3, typename... ChildAndParent, typename... Visited>
struct Visit<P1<>, P2<ChildAndParent...>, P3<Visited...>> { // End of recursion. Every leaf in the tree visited.
using type = P3<Visited...>;
};
// Here First has children, so visit its children, after which visit Rest...
template <template <typename...> class P1, template <typename...> class P2, template <typename...> class P3, typename First, typename... Rest, typename... ChildAndParent, typename... Visited>
struct VisitHelper<P1<First, Rest...>, P2<ChildAndParent...>, P3<Visited...>, true> :
Visit<typename Merge<First, P2<Rest...>>::type, P2<ChildAndParent...,
typename LastType<First>::type, First>, P3<Visited...>> {};
// Idea: Get the last child from First. Store that last child and First here. When that last child is visited, carry out the non-leaf action on First.
// Here First has no children, so the "leaf action" is carried out. In this case, it is appended to P<Visited...> as a simple example.
template <template <typename...> class P1, template <typename...> class P2, template <typename...> class P3, typename First, typename... Rest, typename... ChildAndParent, typename... Visited>
struct VisitHelper<P1<First, Rest...>, P2<ChildAndParent...>, P3<Visited...>, false> :
Visit<P1<Rest...>, P2<ChildAndParent...>, P3<Visited..., First>> {};
Şimdi zor olan kısmı hiç çalışacaktır fikrini varsayarak, düzgün P2<ChildAndParent...> yararlanmak olacaktır.
Güncelleştirme (12 saat sonra): Eh, elimden gelenin en iyisini denedim. İşte bu, hangi derleme, hangi derleme, ama neden hala yanlış sonucu aldığımı kaçırıyor. Belki de birileri buna ışık tutabilir. 2 "Yaprak olmayan vardır
template <int N>
void Graph<N>::topologicalSortHelper (int v, std::array<bool, N>& visited, std::stack<int>& stack) {
visited[v] = true; // Mark the current node as visited.
for (int x : adjacentVertices[v]) // Repeat for all the vertices adjacent to this vertex.
if (!visited[x])
topologicalSortHelper (x, visited, stack);
stack.push(v); // Push current vertex to 'stack' which stores the result.
}
: (besbelli çalışma süresi boyunca yürütülür olan) bu döngü düşünün: Eğer merak durumda
#include <iostream>
#include <type_traits>
#include <typeinfo>
template <typename T>
struct HasChildren : std::false_type {};
template <template <typename...> class P, typename... Types>
struct HasChildren<P<Types...>> : std::true_type {};
template <typename, typename> struct Merge;
template <template <typename...> class P1, template <typename...> class P2, typename... Ts, typename... Us>
struct Merge<P1<Ts...>, P2<Us...>> {
using type = P1<Ts..., Us...>;
};
template <typename> struct FirstType;
template <template <typename...> class P, typename First, typename... Rest>
struct FirstType<P<First, Rest...>> {
using type = First;
};
template <typename> struct LastType;
template <template <typename...> class P, typename Last>
struct LastType<P<Last>> {
using type = Last;
};
template <template <typename...> class P, typename First, typename... Rest>
struct LastType<P<First, Rest...>> : LastType<P<Rest...>> {};
template <typename, typename...> struct ExistsInPack;
template <typename T, typename First, typename... Rest>
struct ExistsInPack<T, First, Rest...> : ExistsInPack<T, Rest...> {};
template <typename T, typename... Rest>
struct ExistsInPack<T, T, Rest...> : std::true_type {};
template <typename T>
struct ExistsInPack<T> : std::false_type {};
template <typename Child, typename First, typename Second, typename... Rest>
struct GetParent : GetParent<Child, Rest...> {};
template <typename Child, typename Parent, typename... Rest>
struct GetParent<Child, Child, Parent, Rest...> {
using type = Parent;
};
template <typename, typename, typename> struct RemoveChildAndParentHelper;
template <template <typename...> class P, typename Child, typename First, typename Second, typename... Rest, typename... Accumulated>
struct RemoveChildAndParentHelper<Child, P<First, Second, Rest...>, P<Accumulated...>> : RemoveChildAndParentHelper<Child, P<Rest...>, P<Accumulated..., First, Second>> {};
template <template <typename...> class P, typename Child, typename Parent, typename... Rest, typename... Accumulated>
struct RemoveChildAndParentHelper<Child, P<Child, Parent, Rest...>, P<Accumulated...>> {
using type = P<Accumulated..., Rest...>;
};
template <template <typename...> class P, typename Child, typename... Accumulated>
struct RemoveChildAndParentHelper<Child, P<>, P<Accumulated...>> {
using type = P<Accumulated...>;
};
template <typename, typename> struct RemoveChildAndParent;
template <template <typename...> class P, typename Child, typename... LastChildAndParent>
struct RemoveChildAndParent<Child, P<LastChildAndParent...>> : RemoveChildAndParentHelper<Child, P<LastChildAndParent...>, P<>> {};
template <typename, typename, typename> struct Visit;
template <typename, typename, typename, bool> struct VisitHelper;
template <typename, typename, typename, bool> struct CheckIfLastChild;
template <template <typename...> class P1, template <typename...> class P2, template <typename...> class P3, typename First, typename... Rest, typename... LastChildAndParent, typename... Visited>
struct Visit<P1<First, Rest...>, P2<LastChildAndParent...>, P3<Visited...>> :
VisitHelper<P1<First, Rest...>, P2<LastChildAndParent...>, P3<Visited...>, HasChildren<First>::value> {};
template <template <typename...> class P1, template <typename...> class P2, template <typename...> class P3, typename... LastChildAndParent, typename... Visited>
struct Visit<P1<>, P2<LastChildAndParent...>, P3<Visited...>> { // End of recursion. Every leaf in the tree visited.
using result = P3<Visited...>;
using storage = P2<LastChildAndParent...>; // just for checking (remove later)
};
// Here First has children, so visit its children, after which visit Rest...
// Get the last child from First. Store that last child and First here. When that last child is visited later on, carry out the non-leaf action on First.
template <template <typename...> class P1, template <typename...> class P2, template <typename...> class P3, typename First, typename... Rest, typename... LastChildAndParent, typename... Visited>
struct VisitHelper<P1<First, Rest...>, P2<LastChildAndParent...>, P3<Visited...>, true> :
Visit<typename Merge<First, P2<Rest...>>::type, P2<LastChildAndParent..., typename LastType<First>::type, First>, P3<Visited...>> {};
// Here First has no children, so the "leaf action" is carried out. In this case, it is appended to P<Visited...>.
// Check if First is a last child. If so the non-leaf action of its parent is to be carried out immediately after First's action is carried out.
template <template <typename...> class P1, template <typename...> class P2, template <typename...> class P3, typename First, typename... Rest, typename... LastChildAndParent, typename... Visited>
struct VisitHelper<P1<First, Rest...>, P2<LastChildAndParent...>, P3<Visited...>, false> :
CheckIfLastChild<P1<First, Rest...>, P2<LastChildAndParent...>, P3<Visited...>, ExistsInPack<First, LastChildAndParent...>::value> {};
// First is a last child (and is a leaf), so append First to P3<Visited...> (the leaf action), and then append the first type of its parent to P3<Visited...> after it (the non-leaf action).
// First and its parent must be removed from P2<LastChildAndParent...> at this point.
template <template <typename...> class P1, template <typename...> class P2, template <typename...> class P3, typename First, typename... Rest, typename... LastChildAndParent, typename... Visited>
struct CheckIfLastChild<P1<First, Rest...>, P2<LastChildAndParent...>, P3<Visited...>, true> :
Visit<P1<Rest...>, typename RemoveChildAndParent<First, P2<LastChildAndParent...>>::type, P3<Visited..., First, typename FirstType<typename GetParent<First, LastChildAndParent...>::type>::type>> {};
// First is not a last child (but is a leaf), so append First to P3<Visited...> (the leaf action) and proceed with visiting the next type in P1<Rest...>.
template <template <typename...> class P1, template <typename...> class P2, template <typename...> class P3, typename First, typename... Rest, typename... LastChildAndParent, typename... Visited>
struct CheckIfLastChild<P1<First, Rest...>, P2<LastChildAndParent...>, P3<Visited...>, false> : Visit<P1<Rest...>, P2<LastChildAndParent...>, P3<Visited..., First>> {};
template <typename> struct VisitTree;
template <template <typename...> class P, typename... Types>
struct VisitTree<P<Types...>> : Visit<P<Types...>, P<>, P<>> {};
// ---------------------------- Testing ----------------------------
template <typename...> struct Pack;
template <typename Last>
struct Pack<Last> {
static void print() {std::cout << typeid(Last).name() << std::endl;}
};
template <typename First, typename... Rest>
struct Pack<First, Rest...> {
static void print() {std::cout << typeid(First).name() << ' '; Pack<Rest...>::print();}
};
template <>
struct Pack<> {
static void print() {std::cout << "empty" << std::endl;}
};
template <typename...> struct Group {};
template <typename...> struct Wrap {};
struct Object {};
int main() {
using Tree = VisitTree<Pack<Wrap<int, Object, double>, bool, Group<char, Pack<int, double, Pack<char, Wrap<char, long, short>, int, Object>, char>, double>, long>>;
Tree::result::print(); // int Object double int bool char int double char char int char long short int Object char char double long
Tree::storage::print(); // empty
std::cout << std::boolalpha << std::is_same<
Tree::result,
Pack<int, Object, double, int, bool, char, int, double, char, char, long, short, char, int, Object, char, char, int, char, double, long>
>::value << std::endl; // false
}
, bunun için burada benim motivasyon olduğunu eylemler "burada. Çocukları ziyaret etmeden önce visited[v] = true; yürütülür, bu yüzden sorun yoktur (sadece mirastaki değişikliği yapın), fakat asıl sorun çocuklar ziyaret edildikten sonra gerçekleştirilen stack.push(v);'dur. Sonunda, Graph<6, 5,2, 5,0, 4,0, 4,1, 2,3, 3,1>::topological_sort'un derleme zamanı sonucu index_sequence<5,4,2,3,1,0> olmasını istiyorum, burada 6 köşe sayısıdır ve 5,2, 5,0, 4,0, 4,1, 2,3, 3,1 grafiğin kenarlarını açıklar. Neredeyse bittiğim, üzerinde çalıştığım gerçek proje. Yukarıdaki genel sorunu çözün ve bu problemi çözeceğim.
Güncelleme: Mantığımdaki hatayı tespit ettim. satır: tip First vardır ağacında diğer yapraklar olabileceğinden son çocuk olduğu
Visit<typename Merge<First, P2<Rest...>>::type, P2<LastChildAndParent..., typename LastType<First>::type, First>, P3<Visited...>>
benzersiz tanımlamaz. Ya
(söz konusu müşteri kodunu değiştirmek için zorlar çünkü son çare) orijinal ağaç her düğüm için benzersiz seri numaraları ile yeniden tasarlanmış olmalıdıralgoritma atamak gerekir: Bu da göstermektedir ağacın içindeki her düğüme, onu geçtikçe benzersiz seri kimlikleri. Bu ikinci fikir, orijinal ağacın yeniden tasarlanması gerekmediği için idealdir, ancak çok daha zorlayıcıdır. Örneğin, var olduğu bilinen ancak geçişte ziyaret edilmemiş bir çocuğun kimlik numarası ne olacak? Şube numaralarının her bir düğüme Kimliğe hizmet etmesi gerekecektir.
arada, bir grafik için bir derleme zamanı topolojik tür orijinal sorunu çözmek başardı: http://ideone.com/9DKh4s
Bu iplik dışarı çalışılan deseni kullanır ve bunu şanslıyım her köşe, benzersiz düğüm değerlerine sahiptir. Ancak, ağacın düğümlerinin, orijinal ağacın her bir düğümüne (orijinal ağacın tasarımını ciddi şekilde çirkinleştiren) benzersiz seri kimlikleri olmadan, benzersiz değerlere sahip olmaması durumunda genel çözümü bilmek istiyorum. Yukarıda açıklanan çözüm # 2, ya da böyle bir şey).
Güncelleştirme (bazı düşünce günlerinden sonra). Şimdi bu sorunun ilgilenen herkese ilham olabilecek, yeni bir fikir üzerinde çalışmaya:
template <typename, typename, typename> struct NonLeafActionPostvisit;
// As a simple example, the postvisit non-leaf action is appending the first type of the pack to P<Visited...>.
template <template <typename...> class P1, template <typename...> class P2, typename ChildrenVisits, typename First, typename... Rest, typename... Visited>
struct NonLeafActionPostvisit<ChildrenVisits, P1<First, Rest...>, P2<Visited...>> :
Visit<P1<Rest...>, P2<Visited..., typename FirstType<First>::type>> {};
// Postvisit:
// Here First has children, so visit its children, after which carry out the postvisit non-leaf action, and then visit Rest...
template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
struct VisitHelper<P1<First, Rest...>, P2<Visited...>, true> :
NonLeafActionPostvisit<Visit<First, P2<Visited...>>, P1<First, Rest...>, P2<Visited...>> {};
// Here First has no children, so the "leaf action" is carried out. In this case, it is appended to P<Visited...> as a simple example.
template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
struct VisitHelper<P1<First, Rest...>, P2<Visited...>, false> :
LeafAction<P1<First, Rest...>, P2<Visited...>> {};
Henüz olsa doğru sonuçları vermez, ama sonunda çalışırsa, çok daha zarif daha görünüyor Zaten çizdiğim fikirler.
Sadece bir ipucu: int [1] ',' gibi türler kullanabilirsiniz. int [2] 've benzeri' int' yerine 'Object' .. testlerinizde/örneklerinizde . Benim deneyimime göre, bu okunabilirliği artırır. ('Struct t {}; '' t [1] '' ',' t [2] 've benzeri ile büyük olasılıkla kısaltılır. – dyp
Ön sıra geçişi, önce kök düğümünü ve sonra çocukları ziyaret etmektir. İstediğiniz gibi görünen post-order, önce çocukları, sonra da son kökü ziyaret etmek anlamına gelir. Uygulamadaki ikisi arasındaki tek fark, 'ziyaret' çağrısının, özyinelemeli aramalardan önce veya sonra gerçekleşip gerçekleşmediğidir. İstediğiniz sıraya ulaşmak için düğümleri herhangi bir yere kaydetmenize gerek yoktur, çünkü * çağrı yığını sizin için bunu yapar *. –
@povman. Bir constexpr işlevi, tek bir return ifadesi kullanır ve hangi şablonların yapılacağını tamamlar, bu nedenle bunlar eşdeğer yöntemlerdir, yani her constexpr işlevi bir şablon analoğuna sahip olur, değil mi? – prestokeys