Sign in to follow this  
Endar

Brain problems

Recommended Posts

I've written a dynamic array, and I've just added a couple of things so that a 'push_back' function will work, and I'm having problems. Mostly that I've stared too long at my code, so nothing new comes to me. The way the push_back function is supposed to work is that it basically adds another element to the end of the array. 'size' is the current size of the array, 'arr' is a pointer to the array and 'space' is the total number of elements that are currently allocated in memory. So, 'size' could be 5, and 'space' could be 7, so there's space for 7 element with the current pointer. If 'size' == 'space' then the array is resized to 'size+1'.
// array.cpp
#ifndef _UTIL_ARRAY_CPP_
#define _UTIL_ARRAY_CPP_

#include "array.h"

namespace util{


/**
 * Default constructor
 * \param s The initial size of the array
 */
template <class T>
array<T>::array()
	:	size(0), space(0), arr(NULL)
{
	
}

/**
 * Constructor
 * \param s The initial size of the array
 */
template <class T>
array<T>::array(unsigned int s)
	:	size(s), space(0), arr(NULL)
{
	resize(s);
}

/**
 * Destructor
 */
template <class T>
array<T>::~array()
{
	delete arr;
}

/**
 * Overloaded operator []
 * \param n The index into the array
 * \return A reference to the 'n-1'th object in the array
 */
template <class T>
T& array<T>::operator[](unsigned int n)
{
	return arr[n];
}

/**
 * Delete the array and sets the size to 0
 */
template <class T>
void array<T>::clear()
{
	delete arr;
	arr = NULL;
	size = 0;
}

/**
 * Resize the array to size s.
 * \param s The new size of the array
 */
template <class T>
void array<T>::resize(unsigned int s)
{
	// if re-size fits in currently reserved memory
	if( s <= space ){
		size = s;	// set size of array
		return;
	}

	// else re-size does NOT fit in currenlty reserved memory
	reserve(s);		// allocate 's' amount of memory
	size = s;		// set size of array
	// by this point, size should equal space     29/08/05
}

/**
 * Allocates this amount of memory for the array.
 * If s < size of the array (different to amount of memory allocated) then the array is cut down.
 */
template <class T>
void array<T>::reserve(unsigned int s)
{
	T* temp;
	int tmp;

	// if the array doesn't exist yet
	if( !arr ){
		arr = new T[s];
		space = s;
		return;
	}

	// if param is the same value as current space, ignore
	if( s == space )
		return;

	temp = new T[s];	// new array

	// the number of elements that has to be looped through to
	// copy the elements of the array
	if( s >= size ){
		tmp = size;
		space = s;			// set amount of elements reserved in memory
	}
	else if( s < size ){
		tmp = s;
		size = space = s;	// set size of array and amount of elements reserved in memory
	}

	for(int i=0; i < tmp; i++)
		temp[i] = arr[i];

	delete arr;		// delete old array
	arr = temp;		// assign new array
}

/**
 * Add an element to the back of the array.
 * \param n A const reference to an object of type T
 */
template <class T>
void array<T>::push_back(const T& n)
{
	int temp = size;// this stores the current position to push_back to in case
		// some re-sizing needs to be done ('size' variable changes, and an array element is skipped)

	// 30-08-05 - FIXME - at some point during previous insertions, 'size' becomes greater than 'space'
	// element to insert into is 'size'
	if( size == space )
		resize( size + 1 );// only adding one at the moment
		
	arr[temp] = n;	// assign T object
	size++;			// increase size
}

}//namespace util
#endif





// array.h
#ifndef _UTIL_ARRAY_H_
#define _UTIL_ARRAY_H_
namespace util{

/**
 * This class defines a wrapper for a templated dynamic array.
 */
template <class T>
class array
{
private:

	unsigned int space;		///< The number of array elements allocated in memory
	unsigned int size;		///< The size of the array
	T* arr;					///< Pointer to the array

public:

	/**
	 * Default constructor
	 */
	array();

	/**
	 * Constructor
	 * \param s The initial size of the array
	 */
	array(unsigned int s);

	/**
	 * Destructor
	 */
	~array();

	/**
	 * Overloaded operator []
	 * \param n The index into the array
	 * \return A reference to the 'n-1'th object in the array
	 */
	T& operator[](unsigned int n);

	/**
	 * Delete the array and sets the size to 0
	 */
	void clear();

	/**
	 * Resize the array to size s.
	 * \param s The new size of the array
	 */
	void resize(unsigned int s);

	/**
	 * Allocates this amount of memory for the array.
	 * If s < size of the array (different to amount of memory allocated) then the array is cut down.
	 */
	void reserve(unsigned int s);

	/**
	 * Returns the size of the array.
	 * \return The current size of the array.
	 */
	unsigned int getSize()	{	return size;	}

	/**
	 * Return the pointer to the array.
	 * \return The address of the array
	 */
	T* getPtr() const	{	return arr;	}

	/**
	 * Add an element to the back of the array.
	 * \param n A const reference to an object of type T
	 */
	void push_back(const T& n);

};
}// namespace util
#endif





// test.cpp

#include <iostream>
using namespace std;


#include "util\array.h"
#include "util\array.cpp"

int main()
{

	util::array<int> a;
	a.reserve(5);
	a.resize(2);

	// by this point, 2 array elements exist
	a.push_back(0);
	a.push_back(1);
	a.push_back(2);
	a.push_back(3);
	a.push_back(4);
	a.push_back(5);
	a.push_back(6);
	a.push_back(7);

	for(int i=0; i < a.getSize(); i++)
		cout << "Arr el["<<i<<"]: " << a[i] << endl;

return 0;
}





And it seems that I'm this close <shows very small space between thumb and forefinger> to understanding, but it won't happen. I just end up staring at the code and nothing happens. When I compile and run the test file here's what I get:
Arr el[0]: -842150451
Arr el[1]: -842150451
Arr el[2]: 0
Arr el[3]: 1
Arr el[4]: 2
Arr el[5]: 3
Arr el[6]: -33686019
Arr el[7]: 4
Arr el[8]: 5
Arr el[9]: 6
Arr el[10]: 7
The first two are fine, because they aren't initialized, so they aren't a problem. My problem is element 6. If all I use is push_back, then the size should just be increased by 1 each time and then the new value inserted into that. Any help you can give would be great.

Share this post


Link to post
Share on other sites
Your push_back function is wrong and causes a problem, this is what I changed and it seems to work correctly. Resizing it causes the last element to be taken up, reserving it allows it to be filled.

template <class T>
void array<T>::push_back(const T& n)
{
int temp = size;// this stores the current position to push_back to in case
// some re-sizing needs to be done ('size' variable changes, and an array element is skipped)

// 30-08-05 - FIXME - at some point during previous insertions, 'size' becomes greater than 'space'
// element to insert into is 'size'
if( size == space )
reserve( size + 1 );// only adding one at the moment

arr[temp] = n; // assign T object
size++; // increase size
}

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
You might want to use "delete[] arr" instead of "delete arr" since you are deleting an array.

Share this post


Link to post
Share on other sites
Incrementing by 1 each time gives quadratic O(n*n) time insertion performance.
You should multiply the size by something instead of adding to it. STL implementation typically double the size when they run out of space.

The theory is that growing the array becomes a more expensive operation over time due to copying a larger amount. This is offset by growing less often such that the amortized effort remains constant.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this