Free Tutorials
Internet
What is Internet
Internet Games
Learn TCP IP
HTML
Learn HTML
Learn CSS
Learn XML
Learn WML
Database
Learn Access
Learn Data-VB
Learn Oracle
Learn SQL
Programming
Learn ActiveX
Learn C++
Learn CGI_Perl
Learn Interdev
Learn Java
Learn JavaScript
Learn Vbscript
Learn VisualBasic
Learn VC++
Operating systems
Learn RedHat
Learn Unix
Learn Winnt


Previous Page Main Page Next Page


26 — Collection Classes

The Microsoft Foundation Classes Library implements a number of collection classes. These collection classes include a variety of lists, arrays, and mappings.

Collections have been supported by the MFC Library since its early versions. In the days of Visual C++ 1.5 and earlier versions, template support was not yet available in the compiler; correspondingly, there are several non-template-based collection classes in the Library.

Newer, 32-bit versions of the compiler obviously provide full template support. Accordingly, starting with MFC 3.0, a series of new type-safe collection classes was introduced. However, they do not render the old classes obsolete; if you have been using the non-template-based collection classes in your code, there is no reason why you should not continue to do so. In new code, it is recommended that you try to use the new, template-based classes, as their type-safe nature provides for safer, more robust code.

Throughout the MFC Library, the most commonly used collections are collections of CObject items. This fact, plus the relative simplicity of the CObject collection classes, provides a good reason for starting our review of collection classes with CObList, and CObArray.

CObject Collections

The MFC Library provides two ordered collections of CObject items. The CObList collection is a list of CObject items; the CObArray collection is an array of CObject items. But, you may ask, what exactly is the difference between the two? What are the advantages of using one or the other?

The CObList class organizes CObject pointers in a linked list. Due to the nature of such a list, insertion and removal of elements are very fast operations. On the other hand, the list is not indexed; retrieving an element by a numerical index is a slow process. List collections are meant to be used in situations where the list is "walked" with the help of an iterator. Consider, for example, a typical use of a CObList collection, namely to organize all items in a document. When the items are accessed in order to serialize or to draw the document, elements in the list are accessed sequentially.

The CObArray class, in contrast, indexes elements by an integer index value. Inserting or removing elements are slow operations, as they involve moving potentially large blocks of data. However, retrieving data by the integer index is fast.

While both classes are nominally collections of CObject pointers, you will probably never use them with the CObject class. While technically not an abstract class, the CObject class is pretty useless by itself. Instead, CObList and CObArray are used as collections of CObject-derived classes, such as collections of items of type CWnd, CView, or CDocItem. In the following sections, I present several small examples of code in which objects of type CObject are declared; note that these code fragments will not compile "as is," as creation of a CObject is prevented by the declaration of a protected constructor in the MFC library. When applying these examples to concrete situations, just substitute a CObject-derived class in these examples and assume any required typecasts.

The CObList Class and the POSITION type

Using a CObList collection involves creating the collection, adding items to the collection, and accessing items through iterator functions.

A CObList can be created either by declaring a variable of type CObList or using the new operator to obtain a pointer to a new CObList collection.

Items can be added to a CObList by calling the AddHead or AddTail functions. As their names imply, these functions add an element at the beginning and at the end of the list, respectively. Items do not need to be unique; the same CObject pointer can occur any number of times in the list.

To obtain the first or the last element on the list, use the GetHead or GetTail member functions.

It is also possible to add a new element to the list at a specific position. The InsertBefore and InsertAfter member functions can be used to insert a new element before or after a specific element. The element position is identified by a variable of type POSITION. This type is used throughout collection classes as a general-purpose iterator type.

A value of type POSITION can be obtained by calling either the GetHeadPosition or the GetTailPosition member functions. The returned POSITION value can be used in subsequent calls to GetNext or GetTail to access elements of the list sequentially. For example, to walk the elements in a CObList from the beginning to the end of the list, you would use code similar to the following:

CObList myList;

...

// Populate the list

...

POSITION pos = myList.GetHeadPosition();

while (pos != NULL)

{

    CObject *pObject = myList.GetNext(pos);

    ...

    // Do something nasty to *pObject

    ...

}

Similarly, you can walk the elements of a CObList backwards as follows:

CObList myList;

...

// Populate the list

...

POSITION pos = myList.GetTailPosition();

