Standard Collections

Now that you've looked at the major similarities among the .NET Framework class library collections, you'll take a look at how they differ. You'll start with the standard, or more common, collections of the class library. There's nothing new about these collection types, as they've been around for quite a long time. What's different is how the .NET Framework class library implements them and what interfaces the library provides.

ArrayList

If you've never coded an array, then you probably haven't been coding very long. Arrays, with their simple syntax, are the easiest of all collections to work with, especially when you know exactly how much data you're working with. Unfortunately, they quickly lose their usefulness when the number of data elements is unknown.

The ArrayList is a solution to the shortcomings of the simple array. You get the simple syntax of an array without having to worry about the number of data elements. Well, that's not quite accurate: You actually get a slightly more complex array syntax, but only after the array is already loaded. Loading the ArrayList requires member method calls—simple ones, but method calls just the same. Once the ArrayList is loaded, though, you can treat it almost exactly as you would a simple array.

There is nothing difficult about creating an ArrayList; it is simply a standard class. It does have three different constructors. The default takes no parameters. This constructor creates an ArrayList with a starting Capacity of 16:

 ArrayList *alist = new ArrayList(); 

That doesn't mean that the ArrayList is restricted to 16; it just means that the first internal array contains space for 16 elements. If the number of elements, also known as the Count, exceeds the Capacity, then the Capacity is doubled or, in other words, the internal array of the ArrayList doubles and the original array are copied to the new, expanded array.

Caution

When the size of the ArrayList exceeds its capacity, the capacity is doubled. This could cause the ArrayList to be larger than is useful. For example, if your capacity is 20,000 and you add a 20,001^st element, then the capacity becomes 40,000, which might not be what you want.

The second constructor allows you to set the initial Capacity. This allows you to optimize the loading of the ArrayList, as no doubling of the Capacity need occur if you can restrict the size of the ArrayList to less than the Capacity.

 ArrayList *alist = new ArrayList(300); 

The last constructor allows you to create an ArrayList from another specified collection. This constructor copies the elements from the originating collection and then sets the Capacity and Count to the number of elements copied.

 ArrayList *org = new ArrayList(); //...populate orgArrayList *alist = new ArrayList(org); 

It is possible to get the Count or Capacity.

 Int32 count = alist->Count; Int32 capacity = alist->Capacity; 

It is also possible to change the Capacity of an ArrayList at runtime by changing the Capacity property. If you change the Capacity to 0, the Capacity changes to the default Capacity of 16. Here is how you would code the setting of the capacity to 123:

 alist->Capacity = 123; 

Caution

Setting the Capacity to a value less than the Count of the ArrayList will result in an ArgumentOutOfRangeException being thrown.

Loading an ArrayList requires the use of member methods. All of the member methods are quite simple to use and self-explanatory. You can append or insert one or a range of elements to an ArrayList. You can also remove a specific element either by index or by specific content, or you can remove a range of elements by index.

 alist->Add(S"One"); String* morenums1[] = {S"Three", S"Six"}; alist->AddRange(dynamic_cast<Array*>(morenums1)); alist->Insert(1, S"Two"); String* morenums2[] = {S"Four", S"Five"}; alist->AddRange(dynamic_cast<Array*>(morenums2)); alist->Remove(S"Six"); alist->RemoveAt(1); alist->RemoveRange(0,4); // Index, Count 

Once the ArrayList is loaded, it is possible to access the ArrayList in nearly the same way as a simple array. The only difference is that you access an array called Item found in the ArrayList instead of accessing the array directly.

 alist->Item[1] = S"Three"; for (Int32 i = 0; i < alist->Count; i++) {     Console::Write(S"{0} ", alist->Item[i]); } 

Caution

Trying to access an ArrayList element that does not exist via the Item array will throw an ArgumentOutOfRangeException.

Note

The Item array's index starts at 0, just like any other array in C++.

The preceding code is the same as the following code, if you prefer using member methods. Why you would use this syntax escapes me, but it is available.

 alist->set_Item(1, S"Three"); for (Int32 i = 0; i < alist->Count; i++) {     Console::Write(S"{0} ", alist->get_Item(i)); } 

The ArrayList provides a few useful methods that might make your coding life a little easier. For example, it is possible to reverse the order of all the elements of the ArrayList with Reverse().

 alist->Reverse(); 

Another useful method is the Sort() method, which allows you to sort the ListArray.

 Alist->Sort(); 

It is also possible to do a binary search of a sorted ArrayList to search for a specific element. With this method, the elements index is returned. If the element is not found, search method returns a negative number that indicates the index of the next largest object in the ArrayList.

 Int32 indx = alist->BinarySearch(S"Four"); 

