具有可变参数模板的数据结构

Question

我有一个Menu<T>class，它的选项是T类型的项目，它可能有Menu<T>类型的子菜单（不限制嵌套子菜单的深度） .

template <typename T>
class Menu {
    private:
        class Option {
            const std::string name;
            const T item;
            Menu<T>* submenu;
            Option* next = nullptr;
            friend class Menu<T>;
            Option (const std::string& itemName, const T& t, Menu<T>* menu = nullptr) : name(itemName), item(t), submenu(menu) {}
            ~Option() {if (submenu) delete submenu;}
            inline T choose() const;
            inline void print (int n) const;
        };
        Option* first = nullptr;  // first option in the menu
        Menu<T>* parent = nullptr;
        Option* parentOption = nullptr;
        enum ChoosingType {Normal, Remove};
    public:
        Menu() = default;
        Menu (const Menu<T>&);
        Menu& operator = (const Menu<T>&);
        ~Menu();
        inline void insert (const std::string& itemName, const T& t, Menu<T>* submenu = nullptr, int pos = END_OF_MENU);  
        T choose() const {return chosenItem().first;}
        inline int print() const;
    private:
        inline std::pair<T, int> chosenItem (ChoosingType = Normal) const;
        inline Option* deepCopy (const Option*);
};

而且我已经测试过它可以正常工作，但是我上面的 Menu<T> class 不支持其项目类型不同于 T 的子菜单。这个额外的功能会非常方便，如果说，主菜单有 Action 作为其选项的类型，然后其中一个选项是 "Take out weapon"，其子菜单理想情况下希望将 Weapon 作为其选项，但作为现在，子菜单必须再次将 Action 作为其选项。

我试图概括

template <typename T, typename U, typename... Rest>
class Menu {  // Menu with T as its option types.
    private:
        class Option {
            const std::string name;
            const T item;
            Menu<U, Rest...>* submenu;  // Submenu with U as its option types.
            Option* next = nullptr;
            friend class Menu<T, U, Rest...>;
            Option (const std::string& itemName, const T& t, Menu<U, Rest...>* menu = nullptr) : name(itemName), item(t), submenu(menu) {}
            ~Option() {if (submenu) delete submenu;}
            inline T choose() const;
            inline void print (int n) const;
        };
        Option* first = nullptr;
// ....
}

int main() {
    Menu<int, std::string> menu;  // Will not compile.
}

不合适，因为 Menu<int, std::string> menu; 我试图创建一个简单的 int 选项菜单和字符串选项的子菜单，甚至不会编译，因为子菜单的类型是 Menu<std::string>与 class 模板不匹配。它也没有意义，因为 Menu<int, std::string> 是 return int 从它的 choose() 功能，但是进入它的子菜单然后 return 一个字符串。 boost::variant 这里需要吗？

我只需要有人指出如何开始。我知道这似乎属于 CodeReview，但他们只想检查我的代码是否已经在工作，但在这里我的归纳尝试远未奏效（甚至还没有开始），所以我需要呼吁此处的专家介绍如何开始。

更新： 按照 gmbeard 的建议，我使用以下简化代码（真正的菜单 classes 将具有链接的选项列表，用户将通过输入从中选择）。但是也有缺点。

#include <iostream>
#include <string>

struct Visitor {
    virtual void visit (int&) = 0;
    virtual void visit (std::string&) = 0;
    virtual void visit (char& c) = 0;
};

struct ChooseVisitor : Visitor {
    std::pair<int, bool> chosenInt;
    std::pair<std::string, bool> chosenString;
    std::pair<char, bool> chosenCharacter;
    virtual void visit (int& num) override {
        chosenInt.first = num;
        chosenInt.second = true;
    }
    virtual void visit (std::string& str) override {
        chosenString.first = str;
        chosenString.second = true;
    }
    virtual void visit (char& c) override {
        chosenCharacter.first = c;
        chosenCharacter.second = true;
    }
};

template <typename...> struct Menu;

template <typename T>
struct Menu<T> {
    struct Option {
        T item;
        void accept (ChooseVisitor& visitor) {visitor.visit(item);}
    };
    Option* option;  // Assume only one option for simplicity here.
    ChooseVisitor choose() const {
        ChooseVisitor visitor;
        option->accept(visitor);
        return visitor;
    }
    void insert (const T& t) {option = new Option{t};}
};