while (pos != NULL)

{

    CObject *pObject = myList.GetPrev(pos);

    ...

    // Do something nasty to *pObject

    ...

}

As you can see from these two examples, the names of the GetNext and GetPrev functions can be slightly misleading. What these functions do is return the current element pointed to by the POSITION parameter, while at the same time advancing this parameter to refer to the next (or previous) element.

A POSITION value can also be used with the GetAt, SetAt, and RemoveAt member functions. All three of these functions take a parameter of type POSITION; GetAt retrieves a CObject pointer corresponding to that position, SetAt sets the element at the given position to a new value, and RemoveAt removes the element from the list altogether.

Removing an element during an iteration may cause problems. In order to ensure that you always maintain a valid POSITION value for GetNext, you should use a method similar to the following:

POSITION pos = myList.GetHeadPosition();

while (pos != NULL)

{

    POSITION pos2 = pos;

    CObject *pObject = GetNext(pos);

    if ( /* pObject is to be removed */ )

    {

        myList.RemoveAt(pos2);

    }

}

Additional functions that can be used to remove elements are RemoveHead and RemoveTail. The RemoveAll function can be used to remove all elements (empty the list).

Removing an element does not destroy the element; the program that created the element is responsible for its destruction. For example:

CObject *pObject;

CObList myList;

...

pObject = new CObject;

myList.AddTail(pObject);

...

// some time later

...

pObject = myList.RemoveTail();

delete pObject;

To determine if a list is empty, use the IsEmpty member function. To obtain the number of elements in the list, call GetCount.

You can also search for a specific element in the list. The Find member function determines whether a particular CObject pointer is in the list; if so, it returns a value of type POSITION indicating its first occurrence. The FindIndex member function returns the POSITION value that corresponds to a given numerical index. Note that as the CObList class does not maintain an index of any kind, these operations can be slow if the list is large.

The CObList type is itself derived from CObject. As such, the CObList class supports serialization. If its Serialize member function is called, it in turn serializes every CObject element in the list using the << and >> operators. In order to ensure that the list is serialized correctly, elements added to it should be of a CObject-derived type that is declared and implemented using the DECLARE_SERIAL and IMPLEMENT_SERIAL macros.

CObList objects can be used in conjunction with the CArchive class and the << and >> operators, as in the following example:

class CMyDocument : public CDocument

{

    CObList m_List;

    // rest of the class declaration follows

    ...

}

void CMyDocument::Serialize(CArchive &ar)

{

    if (ar.IsStoring())

    {

        ar << m_List;

    }

    else

    {

        ar >> m_List;

    }

}

Because CObList is also CObject-derived, it is possible to use a CObList collection to refer to items of type CObList, in effect creating a list of lists.

The CObArray Class

CObArray objects are arrays of CObject pointers. These arrays are similar in function and behavior to C arrays, with one crucial difference: a CObArray can grow or shrink dynamically.

Using a CObArray involves constructing the CObArray object, populating it with CObject pointer elements, and retrieving array elements (possibly by using the overloaded [] operator).

You can create a CObArray like you would create any other variable, either on the stack as an automatic variable or through the new operator.

At the heart of the CObArray class are the SetAt, GetAt, and SetAtGrow member functions. SetAt and GetAt behave as you would expect, setting and retrieving an element at the specified location. SetAtGrow also sets an element at the specified location; however, this function causes the array to grow if the location is past the current array bounds.

Neither SetAt nor GetAt report an error if an invalid index is specified. However, they do cause an assertion in the debug version of the MFC Library.

Elements can also be added to the array using the Add member function. This member function appends a new element to the array, growing the array as necessary.

The current number of elements in the array can be obtained by calling GetSize. The largest valid array index (which is equal to the number of array elements minus one, as array indexes are zero based) can be obtained by calling GetUpperBound.

The SetSize function can be used to set the number of elements in the array, allocating additional memory if necessary. If SetSize is used to shrink the array, unused memory will be freed.

Whenever the array is grown as a result of a call to SetAtGrow, Add, or SetSize, a memory allocation error may occur. These errors are indicated by an exception of type CMemoryException being thrown.

The SetSize function can also be used to specify the amount by which memory allocated by CObArray is grown. Whenever new memory needs to be allocated, the amount allocated will hold as many CObject pointers as specified in the second parameter of SetSize. If this parameter is not set, the CObArray class attempts to determine the optimum amount of memory that it should allocate to avoid heap fragmentation.