Similar to the binary search, you can do a linear search to check if the ArrayList contains an element. If the search finds the element, it returns true. If not, it returns false.

 Boolean fnd = alist->Contains(S"One"); 

Listing 7-2 shows the ArrayList in action and demonstrates many of the functionalities described previously.

Listing 7-2: Working with ArrayLists

  #using <mscorlib.dll> using namespace System; using namespace System::Collections; Int32 main(void) {     ArrayList *alist = new ArrayList();     alist->Add(S"One");     alist->Add(S"-");     alist->Item[1] = S"Three";     alist->Insert(1, S"Two");     String* morenums[] = {S"Four", S"Five"};     alist->AddRange(dynamic_cast<Array*>(morenums));     alist->Reverse();     Console::WriteLine(S"*** The ArrayList ***");     for (Int32 i = 0; i < alist->Count; i++)     {         Console::Write(S"{0} ", alist->Item[i]);     }     Console::WriteLine(S"\n\nCapacity is: {0}", alist->Capacity.ToString());     alist->Capacity = 10;     Console::WriteLine(S"New capacity is: {0}", alist->Capacity.ToString());     Console::WriteLine(S"Count is: {0}", alist->Count.ToString());     Alist->Sort();     Int32 indx = alist->BinarySearch(S"Four");     Console::WriteLine(S"Four found at index: {0}", indx.ToString());     Boolean fnd = alist->Contains(S"One");     Console::WriteLine(S"ArrayList contains a 'One': {0}", fnd.ToString());     Console::WriteLine(S"");     return 0; } 

Figure 7-2 shows the results of the ArrayList.exe program.

Figure 7-2: Results of ArrayList.exe

BitArray

This is a neat little collection that stores an array containing only true and false values. Unlike the ArrayList, the length of the BitArray is fixed at creation. It can, on the other hand, be set to any length (memory permitting, of course).

There are several constructors for creating a BitArray. You can divide them into three different types. The first type simply sets a predetermined array length of Booleans to either true or false.

 BitArray *barray1 = new BitArray( 8 );   // Sets to false BitArray *barray2 = new BitArray( 32, false ); BitArray *barray3 = new BitArray( 256, true ); 

The second type takes an array of Booleans, Bytes, or Int32s and moves their bit values into the BitArray, where, in the case of Bytes and Int32s, bits of 1 are true and bits of 0 are false.

 Boolean bools[] = { true, false, true, true, false }; BitArray *barray1 = new BitArray( bools ); Byte bytes[] = { 0x55,  0xAA }; BitArray *barray2 = new BitArray( bytes ); Int32 ints[] = { 0x55555555, 0xAAAAAAAA }; BitArray *barray3 = new BitArray( ints ); 

The last constructor type takes one BitArray and copies it to another BitArray.

 BitArray *barray1 = new BitArray( 8 ); BitArray *barray2 = new BitArray(barray1); 

A convenient feature of BitArrays is that they can be treated as arrays of Booleans. The array is manipulated in the same way as an ArrayList—that is, using the Item property—but this time the array items are only Booleans.

 barray1->Item[1] = false; barray1->Item[4] = true; Console::WriteLine(S"Item[0]={0}", __box(barray1->Item[0])); Console::WriteLine(S"Item[7]={0}", __box(barray1->Item[7])); 

Notice that you need to __box() the Items[] because they return a bool value and not System::Boolean, which WriteLine() needs.

The functionality associated with BitArrays is obviously related to bit manipulation or, more specifically, AND, OR, XOR, and NOT. The basic idea around these bit manipulation methods is to take the original BitArray, and then take another and apply a bitwise operation on the two BitArrays.

 BitArray *barray1 = new BitArray( 8 ); //...Manipulate bits for barray1 BitArray *barray2 = new BitArray( 8 ); //...Manipulate bits for barray2 barray2->And(barray1); barray2->Or(barray1); barray2->Xor(barray1); 

The NOT method is a little different in that it only works on its own BitArray.

 barray1->Not(); 

One last method that could come in handy is SetAll(). This method returns all the values in the BitArray back to either true or false depending on the value passed to it.

 barray2->SetAll(true); barray2->SetAll(false); 

Listing 7-3 shows the BitArray in action and demonstrates many of the functionalities described previously.

