When you iterate through all the elements of a sequence, you get them "in order" - the first element comes first.

The C++ standard says associative containers "provide an ability for fast retrieval of data based on keys." Practically speaking, this means that the index doesn't have to take an integer. (If it does take an integer, the values don't have to be contiguous; this is known as a "sparse array.") The four types of associative containers are map, multimap, set, and multiset.

The associative containers can only contain elements that can be sorted - you can either make sure that operator less-than works correctly, or else you can construct a class object that knows how to sort the contained objects. When you iterate through all the elements of an associative container, you get them in that sorted order.

The library also defines container adapters such as queue, which accepts a sequence such as list or deque, and ensures that access is always at the beginning or end; stack, which does much the same thing, except that elements are popped off in reverse order from when they were pushed on; and priority_queue, which returns the lowest element first.

These standardized containers solved a lot of problems. With such a rich assortment to choose from, there is bound to be one that satisfies performance requirements for almost any need. Standard C++ library routines understand how to access data in these containers, and there is a rich variety of algorithms included in the library - algorithms for copying, sorting, even I/O.

Unfortunately, there were several problems that standardized C++ containers simply couldn't solve. For instance, the standard containers require all elements to be in memory at once. (However, they provide a framework you can use to develop your own container without this requirement - and your container will work with all Standard C++ algorithms.) Mixed data types are still a major issue.

Also, it's still a bad idea to have a reference or pointer to a contained element, except under certain very well-defined circumstances. To make it possible to iterate through all of the elements in a container, we need some other mechanism. These are called iterators.

C++ Containers Cannot Contain Mixed Types!
We hinted above that C++ containers have a problem with mixed data types, such as a hierarchy of classes. We've written some demonstration code in Listing 1 (Listings 1-4 are available on the Web at www.sys-con.com/webservices/sourcec.cfm). The programmer wanted to display employee information for Wilma, and then the customer information for Barney. But that probably isn't what he'll get. people is a vector of person, so you can't put anything into people except objects convertible to person. employee and customer are convertible to person, so the code above compiles without error or warning messages. Actually, the person subobject is copied into the vector. In other words, the integer i is copied, but not the cname or ename.

The same thing happens with arrays:

void bar() {
Person people[5];
// Copies the person subobject of Wilma
People[0] = Wilma;
// Copies the person subobject of Barney
People[1] = Barney;
}

How C++ Iterators Work
In C++, an iterator is a generalization of a pointer. In fact, any standard library algorithm that accepts an iterator will also accept pointers to an in-memory array. But iterators can do much more than simple pointers do.

The C++ standard defines five different types of iterators:

All C++ containers have methods (member functions) that return iterators that point into the container. The type of iterator returned depends on the container type.

Most algorithms take not one, but two iterators to define a "range" of data. One iterator marks the beginning of the data and another marks the position past the end. This arrangement seems strange at first, but it turns out to be rather convenient. If the iterators are bidirectional or random, you can determine the number of included elements by subtracting the two. There is no need to use special flags to define an empty range; simply pass the same iterator value for beginning and past-the-end. Also, it makes testing for the end of a range simple; with some iterator types, you cannot use less-than or greater-than to tell if the range is finished, but a special sentinel value can be used to mark the end, and when input or output is finished, this value is returned.

When manipulating a container, it's important to consider its effect on existing iterators. For instance, if you add an element to a vector and the internal capacity has to increase, iterators, except for end(), are not necessarily valid any more. This is especially inconvenient when you try to examine and manipulate a container at the same time; for instance, if you write a program that erases entries from a deque of customers, the act of deleting a customer might make you "lose your place." Many operations return new iterators; for instance, erase() might return an iterator to the element after the one that was deleted. Other operations are more problematic.

There is a lot more to C++ iterators; we've only scratched the surface in this article. Consult a good C++ textbook to find out more.

List and Explain C# Collections
Perhaps the most useful C# collection isn't considered a collection at all. C# arrays are much more powerful than C++ arrays, and they natively support many operations that require a class in C++. For instance, the Length property tells you the number of elements in the array, like the size() method in C++ containers.

C# arrays can be made multidimensional in the same way that C++ arrays are: by creating an array of arrays.

int[][] jagged = new int[3][];
jagged[0] = new int[3]; // 3 elements
jagged[1] = new int[8]; // 8 more
jagged[2] = new int[4]; // 4 more, total 15
int q = jagged[1][4];

// Allocate 20 elements.
int[] normal = new int[4,5];
int r = normal[1,4];