Any extra memory allocated when the array was grown can be released by calling FreeExtra. The entire array can be emptied and all memory released by calling RemoveAll.

The CObArray class provides and override version of the [] operator. Through this operator, array elements can be accessed. The operator can be used in situations where an lvalue is needed (for example, on the left side of an assignment operation). This behavior is implemented with the help of the ElementAt member function, which returns a reference to the CObject pointer at the specified location. Thus, the following line:

myArray[10] = &myObject;

is equivalent to

myArray.ElementAt(10) = &myObject;

Two member functions, InsertAt and RemoveAt, can be used to insert elements into the array or to remove an element at a specific index. Note that these operations are slow; in the case of large arrays, they potentially require the moving of large blocks of data.

As with CObList, the CObArray class does not destroy any elements when they are removed from the array. You are responsible for freeing such items yourself. For example:

CObject *pObject;

CObArray myList;

...

pObject = new CObject;

myArray.Add(pObject);

...

// some time later

...

pObject = myArray[myArray.GetUpperBound()];

myArray.SetSize(myArray.GetUpperBound());

delete pObject;

The CObArray type is derived from CObject. One advantage of this fact is that CObArray collections can also be serialized. When the CObArray::Serialize member function is called, it in turn serializes array elements using the << and >> operators. To support serialization, elements added to the array must be of a CObject-derived type that is declared and implemented using the DECLARE_SERIAL and IMPLEMENT_SERIAL macros.

CObArray collections can be used with the CArchive class and the << and >> operators.

Other List Collections

There are several other list collections with features and behavior very similar to that of CObList.

The CPtrList Class

The CPtrList class implements identical behavior to that of CObList, but for elements that are void pointers. The features and member functions of this class are otherwise identical to the features and member functions of CObList.

Note that the CPtrList class does not support serialization.

The CStringList Class

The CStringList class is also similar in behavior and implementation to CObList. However, there is one crucial difference; instead of storing pointers to items of type CString, a CStringList stores copies of the actual CString objects themselves.

As a consequence, the application is no longer required to explicitly delete a CString object after removing it from the CStringList. Nor is it necessary to allocate an element using new or malloc to ensure that an object remains valid after the function in which it was declared terminates. For example, consider the following (incorrect) function implementation:

void MyAddElement(CObList *pList)

{

    CObject myObject;

    pList->AddTail(&myObject);  // WRONG!

}

This is obviously wrong as the address &myObject becomes meaningless when the function returns. Instead, the following implementation should have been used:

void MyAddElement(CObList *pList)

{

    CObject *pObject;

    pObject = new CObject;

    pList->AddTail(pObject);

}

The same problem does not present itself when using a CStringList. The following implementation is correct:

void MyAddElement(CStringList *pList)

{

    CString myString;

    pList->AddTail(myString);

}

Serialization of CStringList collections is supported.

Other Array Collections

In addition to CObArray, the MFC Library provides a series of additional ready-to-use array collections. Analogous to the list collections CPtrList and CStringList are the array collections CPtrArray and CStringArray; however, there are also a series of additional array collections that hold integral types.

The CPtrArray Class

The CPtrArray class implements the same behavior as CObArray but for void pointer elements. The behavior of member functions and the features of the class are identical to the features and member function behavior of CObArray.

Serialization is not supported by CPtrArray.

Integral Array Classes

There are several array classes in MFC that store elements of integral types. These are summarized in Table 26.1.

    Table 26.1. Integral Array Collection Classes.
Class Name


Element Type


CByteArray

BYTE

CWordArray

WORD

CDWordArray

DWORD

CUIntArray

UINT

The type CUIntArray differs from the other three types in that the size of a UINT is implementation-dependent. Under 16-bit Windows, a UINT as 16 bits wide; under Windows NT or Windows 95, it is a 32-bit type. Consequently, unlike the other three types, CUIntArray does not support serialization.

The other three collection classes use element types that are guaranteed to be of the same size on different implementations. A BYTE is always 8 bits wide; a WORD, 16 bits, and a DWORD is always 32 bits.

With the exception of the difference in serialization support by CUIntArray, the features and behavior of these classes is identical to the features and behavior of CObArray.

