A Template For General Data Arrays

• Download source files - 3 Kb

In my programming work, I have to write code to store and manipulate data items almost daily. I like to use arrays better than linked lists of pointers as the containers of my data objects. There are many powerful container classes in various existing commercial libraries. However, they either don't do exactly what I want or they offer too many features (or I just don't like their naming conventions). And that's enough reason for me to write my own simple template class.

XYDataArray is the name of the template class I wrote to handle general data types. The class type parameter must be either a primitive data type (int, double, pointers, etc.) or a class that implements the default constructor and the assignment operator. One feature I like in array classes is the implementation of a stable sort algorithm. In case you don't know, a stable sort does not change the order of elements with equal key values. For example, you want to sort a list of people by gender and this list is already sorted by age. After a stable sort, the new list will be ordered by gender, but within each gender group, the people will still be ordered by age. Therefore, it is easy to use stable sort to implement multi-column sorting of tabulated data. In order to use the stable sort feature of XYDataArray, the corresponding data type has to define the following operators: < (less than), and == (equal to).

The source code for XYDataArray is straight forward except perhaps the stable sort algorithm. There is a simple program in file ArrayTest.cpp that demonstrates how to use XYDataArray. Here I give a brief description of the methods of XYDataArray.

XYDataArray( );
This method constructs an empty array.

XYDataArray(const TYPE* pData, const int nSize, const int nGrowBy = 64);
This method constructs an array with given data. TYPE is the class parameter of the template; pData must point to a block of nSize elements. The nGrowBy parameter specifies how the array's internal buffer grows or shrinks. The default, 64, means that the internal buffer will grow in multiples of 64 elements.

virtual ~XYDataArray( );
The virtual destructor.

int Find(const TYPE& tData) const;
This method returns the index of tData within the array. TYPE is the class parameter of the template. The return value is -1 if tData is not found. If the array is already sorted, this method will use a binary search instead of linear search.

int Locate(const TYPE& tData) const;
This method returns the position at which to insert a new element tData. TYPE is the class parameter of the template. If the array is already sorted, inserting at the returned position will keep the array sorted.

void SetSize(const int nSize, const int nGrowBy = 64);
This method changes the size of the array. If the new size is bigger than the original size, the array will be chopped. Otherwise, new elements will be added using the default constructor of the class parameter of the template. In any case, the original elements, except the ones being chopped off, will be preserved (copied if necessary).

int GetSize( ) const;
This method returns the current size of the array.

TYPE* GetDataPtr( ) const;
This method returns a pointer to the internal data buffer. TYPE is the class parameter of the template.

const TYPE& operator( )(const int nIndex) const;
This method returns a const reference to the element at the position nIndex. TYPE is the class parameter of the template.

TYPE& operator[ ](const int nIndex);
This method returns a reference to the element at the position nIndex. TYPE is the class parameter of the template.

int Add(const TYPE& tData);
This method adds a new element tData to the array. TYPE is the class parameter of the template. If the array is already sorted, adding the new element will keep the array sorted. Otherwise, the new element will be appended to the end of the array. The return value is the position of the newly added element.

int Insert(const int nIndex, const TYPE& tData);
This method inserts a new element tData to the array at position nIndex. TYPE is the class parameter of the template. The return value is -1 if nIndex is invalid (out of the range between 0 and the size of the array). Otherwise, it returns nIndex.

int Remove(const int nIndex);
This method removes the element tData at position nIndex from the array. TYPE is the class parameter of the template. The return value is -1 if nIndex is out of range. Otherwise, it returns the size of the new array.

int SetAt(const int nIndex, const TYPE& tData);
This method assigns the element tData to position nIndex in the array. TYPE is the class parameter of the template. The return value is -1 if nIndex is out of range. Otherwise, it returns nIndex.

void Push(const TYPE& tData);
This method add a new element tData to the end of the array. TYPE is the class parameter of the template.

TYPE Pop( );
This method removes an element from the end of the array. TYPE is the class parameter of the template.

int GetSort() const;
This method returns 1 if the array is sorted in ascending order, it returns -1 if sorted in descending order. Otherwise, it returns 0.

void SetSort(int nSort);
If nSort is 1, it will sort the array in ascending order if not already sorted. If nSort is -1, it will sort the array in descending order if not already sorted.

virtual void Sort(const int nSort = 1);
This method sorts the array. nSort specifies what order to sort, 1 for ascending, -1 for descending.

virtual void SortIndex(int* pIndex, const int nSort = 1) const;
This method does not sort the array itself, instead, it sorts an index array according to the specified order. pIndex must be pointing to a data block containing integers 0, 1, 2, ..., (nSize-1), where nSize is the size of the current array. The Sort method is implemented using this method. The algorithm is a combination of insertion sort and "randomized" quick sort. The implementation looks complicated because it has to be a stable sort.

Note XYDataArray is part of, and has been used extensively in, my client-server tool package XYSystem. You may use the source code provided here with no condition attached. Please visit my web page for more information on XYSystem.

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)