Arrays

[Previous] [Next]

One of the greatest weaknesses of C and C++ is that arrays are not bounds-checked. Consider the following code, which reflects one of the most common bugs found in C and C++ applications:

 int array[10]; for (int i=0; i<=10; i++)     array[i] = i + 1; 

This code is buggy because the final iteration of the for loop writes past the end of the array. When executed, it will cause an access violation.

C++ programmers frequently combat such problems by writing array classes that perform internal bounds checks. The following array class features Get and Set functions that check the array indexes passed to them and assert when passed an invalid index:

 class CArray { protected:     int m_nSize;     // Number of elements in the array.     int* m_pData;    // Where the array's elements are stored. public:     CArray (int nSize)     {         m_nSize = nSize;         m_pData = new int[nSize];     }     ~CArray ()     {         m_nSize = 0;         if (m_pData != NULL) {             delete[] m_pData;             m_pData = NULL;         }     }     int Get (int nIndex)     {         assert (nIndex >= 0 && nIndex < m_nSize);         return m_pData[nIndex];     }     void Set (int nIndex, int nVal)     {         assert (nIndex >= 0 && nIndex < m_nSize);         m_pData[nIndex] = nVal;     } }; 

With this simple class serving as a container for an array of integers, the following code will assert when Set is called for the final time:

 CArray array (10); for (int i=0; i<=10; i++)     array.Set (i, i + 1); // Asserts when i == 10. 

Now the error will be caught before an access violation occurs.

The MFC Array Classes

You don't have to write array classes yourself because MFC provides an assortment of them for you. First there's the generic CArray class, which is actually a template class from which you can create type-safe arrays for data of any type. CArray is defined in the header file Afxtempl.h. Then there are the nontemplatized array classes, each of which is designed to hold a particular type of data. These classes are defined in Afxcoll.h. The following table lists the nontemplatized MFC array classes and the types of data that they store.

Type-Specific MFC Array Classes

Class Name	Data Type
CByteArray	8-bit bytes (BYTEs)
CWordArray	16-bit words (WORDs)
CDWordArray	32-bit double words (DWORDs)
CUIntArray	Unsigned integers (UINTs)
CStringArray	CStrings
CPtrArray	void pointers
CObArray	CObject pointers

Once you learn to use one of these array classes, you can use the others too, because all share a common set of member functions. The following example declares an array of 10 UINTs and initializes it with the numbers 1 through 10:

 CUIntArray array; array.SetSize (10); for (int i=0; i<10; i++)     array[i] = i + 1; 

You can use the same approach to declare an array of CStrings and initialize it with textual representations of the integers 1 through 10:

 CStringArray array; array.SetSize (10); for (int i=0; i<10; i++) {     CString string;     string.Format (_T ("%d"), i);     array[i] = string; } 

In both cases, SetSize sizes the array to hold 10 elements. In both cases, the overloaded [] operator calls the array's SetAt function, which copies a value to an element at a specified location in the array. And in both cases, the code asserts if the array's bounds are violated. The bounds check is built into the code for SetAt:

 ASSERT(nIndex >= 0 && nIndex < m_nSize); 

You can see this code for yourself in the MFC source code file Afxcoll.inl.

You can insert items into an array without overwriting the items that are already there by using the InsertAt function. Unlike SetAt, which simply assigns a value to an existing array element, InsertAt makes room for the new element by moving elements above the insertion point upward in the array. The following statements initialize an array with the numbers 1 through 4 and 6 through 10, and then insert a 5 between the 4 and the 6:

 CUIntArray array; array.SetSize (9); for (int i=0; i<4; i++)     array[i] = i + 1; for (i=4; i<9; i++)     array[i] = i + 2; array.InsertAt (4, 5); // Insert a 5 at index 4. 

You can also pass a third parameter to InsertAt specifying the number of times the item should be inserted or pass a pointer to another array object in parameter 2 to insert an entire array. Note that this example sets the array size to 9, not 10, yet no assertion occurs when InsertAt is called. That's because InsertAt is one of a handful of array functions that automatically grow the array as new items are added. Dynamically sized arrays are discussed in the next section.

Values can be retrieved from an MFC array using standard array addressing syntax. The following example reads back the UINTs written to the CUIntArray in the previous example:

 for (int i=0; i<10; i++)     UINT nVal = array[i]; 

Used this way, the [] operator calls the array's GetAt function, which retrieves a value from a specified position in the array—with bounds checking, of course. If you'd prefer, you can call GetAt directly rather than use the [] operator.

To find out how many elements an array contains, call the array's GetSize function. You can also call GetUpperBound, which returns the 0-based index of the array's upper bound—the number of elements in the array minus 1.

MFC's array classes provide two functions for removing elements from an array: RemoveAt and RemoveAll. RemoveAt removes one or more items from the array and shifts down any items above the ones that were removed. RemoveAll empties the array. Both functions adjust the array's upper bounds to reflect the number of items that were removed, as the following example demonstrates:

 // Add 10 items. CUIntArray array; array.SetSize (10); for (int i=0; i<10; i++)     array[i] = i + 1; // Remove the item at index 0. array.RemoveAt (0); TRACE (_T ("Count = %d\n"), array.GetSize ()); // 9 left. // Remove items 0, 1, and 2. array.RemoveAt (0, 3); TRACE (_T ("Count = %d\n"), array.GetSize ()); // 6 left. // Empty the array. array.RemoveAll (); TRACE (_T ("Count = %d\n"), array.GetSize ()); // 0 left. 

The Remove functions delete elements, but they don't delete the objects that the elements point to if the elements are pointers. If array is a CPtrArray or a CObArray and you want to empty the array and delete the objects referenced by the deleted pointers, rather than write

 array.RemoveAll (); 

you should write this:

 int nSize = array.GetSize (); for (int i=0; i<nSize; i++)     delete array[i]; array.RemoveAll (); 

Failure to delete the objects whose addresses are stored in a pointer array will result in memory leaks. The same is true of MFC lists and maps that store pointers.

Dynamic Array Sizing

Besides being bounds-checked, the MFC array classes also support dynamic sizing. You don't have to predict ahead of time how many elements a dynamically sized array should have because the memory set aside to store array elements can be grown as elements are added and shrunk as elements are removed.

One way to dynamically grow an MFC array is to call SetSize. You can call SetSize as often as needed to allocate additional memory for storage. Suppose you initially size an array to hold 10 items but later find that it needs to hold 20. Simply call SetSize a second time to make room for the additional items:

 // Add 10 items. CUIntArray array; array.SetSize (10); for (int i=0; i<10; i++)     array[i] = i + 1;          // Add 10 more. array.SetSize (20); for (i=10; i<20; i++)     array[i] = i + 1; 

When an array is resized this way, the original items retain their values. Thus, only the new items require explicit initialization following a call to SetSize.

Another way to grow an array is to use SetAtGrow instead of SetAt to add items. For example, the following code attempts to use SetAt to add 10 items to an array of UINTs:

 CUIntArray array; for (int i=0; i<10; i++)     array.SetAt (i, i + 1); 

This code will assert the first time SetAt is called. Why? Because the array's size is 0 (note the absence of a call to SetSize), and SetAt doesn't automatically grow the array to accommodate new elements. Change SetAt to SetAtGrow, however, and the code works just fine:

 CUIntArray array; for (int i=0; i<10; i++)     array.SetAtGrow (i, i + 1); 

Unlike SetAt, SetAtGrow automatically grows the array's memory allocation if necessary. So does Add, which adds an item to the end of the array. The next example is functionally identical to the previous one, but it uses Add instead of SetAtGrow to add elements to the array:

 CUIntArray array; for (int i=0; i<10; i++)     array.Add (i + 1); 

Other functions that automatically grow an array to accommodate new items include InsertAt, Append (which appends one array to another), and Copy, which, as the name implies, copies one array to another.

MFC grows an array by allocating a new memory buffer and copying items from the old buffer to the new one. If a grow operation fails because of insufficient memory, MFC throws an exception. To trap such errors when they occur, wrap calls that grow an array in a try block accompanied by a catch handler for CMemoryExceptions:

 try {     CUIntArray array;     array.SetSize (1000); // Might throw a CMemoryException.          } catch (CMemoryException* e) {     AfxMessageBox (_T ("Error: Insufficient memory"));     e->Delete (); // Delete the exception object. } 

This catch handler displays an error message warning the user that the system is low on memory. In real life, more extensive measures might be required to recover gracefully from out-of-memory situations.

Because a new memory allocation is performed every time an array's size is increased, growing an array too frequently can adversely impact performance and can also lead to memory fragmentation. Consider the following code fragment:

 CUIntArray array; for (int i=0; i<100000; i++)     array.Add (i + 1); 

These statements look innocent enough, but they're inefficient because they require thousands of separate memory allocations. That's why MFC lets you specify a grow size in SetSize's optional second parameter. The following code initializes the array more efficiently because it tells MFC to allocate space for 10,000 new UINTs whenever more memory is required:

 CUIntArray array; array.SetSize (0, 10000); for (int i=0; i<100000; i++)     array.Add (i + 1); 

Of course, this code would be even better if it allocated room for 100,000 items up front. But very often it's impossible to predict in advance how many elements the array will be asked to hold. Large grow sizes are beneficial if you anticipate adding many items to an array but can't determine just how big the number will be up front.

If you don't specify a grow size, MFC picks one for you using a simple formula based on the array size. The larger the array, the larger the grow size. If you specify 0 as the array size or don't call SetSize at all, the default grow size is 4 items. In the first of the two examples in the previous paragraph, the for loop causes memory to be allocated and reallocated no less than 25,000 times. Setting the grow size to 10,000 reduces the allocation count to just 10.

The same SetSize function used to grow an array can also be used to reduce the number of array elements. When it downsizes an array, however, SetSize doesn't automatically shrink the buffer in which the array's data is stored. No memory is freed until you call the array's FreeExtra function, as demonstrated here:

 array.SetSize (50);     // Allocate room for 50 elements. array.SetSize (30);     // Shrink the array size to 30 elements. array.FreeExtra ();     // Shrink the buffer to fit exactly 30 elements. 

You should also call FreeExtra after RemoveAt and RemoveAll if you want to shrink the array to the minimum size necessary to hold the remaining elements.

Creating Type-Safe Array Classes with CArray

CUIntArray, CStringArray, and other MFC array classes work with specific data types. But suppose you need an array for another data type—say, CPoint objects. Because there is no CPointArray class, you must create your own from MFC's CArray class. CArray is a template class used to build type-safe array classes for arbitrary data types.

To illustrate, the following code sample declares a type-safe array class for CPoint objects and then instantiates the class and initializes it with an array of CPoints describing a line:

 CArray<CPoint, CPoint&> array; // Populate the array, growing it as needed. for (int i=0; i<10; i++)     array.SetAtGrow (i, CPoint (i*10, 0)); // Enumerate the items in the array. int nCount = array.GetSize (); for (i=0; i<nCount; i++) {     CPoint point = array[i];     TRACE (_T ("x=%d, y=%d\n"), point.x, point.y); } 

The first CArray template parameter specifies the type of data stored in the array; the second specifies how the type is represented in parameter lists. You could use CPoints instead of CPoint references, but references are more efficient when the size of the item exceeds the size of a pointer.

You can use data of any kind—even classes of your own creation—in CArray's template parameters. The following example declares a class that represents points in three-dimensional space and fills an array with 10 class instances:

 class CPoint3D { public:     CPoint3D ()     {         x = y = z = 0;     }     CPoint3D (int xPos, int yPos, int zPos)     {         x = xPos;         y = yPos;         z = zPos;     }     int x, y, z; }; CArray<CPoint3D, CPoint3D&> array; // Populate the array, growing it as needed. for (int i=0; i<10; i++)     array.SetAtGrow (i, CPoint3D (i*10, 0, 0)); // Enumerate the items in the array. int nCount = array.GetSize (); for (i=0; i<nCount; i++) {     CPoint3D point = array[i];     TRACE (_T ("x=%d, y=%d, z=%d\n"), point.x, point.y, point.z); } 

It's important to include default constructors in classes you use with CArray and other template-based MFC collection classes because MFC uses a class's default constructor to create new items when functions such as InsertAt are called.

With CArray at your disposal, you can, if you want to, do without the older (and nontemplatized) MFC array classes such as CUIntArray and use templates exclusively. The following typedef declares a CUIntArray data type that is functionally equivalent to MFC's CUIntArray:

 typedef CArray<UINT, UINT> CUIntArray; 

Ultimately, the choice of which CUIntArray class to use is up to you. However, the MFC documentation recommends that you use the template classes whenever possible, in part because doing so is more in keeping with modern C++ programming practices.