The CStringArray Class

The CStringArray class represents an array of CString objects. As in the case of CStringList, CStringArray stores copies of the CString objects themselves, not just pointers to them. Consequently, application programmers are not responsible for destroying CString objects that are removed from the array.

The features and behavior of CStringArray are otherwise similar to the features and behavior of CObArray. In particular, CStringArray supports serialization.

Mappings

Mappings represent a type of a collection that is markedly different from lists or arrays. Lists and arrays are ordered collections; in contrast, mappings represent unordered mappings of key objects to value objects. Because of the obvious similarity, mappings are sometimes also referred to as dictionaries (and indeed, implementing the functionality of a dictionary of words is a trivial task using, for example, the mapping collection CMapStringToString).

Mappings are tailored towards fast searches by key value. In all the mapping classes, key values are expected to be unique. An attempt to set a value with an existing key will overwrite the current entry in the mapping as opposed to creating an entry with a duplicate key value.

The MFC Library offers several map collections. Keys that are pointers, strings, or 16-bit words are used to index items that are pointers to CObject, pointer to void, strings, or 16-bit words. Because not all combinations of these types are implemented in the form of a mapping collection, and because there are minor variations and differences in the behavior of these classes, I review them individually.

The CMapStringToString Class

The CMapStringToString class maps keys of type CString to values of the same type.

To construct a CMapStringToString collection, simply declare an object of this type or use the new operator. Once the collection has been constructed, key-value pairs can be added to it using the SetAt member function. A convenient shorthand for using SetAt is the overloaded [] operator. Curiously, this operator can only be used in the place of an lvalue; it cannot be used for looking up keys for the simple reason that key values are often not found in the collection.

To look up data by key value, use instead the Lookup member function. The Boolean return value of this function indicates whether the key was found or not.

I suppose it would be possible to implement an overloaded form of the [] operator that can be used on the right-hand side of assignments and use an exception to communicate a lookup failure. However, an unhandled exception would cause your application to terminate even though the failure to find a key in an index is "normal" behavior.

To remove a key-value pair from the collection, use the RemoveKey member function. You can also remove all key-value pairs and thus empty the collection using RemoveAll.

You can find out if a collection is empty by calling the IsEmpty member function. The GetCount member function returns the number of key-value pairs in the collection.

It is also possible to iterate through a collection. The GetStartPosition member function yields an iterator of type POSITION that can be used in subsequent calls to GetNextAssoc to obtain key-value pairs. Note that the order in which elements are returned is arbitrary and has no significance. In particular, these functions are not guaranteed to yield elements in ascending key order.

CMapStringToString collections can be serialized. They can be used in conjunction with the CArchive class and the << and >> operators.

Listing 26.1 shows a simple, yet functional program that implements a word vocabulary. This command-line application can be compiled from the command line (cl -MT vocab.cpp).

    Listing 26.1. Using CMapStringToString in a console application.
#include <afx.h>

#include <iostream.h>

#include <stdio.h>

void main(void)

{

    CString wrd, def;

    CMapStringToString map;

    CStdioFile inf(stdin);

    cout << "Populating the dictionary\n";

    while (TRUE)

    {

        cout << "Enter word: ";

        cout.flush();

        inf.ReadString(wrd);

        if (wrd == "Q") break;

        cout << "Definition: ";

        cout.flush();

        inf.ReadString(def);

        map[wrd] = def;

    }

    if (map.IsEmpty())

    {

        cout << "Empty vocabulary!\n";

        exit(0);

    }

    cout << "Vocabulary populated with ";

    cout << map.GetCount() << " elements.\n";

    cout << "Looking up words in the dictionary\n";

    while (TRUE)

    {

        cout << "Enter word: ";

        cout.flush();

        inf.ReadString(wrd);

        if (wrd == "Q") break;

        if (map.Lookup(wrd, def))

            cout << def << '\n';

        else

            cout << "not found!\n";

    }

}

This program allocates a CMapStringToString collection and then enters an input loop. In this loop, corresponding word-definition pairs are entered by the user and added to the collection. The loop terminates when the user enters a capital Q for the word. At this time, after displaying the size of the collection, the program enters a second loop. In this loop, the user enters words that are to be looked up in the vocabulary. Here is a sample session with this program:

Populating the dictionary

Enter word: mouse

Definition: small, nocturnal rodent

