// 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;
space = s;
<span class="cpp-keyword">return</span>;
}
<span class="cpp-comment">// if param is the same value as current space, ignore</span>
<span class="cpp-keyword">if</span>( s == space )
<span class="cpp-keyword">return</span>;
temp = <span class="cpp-keyword">new</span> T; <span class="cpp-comment">// new array</span>
<span class="cpp-comment">// the number of elements that has to be looped through to</span>
<span class="cpp-comment">// copy the elements of the array</span>
<span class="cpp-keyword">if</span>( s >= size ){
tmp = size;
space = s; <span class="cpp-comment">// set amount of elements reserved in memory</span>
}
<span class="cpp-keyword">else</span> <span class="cpp-keyword">if</span>( s < size ){
tmp = s;
size = space = s; <span class="cpp-comment">// set size of array and amount of elements reserved in memory</span>
}
<span class="cpp-keyword">for</span>(<span class="cpp-keyword">int</span> i=<span class="cpp-number">0</span>; i < tmp; i++)
temp<span style="font-weight:bold;"> = arr<span style="font-weight:bold;">;
<span class="cpp-keyword">delete</span> arr; <span class="cpp-comment">// delete old array</span>
arr = temp; <span class="cpp-comment">// assign new array</span>
}
<span class="cpp-comment">/**
* Add an element to the back of the array.
* \param n A const reference to an object of type T
*/</span>
<span class="cpp-keyword">template</span> <<span class="cpp-keyword">class</span> T>
<span class="cpp-keyword">void</span> array<T>::push_back(<span class="cpp-keyword">const</span> T& n)
{
<span class="cpp-keyword">int</span> temp = size;<span class="cpp-comment">// this stores the current position to push_back to in case</span>
<span class="cpp-comment">// some re-sizing needs to be done ('size' variable changes, and an array element is skipped)</span>
<span class="cpp-comment">// 30-08-05 - FIXME - at some point during previous insertions, 'size' becomes greater than 'space'</span>
<span class="cpp-comment">// element to insert into is 'size'</span>
<span class="cpp-keyword">if</span>( size == space )
resize( size + <span class="cpp-number">1</span> );<span class="cpp-comment">// only adding one at the moment</span>
arr[temp] = n; <span class="cpp-comment">// assign T object</span>
size++; <span class="cpp-comment">// increase size</span>
}
}<span class="cpp-comment">//namespace util</span>
<span class="cpp-directive">#endif</span>
</pre></div><!–ENDSCRIPT–>
<!–STARTSCRIPT–><!–source lang="cpp"–><div class="source"><pre>
<span class="cpp-comment">// array.h</span>
<span class="cpp-directive">#ifndef</span> _UTIL_ARRAY_H_
<span class="cpp-directive">#define</span> _UTIL_ARRAY_H_
<span class="cpp-keyword">namespace</span> util{
<span class="cpp-comment">/**
* This class defines a wrapper for a templated dynamic array.
*/</span>
<span class="cpp-keyword">template</span> <<span class="cpp-keyword">class</span> T>
<span class="cpp-keyword">class</span> array
{
<span class="cpp-keyword">private</span>:
<span class="cpp-keyword">unsigned</span> <span class="cpp-keyword">int</span> space; <span class="cpp-comment">///< The number of array elements allocated in memory</span>
<span class="cpp-keyword">unsigned</span> <span class="cpp-keyword">int</span> size; <span class="cpp-comment">///< The size of the array</span>
T* arr; <span class="cpp-comment">///< Pointer to the array</span>
<span class="cpp-keyword">public</span>:
<span class="cpp-comment">/**
* Default constructor
*/</span>
array();
<span class="cpp-comment">/**
* Constructor
* \param s The initial size of the array
*/</span>
array(<span class="cpp-keyword">unsigned</span> <span class="cpp-keyword">int</span> s);
<span class="cpp-comment">/**
* Destructor
*/</span>
~array();
<span class="cpp-comment">/**
* Overloaded operator []
* \param n The index into the array
* \return A reference to the 'n-1'th object in the array
*/</span>
T& <span class="cpp-keyword">operator</span>[](<span class="cpp-keyword">unsigned</span> <span class="cpp-keyword">int</span> n);
<span class="cpp-comment">/**
* Delete the array and sets the size to 0
*/</span>
<span class="cpp-keyword">void</span> clear();
<span class="cpp-comment">/**
* Resize the array to size s.
* \param s The new size of the array
*/</span>
<span class="cpp-keyword">void</span> resize(<span class="cpp-keyword">unsigned</span> <span class="cpp-keyword">int</span> s);
<span class="cpp-comment">/**
* 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.
*/</span>
<span class="cpp-keyword">void</span> reserve(<span class="cpp-keyword">unsigned</span> <span class="cpp-keyword">int</span> s);
<span class="cpp-comment">/**
* Returns the size of the array.
* \return The current size of the array.
*/</span>
<span class="cpp-keyword">unsigned</span> <span class="cpp-keyword">int</span> getSize() { <span class="cpp-keyword">return</span> size; }
<span class="cpp-comment">/**
* Return the pointer to the array.
* \return The address of the array
*/</span>
T* getPtr() <span class="cpp-keyword">const</span> { <span class="cpp-keyword">return</span> arr; }
<span class="cpp-comment">/**
* Add an element to the back of the array.
* \param n A const reference to an object of type T
*/</span>
<span class="cpp-keyword">void</span> push_back(<span class="cpp-keyword">const</span> T& n);
};
}<span class="cpp-comment">// namespace util</span>
<span class="cpp-directive">#endif</span>
</pre></div><!–ENDSCRIPT–>
<!–STARTSCRIPT–><!–source lang="cpp"–><div class="source"><pre>
<span class="cpp-comment">// test.cpp</span>
<span class="cpp-directive">#include</span> <iostream>
<span class="cpp-keyword">using</span> <span class="cpp-keyword">namespace</span> std;
<span class="cpp-directive">#include</span> <span class="cpp-literal">"util\array.h"</span>
<span class="cpp-directive">#include</span> <span class="cpp-literal">"util\array.cpp"</span>
<span class="cpp-keyword">int</span> main()
{
util::array<<span class="cpp-keyword">int</span>> a;
a.reserve(<span class="cpp-number">5</span>);
a.resize(<span class="cpp-number">2</span>);
<span class="cpp-comment">// by this point, 2 array elements exist</span>
a.push_back(<span class="cpp-number">0</span>);
a.push_back(<span class="cpp-number">1</span>);
a.push_back(<span class="cpp-number">2</span>);
a.push_back(<span class="cpp-number">3</span>);
a.push_back(<span class="cpp-number">4</span>);
a.push_back(<span class="cpp-number">5</span>);
a.push_back(<span class="cpp-number">6</span>);
a.push_back(<span class="cpp-number">7</span>);
<span class="cpp-keyword">for</span>(<span class="cpp-keyword">int</span> i=<span class="cpp-number">0</span>; i < a.getSize(); i++)
cout << <span class="cpp-literal">"Arr el["</span><<i<<<span class="cpp-literal">"]: "</span> << a<span style="font-weight:bold;"> << endl;
<span class="cpp-keyword">return</span> <span class="cpp-number">0</span>;
}
</pre></div><!–ENDSCRIPT–>
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:
<pre>
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
</pre>
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.Brain problems
Author
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'.
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
}
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
}
You might want to use "delete[] arr" instead of "delete arr" since you are deleting an array.
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
