How to wrap an MFC collection into an STL compliant iterator with the Boost iterator_facade

• Download sample project - 31.6 KB
• Download source code - 1.87 KB

Introduction

For this article, you will need Boost iterator headers files from the Boost website. Methods described here can be applied to any collection, and not just the MFC. But, for the purpose of this article, I will show how to implement STL compliant iterators on top of the MFC collection classes.

Background

Iterators provide uniform access methods to collections that are unrelated in their implementation details. This is true not only for the "implementation details" but also for the whole concept. For instance, it is possible to create an iterator for a directory and file structure (check out the Boost file system library located here). You can write iterators for everything that represents a multitude. For example, monitors, serial ports, TCP connections, XML nodes, HTTP tags, and so on. Furthermore, iterators make it possible to make the underlying collection be manipulated with the algorithms provided by the Standard Template Library (STL) such as for_each, search, find, find_if, find_end, find_first_of, count, count_if, equal, search_n, sort, etc., or third party libraries which require standard iterators.

MFC collections come in three major categories: Indexed arrays (CArray, CPtrArray, CObArray, CTypedPtrArray, CStringArray, CByteArray, CDWordArray, CWordArray, CUIntArray), Linked lists (CList, CPtrList, CObList, CTypedPtrList, CStringList), and Maps (CMap, CMapPtrToWord, CMapPtrToPtr, CMapStringToOb, CMapStringToPtr, CMapStringToString, CMapWordToOb, CMapWordToPtr). Traversal/access of each category is different, thus requiring specific implementations which depend upon the collection used. Consider the following example:

CArray iteration:

//***************************
// CArray
//***************************

CArray < int > array_of_ints;

// Add 10 integers to CArray
for(int i=0; i<10; i++)
  array_of_ints.Add(i);

// Print out contents of CArray
for(int i=0; i < array_of_ints.GetSize(); i++)
  cout << array_of_ints.GetAt(i);

CList iteration:

//**************************
// CList
//**************************
CList < int > list_of_ints;

// Add 10 integers to CList
for(int i=0; i<10; i++)
  list_of_ints.AddTail(i);

// Print out contents of CList
for(POSITION pos = list_of_ints.GetHeadPosition(); pos != NULL; )
         cout << list_of_ints.GetNext(pos) << endl;

CMapStringToString iteration:

//***********************
// CMapStringToString
//***********************
cout << "CMapStringToString. Note that printout" 
        " may not be in sequence" << endl;
CMapStringToString mapStr;
for(int i=0; i<10; i++)
{
  CString s;
  s.Format("%d", i);
  mapStr[s] = s;
}
// Print out CMapStringToString
CString sVal;
CString sKey;
for(POSITION pos = mapStr.GetStartPosition(); pos != NULL;) 
{ 
   mapStr.GetNextAssoc(pos, sKey, sVal);
   cout << sVal << endl;
}

As you can see, the code is quiet different for each collection category; even so, each of the code snippets tries to accomplish the very same thing - print the contents of a collection to cout.

Also, certain core classes in the MFC library are containers themselves. The CWinApp class is a container for CDocTemplate objects, the CDocTemplate class is a container for CDocument objects, and the CDocument class is a container for CView objects. The following code shows how to access CDocTemplate objects:

// Iterate through CDocTemplates
POSITION pos = AfxGetApp()->GetFirstDocTemplatePosition();
while(pos)
      CDocTemplate* pTempl = AfxGetApp()->GetNextDocTemplate(pos);

// Iterate through CDocuments
POSITION pos = pTempl->GetFirstDocPosition();
while(pos)
   CDocument* pDoc = pTempl->GetNextDoc(pos);

// Iterate throuh CDocument views
POSITION pos = pDoc->GetFirstViewPosition();
while(pos)
    CView* pView = pDoc->GetNextView(m_pos);

It is possible to generalize access to all MFC collections in a uniform manner. This process is known in "Generic Programming" as Lifting. For more information, refer to this link.

Lifting MFC collections

Instead of implementing an iterator from scratch, we will use the boost::iterator_facade class as a base class to lift MFC collections. In this case, we will have to write only the minimal amount of code required, yet still end up with an industrial strength STL compliant iterator.

