Walking the CList collection

The CList collection class already has an iterator class, and it already attaches itself to that iterator. You got a sanitized preview of the Attach method on page 175. Here’s the real code:

‘ Attach a list to iterator
Sub Attach(connectA As CList, Optional fEnumerate As Boolean = False)
    ‘ Initialize position in collection
    Set connect = connectA
    If fEnumerate Then
        ‘ Connect walker to CEnumVariant so it can call methods
        Set vars = New CEnumVariant
        vars.Attach Me
    End If
End Sub

If you create the iterator object yourself (as we did in earlier examples), it doesn’t need a connection with CEnumVariant and any implementation of the IVariantWalker interface should be ignored. The fEnumerate flag should be true only when Attach is called by the NewEnum method of CList.

But we do want CList to work with For Each, and since the iteration mechanism is already in place, it’s extremely easy for the IVariantWalker members to take advantage of the existing public More method through delegation. You might remember that the original CListWalker class had a More method that returned True or False to indicate whether there were more items. It returned the actual data through a separate Item property. Here’s how IVariantWalker_More takes advantage of those methods.

Private Function IVariantWalker_More(v As Variant) As Boolean
    ‘ Move to next element
    IVariantWalker_More = More
    If IVariantWalker_More = False Then Exit Function
    ‘ Return element through reference
    If IsObject(lnkCur.Item) Then
        Set v = lnkCur.Item
    Else
        v = lnkCur.Item
    End If
End Function

The implementation of Skip does something even more interesting. It delegates its work to IVariantWalker_More in a loop:

Private Sub IVariantWalker_Skip(c As Long)
    ‘ Skip a given number of elements
    Dim i As Long, v As Variant
    For i = 1 To c
        If IVariantWalker_More(v) = False Then Exit For
    Next
End Sub

Problem: Compare iterating through various data structures, and for each data structure, compare iterating with For Each to iterating with For and an index variable.

Problem	P-Code	Native Code
For I on Variant Integer array	0.0005 sec	0.0002 sec
For Each on Variant Integer array	0.0009 sec	0.0006 sec
For I on Integer array	0.0004 sec	0.0001 sec
For Each on Integer array	0.0008 sec	0.0004 sec
For I on Integer collection	0.0125 sec	0.0082 sec
For Each on Integer collection	0.0013 sec	0.0011 sec
For I on Variant Integer vector	0.0038 sec	0.0033 sec
For Each on Variant Integer vector	0.0231 sec	0.0228 sec
For I on Integer vector	0.0017 sec	0.0013 sec
For Each on Integer vector	0.0183 sec	0.0196 sec
For I on Integer list	0.9113 sec	0.8657 sec
For Each on Integer list	0.0184 sec	0.0195 sec
For I on Variant object array	0.0570 sec	0.0567 sec
For Each on Variant object array	0.0615 sec	0.0607 sec
For I on object array	0.0008 sec	0.0004 sec
For Each on object array	0.0597 sec	0.0625 sec
For I on object collection	0.0834 sec	0.0862 sec

You might want to keep this technique in mind. Usually, you can optimize the Skip method by changing the state variable, but in some kinds of collections (such as lists), the only way to get ahead is to keep iterating.

The original list iterator didn’t have the equivalent of a Reset method (you could restart with the Attach method), so IVariantWalker_Reset has to be implemented from scratch by resetting the Head friend property.

Private Sub IVariantWalker_Reset()
    ‘ Move to first element
    If connect.Count Then Set lnkCur = connect.Head
End Sub

Problem	P-Code	Native Code
For Each on object collection	0.0035 sec	0.0036 sec
For I on object vector	0.0750 sec	0.0745 sec
For Each on object vector	0.0258 sec	0.0241 sec
For I on object list	0.9805 sec	0.9887 sec
For Each on object list	0.0234 sec	0.2240 sec

Conclusion: The results speak for themselves, but let me highlight a few points. I provide two array tests. One is a Variant array, because it’s only fair to compare Variant arrays to Variant collections, vectors, and lists. But if you’re doing real work with integers, you don’t care what’s fair—you just want speed. The difference between using Variant arrays and type-specific arrays is a minor one for Integers but a major one for objects.

Nothing beats an array for raw speed, but vectors do get decent performance. You can’t necessarily see it from the data here, but if you actually run the TimeIt application with different numbers in the Iterations field (iterations here is actually the number of items in the data structure), you’ll see that collections and lists get much slower as you add more data, while arrays and vectors slow at a constant rate. Lists are shown for comparison, but they come in last in every category and you probably don’t want to use them for this kind of operation.

When comparing For Each to For with an index variable, arrays and vectors are far faster with an index variable. Collections and lists are faster with For Each; if you study the implementation of the CVector and CList classes, you can get a good idea why. The internal iterators for Collections and arrays are probably implemented much like the ones for CList and CVector, respectively.

The iterator for the CList class is crucial to its performance. You don’t even want to think about iterating with indexes, because they depend on the iterator anyway. It might look from the outside as if you’re walking through one item at a time, but you’re actually using the internal iterator to walk all the way from the start of the list to the current index. The Performance sidebar above shows the heavy toll this takes.