C++ STL and memory management

fasty

Ah yeah, I see what you mean... I don't think that's too bad. You can either have two functions, one where you pass a Compare functor, one that doesn't, or you can pass a compare functor via the contructor or something like that.

I actually don't think I've sorted a bog standard array of ints or whatever in years, I always need a comparison function so I just go down that route.

Call Me Jimmy

after a lot of attempts, i found the cleanest way for me to do it was to try and determine if T was a pointer or not. I found this solution:

template<typename T>
struct is_pointer { static const bool value = false; };

template<typename T>
struct is_pointer<T*> { static const bool value = true; };

So i call is_pointer<T>::value in sort and call the appropriate function based on that! It looks a lot better.

satchmo

The right way to do this is partial template specialization. You create your template <class T> class Array, but you also create a template <class T> class Array<T*> specialization. Kind of like the way you specialized that struct, but for the whole class. Then you can ditch the SortPtr() function and just implement two different Sort() functions with the correct functionality.

There's a good article on full and partial specialization here.

Call Me Jimmy

Yea I've read that but writing two classes that are almost exactly similar just for a difference of one function seems excessive, time-wise and code-wise (in terms of code-bloat)?

Basically I would end up with two Array template classes that are the exact same except for the sort function... surely that can't be right?

satchmo

But it's not just the Sort function. Try compiling that code using a complex type like a user-defined class, and it will fail because you're trying to assign 0 to it in the constructor. Or if you do try to print out an array of pointers with that code, it will print out the addresses of the pointers, when you probably want it to print out a reasonable representation of the object that is being pointed to (ie, dereferencing the pointer first). Or using a class that doesn't provide a << operator will fail to compile because of the operator<<() function trying to print it directly.

And so on... as you add functionality to your Array class, you will probably find other reasons too. There will be some code duplication, but code is only generated for every different type that uses that template, so having another template type isn't going to make much of a difference - it's how many times you instantiate templates with different types that matters to the executable code size.

There is a clever way of avoiding code duplication and reducing code bloat in templates by leveraging private inheritance and using a base class of void pointers while still guaranteeing type-safety - see Item #43 in 'Effective C++' for more details. Even if you don't want to go as far as implementing it, it's still something that should be read and understood.

Call Me Jimmy

Sorry to come back with more code, but I've implemented the array class to allow for pointer types based on the template specialization stuff and I'd really appreciate if someone could look over it and tell me if I've done it correctly. (that's you satchmo )

#include "shared.h"
#include <algorithm>
#include <cstdlib>
#include <functional>

/*========================================
	Array: Dynamic Array for any Type
=========================================*/

template <class T>
class Array
{
public:
	Array();
	Array(unsigned int);
	Array(const Array<T>&);
	~Array();

	unsigned int			Size() const { return m_nSize; }
	T const*				Data() const { return m_pData; }

	const T&				operator[](unsigned int) const;
	T&						operator[](unsigned int);

	void					Resize(unsigned int);
	void					Sort();
	bool					IsEmpty() const { return (m_pData == 0); }				
		

protected:
	T* m_pData;
	unsigned int m_nSize;
};

/*========================
	Constructor: Array() 
==========================*/
//Don't assume any allocation of memory.

template <class T>
Array<T>::Array():
m_pData(0),
m_nSize(0)
{
}

/*============================
	Constructor: Array( size ) 
=============================*/
template <class T>
Array<T>::Array(unsigned int size):
m_pData(new T [size]),
m_nSize(size)
{
}

/*====================
	Copy Constructor
=====================*/
template <class T>
Array<T>::Array(const Array<T>& rhs):
m_pData(0),
m_nSize(0)
{
	try
	{
		m_pData = new T[rhs.Size()];
	}
	catch(bad_alloc)
	{
		cout<< "Array couldn't allocate new memory";
		return;
	}
	m_nSize = rhs.Size();

	for(int i=0; i< m_nSize; i++)
		m_pData[i] = rhs[i];
}

/*=================
	Destructor
==================*/
template <class T>
Array<T>::~Array()
{
	delete [] m_pData;
}

/*=================
	operator[]
==================*/
template <class T>
const T& Array<T>::operator[](unsigned int offset) const
{
	if(offset >= m_nSize)
		throw out_of_range("Invalid position");

	return m_pData[offset];
}

/*=================
	operator[]
==================*/
template <class T>
T& Array<T>::operator[](unsigned int offset)
{
	if(offset >= m_nSize)
		throw out_of_range("Invalid position");

	return m_pData[offset];
}