To accomplish this goal, we would need a code skeleton that will provide the minimal basic functions:

• begin();
• end();
• increment();
• decrement(); Note that you will not need decrement if the collection is forward move only, like CWinApp::GetNextDocTemplate(), since there is no GetPrevDocTemplate() function.
• equal();
• dereference();

There are additional functions that may be required to be implemented. For example, code like this:

my_iterator it = my_iterator.begin() + 10;

would require implementation of the function advance(difference_type n);. Good news that the compiler will let you know that this function is missing, all you need to do is to provide one.

Our MFC skeleton code will look like this for all MFC collections:

//
// MFC Iterator skeleton 
//
template < typename _Type >
class mfc_iterator : 
   public boost::iterator_facade < mfc_iterator, _Type,
boost::forward_traversal_tag 
/* boost::bidirectional_traversal_tag */ >
{
public:
   ///////////////////////////////////////////////
   /// TODO: Write begin code logic here
   ///////////////////////////////////////////////
   mfc_iterator & begin()
   {
      //....
      return *this;
   }

   ///////////////////////////////////////////////
   /// just call default private contructor.
   /// end is a state when everything in this iterator is set to NULL
   /// or whatever variables values you choose for that
   ///////////////////////////////////////////////
   mfc_iterator end()
   {
      return mfc_iterator ();
   }

private:
   friend class boost::iterator_core_access;

   ///////////////////////////////////////////////
   /// TODO: Write end() constructor here. See end()
   ///////////////////////////////////////////////
   mfc_iterator ():m_node(0)
   {}

   ///////////////////////////////////////////////
   /// TODO: Write increment code here 
   ///////////////////////////////////////////////
   void increment() 
   {
     //....
   }

   ///////////////////////////////////////////////
   /// TODO: Write decrement code here 
   ///////////////////////////////////////////////
   void decrement() 
   {
     //....
   }

   ///////////////////////////////////////////////
   /// TODO white compare criteria here
   ///////////////////////////////////////////////
   bool equal(view_iterator const & other) const
   {
     //....
   }

   ///////////////////////////////////////////////
   /// 
   ///////////////////////////////////////////////
   _Type& dereference() const 
   { 
      return *m_node; 
   }

   _Type* m_node;
};

Believe it or not, we are pretty much done. Just kidding. All we need now is to fill in the blanks for the appropriate MFC collection type. The rest of the goodies are provided by the boost::iterator library. It includes postfix/prefix++, postfix/prefix--, and many other standard iterator items.

Let's fill in the blanks for the CArray class.

Lifted CArray

//
// CArray iterator
//
#include < boost/iterator/iterator_facade.hpp >


template < typename _Type, typename _Tcontainer = CArray<_Type>>
class mfc_carray_iterator : 
   public boost::iterator_facade < mfc_carray_iterator < _Type, 
_Tcontainer >,   _Type, 
boost::bidirectional_traversal_tag >
{
   _Type    m_node;      // element type
   _Tcontainer* m_pCont; // Pointer to underlying CArray container 
   INT_PTR  m_nIndex;    // current CArray index

public:
   ///////////////////////////////////////////////
   ///
   ///////////////////////////////////////////////
   explicit mfc_carray_iterator(_Tcontainer* pCont)
      : m_node(0)
      , m_nIndex(0)
      , m_pCont(pCont)
   {}

   ///////////////////////////////////////////////
   /// Point to first element in CArray
   ///////////////////////////////////////////////
   mfc_carray_iterator& begin()
   {
      m_nIndex = 0;
      if(m_pCont->GetSize() == 0) // safety checks
         *this = end();
      else
         m_node = m_pCont->GetAt(m_nIndex);

      return *this;
   }

   ///////////////////////////////////////////////
   /// just call private conrtuctor
   ///////////////////////////////////////////////
   mfc_carray_iterator end()
   {
      return mfc_carray_iterator();
   }

private:
   friend class boost::iterator_core_access;

   ///////////////////////////////////////////////
   /// constructs end()
   ///////////////////////////////////////////////
   mfc_carray_iterator(): 
        m_node(0)
      , m_nIndex(0)
      , m_pCont(0)
   {
   }

   ///////////////////////////////////////////////
   /// Increment CArray
   ///////////////////////////////////////////////
   void increment() 
   {
       // CArray specific increment code
      m_nIndex++;
      if(m_nIndex >= m_pCont->GetSize())// safety checks
      {
         *this = end();
         return;
      }
      m_node = m_pCont->GetAt(m_nIndex);
   }

   ///////////////////////////////////////////////
   /// Decrement CArray
   ///////////////////////////////////////////////
   void decrement()
   {
      // CArray specific decrement code
      m_nIndex--;
      if(m_nIndex >= m_pCont->GetSize()) // safety checks
         return;

      m_node = m_pCont->GetAt(m_nIndex);
   }

   ///////////////////////////////////////////////
   /// 
   ///////////////////////////////////////////////
   bool equal(mfc_carray_iterator const& other) const
   {
      return m_pCont == other.m_pCont && 
                     m_node == other.m_node && 
                     m_nIndex == other.m_nIndex;
   }

   _Type& dereference() const 
   { 
      return (_Type&) m_node; 
   }    
};

