Enumerating Standard C++ Collections

CComEnumOnSTL^[3]

^[3] Technically, there's no such thing as the "STL"; there's just the standard C++ library. The ATL classes were named before the C++ standard was finalized, so they still use the old "STL" name.

The declaration of CComEnumOnSTL is similar to that of CComEnum:

template <class Base, const IID* piid, class T, class Copy, 
  class CollType, class ThreadModel = CComObjectThreadModel>
class ATL_NO_VTABLE CComEnumOnSTL :                           
    public IEnumOnSTLImpl<Base, piid, T, Copy, CollType>,   
    public CComObjectRootEx< ThreadModel > {                
public:                                                     
    typedef CComEnumOnSTL<Base, piid, T, Copy, CollType,    
        ThreadModel > _CComEnum;                            
    typedef IEnumOnSTLImpl<Base, piid, T, Copy, CollType >  
        _CComEnumBase;                                      
    BEGIN_COM_MAP(_CComEnum)                                
        COM_INTERFACE_ENTRY_IID(*piid, _CComEnumBase)       
    END_COM_MAP()                                           
};

The chief difference between CComEnumOnSTL and CComEnum is the addition of the CollType template parameter. This parameter indicates the type of collection to iterate over. The base class, IEnumOnSTLImpl, uses the collection to implement the Next, Skip, Reset, and Clone methods of the enumeration interface. The type of collection passed as the CollType must expose at least the following C++ interface:

template <typename T> class CollType {
public:
  class const_iterator; // Forward declaration
  const_iterator begin() const;
  const_iterator end() const;

  class const_iterator {
  public:
    const_iterator(const const_iterator& it); // To support
                                              // postfix ++
    const_iterator& operator=(const const_iterator& it);
    bool operator!=(const const_iterator& rhs);
    const T& operator*();
    const_iterator operator++(int); // Postfix ++
  };
};

All existing standard C++ collections adhere to these minimum requirements. If you want to make your own collection, it must adhere to this interface as well. I'll show you later how defining your own collection type is useful for enumerating data calculated on demand.

IEnumOnSTLImpl

The base class of CComEnumOnSTL, IEnumOnSTLImpl, uses the standard C++-like collection passed as the CollType parameter to implement the Next, Skip, Reset, and Clone methods. The following is the declaration of IEnumOnSTLImpl:

template <class Base, const IID* piid, class T,                  
    class Copy, class CollType>                                  
class ATL_NO_VTABLE IEnumOnSTLImpl : public Base {               
public:                                                          
    HRESULT Init(IUnknown *pUnkForRelease, CollType& collection);
                                                                     
    STDMETHOD(Next)(ULONG celt, T* rgelt, ULONG* pceltFetched);  
    STDMETHOD(Skip)(ULONG celt);                                 
    STDMETHOD(Reset)(void);                                      
    STDMETHOD(Clone)(Base** ppEnum);                             
                                                                 
// Data                                                          
    CComPtr<IUnknown> m_spUnk;                                   
    CollType* m_pcollection;                                     
    typename CollType::const_iterator m_iter;                    
};

As with CComEnumImpl, IEnumOnSTLImpl keeps an m_spUnk pointer. However, unlike CComEnumImpl, the m_spUnk pointer should never be NULL and, therefore, the pUnkForRelease parameter to Init should never be NULL. Notice that IEnumOnSTLImpl keeps no m_dwFlags member data. It has no option for copying the data from the collection. Instead, it needs to ensure that the collection holding the data outlives the enumerator. Every call to Init assumes the equivalent of the CComEnum's AtlFlagNoCopy flag. Although this is more efficient than AtlFlagCopy or the manual copying required for AtlFlagTakeOwnership, if the collection changes while it's being enumerated, the behavior is undefined. If you need ATL's C++-based enumerator to have its own copy of the data, you must wrap a copy of the data in its own COM object, a technique I show you later.

CComEnumOnSTL Use

If our prime number collection object held a collection of VARIANTs, the implementation of get__NewEnum would look like this:

STDMETHODIMP CPrimeNumbers::get__NewEnum(IUnknown** ppunkEnum) {
  *ppunkEnum = 0;

  typedef CComEnumOnSTL<IEnumVARIANT, &IID_IEnumVARIANT, VARIANT,
                        _Copy<VARIANT>, vector<VARIANT> >
          CComEnumVariantOnVector;

  CComObject<CComEnumVariantOnVector>* pe = 0;
  HRESULT hr = CComObject<CComEnumVariantOnVector>::CreateInstance(&pe);
  if (SUCCEEDED(hr)) {
    pe->AddRef();

    hr = pe->Init(this->GetUnknown(), m_rgPrimes);
    if (SUCCEEDED(hr)) {
      hr = pe->QueryInterface(ppunkEnum);
    }

    pe->Release();
  }

  return hr;
}

