determining if templated type is dynamic

Question

I am writing a template of a working class, and this might just be a dumb question, but if I have a template structure (linked list) to hold possibly pointers to objects then how do I know that they are being deleted, or that they where pointers in the first place?

for example: the linkedList will be used in 2 ways in this program

a pointer to an object of class Thing is placed inside a node inside a linkedList

an enum is placed inside a node inside a linkedList

I know that the nodes are being deleted, but how do I know that the thing in the node is a pointer so that it can be deleted as well, and not just be a Null referenced object?

Answer 1

Template specialization is the best answer, and will work well as long as you don't mix types of nodes. However if you want to mix types of your linked nodes, let me show you how to do it. First, there is no straightforward template solution. You would have to type cast your linked nodes together due to strict type constrains.

A quite common solution is to construct a variant class (which can hold one value with variant types, and is always aware which one). Qt has a QVariant class, for instance. Boost has boost::any.

Here is a complete example implementation using a custom variant class that could hold any of your types. I can handle your suggested object pointer and enum, but could be extended to hold more.

An example which will print "delete obj" once:

    #include <iostream>                                                                                                                                                                                                    

    int                                                                                                                                                                                                                      
    main( int argc, char **argv )                                                                                                                                                                                            
    {                                                                                                                                                                                                                        
      LinkedList<VariantExample> elementObj( new ExampleObj );                                                                                                                                                                

      LinkedList<VariantExample> elementEnum( enumOne );                                                                                                                                                                      

      elementEnum.setNext( elementObj );                                                                                                                                                                                     
    }  

// VariantExample class. Have a look at [QVariant][4] to see how a fairly
// complete interface could look like.

        struct ExampleObj                                                                                                                                                                                                        
        {                                                                                                                                                                                                                        
        };                                                                                                                                                                                                                       

        enum ExampleEnum                                                                                                                                                                                                         
        {                                                                                                                                                                                                                        
            enumOne,                                                                                                                                                                                                             
            enumTwo                                                                                                                                                                                                              
        };                                                                                                                                                                                                                       

        struct VariantExample                                                                                                                                                                                                     
        {                                                                                                                                                                                                                        
          ExampleObj* obj;      // or better boost::shared_ptr<ExampleObj> obj                                                                                                                                                                                                      
          ExampleEnum en;                                                                                                                                                                                                        

          bool is_obj;                                                                                                                                                                                                           
          bool is_enum;                                                                                                                                                                                                          

          VariantExample() : obj(0), is_obj(false), is_enum(false) {}

          // implicit conversion constructors

          VariantExample( ExampleObj* obj_ ) : is_obj(true), is_enum(false)                                                                                                                                                
          { obj = obj_;                                                                                                                                                                                                          
          }                                                                                                                                                                                                                      

          VariantExample( ExampleEnum en_ ) : obj(0), is_obj(false), is_enum(true)                                                                                                                                                        
          { en = en_;                                                                                                                                                                                                            
          }                                                                                                                                                                                                                      

          // Not needed when using boost::shared_ptr above

          void                                                                                                                                                                                                                   
          destroy()                                                                                                                                                                                                              
          {                                                                                                                                                                                                                      
            if( is_obj && obj )                                                                                                                                                                                                         
              {                                                                                                                                                                                                                  
                std::cout << "delete obj" << std::endl;                                                                                                                                                                          

                delete obj;                                                                                                                                                                                                      
              }                                                                                                                                                                                                                  
          }                                                                                                                                                                                                                      

        };            


// The linked list template class which handles variant classes with a destroy()
// method (see VariantExample).

    template                                                                                                                                                                                                                 
    <                                                                                                                                                                                                                        
      typename _type_ = VariantExample                                                                                                                                                                                                       
    >                                                                                                                                                                                                                        
    struct LinkedList                                                                                                                                                                                                        
    {                                                                                                                                                                                                                        
      LinkedList* m_next;                                                                                                                                                                                                    

      _type_ m_variant;                                                                                                                                                                                                      

      explicit                                                                                                                                                                                                               
      LinkedList( _type_ variant_ ) : m_next(0), m_variant( variant_ ){ }                                                                                                                                                               

      void                                                                                                                                                                                                                   
      setNext( LinkedList& next_ ){ m_next = &next_; }                                                                                                                                                                       

      // Not needed when using boost::shared_ptr above

      ~LinkedList()                                                                                                                                                                                                          
      {                                                                                                                                                                                                                      
        m_variant.destroy();                                                                                                                                                                                                 
      }                                                                                                                                                                                                                      
    };                                                                                                                                                                                                                          

Because elementObj's destroy method called once when the LinkedList's destructor is called, the output "delete obj" is appearing just once. Again, as you were quite specific about the delete/ownership, this example has a destroy method/interface. It will be explicitly called in the destructor of the LinkedList class. A better ownership model could be implemented with ie. boost::shared_ptr. Then you dont need to destroy it manually. It helps to read about conversion constructors, by the way.

  // the first parameter becomes boost::shared_ptr<ExampleObj>( new ExampleObj ) )
  // and is deleted when LinkedList is destroyed. See code comments above.

  LinkedList<> elementObj( new ExampleObj );                                                                                                                                                                

Finally note that you have to have a single variant class to hold all your types which could appear in your LinkedList chain. Two different LinkedList Variant types would not work, again, finally because of the "next" pointer type; which would be not compatible.

Footnote: How type constrains prevent an easy solution ? Imagine your linked node "next" pointer type is not just the the bare template name, its a shortcut, but is actually qualified including the template arguments - what end up as the type symbol the compiler uses to judge type compabilities.

Answer 2

You can specialize the node based on the type of the object, and for the pointer specialization, create a destructor for the node-type that properly allocates and deletes the pointer managed by the node.

For instance:

//general node type for non-pointer types
template<typename T>
struct linked_list_node
{
    T data;
    linked_list_node<T>* next;

    linked_list_node(const T& d): data(d), next(NULL) {}
    ~linked_list_node() {} 
};

//specialized version for pointer types
template<typename T>
struct linked_list_node<T*>
{
    typedef void (*deleter)(T*);

    T* data;
    linked_list_node<T>* next;
    deleter d_func;  //custom function for reclaiming pointer-type

    linked_list_node(const T& d): data(new T(d)), next(NULL), d_func(NULL) {}

    linked_list_node(const T& d, deleter func): data(new T(d)), 
                                                next(NULL), d_func(func) {}
    ~linked_list_node() 
    {
        if(d_func)
            d_func(data);  //execute custom function for reclaiming pointer-type
        else
            delete data;
    }
};

You can then instantiate the different versions by passing the correct template argument when creating an instance of the linked_list_node type. For instance,

linked_list_node<MyPtr*> node(FooPtr); //creates the specialized ptr version
linked_list_node<MyEnum> node(FooEnum); //creates a non-ptr version of the node