Listing 7-3: Working with BitArrays

 #using <mscorlib.dll> using namespace System; using namespace System::Collections; #include "ForEach.h"  void Print( BitArray *barray, String *desc) {     ForEach &loop = *new ForEach();     Object *val;     Console::WriteLine(desc);     Int32 i = 0;     while ( loop.foreach( &val, /*in*/ barray ))     {         Console::Write(S"{0} ", val);         i++;         if (i > 7)         {             Console::WriteLine(S"");             i = 0;         }     }     Console::WriteLine(S""); } Int32 main(void) {     BitArray *barray1 = new BitArray( 8, true );     Print(barray1, S"BitArray( 8, true );");     barray1->Item[1] = false;     barray1->Item[4] = false;     barray1->Not();     Print(barray1, S"Modified bit 1&4 then Not");     BitArray *barray2 = new BitArray( 8, true );     barray2->And(barray1);     Print(barray2, S"And with BitArray( 8, true )");     barray2->SetAll(true);     barray2->Or(barray1);     Print(barray2, S"Or with BitArray( 8, true )");     barray2->SetAll(true);     barray2->Xor(barray1);     Print(barray2, S"Xor with BitArray( 8, true )");     Console::WriteLine(S"");     Byte bytes[] = { 0x55,  0xAA };     BitArray *barray3 = new BitArray( bytes );     Print(barray3, S"BitArray(0x55,  0xAA);");     Console::WriteLine(S"Item[0]={0}", _box(barray3->Item[0]));      Console::WriteLine(S"Item[8]={0}", __box(barray3->Item[8]));     Console::WriteLine(S"");     return 0; } 

Figure 7-3 shows the results of the BitArray.exe program.

Figure 7-3: Results of BitArray.exe

Hashtable and SortedList

The Hashtable is a powerful method for storing data. The Hashtable works by storing its values in memory and then uses its key to later look up these values. What makes the Hashtable so powerful is that it doesn't search through all the keys to find a match; instead, it takes the key and analyzes it to figure out the index to the key's value. It then retrieves the value using this index.

The SortedList is a combination of a Hashtable and an Array. Depending on how you access the SortedList, it will respond like a Hashtable or an Array. For example, if you access the SortedList using the Item indexed property, it works like a Hashtable. On the other hand, if you use the GetByIndex() method, the SortedList works like an Array.

A SortedList can do everything that a Hashtable can do and more. To access the values out of a Hashtable, you use the key. With a SortedList, on the other hand, you can use the key or access the data in a sorted manner directly using an index. The cost of this added functionality is that the SortedList is slower to work with.

The reason the SortedList is slower is that both the keys and the values must be accessible in a sorted manner. This means that when data is added to or removed from the SortedList, the values may be inserted into or removed from the internal value array. This requires memory manipulation. For the Hashtable, the values do not require this manipulation.

Both the Hashtable and SortedList have numerous constructors, but in most cases, you will probably simply use the default constructor.

 Hashtable *hashtable  = new Hashtable(); SortedList *sortedlist = new SortedList(); 

On the other hand, all the other constructors provide parameters to help with the efficiency of the collection.

A major factor both the Hashtable and SortedList have in common is Capacity. If many entries are to be made into these collection types, then creating them with a sufficiently large capacity allows the entries to be inserted more efficiently than if you let them perform automatic rehashing as needed to grow the collections.

 Hashtable *hashtable  = new Hashtable(300); SortedList *sortedlist = new SortedList(300); 

A Hashtable constructor provides another parameter to further refine the collections' efficiency: the load factor. The load factor is the ratio of the number of filled buckets to the total number of buckets available. A bucket is full when it points to or contains a data element. The load factor is a value between 0.1 and 1.0. A smaller load factor means faster lookup at the cost of increased memory consumption. Conversely, a larger load factor uses memory more efficiently at the cost of longer expected time per lookup. The default load factor of 1.0 generally provides the best balance between speed and size.

 Hashtable *hashtable = new Hashtable(300, 0.75); 

You use the Add() method to load these collections. Neither the Hashtable nor the SortedList have an insert method. If you think about it, an insert really doesn't make sense, because the Hashtable analyzes the key and doesn't care where the values are located, and the SortedList is sorted whenever the Add() method is invoked.

 hashtable->Add(__box(0), S"zero"); sortedlist->Add(S"A", S"two"); 

Note

For you database programmers, as you can see in the preceding example, null is a valid key.

Unloading individual elements in the Hashtable and SortedList requires the use of the Remove() method and the specific key. The SortedList also allows elements of the collection to be removed by index value using the RemoveAt() method. It is also possible to remove all the elements of the collections using the Clear() method.

 hashtable->Remove( __box(0) ); hashtable->Clear(); sortedlist->Remove( S"A" ); sortedlist->RemoveAt( 2 ); sortedlist->Clear(); 

