ATL Collections

Using standard C++ puts one burden firmly on the shoulders of the developer: exception handing. Many calls into collections and algorithms can cause exceptions that must be caught before they leave the method boundary.^[5] And because C++ exception handling requires the C runtime (CRT), the CRT libraries must be linked with any ATL project that uses the standard C++ library. Although ATL servers do link with the CRT by default, it remains the case that some ATL servers are built without the CRT; therefore, an alternative for the standard library is needed. ATL includes three classes that provide basic array, list, and map functionality that are not unlike the C++ vector, list, and map classes. In the spirit of ATL, none of these classes throws exceptions or requires the CRT. Arguably more compelling than freedom from the CRT, these classes are specialized to yield additional classes tailored for use with COM by automatically managing collections of types such as interfaces.

^[5] Letting a C++ or Win32 structured exception escape a COM method is illegal. All such exceptions must be caught and turned into appropriate hrESULTs. For more information on this topic, see Effective COM (Addison-Wesley, 1998), by Don Box, Keith Brown, Tim Ewald, and Chris Sells.

CAtlArray

This class is a dynamically sized array that grows on demand. It is a template class, so it can hold any kind of data. Its declaration is as follows:

template< typename E, class ETraits = CElementTraits< E > >
class CatlArray {                                          
                                                           
public:                                                    
    CAtlArray() ;                                          
    ~CAtlArray() ;                                         
                                                           
    size_t GetCount() const ;                              
    bool IsEmpty() const ;                                 
    bool SetCount( size_t nNewSize, int nGrowBy = -1 );    
                                                           
    void FreeExtra() ;                                     
    void RemoveAll() ;                                     
                                                               
    const E& GetAt( size_t iElement ) const;               
    E& GetAt( size_t iElement );                           
                                                               
    const E* GetData() const ;                             
    E* GetData() ;                                         
                                                           
    void SetAt( size_t iElement, INARGTYPE element );      
    void SetAtGrow( size_t iElement, INARGTYPE element );  
                                                            
    size_t Add();                                          
    size_t Add( INARGTYPE element );                       
    size_t Append( const CAtlArray< E, ETraits >& aSrc );  
                                                                      
    void Copy( const CAtlArray< E, ETraits >& aSrc );      
                                                                     
    const E& operator[]( size_t iElement ) const;          
    E& operator[]( size_t iElement );                      
                                                                
    void InsertAt( size_t iElement, INARGTYPE element,     
        size_t nCount = 1 );                               
    void InsertArrayAt( size_t iStart,                     
        const CAtlArray< E, ETraits >* paNew );            
    void RemoveAt( size_t iElement, size_t nCount = 1 );   
                                                           
#ifdef _DEBUG                                              
    void AssertValid() const;                              
#endif // _DEBUG                                           
                                                           
// Implementation                                          
private:                                                   
    E* m_pData;                                            
    size_t m_nSize;                                        
    size_t m_nMaxSize;                                     
    int m_nGrowBy;                                         
                                                            
    // Private to prevent use                              
    CAtlArray( const CAtlArray& ) ;                        
    CAtlArray& operator=( const CAtlArray& ) ;             
};

The class members manage the memory associated with the m_pData member, a dynamically sized array of type E. The second template parameter (Etraits) to the CAtlArray class is the key to understanding how ATL supports collections of different element types. This class provides methods for copying elements, comparing elements, moving elements, and computing element hash values for building hash tables. By default, CAtlArray uses a template class called CElementTraits that supplies implementations of these element policies that are appropriate for simple data types. Storing more complex objects typically requires "overriding" these default policies by passing in an alternate class for the ETRaits parameter. Indeed, you'll see in a moment that ATL does precisely this to provide more specialized collection classes for dealing with commonly used types such as interfaces.

Here are the five static member functions and two typedefs ATL expects you to provide for the class specified as the Etraits template parameter. In these method signatures, T represents the element type.

[View full width]

typedef const T& INARGTYPE; // type to be used for           
                            // adding elements               
typedef T& OUTARGTYPE;      // type to be used for           
                            // retrieving elements           
                                                             
static bool CompareElements( const T& element1,              
  const T& element2 );                                       
                                                                 
static int CompareElementsOrdered( const T& element1,        
  const T& element2 );                                       
                                                                 
static ULONG Hash( const T& element ) ;                      
                                                                                          
      
static void CopyElements( T* pDest, const T* pSrc,           
  size_t nElements );                                        
                                                             
static void RelocateElements( T* pDest, T* pSrc,             
  size_t nElements );

The default CElementTraits class that AtlArray uses ultimately resolves to CDefaultElementTraits when primitive types such as int and bool are specified as the array element type. This class supplies the required static member functions through three base classes, one providing the comparison policy, one encapsulating the hashing algorithm, and another supplying the correct element copy semantics.

template< typename T >               
class CDefaultElementTraits :        
    public CElementTraitsBase< T >,  
    public CDefaultHashTraits< T >,  
    public CDefaultCompareTraits< T >
{... };