/*=================
	Resize
==================*/
template <class T>
void Array<T>::Resize(unsigned int size)
{
	unsigned int min = std::_cpp_min(size, m_nSize);
	unsigned int max = std::_cpp_max(size,m_nSize);
	int i;

	T* newData = 0;
	try
	{
		newData = new T[size];
	}
	catch(bad_alloc)
	{
		cout<< "Array couldn't allocate new memory";
		return;
	}
	
	//copy to new array
	for(i=0; i<min; i++)
		newData[i] = m_pData[i];

	if(m_pData)
		delete [] m_pData;

	m_pData = newData;
	m_nSize = size;
	
}

/*=================
	Sort
==================*/
// wrapper that simply implements std::sort

template <class T>
void Array<T>::Sort()
{
		std::sort(m_pData, (m_pData+ m_nSize));
}





/*==========================================
	Array<T*> Specific Array Template for Pointers
===========================================*/

template <class T>
class Array<T*>
{
public:
	Array();
	Array(unsigned int);
	Array(const Array<T*>&);
	~Array();

	unsigned int			Size() const { return m_nSize; }
	T const*				Data() const { return m_pData; }

	const T*&				operator[](unsigned int) const;
	T*&						operator[](unsigned int);

	void					Resize(unsigned int);
	void					Sort();
	bool					IsEmpty() const { return (m_pData == 0); }				

protected:
	T** m_pData;
	unsigned int m_nSize;
};

/*========================
	Constructor: Array() 
==========================*/
template <class T>
Array<T*>::Array():
m_pData(0),
m_nSize(0)
{
}

/*=============================
	Constructor: Array( size ) 
==============================*/
template <class T>
Array<T*>::Array(unsigned int size):
m_pData(new T*[size]),
m_nSize(size)
{
	for(int i=0; i< m_nSize; i++)
		m_pData[i] = 0;
}

/*=============================
	Copy Constructor
==============================*/
template <class T>
Array<T*>::Array(const Array<T*>& rhs):
m_pData(0),
m_nSize(0)
{
	try
	{
		m_pData = new T*[rhs.Size()];
	}
	catch(bad_alloc)
	{
		cout<< "Array couldn't allocate new memory";
		return;
	}
	m_nSize = rhs.Size();

	for(int i=0; i< m_nSize; i++)
		m_pData[i] = rhs[i];
}

/*=============================
	Destructor
==============================*/
// must delete all pointers in array 
// prior to deleting the array itself

template <class T>
Array<T*>::~Array()
{
	for(int i =0; i< m_nSize; i++)
		delete m_pData[i];
	delete m_pData;
	m_pData = 0;
}

/*=============================
	operator[]
==============================*/
// Usually would return a reference but
// because this is an array of pointers, returns
// a reference to a pointer.

template <class T>
const T*& Array<T*>::operator[](unsigned int offset) const
{
	if(offset >= m_nSize)
		throw out_of_range("Invalid position");

	return (m_pData[offset]);
}

/*================
	operator[]
=================*/
template <class T>
T*& Array<T*>::operator[](unsigned int offset)
{
	if(offset >= m_nSize)
		throw out_of_range("Invalid position");

	return (m_pData[offset]);
}

/*==============
	Resize
===============*/
template <class T>
void Array<T*>::Resize(unsigned int size)
{
	unsigned int min = std::_cpp_min(size, m_nSize);
	unsigned int max = std::_cpp_max(size,m_nSize);
	int i;

	T** newData = 0;
	try
	{
		newData = new T*[size];
	}
	catch(bad_alloc)
	{
		cout<< "Array couldn't allocate new memory";
		return;
	}
	
	//copy to new array
	for(i=0; i<min; i++)
		newData[i] = m_pData[i];

	// if the new array is larger than the old one
	// then initialize the surplus cells(pointers) to 0
	if(size > m_nSize)
	{
		for(i=min; i<max; i++)
			newData[i] = 0;
	}

	if(m_pData)
		delete [] m_pData;

	m_pData = newData;
	m_nSize = size;
	
}

/*==============
	Sort
===============*/
// uses pointer compare functor as comparison
// function in std::sort so that it is the objects
// being compared, not the pointers.

// hack function to facilitate std::sort with pointers
template <class T>
struct PtrCmp : public std::binary_function<T,T,bool>
{
	inline bool operator()(const T ptr, const T ptr2)
	{
		if(ptr && ptr2)
			return *ptr < *ptr2;
		else
			return false;
	}
};

template <class T>
void Array<T*>::Sort()
{
		std::sort(m_pData, (m_pData+ m_nSize), PtrCmp<T*>());
}

Any pointers (pun intended) would be greatly appreciated!