# Brain problems

This topic is 4529 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

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

/**
* \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 = arr;

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();

/**
* \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 << 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 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 on other sites
You might want to use "delete[] arr" instead of "delete arr" since you are deleting an array.

##### 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.