CListCtrl and sorting rows

• Download source code - 123 KB

Introduction

Microsoft's CListCtrl has support for displaying data in a grid using the report style, but certain changes are required to enable row sorting.

This article will demonstrate the following:

• How to sort items in a CListCtrl.
• How to display the sort order in the column header, while maintaining the Windows XP/Vista look.

Background

There are lots of advanced grid controls that extend the CListCtrl so it can perform column sorting. But, because these grid controls can be very complex, it can be difficult to see how they do it.

The article Sort List Control demonstrates only one way to perform the sorting (using CListCtrl::SortItems).

How to sort items in CListCtrl

There are usually three approaches for inserting data in the CListCtrl, and this also has an influence on the sorting method that we choose:

• The text of each cell is supplied using CListCtrl::SetItemText(). This will store the values inside the CListCtrl, and the values can only be updated manually. This will, of course, take extra memory as the entire data model is now stored twice.
• Instead of storing a copy of the entire data model in the CListCtrl, we can tell the CListCtrl that it should retrieve the cell text using a callback. To make this work, we can call CListCtrl::SetItemText() using LPSTR_TEXTCALLBACK, and it will send a LVN_GETDISPINFO message every time it needs to know the value of a certain cell.
• Virtual lists is an extension of the callback approach, where the CListCtrl is only told how many items there are in the entire data model. The CListCtrl becomes a mirror of the data model, but usually, it only mirrors a cache of the entire data model.

When using a callback from the CListCtrl to the data model, there are some extra considerations because the LVN_GETDISPINFO message uses the row- and column-index of the CListCtrl.

• The row-index will change every time we perform a row-sort, so we must assign a unique identifier to each inserted row using CListCtrl::SetItemData(). The unique identifier should correspond to an object in the data model. When receiving the LVN_GETDISPINFO message, the row-index can be converted back to the unique identifier using CListCtrl::GetItemData().
• The column-index must be sequential, so we should strongly consider assigning a unique identifier to each inserted column using CListCtrl::InsertColumn()'s last parameter nSubItem. The benefit of this can be seen when we need to have persistence for column configuration combined with rows being removed and added over time. When receiving the LVN_GETDISPINFO message, the column-index can be converted back to the unique identifier using CListCtrl::GetColumn() with the mask LVCF_SUBITEM.

Using CListCtrl::SortItemsEx

If storing the text of each cell inside the CListCtrl, the best choice is to use SortItemsEx() with a sort function as an argument. The sort function will get the row index of the two cells to compare.

namespace {
    struct PARAMSORT
    {
        PARAMSORT(HWND hWnd, int columnIndex, bool ascending)
            :m_hWnd(hWnd)
            ,m_ColumnIndex(columnIndex)
            ,m_Ascending(ascending)
        {}

        HWND m_hWnd;
        int  m_ColumnIndex;
        bool m_Ascending;
    };

    // Comparison extracts values from the List-Control
    int CALLBACK SortFunc(LPARAM lParam1, LPARAM lParam2, LPARAM lParamSort)
    {
        PARAMSORT& ps = *(PARAMSORT*)lParamSort;

        TCHAR left[256] = _T(""), right[256] = _T("");
        ListView_GetItemText(ps.m_hWnd, lParam1, 
          ps.m_ColumnIndex, left, sizeof(left));
        ListView_GetItemText(ps.m_hWnd, lParam2, 
          ps.m_ColumnIndex, right, sizeof(right));    

        if (ps.m_Ascending)
            return _tcscmp( left, right );
        else
            return _tcscmp( right, left );            
    }
}

bool CListCtrl_SortItemsEx::SortColumn(int columnIndex, bool ascending)
{
    PARAMSORT paramsort(m_hWnd, columnIndex, ascending);
    ListView_SortItemsEx(m_hWnd, SortFunc, ¶msort);
    return true;
}

Using CListCtrl::SortItems

If using callback to display data in the CListCtrl, we can use SortItems() with a sort function as an argument. The sort function will get the row item data of the two cells to compare.

This method is sometimes also used even when data is contained in the CListCtrl, but this is not recommended because converting the item data to the proper row-index is slow.

namespace {
    struct PARAMSORT
    {
        PARAMSORT(const CListCtrl_DataModel& datamodel, 
                  int columnData, bool ascending)
            :m_DataModel(datamodel)
            ,m_ColumnData(columnData)
            ,m_Ascending(ascending)
        {}

        const CListCtrl_DataModel& m_DataModel;
        int  m_ColumnData;
        bool m_Ascending;
    };

    // Comparison extracts values from the DataModel
    int CALLBACK SortFunc(LPARAM lParam1, LPARAM lParam2, LPARAM lParamSort)
    {
        PARAMSORT& ps = *(PARAMSORT*)lParamSort;

        const string& left = 
          ps.m_DataModel.GetCellText((size_t)lParam1, ps.m_ColumnData);
        const string& right = 
          ps.m_DataModel.GetCellText((size_t)lParam2, ps.m_ColumnData);

        if (ps.m_Ascending)
            return _tcscmp( left.c_str(), right.c_str() );    
        else
            return _tcscmp( right.c_str(), left.c_str() );                    
    }
}

bool CListCtrl_SortItems::SortColumn(int columnIndex, bool ascending)
{
    if (GetItemCount()!=m_DataModel.GetRowIds())
        return false;

    int columnData = GetColumnData(columnIndex);
    PARAMSORT paramsort(m_DataModel, columnData, ascending);
    SortItems(SortFunc, (DWORD_PTR)¶msort);
    return true;
}

