Welcome, Guest! Login | Register

Dynamic Data Structures (Part 2): Dynamic Arrays [Print this Article]
Posted by: rkzad
Date posted: Jun 19 2003
User Rating: 5 out of 5.0
Number of views: 4751
Number of comments: 0
Description: Next up, dynamic arrays. Something familiar turned dynamic.
Introduction
Okay! Now here's what you've been waiting for: the first dynamic data structure. Oh wait you didn't really have to wait did you? I posted these articles about the same time. Anyways, a dynamic array is much like a normal array, except that we can resize it through the course of the program. This is essentially what Dar is in the VGUI code of the Half-Life SDK (Dynamic array). I don't have the HL SDK installed on my computer anymore, but I remember it being there, and I will not be able to reference it. Dynamic arrays are not far off from using a normal array, so that's why I'm starting out with this.

This here is part 2. Part 1 dealt with pointers. If you do not understand pointers, check out Part 1 before going on, please.

How we're going to go about it
Now we could be using templates so we wouldn't have to re-implement dynamic arrays each time we wanted to use them, but not everybody understands templates, so I'm just going to make a general example of dynamic arrays. For our example, we're going to make a dynamic array of int variables. We'll be programming a C++ solution to this, so if you don't know classes, I'm sorry, that's not what this tutorial is about. (Be happy I taught you pointers! user posted image)

Our dynamic array will need the ability to: resize itself, take in a new element at the end of it, take in a new element in a specific spot, remove an element, access an element, change an element's value, clear all its values, and to return information on its size and the number of elements it contains. Also, since the idea is to save space, a dynamic array will not let empty elements stay between two occupied elements. So, when we remove an element from the middle, we have to move all of the elements above it down one.

Class Definition
Whether or not it's good programming practice, I generally start off with defining my classes as a planning process. This way you don't get busy implementing, and you can figure how classes would call each other, what members they have, and what functions they should have. It works for me.

 CODE (C++) 
#pragma once
 
class CDynIntArray
{
private:
    int *m_pIntArray;
    int m_iSize;
    int m_iCount;
 
public:
    CDynIntArray(int iSize);
    ~CDynIntArray();
 
    inline int GetSize() const { return m_iSize; }
    inline int GetCount() const { return m_iCount; }
 
    void Resize(int iSize);
    void ClearAll();
 
    void InsertElement(int iElement, int iValue);
    void RemoveElement(int iElement);
    void AddElement(int iValue);
    int &operator[](int iElement);
};


There's our definition for our dynamic integer array. If you didn't get parts of that, do not worry, I will explain them to you. First off, I'll explain the member variables. m_iCount and m_iSize hold information on the array: how many elements are in the array, and how many elements the array can currently stored. m_pIntArray will hold our dynamically allocated array, as seen in Part 1: Pointers.

I'm going to explain the functions as I go through the c++ file. So without further ado:

Implementation
 CODE (C++) 
#include <stdio.h>
#include <memory.h>
#include "DynArray.h"
 
CDynIntArray::CDynIntArray(int iSize)
: m_iSize(iSize),
  m_iCount(0)
{
    m_pIntArray = new int[iSize];
}


As you can see, our constructor takes one parameter: "iSize". This will be the initial size of the array. The reason we do this is so that if we know the array will be at least 20 elements, we may as well create our array with a size of 20 to begin with so we don't have to waste time allocating and copying all the data each time we want to add a new element. We also initialize the element count to 0 since we obviously don't have any data yet, and we dynamically allocate our integer array with the specified size.

 CODE (C++) 
CDynIntArray::~CDynIntArray()
{
    if (m_pIntArray)
        delete []m_pIntArray;
}


Our dynamic array class has a very simple destructor. It just checks if m_pIntArray was successfully created, and if so it deletes it. We do not have to worry about deleting each element individually since we know exactly how much memory we want to free.

 CODE (C++) 
void CDynIntArray::Resize(int iSize)
{
    int *pTemp = m_pIntArray;

    if (!m_pIntArray || iSize < 1)
        return;
 
    m_pIntArray = new int[iSize];
 
    if (m_pIntArray || !iSize)
    {
        memcpy(m_pIntArray, pTemp, sizeof(int) * (iSize > m_iSize ? m_iSize : iSize));
 
        m_iSize = iSize;
        m_iCount = (m_iCount > m_iSize ? m_iSize : m_iCount);
 
        delete []pTemp;
    }
    else
        m_pIntArray = pTemp;
}


As you may have been able to tell by the name of the function, this code resizes the dynamic array. The general algorith for this is: Make sure our input is valid, store the address to our previous array in a temporary pointer, allocate a new array. If we were able to allocate our new array, copy as much data as possible into our new array, update the size and count values, and delete the old array. If we were not able to allocate our new array, simply use our old array again. This function will get called by the class whenever it's running out of space.

 CODE (C++) 
void CDynIntArray::ClearAll()
{
    m_iCount = 0;
}


This is a very simple function. This doesn't actually clear all the data, but it has the class treat the array as if it has no more elements, and saves all the data it originally had, keeping all the memory it had available to it. If you want to resize the array back to a size of 1, simply call Resize(1).

 CODE (C++) 
void CDynIntArray::AddElement(int iValue)
{
    if (!m_pIntArray)
        return;
 
    if (m_iCount == m_iSize)
        Resize(m_iSize + m_iResizeBy);
 
    m_pIntArray[m_iCount++] = iValue;
}