C# Collections Are Weakly Typed
Unlike C++ containers, C# collections can contain any type of object. You can easily mix employees, customers, and even nonperson objects in any of the C# collections without worrying about memory corruption or unintentional object splicing.

This eliminates an entire classification of hard-to-explain, hard-to-find errors. But this freedom doesn't come for free. C# collections return the contained object as a pointer to an object; that means most of your custom methods won't work correctly until you fix the pointer type.

CollectionOfFoo[j].bar(j); // Won't compile
((Foo)CollectionOfFoo[j]).bar(j); //
Okay

Comparison of C++ Container Classes with C# Collections
There are some obvious parallels between C++ containers and C# collections. Although a C++ queue<> isn't the same as a C# queue, the two are equivalent enough that they can usually serve the same purpose. Table 1 shows the comparison.

C# does support the equivalent of a C++ forward iterator, but this is rarely used. Instead, elements in C# collections are generally accessed in one of two ways: through the indexer or through a foreach statement.

To use the indexer, simply use familiar array notation to access an element. Like C++, different C# collections can use different data types for the index. For instance, a HashTable might let you look up a customer by Customer Number.

If you wish to process an entire collection or search through the elements in order, you should use the foreach statement.

How foreach Works
One feature that sometimes makes C++ programmers jealous of their VB counterparts is the for each loop.

Consider a simple for loop and array access in C++:

for(int j = 0; j < mylist.Count(); j++)
{
dosomething(mylist[j]);
}

With the introduction of the foreach loop in C#, problems like these are outdated. foreach iterates through each element in a collection. A simple foreach loop may look like:

int[] numbers = {1,2,3,4};
foreach (int j in numbers) {
dosomething(j);
}

A foreach loop allows iteration for any class implementing the IEnumerable interface. This includes all C# collections and collection classes included in namespace System.Collec- tions. You can also write your own collection class and make it work with foreach by following IEnumerable guidelines.

foreach will automatically place the fetched element into a temporary variable. Note that the temporary variable j cannot be modified, i.e., j is read-only. Attempts to modify j will produce a compile error.

foreach(int j in numbers) {
j++; //will fail to compile.
dosomething(j);
}

The easiest way to create your own collection is to implement the indexer property. A simple indexer property might look like this:

public object this[int index] {
get {
if (index > -1 && index < this.List.Count) {
return (this.List [index]);
}
}

set {
if (index > -1 && index < this.List.Count) {
this.List [index] = value;
}
}
}

Foo f = myCollection[3];

C# automatically calls your property get code with index set to 3. The set access occurs, naturally enough, when the index expression is on the left-hand-side of an assignment statement.

myCollection[3] = f;

In Listing 3, we implement an indexer and access objects using it. What happens when client code tries to use a foreach loop instead of using an indexer?

class MyClass {
static void Main(string[] args) {
MyCollection words = new MyCollection();
foreach(string str in words) {
Console.WriteLine(str);
}
}
}

Perhaps surprisingly, IEnumerable has only one method; IEnumerator GetEnumerator(). GetEnumerator() returns an instance of interface IEnumerator, which is also defined in the System.Collections namespace. The IEnumerator allows unidirectional iteration (read-only access) of items in a collection. IEnumerator publishes two methods: bool MoveNext() and void Reset(); and one property, object Current {get;}.

MoveNext(), like the name suggests, moves the enumerator to the next element in the collection. It returns true if the operation was successful, or false: if there aren't any elements left to enumerate.

Reset() sets the enumerator to the initial position, which prepares the Enumerator for iteration over the collection. Note: Initial position is not the first element in the collection; rather, it's a virtual position before the first element in the collection.

Current {get;} gets the current element in the collection. If the last call to MoveNext() returned false, or if MoveNext() hasn't even been called after Reset(), then Current {get;} throws an IndexOutOfRangeException.

To make our class support all of the same types of access that other C# collections do, all we need to do is derive our class from IEnumerable, define a support class from IEnumerator, and then implement GetEnumerator() by returning an instance of our new class. (Note: It's possible to have our class derive from both IEnumerator and IEnumerable, and GetEnumerator() would just return this. We don't recommend this, because it isn't thread-safe.)

Listing 4 shows all the changes required to implement an enumerator for use with the foreach construct. This class can be used the same way as any other C# collection class.

Conclusion
C# doesn't have templates or the STL, so it can't use C++ container classes. C# does have a rich assortment of collection classes. In C++ it's usually dangerous to mix types within one container; C# always allows this, but there are disadvantages to this approach. The C# for each statement is a convenient way to process all elements in a collection. It's surprisingly easy to write your own C# collections that work just like the library versions.