We can now test our CArray iterator with the following code snippet:

#include < boost/iterator/iterator_facade.hpp >
#include < algorithm >

// Use functor to populate out CArray
struct F_Generate
{
   int m_nValue;
   CArray < int > * m_pArray;
   F_Generate(CArray < int > * pArray): m_nValue(0), m_pArray(pArray){}
   int operator()()
   {
      m_pArray->GetAt(m_nValue) = m_nValue++;
      return m_nValue;
   }
};

void print_int(int i)
{
   cout << i << endl;
}

int main(int argc, TCHAR* argv[], TCHAR* envp[])
{
   CArray < int > array_of_ints;

   // Add 10 integers to CArray
   //for(int i=0; i<10; i++)
   //   array_of_ints.Add(i);
  
  // We going to generalize array population
  array_of_ints.SetSize(10);

   mfc_carray_iterator < int > it(&array_of_ints);
   // generate does the same job as commented out for loop.
   // Note how structure of the program becomes generic 
   //ripe for further lifting
   std::generate(it.begin(), it.end(), F_Generate(&array_of_ints));
   for_each(it.begin(), it.end(), print_int);

   return 0;
}

Lifted CList

//
// CList iterator
//
#include < boost/iterator/iterator_facade.hpp >

template < typename _Type, typename _Tcontainer = CList<_Type> >
class mfc_clist_iterator : 
   public boost::iterator_facade < 
mfc_clist_iterator < _Type, _Tcontainer >, 
_Type, 
boost::bidirectional_traversal_tag >
{
   _Type    m_node;      // element type
   _Tcontainer* m_pCont; // Pointer to underlying CList container 
   POSITION  m_pos;    // current CList position

public:
   ///////////////////////////////////////////////
   ///
   ///////////////////////////////////////////////
   explicit mfc_clist_iterator(_Tcontainer* pCont)
      : m_node(0)
      , m_pos(0)
      , m_pCont(pCont)
   {}

   ///////////////////////////////////////////////
   /// Point to first element in CList
   ///////////////////////////////////////////////
   mfc_clist_iterator& begin()
   {
      m_pos = m_pCont->GetHeadPosition();

      if(m_pos == 0) // safety checks
         *this = end();
      else
         m_node = m_pCont->GetNext(m_pos);
      return *this;
   }

   ///////////////////////////////////////////////
   /// just call private constructor
   ///////////////////////////////////////////////
   mfc_clist_iterator end()
   {
      return mfc_clist_iterator();
   }

private:
   friend class boost::iterator_core_access;

   ///////////////////////////////////////////////
   /// constructs end()
   ///////////////////////////////////////////////
   mfc_clist_iterator(): 
   m_node(0)
      , m_pos(0)
      , m_pCont(0)
   {
   }

   ///////////////////////////////////////////////
   /// Increment CList
   ///////////////////////////////////////////////
   void increment() 
   {
      if(m_pos == NULL)// safety checks
      {
         *this = end();
         return;
      }

      m_node = m_pCont->GetNext(m_pos);
   }

   ///////////////////////////////////////////////
   /// Decrement CList
   ///////////////////////////////////////////////
   void decrement()
   {
      if(m_pos == NULL)// safety checks
      {
         *this = end();
         return;
      }

      m_node = m_pCont->GetPrev(m_pos);
   }

   ///////////////////////////////////////////////
   /// 
   ///////////////////////////////////////////////
   bool equal(mfc_clist_iterator const & other) const
   {
      return m_pCont == other.m_pCont && m_node == 
          other.m_node && m_pos == other.m_pos;
   }

   _Type& dereference() const 
   { 
      return (_Type&)m_node; 
   }

};