This is the easier of the insertion functions, and just adds a value to the end of the array, making sure the array is big enough to hold the data.

 CODE (C++) 
void CDynIntArray::InsertElement(int iElement, int iValue)
{
    if (!m_pIntArray || iElement < 0 || iElement > m_iCount)
        return;
 
    if (m_iCount == m_iSize)
        Resize(m_iSize + m_iResizeBy);
 
    for (int i = m_iCount; i > iElement; --i)
        m_pIntArray[i] = m_pIntArray[i-1];
 
    m_pIntArray[iElement] = iValue;
 
    ++m_iCount;
}


This is the more complicated insertion function, and allows a value to be inserted anywhere into the array (pushing the rest of the elements out of it's way).

For example, say the array was: 1, 2, 3, 4, 5, 6
and you called InsertElement(2, 0);
the array would now be: 1, 2, 0, 3, 4, 5, 6

Now the difference between this and AddElement is obviously that InsertElement takes an iElement value, and must also validate it. Our dynamic array only lets somebody insert a value anywhere from the beginning of the array to the end of the array, but not past the end of the array (for example, slot 8 when the array has a size of 5).

 CODE (C++) 
void CDynIntArray::RemoveElement(int iElement)
{
    if (!m_pIntArray || iElement < 0 || iElement >= m_iCount)
        return;
 
    for (int i = iElement; i < m_iCount - 1; ++i)
        m_pIntArray[i] = m_pIntArray[i+1];
 
    --m_iCount;
}


Well (obviously) this is the code to remove an element out of the array. When an element is removed, all the elements above it are moved down to get rid of the "hole". Unlike when we're adding an element, the array is not resized when we remove an element, since we anticipate we will most likely be going back to that size again in the near future.

All this work for an array which is more complicated to use? All these functions! Well, operator overloading lets us make certain things easier:
 CODE (C++) 
int& CDynIntArray::operator[](int iElement)
{
    static int iError = -1;
 
    if (!m_pIntArray || iElement < 0 || iElement > m_iSize - 1)
        return iError;
 
    return m_pIntArray[iElement];
}

This lets us use our class as if it was an actual array and we will now be able to use substripting (the brackets []) to access any element that already exists inside our array. You can even replace an element's value with this, just as if you would an array. This is possible since we return a reference to our element (the & in int) so that it will affect our int value in our array.

Here's some sample code showing what the array would contain at each step
 CODE (C++) 
CDynIntArray ar(5);
ar.AddElement(1);
ar.AddElement(2);
ar.AddElement(3);
ar[1] = 5;
// The array is now: 1, 5, 3
 
cout << ar[1];
// Output: 5
 
ar.InsertElement(2, 10);
// The array is now: 1, 5, 10, 3
 
ar.RemoveElement(0);
// The array is now: 5, 10, 3
 
ar.Resize(1);
// The array is now: 5
 
ar.ClearAll();
// The array is now:


That's it for dynamic arrays, and part 2 of the series. If you see any mistakes or things I left out, please let me know so I can fix them by PM'ing me or e-mailing me at rkzad@hotmail.com. If you have any questions about dynamic arrays, please visit the General Programming forum.

Rate This Article
This article is currently rated: 5 out of 5.0 (1 Votes)

You have to register to rate this article.
User Comments

No User Comments

You must register to post a comment. If you have already registered, you must login.

Latest Articles
3rd person View in Multiplayer
Half-Life 2 | Coding | Client Side Tutorials
How to enable it in HL2DM

By: cct | Nov 13 2006

Making a Camera
Half-Life 2 | Level Design
This camera is good for when you join a map, it gives you a view of the map before you join a team

By: slackiller | Mar 05 2006

Making a camera , Part 2
Half-Life 2 | Level Design
these cameras are working monitors that turn on when a button is pushed.

By: slackiller | Mar 04 2006

Storing weapons on ladder
Half-Life 2 | Coding | Snippets
like Raven Sheild or BF2

By: British_Bomber | Dec 24 2005

Implementation of a string lookup table
Half-Life 2 | Coding | Snippets
A string lookup table is a set of functions that is used to convert strings to pre-defined values

By: deathz0rz | Nov 13 2005


Latest Comments
knock knock
General | News
By: omega | Dec 22 2016
 
knock knock
General | News
By: MIFUNE | Oct 10 2015
 
New HL HUD Message System
Half-Life | Coding | Shared Tutorials
By: chbrules | Dec 31 2011
 
knock knock
General | News
By: Whistler | Nov 05 2011
 
Particle Engine tutorial part 4
Half-Life | Coding | Client Side Tutorials
By: darkPhoenix | Feb 18 2010
 
Particle Engine tutorial part 2
Half-Life | Coding | Client Side Tutorials
By: darkPhoenix | Feb 11 2010
 
Particle Engine tutorial part 3
Half-Life | Coding | Client Side Tutorials
By: darkPhoenix | Feb 11 2010
 
Game Movement Series #2: Analog Jumping and Floating
Half-Life 2 | Coding | Shared Tutorials
By: mars3554 | Oct 26 2009
 
Particle Engine tutorial part 5
Half-Life | Coding | Client Side Tutorials
By: Deadpool | Aug 02 2009
 
Particle Engine tutorial part 5
Half-Life | Coding | Client Side Tutorials
By: Persuter | Aug 02 2009
 

Site Info
297 Approved Articless
8 Pending Articles
3940 Registered Members
0 People Online (7 guests)
About - Credits - Contact Us

Wavelength version: 3.0.0.9
Valid XHTML 1.0! Valid CSS!