Quelle est la meilleure façon de gérer les types inconnus dans une structure C++?

Question

J'écris un interpréteur pour un langage de programmation simple, de type Lisp. Il va traiter le code en nœuds, tous ont des types et certains d'entre eux peuvent avoir des nœuds enfants dans un ordre indexé. En raison de la différence dans la nature de l'information, je ne peux pas utiliser la même longueur de type pour toutes les valeurs de nœud. Le nom de leur type est un type enum, mais la seule idée que j'ai pour le type de valeurs est void *. Mais quand je l'utilise, je dois être très prudent, je pense. Je veux dire, je ne peux pas utiliser de destructeurs par défaut, je dois écrire un destructeur qui se soucie du type de nœud. Aussi, je devrais utiliser beaucoup de moulages, même pour accéder aux valeurs.

C'est ce dont je parle:

enum NodeType {/* Some node types */} 

class Node 
{ 
public: 
    Node(string input_code); 
private: 
    NodeType type; // Having this I can know the type of value 
    void* value; 
}; 

Y at-il une manière qui est plus sûr, fait un meilleur code, mais est toujours aussi efficace que l'utilisation de pointeurs vides?

Answer 1

Il y a deux options auxquelles je peux penser. La première consiste à utiliser le polymorphisme, dans lequel vous avez une classe de base abstraite, Node et un certain nombre de sous-classes spécifiques au type. Peut-être quelque chose comme:

class Node 
{ 
public: 
    virtual ~Node() = 0; 
}; 

class String : public Node 
{ 
public: 
    ~String() {} 
}; 

class Float : public Node 
{ 
public: 
    ~Float() {} 
}; 

Lorsque le stockage de ces nœuds, vous stockerait Node* plutôt que void*. La présence de la (abstraite) destructor virtuelle dans la classe de base permet de bien détruire des objets concrets via le pointeur de la classe de base, comme:

Node* obj = new String; 
delete obj; 

Vous pouvez également appeler des méthodes déclarées dans la classe de base et de les exécute du code dans la classe dérivée correcte, si ces méthodes sont virtuelles dans la classe de base. ceux-ci seront souvent aussi pures virtuals, comme avec:

class Node 
{ 
public: 
    std::string Speak() const = 0; // pure virt 
}; 

class String : public Node 
{ 
public: 
    std::string Speak() const { return "Hello"; } 
}; 

Une autre option est d'utiliser une sorte de classe variante. C++ lui-même n'a pas de classe de variante intégrée au langage, mais certaines bibliothèques ont été écrites comme Boost, qui fournissent une telle classe.

Answer 2

Vous devez utiliser une sorte de type de variante. Boost en a un et les détails peuvent être trouvés here.

Answer 3

utiliser l'héritage/Interfaces:

struct BaseNode { 
    std::vector<BaseNode*> _children; 
    /*Some functions here*/ 
} 

Pour chaque type dans le enum NodeType font une nouvelle classe qui hérite BaseNode.

Answer 4

Voici un croquis rapide d'un système de nœud basé boost::variant:

class Node; 
struct Empty {}; 

// Keep enum and variant in sync: 
enum NodeType { 
    eEmptyNode, 
    eStringNode, 
    eIntNode, 
    eListNode, 
}; 
typedef std::vector< const Node > NodeList; 
typedef boost::variant< std::string, int, NodeList > NodeData; 

// Keep this in sync with types in Node and enum: 
NodeType GetNodeType(Empty const&) { return eEmptyNode; } 
NodeType GetNodeType(std::string const&) { return eStringNode; } 
NodeType GetNodeType(int const&) { return eIntNode; } 
NodeType GetNodeType(NodeList const&) { return eListNode; } 


// Some helper code: 
struct GetNodeType_visitor 
{ 
    typedef NodeType return_type; 
    template<typename T> 
    NodeType operator()(T const& t) const { return GetNodeType(t); } 
}; 

template<typename T, typename Function> 
struct OneType_visitor 
{ 
    typedef bool return_type; 
    Function func; 
    OneType_visitor(Function const& f):func(f) {} 
    template<typename U> 
    bool operator()(U const& u) const { return false; } 
    bool operator()(T const& t) const { func(t); return true; } 
}; 

struct Node 
{ 
    NodeData data; 
    NodeType GetType() { return boost::apply_visitor(GetNodeType_visitor, data); } 
    template<typename T, typename Function> 
    bool Apply(Function const& func) const 
    { 
    return boost::apply_visitor(OneType_visitor<T>(func), data); 
    } 
    template<typename T> 
    Node(T const& t):data(t) {} 
    Node():data(Empty()) {} 
}; 

// example usage: 
int main() 
{ 
    NodeList nodes; 
    nodes.push_back(Node<int>(7)); 
    nodes.push_back(Node<std::string>("hello")); 
    Node root(nodes); 

    Assert(root.GetType() == eListNode); 
    std::function<void(Node const&)> PrintNode; 
    auto PrintInt = [](int const& i) { std::cout << "#" << i; }; 
    auto PrintString = [](std::string const& s) { std::cout << "\"" << s << "\""; }; 
    auto PrintList = [&](NodeList const& list) { 
    std::cout << "["; 
    for (auto it = list.begin(); it !=list.end(); ++it) 
    { 
     if (it != list.begin()) std::cout << ","; 
     PrintNode(*it); 
    } 
    std::cout << "]"; 
    } 
    auto PrintEmpty = [](Empty const&) { std::cout << "{}"; } 
    PrintNode = [&](Node const& n) 
    { 
    bool bPrinted = false; 
    bPrinted = n.Apply<int>(PrintInt) || bPrinted; 
    bPrinted = n.Apply<std::string>(PrintString) || bPrinted; 
    bPrinted = n.Apply<NodeList>(PrintList) || bPrinted; 
    bPrinted = n.Apply<Empty>(PrintEmpty) || bPrinted; 
    Assert(bPrinted); 
    } 
    PrintNode(root); 
} 

Code

n'est pas testé, mais devrait tenir l'idée de base.

Notez que j'utilise des nœuds immuables, comme c'est le cas pour un langage de type lisp. Vraiment, je devrais utiliser std::shared_ptr<const Node> ou quelque chose comme ça, donc deux arbres peuvent partager des données.

boost::variant gère le problème de typage dynamique.