ATL provides template specializations of the CElementTraits class that automatically handle the unique comparison and copying semantics of the CComBSTR and CComVariant smart types. Additionally, a different hashing algorithm is used for these types to produce a better statistical distribution of hash keys than would result with the trivial algorithm used for primitive types.

For dealing with arrays of interfaces, ATL provides CInterfaceArray. Its definition simply derives from CAtlArray and uses CComQIPtr as the array element type and a special interface-savvy element traits class.

template< class I, const IID* piid = &__uuidof( I ) >
class CInterfaceArray :                              
  public CAtlArray< ATL::CComQIPtr< I, piid >,       
    CComQIPtrElementTraits< I, piid > >              
{... }

A special array type called CAutoPtrArray is also available for dealing with arrays of smart pointers. It is also defined in terms of CAtlArray.

template< typename E >                 
class CAutoPtrArray :                  
  public CAtlArray< ATL::CAutoPtr< E >,
    CAutoPtrElementTraits< E > >       
{... }

Here's how you might use CInterfaceArray in code:

void GetPrimes(CInterfaceArray<IPrimeCalc>* prgCalc) {
  // Declare array of IPrimeCalc interface pointers
  CInterfaceArray<IPrimeCalc> rgCalc;

  // Populate array
  for (int i = 0; i < 50; i++) {
    IPrimeCalc* pCalc = NULL;
    ::CoCreateInstance(CLSID_CPrimeCalc, NULL, CLSCTX_ALL,
      __uuidof(pCalc), (void**)&pCalc);

    rgCalc[i] = pCalc; // ERROR: operator[] doesn't grow array

    rgCalc.Add(pCalc); // grows array, inserts, calls AddRef
    pCalc->Release();
  }

  *prgCalc = rgCalc; // ERROR: operator= marked private
                     // to prevent use

  prgCalc->InsertArrayAt(0, &rgCalc); // OK, prgCalc has
                                      // 50 AddRef'd itfs
} // CInterfaceArray destructor calls
  // Release on all elements in rgCalc

Unfortunately, CAtlArray isn't very useful for implementing an enumeration interface, even though it could be easily used with CComEnum, because you're not likely to want to hold data in the same type as is being enumerated. Because CComEnum doesn't support conversion on demand as CComEnumOnSTL does, you must manually convert your CAtlArray data into an array of data appropriate for enumerating.

CAtlList

The CAtlList collection class provides a convenient way to store objects in an ordered list. Compared to CAtlArray, inserting elements into CAtlList is quite fast because it occurs in constant time. However, you can't access the elements in a list by index as you can with an array. Like its array-based cousin, CAtlList is defined in terms of an element traits class that encapsulates the details of dealing with individual items in the list.

template< typename E, class ETraits = CElementTraits< E > >  
class CAtlList {                                             
public:                                                      
    typedef typename ETraits::INARGTYPE INARGTYPE;           
                                                             
private:                                                     
    class CNode : ... {                                      
    ...                                                      
    public:                                                  
        CNode* m_pNext;                                      
        CNode* m_pPrev;                                      
        E m_element;                                         
    };                                                       
                                                             
public:                                                      
    CAtlList( UINT nBlockSize = 10 ) ;                       
    ~CAtlList() ;                                            
                                                             
    size_t GetCount() const ;                                
    bool IsEmpty() const ;                                   
                                                             
    E& GetHead() ;                                           
    const E& GetHead() const ;                               
    E& GetTail() ;                                           
    const E& GetTail() const ;                               

    E RemoveHead();                                          
    E RemoveTail();                                          
    void RemoveHeadNoReturn() ;                              
    void RemoveTailNoReturn() ;                              
                                                             
    POSITION AddHead();                                      
    POSITION AddHead( INARGTYPE element );                   
    void AddHeadList( const CAtlList< E, ETraits >* plNew ); 
                                                                   
    POSITION AddTail();                                      
    POSITION AddTail( INARGTYPE element );                   
    void AddTailList( const CAtlList< E, ETraits >* plNew ); 
                                                                   
    void RemoveAll() ;                                       
                                                             
    POSITION GetHeadPosition() const ;                       
    POSITION GetTailPosition() const ;                       
    E& GetNext( POSITION& pos ) ;                            
    const E& GetNext( POSITION& pos ) const ;                
    E& GetPrev( POSITION& pos ) ;                            
    const E& GetPrev( POSITION& pos ) const ;                
                                                                     
    E& GetAt( POSITION pos ) ;                               
    const E& GetAt( POSITION pos ) const ;                   
    void SetAt( POSITION pos, INARGTYPE element );           
    void RemoveAt( POSITION pos ) ;                          
                                                             
    POSITION InsertBefore( POSITION pos, INARGTYPE element );
    POSITION InsertAfter( POSITION pos, INARGTYPE element ); 
                                                             