Using Stable Sort

If using a callback to display data in the CListCtrl, and the data model container is "slow" to lookup a single item, then we can consider caching the contents of the entire column and then sorting them without the lookup penalty.

1. Create a temporary container with the item data and the column cell text for each row.
2. Sort the container according to the column cell text.
3. Loop through all the rows and call CListCtrl::SetItemData() in the same order as the container. Now, the first row in the CListCtrl will have the item data of the first row according to the chosen sort order.

stable_sort() requires a bit more work, as we should try to preserve the original row order from the CListCtrl. The source code of the demo application contains an example of how it can be done.

namespace {
    bool AscSortFunc(const pair<string,size_t>& left, 
                     const pair<string,size_t>& right)
    {
        return left.first < right.first;
    }
    bool DescSortFunc(const pair<string,size_t>& left, 
                      const pair<string,size_t>& right)
    {
        return right.first < left.first;
    }
}

bool CListCtrl_StableSort::SortColumn(int columnIndex, bool ascending)
{
    // Sorting optimized for a datamodel where lookup is slow
    //    - Uses more memory during sort, because it takes a copy of an entire column
    //    - Even faster if one can iterate over the datamodel without lookup
    int columnData = GetColumnData(columnIndex);
    
    // Extract entire column from datamodel
    vector< pair<string,size_t> > entireColumn;
    entireColumn.reserve( m_DataModel.GetRowIds() );
    for(size_t rowId = 0; rowId < m_DataModel.GetRowIds(); ++rowId)
    {
        entireColumn.push_back( make_pair(m_DataModel.GetCellText(rowId, 
                                          columnData),rowId) );
    }

    // Sort entire column
    if (ascending)
        sort(entireColumn.begin(), entireColumn.end(), AscSortFunc);
    else
        sort(entireColumn.begin(), entireColumn.end(), DescSortFunc);

    // Update list-control with new column-order
    for(int nItem = 0; nItem < GetItemCount(); ++nItem)
    {
        SetItemData(nItem, entireColumn[nItem].second);
    }

    return true;
}

Using Sort Style

First of all, the styles LVS_SORTASCENDING and LVS_SORTDESCENDING are not recommended by Microsoft for sorting, because it doesn't support local characters. More info: MS KB191295.

• It doesn't support LPSTR_TEXTCALLBACK, so text cannot be provided using callback, but must be inserted directly using CListCtrl::SetItemText().
• It only works on the label column (first inserted column).
• It only sorts when inserting items, so it is not possible to change the sort order after the items have been inserted.

If having a static list where it should only sort according to a single column, then this option is very easy to implement.

void CListCtrl_SortStyle::LoadData(const CListCtrl_DataModel& dataModel)
{
    // Must decide sort-order before inserting !
    if (IsAscending())
        ModifyStyle(NULL, LVS_SORTASCENDING);
    else
        ModifyStyle(NULL, LVS_SORTDESCENDING);

    for(size_t rowId = 0; rowId < dataModel.GetRowIds() ; ++rowId)
    {
        // When inserting item, then one must provide cell-text
        InsertItem(++nItem, dataModel.GetCellText(rowId, 0).c_str());
    }
}

Using Virtual List

CListCtrl can be turned into a virtual list by applying the owner data style LVS_OWNERDATA. Since the virtual list is completely synchronized with the data model, we have to sort the records in the data model according to the wanted column sort order.

Usually, the CListCtrl will only mirror a small cache of the entire data model, so the sort operation becomes a query to the entire data model for the visible rows matching the sort criteria. The example code does not cover how this could be done, as implementing a data model cache system is beyond the scope of this article.

How to display the sort order arrow in the column header

When the user clicks a column header to sort all the rows according to the chosen column, the column header should change to reflect the actual sort order.

Windows XP introduces the column header item styles HDF_SORTDOWN and HDF_SORTUP, which makes it somewhat easy to display the sort order. Before, we had the choice to load a bitmap image into the column header, or to perform owner drawing of the column header. The challenge is to detect whether Windows XP can help in displaying the sort order arrow, or we have to use a bitmap image (HDF_BITMAP).

The details of how to update the column header has already been answered by Massimo Galbusera, and this technique is being used by many of the more advanced grid controls that extends from CListCtrl.

Using the code

The source code provided includes implementations of the five different sort methods, so we can see the different ways in action.

Points of interest

While developing the demo application, there were some performance issues with the item insert for the non-virtual list implementations. This was solved by using the SetRedraw() function, and it also gave an increase in speed by making sure to insert new rows at the bottom of the list.

void CListCtrl_SortItemsEx::LoadData(const CListCtrl_DataModel& dataModel)
{
    // Insert data into list-control by copying from datamodel
    SetRedraw(FALSE);    // Disable redraw as InsertItem becomes so much faster
    int nItem = 0;
    for(size_t rowId = 0; rowId < dataModel.GetRowIds() ; ++rowId)
    {
        nItem = InsertItem(++nItem, "");    // Faster to insert at the end
        SetItemData(nItem, rowId);
        for(int col = 0; col < dataModel.GetColCount() ; ++col)
        {
            SetItemText(nItem, col, dataModel.GetCellText(rowId, col).c_str());
        }
    }
    SetRedraw(TRUE);
    Invalidate();
    UpdateWindow();
}

History

• 2008-07-14 - First release of the article.