How to define a template for pointers and dynamic memory allocation?

Question

I've made a class template called Queue but I'm having problems trying to instanciate it with a pointer to another class called Worker as the type. Queue<Worker*>

The problem I think comes with this concrete Queue method:

// Add item to queue
template <typename Type>
bool Queue<Type>::enqueue(const Type& item)
{
    if (isfull())
        return false;
    Node* add = new Node; // create node
    // on failure, new throws std::bad_alloc exception
    add->item = item; // set node pointers (shallow copying!!!!!)
    add->next = nullptr;
    items++;
    if (front == nullptr) // if queue is empty,
        front = add; // place item at front
    else
        rear->next = add; // else place at rear
    rear = add; // have rear point to new node
    return true;
}

In the case of the type parameter being a pointer I need to copy the pointed-to value, not the address (I'm using dynamic memory management) to avoid the program crashing.

I don't know how to solve this with a template.

Any help?

Answer 1

Although it will cause a bit of code duplication, you can create a specialization of your Queue class for instantiations with pointer-types. My recommendation in order to reduce the amount of code duplication would be to create a base-class that each specialized class will inherit from, where the base-class contains all the methods and members that will not change depending on the type that the class is instantiated with.

So for instance:

template<typename T>
base_queue; //keep everything "common" in this class

template<typename T>
queue : public base_queue<T> { ... }; //unspecialized queue class

template<typename T>
queue<T*> : public base_queue<T> { ... }; //pointer specialized version

Now in the specialized version of your Queue<T*> class, your enqueue method can look like the following:

template <typename T>
bool Queue<T*>::enqueue(const T* item)
{
    //... code

    add->item = *item; // copy the value being pointed to, not the pointer itself

    //... more code

    return true;
}

Answer 2

Use traits technique.

I mean define simple struct where all magic will be implemented. Something like this deep_copy:

  template <typename T>
  struct deep_copy {
     void do_copy(T& d, const T& s)
     {
        d = s;
     }
  };

And specialization for pointers

   template <typename T>  
   struct deep_copy<T*> {
     void do_copy(T*& d, const T* s)
     {
       if(s) d=new(*s); else d=0; }};
     }
   };         

[UPDATE1] More details and more examples:

And use deep_copy in your Queue:

template <typename T>
class Queue {
public:
   void push_back(const T& elem)
   {
       Node* n = new Node();
       copyTraits.doCopy(n->elem, elem);
   }
private:
  deep_copy<T> copyTraits;
};

Or even better make it default parameter to your template like less<> is default for map.

template <typename T, typename CopyTraits = deep_copy<T> >
class Queue {
public:
   void push_back(const T& elem)
   {
       Node* n = new Node();
       copyTraits.doCopy(n->elem, elem);
   }
private:
  CopyTraits copyTraits;
};

And do not forget about destroy method, if you want your Queue::~Qeueu() d-tor to be safe:

  template <typename T>
  struct deep_copy {
     void do_copy(T& d, const T& s)
     {
        d = s;
     }
     void do_destroy(const T& elem) {} // do nothing
  };


   template <typename T>  
   struct deep_copy<T*> {
     void do_copy(T*& d, const T* s)
     {
       if(s) d=new(*s); else d=0; }};
     }
     void do_destroy(const T& elem) {
       delete elem;
     }
   };         


template <typename T, typename AllocTraits = deep_copy<T> >
class Queue {
public:
   ...
   ~Queue() {
      for (n in Nodes) { // pseudo-code
         allocTraits.doDestroy(n->elem);
      }
   }
private:
  AllocTraits allocTraits;
};