Of course, we'd prefer not to keep a collection of VARIANTs. Instead, we'd like to keep a collection of a type that matches our needsin this case, longs. Fortunately, unlike CComEnumImpl, IEnumOnSTLImpl allows on-demand data conversion, enabling us to keep our collection in a convenient type but still providing the data in a format that the enumerator requires.

On-Demand Data Conversion

The implementations of the Next, Skip, Reset, and Clone methods using a standard C++ collection are almost identical to those of the CComEnumImpl class. The single significant difference is a nifty loophole in the IEnumOnSTLImpl's Next method. The CComEnumImpl class ties the data type being enumerated to the data type held in the array of the enumerator. However, IEnumOnSTLImpl has no such limitation. Look at this snippet from IEnumOnSTLImpl's Next method:

template <class Base, const IID* piid, class T, class Copy,
  class CollType>                                          
STDMETHODIMP                                               
IEnumOnSTLImpl<Base, piid, T, Copy, CollType>::Next(       
  ULONG celt, T* rgelt, ULONG* pceltFetched) {             
  ...                                                      
  T* pelt = rgelt;                                         
  while (SUCCEEDED(hr) && m_iter != m_pcollection->end() &&
    nActual < celt) {                                      
    hr = Copy::copy(pelt, &*m_iter);                           
    ...                                                    
  }                                                        
  ...                                                      
    return hr;                                             
}

The template parameters allow the type of the *pelt to be different from the type of the &*m_iter. In other words, the type of data that the collection holds can be different from the type of data that the client receives in the call to Next. This means that the copy policy class must still be capable of initializing and destroying the data of the type being enumerated, but the copy operation could actually be hijacked to convert from one data type to another.

Imagine the following copy policy:

struct _CopyVariantFromLong {
    static HRESULT copy(VARIANT* p1, long* p2) {
    p1->vt = VT_I4;
    p1->lVal = *p2;
    return S_OK;
  }

  static void init(VARIANT* p) { VariantInit(p); }
  static void destroy(VARIANT* p) { VariantClear(p); }
};

If the collection held longs but the enumerator exposed VARIANTs, the _CopyVariantFromLong copy policy could be used to convert that data on demand. For example, if the prime number collection object was keeping a collection of longs, the following code would create an enumerator that could convert from long to VARIANT, as appropriate, during the client's Next call:

STDMETHODIMP CPrimeNumbers::get__NewEnum(IUnknown** ppunkEnum) {
  *ppunkEnum = 0;

  typedef CComEnumOnSTL<IEnumVARIANT, &IID_IEnumVARIANT, VARIANT,
                        _CopyVariantFromLong, vector<long> >
          CComEnumVariantOnVectorOfLongs;

  CComObject<CComEnumVariantOnVectorOfLongs>* pe = 0;
  ... // The rest is the same!
}

The only difference between this example and the previous one is the enumerator type definition. Instead of building it using a vector of VARIANTs, we build it using a vector of longs. Because the data type of the collection is different from the data type of the enumerator, we simply provide a copy policy class whose copy method converts appropriately. This is an especially useful technique for mapping between whatever is the most convenient type to hold in your collection object and VARIANTs to support the VB For-Each syntax.

Giving CComEnumOnSTL Its Own Copy

As I mentioned, unlike CComEnum, CComEnumOnSTL doesn't provide an option to copy the data the collection holds. Instead, it assumes that it will share the data with the collection. Sometimes, this can lead to undefined behavior if the collection is being modified while it is also being enumerated. All is not lost, however. It is possible to give a CComEnumOnSTL object its own copy of the data. The key is to build a COM object whose job it is to hold the original container for the life of the enumerator. Then, when Init is called, pUnkForRelease is the pointer to this container copy object. When the enumerator is done, it releases the container copy object, thus destroying the copy of the data. Unfortunately, ATL provides no such class. Fortunately, it's easy to build one. CComContainerCopy is a generic class for holding a copy of a standard C++ container. The complete implementation follows:

template <typename CollType, typename ThreadingModel =
  CComObjectThreadModel>
class CComContainerCopy :
  public CComObjectRootEx<ThreadingModel>,
  public IUnknown { // CComEnumOnSTL only needs an IUnknown*
public:
  HRESULT Copy(const CollType& coll) {
    try {
      m_coll = coll;
      return S_OK;
    }
    catch(...) {
      return E_OUTOFMEMORY;
    }
  }

BEGIN_COM_MAP(CComContainerCopy)
    COM_INTERFACE_ENTRY(IUnknown)
END_COM_MAP()

  CollType m_coll;
};