Test application for CList:

#include < boost/iterator/iterator_facade.hpp >
#include < algorithm >

void print_int(int i)
{
   cout << i << endl;
}

int main(int argc, TCHAR* argv[], TCHAR* envp[])
{
   CList < int > list_of_ints;

   // Add 10 integers to CList
   for(int i=0; i<10; i++)
      list_of_ints.AddTail(i);

  cout << "CList" << endl;

   mfc_clist_iterator < int > it(&list_of_ints);
   for_each(it.begin(), it.end(), print_int);
   return 0;
}

Lifting the CView iterator

You would ultimately follow the same pattern for lifting other types of collections:

#include < boost/iterator/iterator_facade.hpp >

// CView 
class view_iterator : 
   public boost::iterator_facade< view_iterator, CView, 
          boost::forward_traversal_tag >
{
CView* m_node;
   POSITION m_pos;
   CDocument* m_pDoc;

public:
   ///////////////////////////////////////////////
   ///
   ///////////////////////////////////////////////
   explicit view_iterator(CDocument* pDoc)
      : m_node(0)
      , m_pos(0)
      , m_pDoc(pDoc)
   {}

   ///////////////////////////////////////////////
   ///
   ///////////////////////////////////////////////
   view_iterator& begin()
   {
      m_pos = m_pDoc->GetFirstViewPosition();
      m_node = m_pDoc->GetNextView(m_pos);
      return *this;
   }

   ///////////////////////////////////////////////
   ///
   ///////////////////////////////////////////////
   view_iterator end()
   {
      return view_iterator();
   }

private:
   friend class boost::iterator_core_access;

   ///////////////////////////////////////////////
   /// for end()
   ///////////////////////////////////////////////
   view_iterator()
      : m_node(0)
      , m_pos(0)
      , m_pDoc(0)
   {}

   ///////////////////////////////////////////////
   ///
   ///////////////////////////////////////////////
   void increment() 
   {
      if(m_node == 0)
      {
         m_pos = m_pDoc->GetFirstViewPosition();
         m_node = m_pDoc->GetNextView(m_pos);
      }
      else
         m_node = m_pDoc->GetNextView(m_pos);
   }

   ///////////////////////////////////////////////
   ///
   ///////////////////////////////////////////////
   bool equal(view_iterator const& other) const
   {
      return this->m_node == other.m_node;
   }

   ///////////////////////////////////////////////
   ///
   ///////////////////////////////////////////////
   CView& dereference() const 
   { 
      return *m_node; 
   }

};

In a Document View application, you can test this code like this:

// In CDocument derived class

view_iterator it = view_iterator(this).begin();
while(*it)
{
  // Repaint the view
  it->SendMessage(WM_PAINT);
  it++;
}

By the same token, with the CDocTemplate iterator given below:

doc_templ_iterator it = doc_templ_iterator(AfxGetApp()).begin();
// Autosave feature
while(*it)
{
  it->SaveAllModified();//Save all documents that were modified.
  it++;
}

Lifting the CDocTemplate iterator

