如何使用variant / visitor来概括树结构 [英] How to generalize a tree structure with variant/visitor

问题描述

这是我的问题的第2部分，最初是这里发布的。感谢@sehe的澄清和帮助。我结束了以下的代码，但我不知道如何减少这个东西一个通用的解决方案与变体和访问者。帮助/建议是非常感谢。感谢。

This is a part 2 of my question, originally posted here. Thanks to @sehe for clarifications and help. I ended up with the code that follows, but I can't figure out how can I reduce this thing to a generic solution with variant and visitor. Help/advise is greatly appreciated. Thanks.

#include "stdafx.h"
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <boost/format.hpp>
#include <boost/variant.hpp>


template <typename T> class A 
{
public:
    typename T L;
    typename std::shared_ptr<T> Lptr;
    using tlist = std::vector<std::shared_ptr<T>>;
    A(std::string n = "") : _n(n){}
    A(const A& another) : _n(another._n){};
    A(A&& a) : _n(a._n){ _lst = std::move(another._lst); }
    tlist &lst() { return _lst; }
    void emplace_back(std::shared_ptr<T> wp) {
        _lst.emplace_back(wp);
    }
    std::string n() const { return _n; }
private:
    tlist _lst;
    std::string _n;
};

/*
suppose I have following tree structure
    Store
        Shelves
            Products on the shelve
*/
using lA = A<boost::blank>; // product
using lB = A<lA>;           // shelf
using lC = A<lB>;           // store
using lAp = std::shared_ptr<lA>;
using lBp = std::shared_ptr<lB>;
using lCp = std::shared_ptr<lC>;


void printIt(lAp p, int indent){
    for (int i = 0; i < indent; ++i)
        std::cout << '\t';
    std::cout << p->n() << std::endl;
}


void printIt(lBp p, int indent){
    for (int i = 0; i < indent; ++i)
        std::cout << '\t';
    std::cout << p->n() << std::endl;;
    std::for_each(begin(p->lst()), end(p->lst()), [&](lAp i){
        printIt(i, indent + 1); }
    );
}


void printIt(lCp p, int indent){
    for (int i = 0; i < indent; ++i)
        std::cout << '\t';
    std::cout << p->n() << std::endl;
    std::for_each ( begin(p->lst()), end(p->lst()), [&](lBp i)
    {
        printIt(i, indent + 1);
    });
}


int main() {
    using storage = boost::variant<lAp, lBp, lCp>;
    std::vector<lCp> stores;
    for (int s = 0; s < 5; ++s) {
        lCp store(new lC((boost::format("store %1%") % s).str()));
        stores.emplace_back(store);
        for (int i = 0; i < 3; ++i) {// ten shelves in the store
            lBp shelf(new lB((boost::format("shelf %1%") % i).str()));
            store->emplace_back(shelf);
            for (int j = 0; j < 2; ++j) // twenty producs per shelf
                shelf->emplace_back(std::shared_ptr<lA>(new lA((boost::format("product %1%") % j).str())));
        }
    }
    std::for_each(begin(stores), end(stores), [](lCp p){printIt(p,0); });
    int i;
    std::cin >> i;
}

推荐答案

1. KISS 首先

   
   
   

   我不知道目标是与所有的多态性，静态和动态。我会说如果你的类型结构是固定的，只是使用：

1. KISS first

   I'm not sure what the goal is with all the polymorphism, both static and dynamic. I'd say if your type structure is fixed like that, just use:

Live on Coliru

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

namespace SimpleDomain {

    struct Product {
        std::string name;
    };

    struct Shelf {
        std::string name;
        std::vector<Product> _products;
    };

    struct Store {
        std::string name;
        std::vector<Shelf> _shelves;
    };

    std::ostream& operator<<(std::ostream& os, Product const& p) {
        return os << "\t\t" << p.name << "\n";
    }
    std::ostream& operator<<(std::ostream& os, Shelf const& s) {
        os << "\t" << s.name << "\n";
        for (auto& p : s._products) os << p;
        return os;
    }
    std::ostream& operator<<(std::ostream& os, Store const& s) {
        os << s.name << "\n";
        for (auto& sh : s._shelves) os << sh;
        return os;
    }
}