// A specialization for the Menu instances that will have submenus.
template <typename T, typename... Rest>
struct Menu<T, Rest...> {  // Menu with T as its options type.
    struct Option {
        T item;
        Menu<Rest...>* submenu;  // Submenu with the first type in Rest... as its options type.
        void accept (ChooseVisitor& visitor) {visitor.visit(item);}
    };
    Option* option;
    ChooseVisitor choose() const {
    // In reality there will be user input, of course.  The user might not choose to enter a submenu,
    // but instead choose from among the options in the current menu.
        ChooseVisitor visitor;
        if (option->submenu)  
            return option->submenu->choose();
        else
            option->accept(visitor);
        return visitor;
    }
    void insert (const T& t, Menu<Rest...>* submenu = nullptr) {option = new Option{t, submenu};}
}; 

int main() {
    Menu<int, std::string, char> menu;
    Menu<std::string, char> submenu;
    Menu<char> subsubmenu;
    subsubmenu.insert('t');
    submenu.insert ("", &subsubmenu);
    menu.insert (0, &submenu);
    const ChooseVisitor visitor = menu.choose();
    if (visitor.chosenInt.second)
        std::cout << "You chose " << visitor.chosenInt.first << ".\n";  // Do whatever with it.
    else if (visitor.chosenString.second)
        std::cout << "You chose " << visitor.chosenString.first << ".\n";  // Do whatever with it.
    else if (visitor.chosenCharacter.second)
        std::cout << "You chose " << visitor.chosenCharacter.first << ".\n";  // Do whatever with it.
}

输出：

You chose t.

最大的问题是 ChooseVisitor 需要针对所有可能的菜单选项类型不断更新（最终可能会出现数百个数据成员和重载），更不用说可怕的 if-checks 了获取所需的 returned 项目。但是选择的项目需要存储，而不仅仅是短期使用。我欢迎提出改进意见。

Answer 1

一个解决方案是创建一些 Menu 的部分特化来解包可变参数包。

首先，创建模板class...

// Can be incomplete; only specialized versions will be instantiated...
template<typename... Args> class Menu;

现在，为菜单链的末尾创建一个专业化（无子菜单）...

template<typename T>
class Menu<T>
{
public:
  // No submenu in this specialization
  using item_type = T;
  std::vector<item_type> items;
  ...
};

最后，为将具有子菜单的 Menu 个实例创建一个专业化...

template<typename Head, typename... Tail>
class Menu<Head, Tail...>
{
public:
  Menu<Tail...> submenu;
  using item_type = Head;
  std::vector<item_type> items;

  ...
};

为简洁起见，这是 class 的简化版本，但如果您添加嵌套的 Option class.

，同样的原则仍然适用

您可以使用类似的技术通过重载非成员函数来递归访问子菜单...

template<typename T>
void
print_menu(Menu<T> const& menu)
{
  for(auto i : menu.items) {
    std::cout << i << std::endl;
  }
}

template<typename... T>
void
print_menu(Menu<T...> const& menu)
{
  for(auto i : menu.items) {
    std::cout << i << std::endl;
  }
  print_menu(menu.submenu);
}

int
main(int, char*[])
{
  Menu<int, std::string> menu{};
  menu.items.emplace_back(1);
  menu.submenu.items.emplace_back("42");
  print_menu(menu);
  ...
}

更新： choose() 功能的可能实现可以使用访问者模式。您需要为菜单中包含的每种类型提供重载 operator() 的类型（在本例中为 int 和 std::string）...

struct ChooseVisitor
{
  void operator()(std::string const& string_val) const
    { /* Do something when a string value is chosen */ }

  void operator()(int int_val) const
    { /* Do something when an int value is chosen */ }
};

类似于 print_menu 函数，您可以定义几个 choose_menu 函数重载 ...

template<typename... Types, typename Visitor>
void
choose_menu(Menu<Types...> const& menu, Visitor const& visitor)
{
  for(auto i : menu.items) {
    if(/* is menu item chosen? */) {
      visitor(i);
      return;
    }
  }
  choose_menu(menu.Submenu, visitor);
}

template<typename Type, typename Visitor>
void
choose_menu(Menu<Type> const& menu, Visitor const& visitor)
{
  for(auto i : menu.items) {
    if(/* is menu item chosen? */) {
      visitor(i);
      return;
    }
  }
}

这会像这样使用...

Menu<int, std::string> menu{};
...
choose_menu(menu, ChooseVisitor{});

