What is the best way to handle unknown types in a C ++ structure?

Question

I am writing an interpreter for a simple, Lisp-like programming language. It will process the code in nodes, all of them have types, and some of them can have child nodes in indexed order. Due to the difference in the nature of the information, I cannot use the same length for all node values. Their type name is an enumeration type, but the only idea I have for a value type is void * . But when I use this, I have to be very careful, I think. I mean, I cannot use default destructors, I have to write a destructor that takes care of the node type. I would also have to use many drives, even to access the values.

This is what I am talking about:

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

Is there a way that is safer doing the best code, but still efficient, like using void pointers?

Answer 1

There are two options that I can think of. One of them is to use polymorphism, in which you have an abstract base class, Node and a number of subclasses of the type. Perhaps something like:

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

When storing these nodes, you will save Node* , not void* . The presence of an (abstract) virtual destructor in the base class allows you to correctly destroy specific objects using the base class pointer, for example:

 Node* obj = new String; delete obj; 

You can also call methods declared in the base class and execute their code in the correct derived class if these methods are virtual in the base class. they will often also be pure virtual, for example:

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

Another option is to use some kind of variant class. C ++ itself does not have an alternative class built into the language, but some libraries have been written, such as Boost, that provide such a class.

Answer 2

Use Inheritance / Interfaces:

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

For each type in enum NodeType create a new class that inherits BaseNode .

Answer 3

You need to use some type of option. Boost has one thing, and details can be found here .

Answer 4

The following is a quick sketch of the node 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); } 

not tested, but the basic idea should be implemented.

Please note that I use immutable nodes, as this applies to the lisp language. Indeed, I should use std::shared_ptr<const Node> or something similar so that the two trees can exchange data.

boost::variant handles the dynamic typing issue.