可变参数模板的数据结构 [英] Data structure with variadic templates

问题描述

我有一个 Menu< T> 类，其选项是类型T的项，并且它可能具有类型为 Menu< T> 的子菜单(嵌套子菜单的深度).

I have a Menu<T> class, whose options are items of type T, and it may have submenus of type Menu<T> (with no limit to the depth of nested submenus).

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> 类不支持子菜单，该子菜单的项与T的类型不同.此附加功能非常方便，如果说的话，主菜单的操作类型为 Action ，然后其中一个选项为"Take Out武器"，其子菜单理想情况下将具有 Weapon 作为其选项，但就目前而言，子菜单将再次必须具有 Action 作为其选项.

And I've tested that it works correctly, but my Menu<T> class above does not support submenus whose items are of a different type than T. This extra feature would be very handy, if say, the main menu had Action as the type for its options, and then one of the options is "Take out weapon", whose submenu would ideally like to have Weapon as its options, but as it is right now, the submenu would again have to have Action as its options.

我尝试推广

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> 与类模板不匹配.这也是没有意义的，因为 Menu< int，std :: string> 是要从其 choose()函数返回int，但随后进入其子菜单将返回一个字符串.boost ::这里需要变体吗?

is not proper because Menu<int, std::string> menu; whereby I'm trying to create a simple menu of int options with submenus of string options, won't even compile because then the submenus are of type Menu<std::string> which does not match the class template. It also doesn't make sense because Menu<int, std::string> is to return int from its choose() function, but going into its submenu will then return a string. boost::variant needed here?

我只需要有人指出如何开始.我知道这似乎属于CodeReview，但是他们只想检查我的代码是否已经在工作，但是在这里我试图推广的努力还差得很远(甚至还没有开始)，所以我需要呼吁这里的专家介绍了如何开始.

I just need someone to point out how to start. I know this may seem to belong to CodeReview, but there they only want to examine my code if it is already working, but here my attempt to generalize is nowhere near working (hasn't even started yet), so I need to appeal to the experts here on just how to start.

更新:遵循gmbeard的建议，我使用以下简化代码进行了工作(真正的Menu类将具有链接的选项列表，用户可以通过输入从中进行选择).但是也有缺点.

Update: Following gmbeard's suggestion, I got it working with the following simplified code (the real Menu classes will have linked list of options which the user will choose from through input). But there are drawbacks.

#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.

最大的问题是，对于所有可能的Menu选项类型， ChooseVisitor 需要不断更新(它最终可能会产生数百个数据成员和重载)，更不用说可怕的if-checks了.获得所需的退货项目.但是所选项目需要存储，而不仅仅是短期使用.我欢迎提出改进的想法.

The biggest problem is that ChooseVisitor needs to be constantly updated for all possible Menu option types (it could end up with literally hundreds of data members and overloads), not to mention the horrendous if-checks to get the desired returned item. But the chosen item needs to be stored, and not just used for the short term. I welcome ideas for improvement.

推荐答案

一种解决方案是创建 Menu 的部分局部特性以解开可变参数包.

One solution is to create some partial specializations of Menu to unwrap the variadic parameter pack.

首先，创建模板类...

First, create the template class...

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

现在，为菜单链的末尾创建一个特殊化(无子菜单)...

Now, create a specialization for the end of the menu chain (no submenus)...

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

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

Lastly, create a specialization for the Menu instances that will have submenus...

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

  ...
};

为简洁起见，这是类的简化版本，但是如果添加嵌套的 Option 类，则同样的原理仍然适用.

This is a simplified version of your class for brevity but the same principle still applies if you add a nested Option class.

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

You can use a similar technique to recurse through the submenus by overloading a non-member function...

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 )...

Update: A possible implementation of the choose() functionality could use a visitor pattern. You would need to provide a type that overloads operator() for each type contained in your menu (in this case, int and 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 函数重载...

Similar to the print_menu function, you could define a couple of choose_menu function overloads ...

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

这将像这样使用...

This would be used like so ...

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

要想导出 choose()函数的构想有点困难，但是您应该能够使上述内容适应大多数情况.

It's a bit difficult to derive what you had in mind for your choose() function but you should be able to adapt the above to suit most scenarios.

这篇关于可变参数模板的数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！