很难得出您对 choose() 函数的想法，但您应该能够调整以上内容以适应大多数情况。

Answer 2

我有一种轻微的感觉，这里设计过度了。

如您所料，这是一个使用 Boost Variant 的版本。

我简化了一些事情。特别是我喜欢初始化列表构造函数，因此您可以简单地递归构造菜单树，如：

Menu menu = MenuT<int> { 
    { "one",   1 },
    { "two",   2 },
    { "three", 3 },

    { "forty-two", 42, 
            Menu(MenuT<std::string> {
                {"Life, The Universe And Everything", "LtUae"},
                {"Dent", "Arthur", 
                    Menu(MenuT<bool> {
                        {"yes", true},
                        {"no", false},
                    })
                },
            })
    },
};

如您所见，它在不同级别混合了 MenuT<int>、MenuT<std::string> 和 MenuT<bool>。您可以毫不费力地访问它：

struct simple : boost::static_visitor<>
{
    void operator()(Menu& m) const { boost::apply_visitor(*this, m); }

    template <typename T> void operator()(MenuT<T>& m) const {
        std::cout << "-----------\n";

        for (auto& o : m.options) {
            std::cout << "option '" << o.name << "':\t" << o.item << "\n";
            if (o.submenu)
                (*this)(*o.submenu);
        }
    }
};

打印

-----------
option 'one':   1
option 'two':   2
option 'three': 3
option 'forty-two': 42
-----------
option 'Life, The Universe And Everything': LtUae
option 'Dent':  Arthur
-----------
option 'yes':   true
option 'no':    false

Live On Coliru

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

template <typename> struct MenuT;

using Menu = boost::make_recursive_variant < 
        boost::recursive_wrapper<MenuT<int>>,
        boost::recursive_wrapper<MenuT<std::string>>,
        boost::recursive_wrapper<MenuT<bool>>
    >::type;

template <typename T> struct MenuT {
    struct Option {
        std::string           name;
        T                     item;
        boost::optional<Menu> submenu;

        Option(std::string name, T t, boost::optional<Menu> submenu = boost::none)
            : name(name), item(t), submenu(submenu)
        { }

        T choose() const;
        void print(int n) const;
    };

  private:
    template <typename U> friend struct MenuT;
    friend struct visitors;

    std::vector<Option> options;
    //boost::optional<Menu&> parent; // TODO e.g. link_parents_visitor
    enum ChoosingType { Normal, Remove };

  public:
    enum SpecialPosition : size_t { END_OF_MENU = size_t(-1) };

    MenuT() = default;
    MenuT(std::initializer_list<Option> options) : options(options) {}

    void insert(const std::string &itemName, const T &t, boost::optional<Menu> submenu = boost::none, size_t pos = END_OF_MENU) {
        auto it = (pos == END_OF_MENU 
                ? options.end() 
                : std::next(options.begin(), std::min(pos, options.size())));

        options.emplace(it, itemName, t, submenu);
    }

    T choose() const { return chosenItem().first; }
    int print() const;

  private:
    std::pair<T, int> chosenItem(ChoosingType = Normal) const;
};

struct visitors {
    struct simple : boost::static_visitor<>
    {
        void operator()(Menu& m) const { boost::apply_visitor(*this, m); }

        template <typename T> void operator()(MenuT<T>& m) const {
            std::cout << "-----------\n";

            for (auto& o : m.options) {
                std::cout << "option '" << o.name << "':\t" << o.item << "\n";
                if (o.submenu)
                    (*this)(*o.submenu);
            }
        }
    };
}; 

static const visitors::simple demo { };

int main()
{
    Menu menu = MenuT<int> { 
        { "one",   1 },
        { "two",   2 },
        { "three", 3 },

        { "forty-two", 42, 
                Menu(MenuT<std::string> {
                    {"Life, The Universe And Everything", "LtUae"},
                    {"Dent", "Arthur", 
                        Menu(MenuT<bool> {
                            {"yes", true},
                            {"no", false},
                        })
                    },
                })
        },
    };

    std::cout << std::boolalpha;
    demo(menu);
}

备注

值得注意的遗漏是我没有初始化

boost::optional<Menu&> parent; // TODO e.g. link_parents_visitor

我想你仍然想要简化这个（我想你可能一开始就不想把 MenuT 和 Option 分开。你刚刚介绍了吗试图嵌套不同类型的菜单选项？

具有可变参数模板的数据结构

Data structure with variadic templates

c++

templates

variadic

c++11