int main() {
    std::vector<SimpleDomain::Store> stores = {
        { "store 1", {
                { "shelf 1", { { "product 1" }, { "product 2" }, { "product 3" }, } },
                { "shelf 2", { { "product 4" }, { "product 5" }, { "product 6" }, } },
             },
        },
        { "store 2", {
                { "shelf 1", { { "product 7" }, { "product 8" }, { "product 9" }, } },
                { "shelf 2", { { "product 10" }, { "product 11" }, { "product 12" }, } },
             },
        }
    };

    std::for_each(begin(stores), end(stores), 
            [](SimpleDomain::Store const& p){std::cout << p;});
}

列印

store 1
    shelf 1
        product 1
        product 2
        product 3
    shelf 2
        product 4
        product 5
        product 6
store 2
    shelf 1
        product 7
        product 8
        product 9
    shelf 2
        product 10
        product 11
        product 12

多态性：

您可以使用递归变量更通用：

Full Genericity, No Dynamic Polymorphism:

Here you could use a recursive variant to be more generic:

Live On Coliru

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <boost/variant.hpp>

namespace GenericDomain {

    namespace Tag {
        struct Store{};
        struct Shelf{};
        struct Product{};
    }

    template <typename Kind> struct Node;

    using Store   = Node<Tag::Store>;
    using Shelf   = Node<Tag::Shelf>;
    using Product = Node<Tag::Product>;

    using Tree = boost::variant<
        boost::recursive_wrapper<Product>,
        boost::recursive_wrapper<Store>,
        boost::recursive_wrapper<Shelf>
    >;

    template <typename Kind> struct Node {
        std::string name;
        std::vector<Tree> children;
    };

    template <> struct Node<Tag::Product> {
        std::string name;
    };

    std::ostream& operator<<(std::ostream& os, Tag::Store)   { return os << "Store";   }
    std::ostream& operator<<(std::ostream& os, Tag::Shelf)   { return os << "\tShelf";   }
    std::ostream& operator<<(std::ostream& os, Tag::Product) { return os << "\t\tProduct"; }

    template <typename Kind> std::ostream& operator<<(std::ostream& os, Node<Kind> const& n) {
        os << Kind{} << ": " << n.name << "\n";
        for (auto& child : n.children) os << child;
        return os;
    }
    std::ostream& operator<<(std::ostream& os, Product const& p) {
        return os << Tag::Product{} << ": " << p.name << "\n";
    }
}

int main() {
    using namespace GenericDomain;
    std::vector<Store> stores = {
        Store { "store 1", {
                Shelf { "shelf 1", { Product { "product 1" },  Product { "product 2" },  Product { "product 3" }, } },
                Shelf { "shelf 2", { Product { "product 4" },  Product { "product 5" },  Product { "product 6" }, } },
             },
        },
        Store { "store 2", {
                Shelf { "shelf 1", { Product { "product 7" },  Product { "product 8" },  Product { "product 9" }, } },
                Shelf { "shelf 2", { Product { "product 10" }, Product { "product 11" }, Product { "product 12" }, } },
             },
        }
    };

    std::for_each(begin(stores), end(stores), 
            [](GenericDomain::Store const& p){std::cout << p;});
}

列印

Store: store 1
    Shelf: shelf 1
        Product: product 1
        Product: product 2
        Product: product 3
    Shelf: shelf 2
        Product: product 4
        Product: product 5
        Product: product 6
Store: store 2
    Shelf: shelf 1
        Product: product 7
        Product: product 8
        Product: product 9
    Shelf: shelf 2
        Product: product 10
        Product: product 11
        Product: product 12

您可以看到我们可以检测节点的类型。当然，没有什么能阻止我们制造奇怪的层次结构：

You can see that we can detect the type of node. Of course, nothing prevents us from making bizarre hierarchies:

std::vector<Store> stores = {
    Store { "store 1", {
        Shelf { "shelf 1", { 
            Product { "product 1" },
            Store { "store 2", {
                Shelf { "shelf 1", { Product { "product 7" },  Product { "product 8" },  Product { "product 9" }, } },
                Shelf { "shelf 2", { Product { "product 10" }, Product { "product 11" }, Product { "product 12" }, } },
            }, },
            Product { "product 3" },
        } },
        Shelf { "shelf 2", { Product { "product 4" },  Product { "product 5" },  Product { "product 6" }, } },
    }, },
};