Now that you can put key/value pairs into a Hashtable and a SortedList, you need to be able to get them out. Both of these collection types provide a plethora of methods to do just that. One of the easiest methods is to use the Item indexed property. Be careful: This is not an array property like you have seen in the previous collection types. An indexed property, if you recall from Chapter 3, takes an Object instead of an integer value type between the square brackets, which you normally associate with an array. In this case, the object you would use is the key of the value you wish to retrieve.

 Console::WriteLine(S"key="A" value={1}", hash->Item[S"A"]); Console::WriteLine(S"key="A" value={1}", sort->Item[S"A"]); 

If you don't know the keys or you simply want all the data and, in the case of a Hashtable, don't care about the order, then you can enumerate through the collections. It's possible to enumerate by key, by value, or by both key and value at the same time. To get the enumerator, you need to use the Keys property, the Values property, or the GetEnumerator() method.

 IDictionaryEnumerator *enum1 = hash->GetEnumerator(); IDictionaryEnumerator *enum2 = sort->GetEnumerator(); IEnumerator *keys1 = hash->Keys->GetEnumerator(); IEnumerator *keys2 = sort->Keys->GetEnumerator(); IEnumerator *vals1 = hash->Values->GetEnumerator(); IEnumerator *vals2 = sort->Values->GetEnumerator(); 

Enumerating by both key and value at the same time is a little different from what you have seen so far. You need to use the IDictionaryEnumerator interface instead of IEnumerator. Also, to retrieve the key and value from the collection, you use the Key and Value properties and not the Current property (see Listing 7-4 for an example).

Listing 7-4: Working with Hashtables and SortedLists

  #using <mscorlib.dll> using namespace System; using namespace System::Collections; Int32 main(void) {     Hashtable *hash  = new Hashtable();     SortedList *sort = new SortedList();     String *keys[]  = { S"B", S"A", S"C", S"D" };     String *skeys[] = { S"A", S"B", S"C", S"D" };     String *values[] = { S"moose", S"zebra", S"frog", S"horse" };     for (Int32 i = 0; i < keys->Count; i++)     {         hash->Add(keys[i], values[i]);         sort->Add(keys[i], values[i]);     }     Console::WriteLine(S"Hashtable\tSortedList");     Console::WriteLine(S"By indexed property");     for (Int32 i = 0; i < hash->Count; i++)     {         Console::WriteLine(S"{0} {1}\t\t{2} {3}", skeys[i],             hash->Item[skeys[i]], skeys[i], sort->Item[skeys[i]]);     }     Console::WriteLine(S"\nBy index");     for (Int32 i = 0; i < sort->Count; i++)     {         Console::WriteLine(S"N/A\t\t{0} {1}", __box(i), sort->GetByIndex(i));     }     Console::WriteLine(S"\nBy enumerator");     IDictionaryEnumerator *enum1 = hash->GetEnumerator();     IDictionaryEnumerator *enum2 = sort->GetEnumerator();     while ( enum1->MoveNext() && enum2->MoveNext())     {         Console::Write(S"{0} {1}\t\t", enum1->Key, enum1->Value);         Console::WriteLine(S"{0} {1}", enum2->Key, enum2->Value);     }     Console::WriteLine(S"\nEnumerate Keys");     IEnumerator *keys1 = hash->Keys->GetEnumerator();     IEnumerator *keys2 = sort->Keys->GetEnumerator();     while ( keys1->MoveNext() && keys2->MoveNext())     {         Console::Write(S"{0}\t\t", keys1->Current);         Console::WriteLine(S"{0}", keys2->Current);     }     Console::WriteLine(S"\nEnumerate Values");     IEnumerator *vals1 = hash->Values->GetEnumerator();     IEnumerator *vals2 = sort->Values->GetEnumerator();     while ( vals1->MoveNext() && vals2->MoveNext())     {         Console::Write(S"{0}\t\t", vals1->Current);         Console::WriteLine(S"{0}", vals2->Current);     }     Console::WriteLine(S"\nContains a Key 'A' and 'Z'");     Console::WriteLine(S"{0}\t\t{1}", __box(hash->Contains(S"A")),                                       __box(sort->Contains(S"A")));     Console::WriteLine(S"{0}\t\t{1}", __box(hash->ContainsKey(S"Z")),                                       __box(sort->ContainsKey(S"Z")));     Console::WriteLine(S"\nContains a Value 'frog' and 'cow'");     Console::WriteLine(S"{0}\t\t{1}", __box(hash->ContainsValue(S"frog")),                                       __box(sort->ContainsValue(S"frog")));     Console::WriteLine(S"{0}\t\t{1}", __box(hash->ContainsValue(S"cow")),                                       __box(sort->ContainsValue(S"cow")));     Console::WriteLine(S"\n\t\t'B' key index: {0}",         __box(sort->IndexOfKey(S"B")));     Console::WriteLine(S"\t\t'frog' value index: {0}",         __box(sort->IndexOfValue(S"frog")));     return 0; } 