Notice that the CComContainerCopy class is parameterized by the type of collection it is to hold. This class can be used to copy any standard C++-like container. The Copy method copies the collection using assignment. Because the CComContainerCopy class derives only from IUnknown, it is ideally suited for one purpose: as the first argument to IEnumOnStlImpl's Init method. The second argument is the public m_coll member. Using the Copy method of the CComContainerCopy class mimics the use of the CComEnum class's AtlFlagCopy. The collection already has the data in the appropriate format, but the enumerator should have its own copy. Populating the m_coll member of the CComContainerCopy directly works like AtlFlagTakeOwnership. The collection doesn't already have the data in the appropriate format, but the container has converted the data for use by the enumerator. An example of CComContainerCopy using the Copy method follows:

STDMETHODIMP CPrimeNumbers::get__NewEnum(IUnknown** ppunkEnum) {
  *ppunkEnum = 0;

  typedef CComEnumOnSTL<IEnumVARIANT, &IID_IEnumVARIANT, VARIANT,
                        _Copy<VARIANT>, vector<VARIANT> >
          CComEnumVariantOnVector;

  CComObject<CComEnumVariantOnVector>* pe = NULL;
  HRESULT hr = CComObject<CComEnumVariantOnVector>::CreateInstance(&pe);
  if (SUCCEEDED(hr)) {
    pe->AddRef();

    // Create the container copy
    CComObject< CComContainerCopy< vector<VARIANT> > >*
      pCopy = NULL;
    // Use pCopy as a scoping mechanism to bind to the
    // static CreateInstance
    hr = pCopy->CreateInstance(&pCopy);
    if (SUCCEEDED(hr)) {
      pCopy->AddRef();

      // Copy the C++ container to the container copy
      hr = pCopy->Copy(m_rgPrimes);
      if (SUCCEEDED(hr)) {

         // Init the enumerator with the copy
         hr = pe->Init(pCopy->GetUnknown(), pCopy->m_coll);
         if (SUCCEEDED(hr)) {
            hr = pe->QueryInterface(ppunkEnum);
         }
      }
      pCopy->Release();
    }
    pe->Release();
  }

  return hr;
}

On-Demand Data Calculation

CComEnum requires initialization with an array of data that is already calculated. CComEnumOnSTL, on the other hand, accesses the data by calling member functions on objects that we provide. Therefore, calculating data on demand is a matter of providing implementations of the member functions that perform the calculations instead of accessing precalculated results.

For example, there's no reason the collection of prime numbers needs to precalculate all the results and store them. Instead, we need a standard C++-like container that looks like what CComEnumOnSTL needs (as I showed you before) but calculates the next prime number on demand. This container has two responsibilities. The first is to keep track of the range of values to iterate over. The second responsibility is to expose an iterator for both the beginning and one past the ending of the data. The beginning and ending iterator must be exposed via begin and end methods, and each must return a value of type const_iterator, a type nested inside the class. The PrimesContainer class lives up to both these responsibilities:

class PrimesContainer {
public:
  class const_iterator; // Forward declaration

  PrimesContainer() : m_min(0), m_max(0) {}

  // For IPrimeNumbers::CalcPrimes
  void SetRange(long min, long max)
  { m_min = min; m_max = max; }

  // For IPrimeNumbers::get_Count
  size_t size()
  { return CountPrimes(m_min, m_max); }

  // For IPrimeNumbers::get_Item
  long operator[](size_t i)
  { return NthPrime(i + 1, m_min, m_max); }

  // The rest is for CComEnumOnSTL
  const_iterator begin() const
  { return const_iterator(m_min, m_max); }

  const_iterator end() const
  { return const_iterator(); }

  class const_iterator {...};
private:
  long m_min, m_max;
};

Notice that, in addition to supporting the minimum interface required by the implementation of CComEnumOnSTL, the PrimesContainer class provides a SetRange method for managing the range of prime numbers, a size method for counting the prime numbers in the range, and an operator[] method for extracting items in a random-access fashion. These methods make the PrimesContainer class suitable for implementing the IPrimeNumbers interface.

class ATL_NO_VTABLE CPrimeNumbers :
    public CComObjectRootEx<CComSingleThreadModel>,
    public CComCoClass<CPrimeNumbers, &CLSID_PrimeNumbers>,
    public IDispatchImpl<IPrimeNumbers, &IID_IPrimeNumbers> {
public:
...
// IPrimeNumbers
public:
  STDMETHODIMP CalcPrimes(long min, long max)
  { m_rgPrimes.SetRange(min, max); return S_OK; }

  STDMETHODIMP get_Count(long* pnCount)
  { *pnCount = m_rgPrimes.size(); return S_OK; }

  STDMETHODIMP get_Item(long n, long* pnPrime) {
    if (n < 1 || n > m_rgPrimes.size() ) return E_INVALIDARG;
    *pnPrime = m_rgPrimes[n-1];
    return S_OK;
  }

  STDMETHODIMP get__NewEnum(IUnknown** ppunkEnum) {
    *ppunkEnum = NULL;

    typedef CComEnumOnSTL<IEnumVARIANT, &IID_IEnumVARIANT,
      VARIANT, _CopyVariantFromLong, PrimesContainer >
      CComEnumVariantOnPrimesContainer;

    CComObject<CComEnumVariantOnPrimesContainer>* pe = NULL;
    HRESULT hr = pe->CreateInstance(&pe);
    if (SUCCEEDED(hr)) {
      pe->AddRef();

      hr = pe->Init(this->GetUnknown(), m_rgPrimes);
      if (SUCCEEDED(hr)) {
        hr = pe->QueryInterface(ppunkEnum);
      }
      pe->Release();
    }
    return hr;
  }

  private:
    PrimesContainer m_rgPrimes;
};