Enter word: cat

Definition: small, domesticated carnivore

Enter word: dog

Definition: large, supposedly domesticated ugly animal that barks

Enter word: Q

Vocabulary populated with 3 elements.

Looking up words in the dictionary

Enter word: cat

small, domesticated carnivore

Enter word: mouse

small, nocturnal rodent

Enter word: rat

not found!

Enter word:

As I said, implementing a dictionary with these dictionary collections is indeed a trivially simple task.

The CMapStringToOb Class

The CMapStringToOb class maps objects of type CString to CObject pointers. That is, it uses string indexes to maintain a collection of CObject items. The obvious use of this class is to create a named set of CObject items.

The features and behavior of this class are almost identical to the features and behavior of CMapStringToString, with one crucial difference. As this class stores CObject pointers, it is the programmer's responsibility that any CObject items that are removed from the collection are destroyed. For example:

CObject *pObject;

CMapStringToOb myMap;

...

pObject = new CObject;

myMap["myObject"] = pObject;

...

// some time later

...

if (myMap.Lookup("myObject", pObject))

{

    myMap.RemoveKey("myObject");

    delete pObject;

};

CMapStringToOb can also be serialized and used with the CArchive class, and the << and >> operators.

The CMapStringToPtr Class

The CMapStringToPtr class maps objects of type CString to pointers to void. This class can be used to provide a collection of named items of arbitrary type.

Like the CMapStringToOb class, this class also stores pointers to items and does not free the items when the pointers are removed from the collection. It is the application programmer's responsibility to destroy the items the pointers point to.

Unlike the CMapStringToOb class, CMapStringToPtr collections cannot be serialized.

In all other respects, the features and behavior of CMapStringToPtr are identical to the features and behavior of CMapStringToOb.

The CMapPtrToPtr Class

The CMapPtrToPtr class maps void pointers to void pointers. Note that it is the pointer value that serves as a key to this collection, not the entities that these pointers refer. Thus, two pointers that refer to two identical but distinct objects will be treated as unequal keys by CMapPtrToPtr. For example, consider the following code:

CMapPtrToPtr myMap;

int a, b, x, y;

a = b = 123;

myMap[&a] = &x;

myMap[&b] = &y;

Although a and b are equal, &a and &b are not; consequently, this code adds two distinct key-value pairs to the collection.

When a key-value pair is removed from a CMapPtrToPtr collection, the application is responsible for destroying both entities that the two pointers (the key and the value) refer to.

The CMapPtrToWord Class

The CMapPtrToWord class maps void pointers to values of type WORD. Note that as with CMapPtrToPtr, it is the pointer value, not the entity it points to, that serves as the key to this collection.

When removing a key-value pair from this collection, applications should ensure that the entities the keys point to are appropriately destroyed.

The CMapWordToOb Class

The CMapWordToOb class maps an index of type WORD to items that are CObject pointers.

What is the difference between this class and a CObArray? In an array collection, indexes are assumed to start at zero and be consecutive. In contrast, the WORD indexes in a CMapWordToOb collection can be arbitrary. For example, to use the indexes 1 and 100 in a CObArray collection requires allocating memory for 101 elements; the same two indexes in a CMapWordToOb only occupy two slots in the collection.

Collections of type CMapWordToOb support serialization and work in conjunction with the CArchive class, and the << and >> operators.

The CMapWordToPtr Class

The CMapWordToPtr class maps an index of type WORD to items that are void pointers. The features and behavior of this class are identical to the features and behavior of CMapWordToOb with one exception: CMapWordToPtr does not support serialization.

Template-Based Object Collections

The collection classes that we have reviewed thus far are not type safe. Allow me to elaborate on this point.

Consider, for example, how a collection of CWnd objects would be implemented using CObList. Items that are CWnd pointers would be added to the list in a fashion similar to the following:

CWnd *pWnd;

CObList myList;

...

myList.AddTail((CObject *)pWnd);

...

pWnd = (CWnd *)(myList.GetHead());

Because of the typecast in the call to AddTail, the collection has no way of verifying that the object passed to it is indeed of the correct type. Similarly, when the item is retrieved from the collection, it is always a pointer to the CObject type. If, due to a programming error, a pointer of another CObject-derived type is passed to the collection, there will be no errors, no compiler warnings, but the application will silently fail. For example, you can add a pointer of type CDocument to the collection:

CDocument *pDoc;

...

myList.AddTail((CObject *)pDoc);

and not notice a thing; only later, when you retrieve this pointer assuming it is a pointer to a CWnd object, will your program show hard-to-analyze signs of misbehavior.

Type-safe collection templates provide a solution to this problem. By declaring the collection as follows:

CTypedPtrList<CObList, CWnd *> myList;

one can eliminate the need for typecasts and thus ensure that if anything other than a CWnd pointer is added to the collection, the compiler will indicate an error.


NOTE: It is also possible to derive type-safe versions from non-template collection classes by adding properly typed wrapper functions. However, the templates discussed here represent a more general approach.

There are two types of template collections. The first category consists of simple arrays, lists, and mappings; the second category consists of arrays, lists, and maps of typed pointers. Members of the first category are the CList, CArray, and CMap templates; members of the second category include CTypedPtrList, CTypedPtrArray, and CTypedPtrMap.

Collection Class Helper Functions

The simple collection templates CList, CArray, and CMap use seven collection class helper functions. Implementing these functions may be necessary in order for these classes to provide expected behavior.

For construction of elements, the collection classes use the ConstructElements helper function. ConstructElements is called after memory has been allocated for the new elements. The default implementation uses the constructor of type TYPE to create the elements. This function is used by all three simple collection templates when memory for new elements is allocated.

The function DestructElements is called before memory allocated for elements in the collection is deallocated. The default implementation of this function uses the destructor of type TYPE to deinitialize collection elements. This function is also used by all three simple collection templates.

The CompareElements function compares two elements for equality. The default implementation uses the == operator for this purpose. This function is used by the function CList::Find and by CMap-based collections.

The CopyElements function copies elements. The default implementation performs a bitwise copy (hardly adequate in many situations). This function is used by the CArray::Append and CArray::Copy member functions.

The SerializeElements helper function serializes elements in the collection. The default implementation performs bitwise serialization (again, this is hardly adequate in many cases). Override this function, for example, when you wish to call the Serialize member function of your collection elements instead.

The HashKey helper function is used by CMap-based collections to create a hash key. The default implementation creates a hash key by right-shifting the key value by four bit positions. Override this member function if you wish to use a hash key that is more appropriate for your application.

Finally, the DumpElements member function is used to create a diagnostic dump of collection elements. The default implementation of this function does nothing. Override this function, for example, if you wish to call the Dump member function of the collection elements instead.

The CList Template

The CList template is used to create lists of a given element type. A list is an ordered collection of items; it supports access to these items using an iterator.

The CList template takes two parameters. It is declared as follows:

template<class TYPE, class ARG_TYPE> class CList : public CObject

{

...

};

Of the two parameters, TYPE represents the type of elements that the list consists of; ARG_TYPE represents the type used in function arguments. ARG_TYPE is often a reference to TYPE. For example, a list of CString objects could be declared as follows:

CList<CString, CString&> myList;

Although the behavior of a CList and a CObList are similar, note one fundamental difference; a CList stores objects of type TYPE, not pointers to those objects. In the previous example, for every CString that is added to the list, a copy of the item is created.

A CList collection is constructed when it is declared. Elements of type TYPE are added to the collection using the AddHead or AddTail member functions. You can also add elements at a given position, identified by a POSITION value using InsertBefore and InsertAfter.

An iterator of type POSITION can be obtained by calling GetHeadPosition or GetTailPosition. Iterating through elements in the collection can be done by repeatedly calling GetNext or GetPrev, as in the following example:

CList<CString, CString&> myList;

...

// Populate the list

...

POSITION pos = myList.GetHeadPosition();

while (pos != NULL)

{

    CString str = GetNext(pos);

    ...

    // Do something ugly with str

    ...

}

The head and tail element of the list can be obtained using the GetHead and GetTail member functions.

A POSITION value can also be used in calls to GetAt, SetAt, and RemoveAt. These member functions obtain an element at a given position, set the element at a given position to a new value, and remove an element at a given position.

The head or tail of the list can be removed by calling RemoveHead or RemoveTail. The entire list can be emptied by calling RemoveAll. To find out if the list is empty, call the IsEmpty member function; GetCount can be used to obtain the number of elements in the list.

