Virtualizing List Views to Handle Large Amounts of Data

The technique I use is made possible with the LVS_OWNERDATA style. Basically what that style does, is tell the CListCtrl that we are in charge of all memory handling. You never call CListCtrl::InsertItem() when this style is set. Everytime the control needs to paint or display text, Windows will ask you for the text located at item, subitem (in the form of a LVN_GETDISPINFO message). It is then your job to supply this information.

An example of this:

BEGIN_MESSAGE_MAP(CMyListCtrl, CListCtrl)
 //{{AFX_MSG_MAP(CMyListCtrl)
 ON_NOTIFY_REFLECT(LVN_GETDISPINFO, OnGetdispinfo)
 //}}AFX_MSG_MAP
END_MESSAGE_MAP()

//Windows is asking for the text to display, 
//at item(iItemIndex), subitem(pItem->iSubItem)
void CMyListCtrl::OnGetdispinfo(NMHDR* pNMHDR, LRESULT* pResult)
{
 LV_DISPINFO* pDispInfo = (LV_DISPINFO*)pNMHDR;
 LV_ITEM* pItem= &(pDispInfo)->item;
 int iItemIndex= pItem->iItem;

 if(pItem->mask & LVIF_TEXT)
 {
  if(pItem->iSubItem == 0) //first column
   lstrcpyn(pItem->pszText, 
            "This is the first columns data",
            pItem->cchTextMax);
  else
  if(pItem->iSubItem == 1) //second column
   lstrcpyn(pItem->pszText, 
            "Second column data", 
            pItem->cchTextMax);
 }
 *pResult = 0;
}

In the project I described earlier, I have a single linked list, with hundreds of thousands of elements in it. I have three different windows, each displaying different information about the data within this massive linked list, each in its own particular sorting order. I knew right away I didn't want to call InsertItem() and DeleteItem() hundreds of thousands of times, each time the user wanted to sort. And I definitely wasn't about to sort this entire linked list, or make duplicate copies for the other windows. So the technique I decided on was to simply have each CListCtrl object maintain its own dynamic array of pointers within this linked list. Everytime a new node is added to the linked list, I pass a pointer of the newly created node to the CListCtrl object, which stores the pointer in its array. I then simply call CListCtrl::SetItemCount(new_count);, which forces a redraw of the control. No new memory is allocated (unless the array needs to grow), and there is no delay at all from inserting the item. If many nodes are created at the same time (as is done with this example), then I pass them all to the view in one function call, so only a single screen update is needed.

This technique has several advantages. The first being that I can now easily have many CListCtrls working off the same data source, maintaining their own personal sort order, while minimizing the amount of memory required. Sorting is a snap: simply call the ANSI C function qsort() passing in the address of your array, along with your own compare function. After qsort() completes, call CListCtrl::SetItemCount(current_count) to redisplay the data. Done!

Another advantage is pure, raw speed. In the example code provided, I tested the window with 1,000,000 items in it, and it displays and scrolls in real time. It will scroll as fast as you can drag the mouse down. The only delay you will notice is the time spent to initially allocate and create a linked list with 1,000,000 elements in it. Of course that is only done once, and if your linked list is already created, with this technique you could create and display a CListCtrl object with well over 1,000,000 elements in less than a second! Sorting is also faster, as the only memory being moved around are the tiny 4byte pointers being stored in the array.

Downloads