要一般地处理缩进，请使用有状态的访问者：

To generically handle the indentation, make a stateful visitor:

std::ostream& operator<<(std::ostream& os, Tag::Store)   { return os << "Store";   }
std::ostream& operator<<(std::ostream& os, Tag::Shelf)   { return os << "Shelf";   }
std::ostream& operator<<(std::ostream& os, Tag::Product) { return os << "Product"; }

struct print_vis {
    size_t indent = 0;
    std::ostream& _os;

    using result_type = void;

    template <typename Kind> void operator()(Node<Kind> const& n) const {
        _os << std::string(indent, ' ') << Kind{} << ": " << n.name << "\n";
        print_vis sub { indent+4, _os };
        for (auto& child : n.children) sub(child);
    }

    void operator()(Product const& p) const {
        _os << std::string(indent, ' ') << Tag::Product{} << ": " << p.name << "\n";
    }

    void operator()(Tree const& tree) const {
        boost::apply_visitor(*this, tree);
    }

列印： Live on Coliru

Store: store 1
    Shelf: shelf 1
        Product: product 1
        Store: store 2
            Shelf: shelf 1
                Product: product 7
                Product: product 8
                Product: product 9
            Shelf: shelf 2
                Product: product 10
                Product: product 11
                Product: product 12
        Product: product 3
    Shelf: shelf 2
        Product: product 4
        Product: product 5
        Product: product 6

没有变体，只有动态多态性

正如上面的GenericDomain树：

No Variants, Dynamic Polymorphism Only

With the same "weird" tree as just above with the GenericDomain tree:

Live on Coliru

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <memory>

namespace DynamicDomain {

    struct Node;
    using Tree = std::shared_ptr<Node>;

    struct Node {
        virtual std::string type() const = 0;
        std::string name;
        std::vector<Tree> children;

        template <typename... Child>
        Node(std::string name, Child&&... children) : 
            name(std::move(name)), children { std::forward<Child>(children)... }
        { }
    };

    struct Product : Node { using Node::Node; virtual std::string type() const { return "Product"; } };
    struct Shelf   : Node { using Node::Node; virtual std::string type() const { return "Shelf"; } };
    struct Store   : Node { using Node::Node; virtual std::string type() const { return "Store"; } };

    struct print_vis {
        size_t indent;
        std::ostream* _os;

        using result_type = void;

        void operator()(Tree const& tree) const {
            if (tree) (*this) (*tree); else *_os << "[null]";
        }
        void operator()(Node const& node) const {
            *_os << std::string(indent, ' ') << node.type() << ": " << node.name << "\n";
            print_vis sub { indent+4, _os };
            for (auto const& child : node.children) sub(child);
        }
    };

    std::ostream& operator<<(std::ostream& os, Tree const& n) {
        print_vis{0, &os} (n);
        return os;
    }
}

int main() {
    using namespace DynamicDomain;
    std::vector<Tree> stores = {
        std::make_shared<Store> ("store 1", 
                std::make_shared<Shelf> ("shelf 1",
                        std::make_shared<Product> ("product 1"),
                        std::make_shared<Store> ("store 2",
                                std::make_shared<Shelf> ("shelf 1",  std::make_shared<Product> ("product 7"),  std::make_shared<Product> ("product 8"),  std::make_shared<Product> ("product 9") ),
                                std::make_shared<Shelf> ("shelf 2",  std::make_shared<Product> ("product 10"), std::make_shared<Product> ("product 11"), std::make_shared<Product> ("product 12") )
                                ),
                        std::make_shared<Product> ("product 3")
                        ),
                std::make_shared<Shelf> ("shelf 2",  std::make_shared<Product> ("product 4"),  std::make_shared<Product> ("product 5"),  std::make_shared<Product> ("product 6") )
                ),
    };

    std::for_each(begin(stores), end(stores), 
            [](DynamicDomain::Tree const& p){ std::cout << p; });
}

不是我的整洁的想法，允许可空节点和子树共享。

Not my idea of "neat" and potentially much less efficient - although it does allow for nullable nodes and sharing of subtrees.

这篇关于如何使用variant / visitor来概括树结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！