The code to enumerate keys and values on their own, though, is no different than any other collection.

If you are not sure, but you want a quick way to see if a Hashtable or SortedList contains a key or a value, you would use the ContainsKey() (or Contains()) method and the ContainsValue() method. Simply use the key or value you are searching for as a parameter. The methods will return true or false.

 Boolean b1 = hash->Contains(S"A"); Boolean b2 = sort->Contains(S"A"); Boolean b3 = hash->ContainsKey(S"Z"); Boolean b4 = sort->ContainsKey(S"Z"); Boolean b5 = hash->ContainsValue(S"cat"); Boolean b6 = sort->ContainsValue(S"cat"); 

Three methods specific to SortedList are based on indexes to values. Because a Hashtable doesn't have an index to its values, these methods wouldn't make sense, so they aren't included. You can get a value by index or you can get the index of a key or a value.

 Console::WriteLine(S"Index {0} contains: {1}", __box(i), sort->GetByIndex(i)); Console::WriteLine(S"Index key 'B': {0}", __box(sort->IndexOfKey(S"B"))); Console::WriteLine(S"Index val 'cat': {0}", __box(sort->IndexOfValue(S"cat"))); 

Listing 7-4 shows the Hashtable and SortedList in action and demonstrates the functionality described previously.

Figure 7-4 shows the results of the HashSortList.exe program.

Figure 7-4: Results of HashSortList.exe

Queue and Stack

The Queue and Stack collections are simple but handy. If you have ever been to an amusement park and waited to get on a ride, then you should be very familiar with a queue. Basically, the order you go in is the order you come out. A Queue is often known as a first-in-first-out (FIFO) collection. The best real-world example that I know of a stack is a plate dispenser at an all-you-can-eat buffet. Here, the last plate placed in is the first one out. A Stack is often known as a last-in-first-out (LIFO) collection.

The Queue and Stack collections don't provide a vast array of methods, as many of the other collections do. They do both contain the standard Count property, and the GetEnumerator() and Contains() methods.

Even the constructors of a Queue and a Stack are quite simple. You can create them from another collection, specifying their initial size or taking the default size.

 Queue *que1 = new Queue(); Stack *stk1 = new Stack(); Queue *que2 = new Queue(8); Stack *stk2 = new Stack(8); Queue *que3 = new Queue(stk1); Stack *stk3 = new Stack(que1); 

Both the Queue and Stack have one more method in common: the Peek() method. This method allows the program to see the next element that is going to come off the Queue or Stack but does not actually remove it.

 Console::WriteLine( que->Peek() ); Console::WriteLine( stk->Peek() ); 

Both the Queue and Stack collections have the same process of placing elements on and off. However, they use different method names that more closely resemble the type of collection they are. To place an element onto a Queue, you use the Enqueue() method, and to take an element off the Queue, you use the Dequeue() method. (I know, neither of these method names are actually English words, but hey, we're programmers, not authors. Wait a minute—I am!)

 que->Enqueue(S"First"); que->Dequeue(); 

To place an element onto a Stack, you use the Push() method, and to take it off, you use the Pop() method.

 stk->Push(S"First"); stk->Pop(); 

There are occasions when you want to Dequeue or Pop all elements of the Queue or Stack. You can do this with the single method Clear().

Listing 7-5 shows the Queue and Stack in action and demonstrates the functionality described previously.

Listing 7-5: Working with Queues and Stacks

 #using <mscorlib.dll> using namespace System; using namespace System::Collections; Int32 main(void) {     Queue *que = new Queue();     Stack *stk = new Stack();     String *entry[] = { S"First", S"Second", S"Third", S"Fourth" };     Console::WriteLine(S"Queue\t\tStack");     Console::WriteLine(S"** ON **");     for (Int32 i = 0; i < entry->Count; i++)     {         que->Enqueue(entry[i]);         stk->Push(entry[i]);         Console::WriteLine(S"{0}\t\t{1}", entry[i], entry[i]);     }     Console::WriteLine(S"\n** OFF **");     while ((que->Count > 0) && (stk->Count > 0))     {         Console::WriteLine(S"{0}\t\t{1}", que->Dequeue(), stk->Pop());     }     que->Clear();     stk->Clear();     Console::WriteLine(S"\n");     return 0; } 

Figure 7-5 shows the results of the QueueStack.exe program.

Figure 7-5: Results of QueueStack.exe