    POSITION Find( INARGTYPE element,                        
        POSITION posStartAfter = NULL ) const ;              
    POSITION FindIndex( size_t iElement ) const ;            
                                                             
    void MoveToHead( POSITION pos ) ;                        
    void MoveToTail( POSITION pos ) ;                        
    void SwapElements( POSITION pos1, POSITION pos2 ) ;      
                                                             
// Implementation                                            
private:                                                     
    CNode* m_pHead;                                          
    CNode* m_pTail;                                          
    CNode* m_pFree;                                          
    ...                                                      
};

This class manages a doubly linked list of CNode objects, each of which simply hold pointers to the data of the specified type (E), as well as pointers to the previous and next nodes in the list. Two list classes are also provided for dealing with smart pointers and interface pointers: CAutoPtrList and CInterfaceList. As with their array-based counterparts, these classes simply use CAtlList as their base class and specify type-specific element trait classes.

template< class I, const IID* piid = &__uuidof( I ) >
class CInterfaceList :                               
  public CAtlList< ATL::CComQIPtr< I, piid >,        
    CComQIPtrElementTraits< I, piid > >              
{... }                                               
                                                     
template< typename E >                               
class CAutoPtrList :                                 
  public CAtlList< ATL::CAutoPtr< E >,               
    CAutoPtrElementTraits< E > >                     
{... }

CAtlMap

If you want the functionality of the C++ map class, ATL provides CAtlMap:

template< typename K, typename V,                             
  class KTraits = CElementTraits< K >,                        
  class VTraits = CElementTraits< V > >                       
class CAtlMap {                                               
public:                                                       
  typedef typename KTraits::INARGTYPE KINARGTYPE;             
  typedef typename KTraits::OUTARGTYPE KOUTARGTYPE;           
  typedef typename VTraits::INARGTYPE VINARGTYPE;             
  typedef typename VTraits::OUTARGTYPE VOUTARGTYPE;           
                                                              
  class CPair : ... {                                         
  public:                                                     
    const K m_key;                                            
    V m_value;                                                
  };                                                          
                                                              
private:                                                      
  class CNode : public CPair { ... }                          
  ...                                                         
  size_t GetCount() const ;                                   
  bool IsEmpty() const ;                                      
                                                              
  bool Lookup( KINARGTYPE key, VOUTARGTYPE value ) const;     
  const CPair* Lookup( KINARGTYPE key ) const ;               
  CPair* Lookup( KINARGTYPE key ) ;                           
  V& operator[]( KINARGTYPE key ) ;                           
                                                               
  POSITION SetAt( KINARGTYPE key, VINARGTYPE value );         
  void SetValueAt( POSITION pos, VINARGTYPE value );          
                                                              
  bool RemoveKey( KINARGTYPE key ) ;                          
  void RemoveAll() ;                                          
  void RemoveAtPos( POSITION pos ) ;                          
                                                              
  POSITION GetStartPosition() const ;                         
  void GetNextAssoc( POSITION& pos, KOUTARGTYPE key,          
    VOUTARGTYPE value ) const;                                
  const CPair* GetNext( POSITION& pos ) const ;               
  CPair* GetNext( POSITION& pos ) ;                           
  const K& GetNextKey( POSITION& pos ) const ;                
  const V& GetNextValue( POSITION& pos ) const ;              
  V& GetNextValue( POSITION& pos ) ;                          
  void GetAt( POSITION pos, KOUTARGTYPE key,                  
    VOUTARGTYPE value ) const;                                
  CPair* GetAt( POSITION pos ) ;                              
  const CPair* GetAt( POSITION pos ) const ;                  
  const K& GetKeyAt( POSITION pos ) const ;                   
  const V& GetValueAt( POSITION pos ) const ;                 
  V& GetValueAt( POSITION pos ) ;                             
                                                                  
  UINT GetHashTableSize() const ;                             
  bool InitHashTable( UINT nBins, bool bAllocNow = true );    
  void EnableAutoRehash() ;                                   
  void DisableAutoRehash() ;                                  
  void Rehash( UINT nBins = 0 );                              
  void SetOptimalLoad( float fOptimalLoad, float fLoThreshold,
    float fHiThreshold, bool bRehashNow = false );            
                                                              
// Implementation                                             
private:                                                      
  CNode** m_ppBins;                                           
  CNode* m_pFree;                                             
  ...                                                         
};

CAtlMap maintains a list of nodes, each of which holds a key and a value. In this case, element trait classes must be provided for both the key type and the value type. The key is used to generate a hash for locating nodes in the list. CAtlMap would be useful for implementing collection item lookup by name instead of by index.

Be aware that CAtlMap does not have the same performance guarantees as the C++ std::map<> container. std::map<> uses a balanced binary tree that guarantees O(lg N) performance for inserts or lookups. CAtlMap, on the other hand, uses a hash table. Under good conditions, the hash table can give O(1) lookup performance, but a bad hash function can reduce the hash table to linear searches.