Elements can be searched for by numerical index using the FindIndex function; and by value, using the Find function. Note that you may need to provide an override version of CompareElements in order for the Find member function to work correctly.

The CList template supports serialization. In order for serialization to work properly, it may be necessary to provide an override version of the SerializeElements helper function.

The CArray Template

The CArray template is used to create a dynamically allocated array of a given element type. An array is a collection of elements accessed through a zero-based integer index. The function and behavior of CArray are identical to the function and behavior of C arrays, with the important exception that a CArray can dynamically grow and shrink.

The CArray template takes two parameters. It is declared as follows:

template<class TYPE, class ARG_TYPE> class CArray : public CObject

{

...

};

The TYPE parameter represents the type of items that this collection consists of; the ARG_TYPE represents the argument type passed to functions. Often, ARG_TYPE is a reference to type. For example:

CArray<CString, CString&> myArray;

Despite the many similarities, there is a fundamental difference between the behavior of CArray and the non-template-based array collection CObArray. CArray stores copies the items themselves as opposed to pointers to items, as is the case with CObArray.

After declaring and thus constructing a CArray object, you can use the SetSize member function to set its size. To set an element at a given index, use the SetAt member function; to obtain an element at a given index, use GetAt. SetAt will not grow the array if an index is specified that is out of bounds. However, you can use SetAtGrow for this purpose. You can also add elements to the array and grow the array as necessary by calling the Add member function.

The [] operator is a shortcut for the SetAt and GetAt member functions. It can be used on both sides of an assignment operation. When used as an lvalue, it utilizes the ElementAt member function that retrieves a reference to the specified element.

The SetSize function can also be used to define the amount by which memory allocated for the array grows when additional memory is allocated. The default implementation attempts to use an optimal value to minimize heap fragmentation. Any extra memory thus allocated can be freed by calling the FreeExtra member function.