In fact, this code is nearly identical to the code I've already shown you. The difference is that, instead of using a container that already has a precalculated set of values, we have one that knows how to calculate them on demand. Specifically, the iterator does the magic:

class PrimesContainer {
...
  const_iterator begin() const
  { return const_iterator(m_min, m_max); }

  const_iterator end() const
  { return iterator(); }

class const_iterator {
  public:
    const_iterator (long min = -1, long max = -1)
    : m_max(max), m_next(NthPrime(1, min, max))
    { if( m_next == -1 ) m_max = -1; } // Match end()

    bool operator!=(const const_iterator& rhs)
    { return (m_next != rhs.m_next || m_max != rhs.m_max); }

    const long& operator*()
    { return m_next; }

    const_iterator operator++(int) {
      const_iterator it(m_next, m_max);
      m_next = NthPrime(1, m_next + 1, m_max);
      if( m_next == -1 ) m_max = -1; // Match end()
      return it;
    }

  private:
    long m_next, m_max;
  };
...
};

The key to understanding the iterator is understanding how CComEnumOnSTL uses it. CComEnumOnSTL keeps a pointer to the collection, called m_pcollection, and an iterator, called m_iter, that marks the current position in the container. The m_iter data member is initialized when the enumerator is constructed or when Reset is called to the result of m_pcollection->begin(). The implementation of begin constructs an iterator that uses the range of possible prime numbers to cache the next prime number and the maximum number to check. As the container is iterated, the next prime number is calculated one ahead of the request. For every element in the container, the following sequence is performed:

m_pcollection->end() constructs an iterator that marks the end of the data. This, in turn, creates an iterator with 1 for each of m_min, m_max, and m_next. Special member data values are common for constructing an iterator that marks the end of the data.
operator!= compares the current iterator with the ending iterator.
operator* pulls out the prime number at the current location of the iterator.
The postfix operator++ calculates the next prime number. If there are no more prime numbers, m_min, m_max, and m_next are each set to 1 to indicate the end of the data. The next time through the loop, the comparison with the ending iterator succeeds and CComEnumOnSTL detects that it has reached the end of the collection.

You can see this behavior by looking at the main loop in the CComEnumOnSTLImpl::Next implementation:

template <class Base, const IID* piid, class T, class Copy, 
  class CollType>                                           
STDMETHODIMP                                                
IEnumOnSTLImpl<Base, piid, T, Copy, CollType>::Next(        
  ULONG celt, T* rgelt, ULONG* pceltFetched) {              
  ...                                                       
                                                            
  ULONG nActual = 0;                                        
  HRESULT hr = S_OK;                                        
  T* pelt = rgelt;                                          
  while (SUCCEEDED(hr) &&                                   
         m_iter != m_pcollection->end() && nActual < celt) {
    hr = Copy::copy(pelt, &*m_iter);                        
    if (FAILED(hr)) {                                       
      while (rgelt < pelt) Copy::destroy(rgelt++);          
      nActual = 0;                                          
    }                                                       
    else {                                                  
      pelt++;                                               
      m_iter++;                     
      nActual++;                                            
    }                                                       
  }                                                         
  ...                                                       
  return hr;                                                
}

If you find the occasion to calculate data on demand using a custom container and iterator pair, yours will be called in the same sequence. This gives you an opportunity to calculate data appropriately for your data setfor example, lines in a file, records in a database, bytes from a socket. Why go to all this trouble to calculate data on demand? Efficiency in both time and space. There are 9,592 prime numbers between 0 and 100,000. Precalculating and storing the primes as longs costs nearly 38 KB. Worse, the client must wait for all primes to be calculated in this range, even if it never gets around to enumerating them all. On the other hand, calculating them on demand requires the m_min and m_max members of the container and the m_next and m_max members of the current iterator. That's 16 bytes no matter how many prime numbers we'd like to calculate, and the cost of calculating them is realized only when the client requests the next chunk.^[4]

^[4] Of course, there are far more efficient ways to store and calculate prime numbers than what I have shown here. Even so, space versus time trade-offs make calculating on demand an attractive option.