// CDocTemplate
class doc_templ_iterator : 
   public boost::iterator_facade< doc_templ_iterator, 
          CDocTemplate, boost::forward_traversal_tag >
{
   CDocTemplate* m_node;
   POSITION m_pos;
   CWinApp* m_pApp;

public:
   ///////////////////////////////////////////////
   ///
   ///////////////////////////////////////////////
   explicit doc_templ_iterator(CWinApp* pApp)
      : m_node(0)
      , m_pos(0)
      , m_pApp(pApp)
   {}

   ///////////////////////////////////////////////
   ///
   ///////////////////////////////////////////////
   doc_templ_iterator& begin()
   {
      m_pos = m_pApp->GetFirstDocTemplatePosition();
      m_node = m_pApp->GetNextDocTemplate(m_pos);
      return *this;
   }

   ///////////////////////////////////////////////
   ///
   ///////////////////////////////////////////////
   doc_templ_iterator end()
   {
      return doc_templ_iterator();
   }

   ///////////////////////////////////////////////
   ///
   ///////////////////////////////////////////////
   CDocTemplate* operator*()
   {
      return m_node;
   }
   CDocTemplate* operator->()
   {
      return m_node;
   }

private:
   friend class boost::iterator_core_access;

   ///////////////////////////////////////////////
   /// for end()
   ///////////////////////////////////////////////
   doc_templ_iterator()
      : m_node(0)
      , m_pos(0)
      , m_pApp(0)
   {}

   ///////////////////////////////////////////////
   ///
   ///////////////////////////////////////////////
   void increment() 
   {
      if(m_pos == 0)
      {
         *this = end();
         return;
      }
      else
         m_node = m_pApp->GetNextDocTemplate(m_pos);
   }

   ///////////////////////////////////////////////
   ///
   ///////////////////////////////////////////////
   bool equal(doc_templ_iterator const& other) const
   {
      return this->m_node == other.m_node;
   }

   ///////////////////////////////////////////////
   ///
   ///////////////////////////////////////////////
   CDocTemplate& dereference() const 
   { 
      return *m_node; 
   }

};

Benefits of generalization

I will highlight one of the many benefits of lifting MFC collections into STL iterators. Consider a CArray and CList of dynamically allocated pointers.

// Allocate CArray of pointers
CArray < CMyClass* > array_of_my_class_ptrs;
for(int i=0; i<10; i++)
   array_of_my_class_ptrs.Add(new CMyClass);

// Allocate CList of pointers
CList < CMyOtherObj* > list_of_stuff;
for(int i=0; i<10; i++)
   list_of_stuff.AddTail(new CMyOtherObj);

When you are done with these objects, at the end, you'd need to manually traverse each container to delete each pointer with the delete opeartor. Note that the semantics of the iteration for both CArray and CList is different. So, you need two different implementations for the deletion logic.

// implementation of delete CArray pointers
for(int i=0; i< array_of_my_class_ptrs.GetSize(); i++)
   delete array_of_my_class_ptrs.GetAt(i);

// implementation of delete for CList
while(list_of_stuff.GetCount() > 0)
   delete  list_of_stuff.RemoveHead();

With the lifted CArray and CList iterators, you can write a single point uniform deletion functor (taken from item #7, Effective STL, by Scott Meyers):

struct DeleteObject
{
  template < typename T >
  void operator () (const T* ptr)
  {
    delete ptr;
    ptr = 0;
  }
};

Now, you can do the deletion in this manner:

mfc_carray_iterator itA(&array_of_my_class_ptrs);
mfc_clist_iterator  itL(&list_of_stuff);
// Delete all pointers in both CArray and CList
for_each(itA.begin(), itA.end(), DeleteObject());
for_each(itL.begin(), itL.end(), DeleteObject());

Points of interest

If you noticed, all iterators presented here can be lifted significantly further. I will leave this exercise to the reader.

From this point forward, MFC collection iterators can be used in a very generic uniform fashion. Plus, in an abundance of algorithms, both custom made or STL's, such as sorting or searching, etc. We also implemented safety checks if you use the ++ or -- operators. Once the end of the sequence has been reached, the iterator is reset to the end() state so it evaluates to TRUE when tested against the end() function.

Credits

• Many thanks to the Boost website and the authors of the boost::iterator library.
• Iterator library link
• Generic programming link
• Effective STL, by Scott Meyers

Bugs

I never tested this code in MS VC 6.0, but chances are that on Visual Studio 6.0 SP6, you will have problems compiling this code. Compiler in that version incorrectly parses code:

template < typename _T, typename _Tcont=CArray<_T>>

It assumes that the bold chunk of code is a shift operator (doh!). You'd need to put spaces in there, like this:

template < typename _T, typename _Tcont=CArray<_T> >

History

• October 20, 2008. Initial article.