The current size of the array can be obtained by calling GetSize. The GetUpperBound function returns the maximum allowable index in the array (which is one less than the array's size).

It is possible to insert elements at a given location or remove an element at a given location using the InsertAt and RemoveAt functions. However, these operations may involve moving large chunks of data and thus tend to be slow.

Elements from another array (of the same type) can be copied into the array at a specified index position using the Copy member function, or appended to the end of the array using the Append member function. Proper operation of these functions may require that you provide an overloaded version of the CopyElements helper function.

The CArray class supports serialization. Proper serialization behavior may require that you provide an overloaded implementation of SerializeElements.

The CMap Template

The CMap collection template provides an indexed collection of key-value pairs. CMap is declared as follows:

template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>

        class CMap : public CObject

{

    ...

};

KEY and VALUE represent the types of keys and values; ARG_KEY and ARG_VALUE represent types passed as function arguments. Often, ARG_KEY is a reference to KEY and ARG_TYPE is a reference to TYPE, as in the following example:

CMap<CString, CString&, CString, CString&> myMap;

An efficient implementation of a CMap-based collection may require that you provide a version of the HashKey function overloaded for your KEY type.

To use a CMap-based collection, construct it by declaring it. Key-value pairs can be added to the collection by calling the SetAt member function. The [] operator is a shortcut for this function. It can only be used in this situation; because not every key value is expected to be found in the collection, the [] operator cannot be used on the right-hand side of assignment expressions (in other words, as something other than an lvalue).

Elements in the collection can be found using the LookUp member function. An element identified by a given key can be removed using the RemoveKey member function; to remove all elements (empty the collection), call RemoveAll.

It is possible to iterate through the collection. An iterator of type POSITION can be obtained by calling GetStartPosition; elements can be obtained one by one by repeatedly calling GetNextAssoc. The order in which the elements are returned is arbitrary and is not expected to match the key order.

To obtain the number of elements, call GetCount. Call IsEmpty to determine whether the collection has any elements.

Two additional functions, InitHashTable and GetHashTable, can be used to initialize the collection's hashing table to a given size and to retrieve the hashing table's size.

The CTypedPtrList Template

The CTypedPtrList template provides a type-safe list of pointers by implementing a template wrapper for the non-template-based classes CObList and CPtrList. CTypedPtrList is declared as follows:

template<class BASE_CLASS, class TYPE>

        CTypedPtrList : public BASE_CLASS

{

...

};

The type BASE_CLASS should be either CObList or CPtrList. If CObList is used, TYPE must represent a pointer to CObject-derived class; if CPtrList is used, TYPE can be any kind of a pointer.

CTypedPtrList works by providing wrapper functions for all CObList or CPtrList member functions that refer to the collection elements by type. The wrapper functions perform any necessary type casting. Otherwise, the behavior of CTypedPtrList is identical to that of CObList or CPtrList. In particular, CTypedPtrList supports serialization of it is used in conjunction with CObList; however, serialization is not supported when CPtrList is used.

The CTypedPtrArray Template

The CTypedPtrArray collection template provides a type-safe array of pointers. This template is a wrapper for the non-template-based collections CObArray and CPtrArray. It is declared as follows:

template<class BASE_CLASS, class TYPE>

        CTypedPtrArray : public BASE_CLASS

{

...

};

The BASE_CLASS type should be either CObArray or CPtrArray. TYPE represents a pointer type; this must be a pointer to a CObject-derived type if CObArray is used as the BASE_CLASS but can be any pointer type if CPtrArray is used.

CTypedPtrArray works by providing a wrapper function for every CObArray or CPtrArray function that refers to collection elements by type. The wrapper functions also perform all necessary type casting.

Serialization is supported by CTypedPtrArray-derived classes if they are based on CObArray.

The CTypedPtrMap Template

The CTypedPtrMap template provides type-safe mappings. It is a wrapper template for the mapping collection classes CMapPtrToPtr, CMapPtrToWord, CMapWordToPtr, and CMapStringToPtr.

Type-safe behavior is provided by implementing wrapper functions for base class member functions that reference the type of elements.

CTypedPtrMap-based classes do not support serialization.

Summary

The Microsoft Foundation Classes Library provides a series of collection classes. There are several non-template-based collections, and also several type-safe collection templates.

Perhaps the most widely used collection classes are collections of CObject pointers. The CObList collection represents an ordered list (linked list) of CObject pointers and is used frequently for storing, for example, lists of windows in the MFC. Elements in the collection are accessed through an iterator of the special type POSITION. The other CObject pointer collection is CObArray; the function and behavior of this type of collection are similar to the function and behavior of C arrays with one crucial difference: a CObArray can dynamically grow and shrink. Both CObArray and CObList are serializable collections.

Other list collections include CPtrList (a list of void pointers) and CStringList (a list of CString items). Of these two, CPtrList does not support serialization.

Other array collections include CPtrArray, CStringArray, and a variety of integral array types. The CPtrArray class does not support serialization.

In addition to lists and arrays, the MFC Library also supports mappings. Mappings are unordered collections of key-value pairs indexed by the key. A variety of mapping classes provides support for keys of type CString, WORD, and pointers to void; values can be of type CString, WORD, pointers to void, and CObject pointers (not all combinations are supported). With the exception of mappings where either the key or the value (or both) are void pointers, mapping classes also support serialization.

Ever since template support was introduced in Visual C++, the MFC Library supports type-safe collection templates. Two types of collection templates exist; simple templates support collections of a specific type, and typed pointer templates support type-safe collections of pointers.

The simple collection templates rely on several overridable helper functions to work correctly. These include SerializeElements, which is used when collection items are serialized, and CompareElements, which is used when collection items are searched for by value. Other helper functions are used for construction and destruction, element copy, diagnostic dumping, and hashing.

The simple collection templates include CList (linked list collection), CArray (dynamically allocated array), and CMap (key-value mappings). The pointer-based collection templates include CTypedPtrList, CTypedPtrArray, and CTypedPtrMap.

The simple collection templates can be used with any type. They support serialization through the helper function SerializeElements.

The pointer-based collection templates rely on non-template collections for their behavior. Specifically, they build upon the behavior of CObList and CPtrList, CObArray and CPtrArray, and any of the pointer-based mapping classes (CMapPtrToPtr, CMapPtrToWord, CMapWordToPtr, and CMapStringToPtr). Serialization is supported by CTypedPtrList and CTypedPtrArray if they are used in conjunction with CObList and CObArray, but not when they are used in conjunction with CPtrList or CPtrArray. Serialization of pointer-based mapping templates is not supported.

Previous Page Main Page Next Page



|  About us | Categories | New Releases | Most Popular | Web Tutorial | Free Download | Drivers |



2013 Soft Lookup Corp. Privacy Statement