65.9K
CodeProject 正在变化。 阅读更多。
Home

更快的树控件

Tibor Blazko
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.69/5 (11投票s)

2001 年 8 月 19 日

CPOL

5分钟阅读

viewsIcon

419491

downloadIcon

3720

关于一个开源免费的快速树控件的文章。

Sample Image - RGTree.gif

引言

我正在编写一个用于探索注册表的应用程序。因此，我需要树形控件。起初，我直接使用 InsertItem 配合注册表项。在 SysTree 中插入一个项的速度足够快，但删除项的速度非常慢。我使用了 Tibor 的文章 中描述的优化方法，但速度并没有显著提升。然后我使用了文本回调项，但效果一样。

例如：在我的 Thunderbird 1200 上，向系统树形控件添加约 50000 个注册表项需要大约 6 秒，删除这些项需要大约 22 秒（！）

因为我找到的每个快速树形控件都需要付费，而找到的免费控件并没有比标准的树形控件更快，所以我决定自己编写一个。这个树形控件应该像系统树形控件一样工作。

控件内部

控件的数据存储基于 template CRGTreeT<_ITEMDATA>。这是一个实现双向链表的对象，每个元素包含一个 ITEMDATA 类型的成员。

template<class _ITEMDATA> class CRGTreeT
{
 public:
   // Construction / Destruction
   CRGTreeT();
   ~CRGTreeT();

   // returns the count of all items
   UINT GetItemCount() const;
   // returns the count of all child items
   UINT GetChildCount( /*[in]*/ POSITION posParent) const;
   // returns the root
   POSITION GetRootPosition() const;

   // returns the parent of an item
   POSITION GetParentPosition( /*[in]*/ POSITION pos) const;

   // adds an items at the begin of the list
   POSITION AddHead( /*[in]*/ const _ITEMDATA *pItemData, 
                     /*[in]*/ POSITION posParent=NULL);
   // adds an items at the end of the list
   POSITION AddTail( /*[in]*/ const _ITEMDATA *pItemData, 
                     /*[in]*/ POSITION posParent=NULL);

   POSITION InsertAfter( /*[in]*/ const _ITEMDATA *pItemData, 
                         POSITION posParent=NULL, 
                         /*[in]*/POSITION posAfter=NULL);
   // Remove the item at position pos including all subitems
   void RemoveAt( /*[in]*/ POSITION pos);
   // Removes all items
   void RemoveAll();

   // returns the first/last child item of the item at position posParent
   POSITION GetChildPosition( /*[in]*/ POSITION posParent, 
                              /*[in]*/ BOOL bFirst=TRUE) const;
   // returns the next list element, NULL if none
   POSITION GetNextPosition( /*[in]*/ POSITION pos) const;

   // returns the previous element, NULL if none
   POSITION GetPrevPosition( /*[in]*/ POSITION pos) const    

   // returning a copy of the ITEMDATA at position pos
   void GetAt( /*[in]*/ POSITION pos, /*[out]*/ _ITEMDATA* pItemData) const;
   // Returning a pointer to the ITEMDATA at position pos
   _ITEMDATA* GetAt( /*[in]*/ POSITION pos);
   // replace the ITEMDATA at position pos
   void SetAt( /*[in]*/ POSITION pos, /*[in]*/ const _ITEMDATA* pItemData);

   // sort childrens of the item at position posParent
   BOOL SortChildren( /*[in]*/ POSITION posParent, 
                      /*[in]*/ BOOL bAscending=TRUE);
   // search for an item based on the compare function
   POSITION Find( /*[in]*/ const _ITEMDATA *pItemData, 
                  /*[in]*/ POSITION posParent);

   // setting a callback function for sorting and finding items
   CompareFunc SetCompareFunc( /*[in]*/ CompareFunc func);
   DeleteFunc SetDeleteFunc( /*[in]*/ DeleteFunc func, LPARAM lParam);

protected:
   // remove all childs from an item
   void RemoveChilds( POSITION pos);

   // quick sort algorithms for sorting up- or downwards
   void QSortA( /*[in]*/ CTreeItem **pLow, /*[in]*/ CTreeItem **pHigh);
   void QSortD( /*[in]*/ CTreeItem **pLow, /*[in]*/ CTreeItem **pHigh);

private:
   CTreeItem      m_ItemRoot;
   UINT           m_nCount;
   CompareFunc    m_pCompareFunc;
   DeleteFunc     m_pDeleteFunc;
   LPARAM         m_lParamDeleteFunc;
};

消息将在其自身的窗口过程中处理。我直接实现了一些小的函数，其他的则作为独立函数存在，形式如下：

LRESULT On[MessageName]( HWND hwnd, TREE_MAP_STRUCT *ptms, 
                         WPARAM wParam, LPARAM lParam)

有一个数据结构保存每个树形控件 HWND 的特性

struct TREE_MAP_STRUCT
{
   HWND         hwnd;                  // the handle of the control
   HWND         hWndEdit;              // the handle of the controls 
                                       //   edit window
   WNDPROC      pOldWndProc;           // the old window procedure
   int          nItemCount;            // all items inserted
   int          nMaxWidth;             // max width of the control
   int          nVScrollPos;           // vertical scroll position
   int          nHScrollPos;           // horizontal scroll position
   HTREEITEM    hItemFirstVisible;     // items ...
   HTREEITEM    hItemSelected; 
   HTREEITEM    hItemEditing;
   HTREEITEM    hItemClicked;
   HIMAGELIST   hNormalImageList;      // image list
   HIMAGELIST   hStateImageList;
   bool         bRedrawFlag;           // should the control be redrawed 
                                       //   on each inserting/erasing
   _rgTree      rgTree;                // the CRGTreeT template
};

为了更快地计算项的宽度，Tibor 编写了一个类来保存可重复使用的对象，特别是 HDC 和 HFONT。您可以通过 SetRedraw() 调用来缓存它们的创建。

下一个优化用于内部的 GetItemVisibleIndex()。当项很多时，它会尝试查找靠近第一个可见项的项。

class CItemRectCache
{
public:
   CItemRectCache(HWND hWnd);
   ~CItemRectCache();
   void SetItem( RGTVITEM* pItem);
   int GetItemTextWidth();
   SIZE GetStateImageSize(TREE_MAP_STRUCT *ptms);
   SIZE GetNormalImageSizeAndOffset(TREE_MAP_STRUCT *ptms);
protected:
   bool         m_bHasLinesAtRoot;
   bool         m_bStateImageSizeInitialized;
   SIZE         m_StateImageSize;
   bool         m_bNormalImageSizeInitialized;
   SIZE         m_NormalImageSize;
   HWND         m_hWnd;
   HDC          m_hDC;
   HGDIOBJ      m_hFont;
   HGDIOBJ      m_hBoldFont;
   HGDIOBJ      m_hOldFont;
   bool         m_bBoldSelected;
   RGTVITEM*    m_pItemSet;
}

已知待办事项和限制

  • 完整的 (或更完整的) TreeCtrl 功能。目前，我们只实现了对我们有用的情况。主要缺失的情况包括：
    • 自定义绘制
    • TVM_INSERTITEM 配合 TVI_SORT
    • TVM_SETSCROLLTIME
    • 工具提示支持
    • 信息提示
    • 键盘通知和增量搜索
  • 排序速度较慢，因为使用了快速排序算法，需要构建一个包含所有项的数组来进行排序，排序后还需要更新项的先前/后继位置。
  • 更精简的代码，避免重复和未注释的部分。
  • 更多的 1:1 实现。
    • 当 Expand 调用后，hItemFirstVisible 的情况与系统树不一致。
    • 编辑控件的大小和位置取决于水平滚动条的位置。
  • 更智能的用户界面优化。
    • 有时重绘次数可能过多。
    • 可以优化更多的搜索（参见 SetItem 中的 __GetItemVisibleIndex 调用）。
    • 请参阅 bInSetScrollBars 的用法，这是一个糟糕的例子。
  • 绝对正确的代码。
    • 现在更改项的 TVIS_BOLD 状态不会重新计算水平滚动条。
    • 直接定义的 ID_EDIT 可能会与您的对话框控件 ID 冲突（？）。
  • 当在 InsertItem()/TVIF_TEXT 前使用 SetRedraw(false) 时，系统树返回的项的矩形文本宽度为零，而 rgtree 返回计算出的尺寸。系统树需要显式调用 SetItemText() 或在调用 GetItemRect(... , true) 之前调用 SetRedraw(true)。

演示项目

我编写了一个演示项目，用于比较 CRGTreeCtrl 与标准树形控件的速度。它测量了插入、排序和删除项的时间。

首先，您必须构建 RGTree，然后是 TreeDlg 配置。

我们在调试 DeleteAllItems() 中发布版本比调试版本慢的原因上花费了一些时间。您可能不会相信，问题竟然在于 delete[] pItemData->pszText 调用。有趣的是，当您不从开发人员工作室运行它时，一切都正常（为什么我们没有早点发现？）。

如何在您的项目中应用

如果您想使用它，请构建 (发布版) RGTree.dll。这将生成导入库 RGTree.lib。将其包含在 Project\Settings\Link\General\Object/Library 模块中。从 CRGTree 派生您的树形控件。

CYourTreeCtrl.h

#include "RGTreeCtrl.h"
class CYourTreeCtrl : public CRGTreeCtrl

像这样更改所有 CTreeCtrl 的提及……

BEGIN_MESSAGE_MAP(CYourTreeCtrl, CTreeCtrl)

…到 CRGTreeCtrl，在 CYourTreeCtrl 中。* 然后重新构建。不要忘记在进行大量树数据更改之前和之后调用 SetRedraw()。

如果您创建自己的项目来存放树形控件的源代码，请不要忘记在那里定义 RGTREECTRL_EXPORTS。

最后

总的来说，该控件是可用的。特别是，与系统控件相比，插入/删除大量项的速度更快。

如果您发现任何更正、改进或添加的功能，请告知我们，以便更新本文。首先，我们对 Bug (附带明确的复现场景) 感兴趣，最重要的是 (因为你们是程序员) 附带可能的解决方案。

如果您有兴趣加入我们，并且不介意阅读源代码，我们非常欢迎。请在您进行更改之前联系我们，以避免重复开发。

更新历史

  • InvalidateItemRect() 调用 GetItemRect() 时传入 FALSE
  • OnGetItem()/TVIF_TEXT 修复
  • HitTest() 支持 TVHT_TOLEFT 和类似标志
  • WM_MOUSEWHEEL 处理程序
2002年1月25日
  • InsertItem_UpdateVScrollPos()
  • HitTest() 与水平滚动
2002年3月2日
  • SetTVITEMforNotify()
  • DoScroll()
  • GetNextItem()/TVGN_LASTVISIBLE
2002年4月15日
  • 编辑和滚动定时器使用 GetDoubleClickTime()
  • TVS_FULLROWSELECT 仅在没有 TVS_HASLINES 时也有效
  • 拖放支持
  • IsBeforeFirstVisibleItem()
2002年5月23日
  • TVE_COLLAPSE 修复
2002年8月7日
  • NM_RCLICK (感谢 Doug Garno)
  • I_IMAGECALLBACK (感谢 Doug Garno)
  • DeleteObject(hBrush) 在 OnPaint() 中
  • SetItem() 包含图像更改的情况
2002年9月12日
  • WM_CONTEXTMENU 与 NM_RCLICK 的返回值
  • 在 SetItem() 中进行 Expand() 而不进行通知
  • GetNextItem(NULL) 及其类似的新功能将返回 NULL 而不是崩溃。
  • 为未处理的事件调用 MessageBeep() 到 OnKeyDown()
  • 两个 TVGN_DROPHILITE 项 - 第二个用于“按下”状态 (但按下状态的 rgtree 仍然可以通过 Tab 键切换)
  • nmtv.itemNew 在 TVN_DELETEITEM 中更正为 nmtv.itemOld (感谢 Doug Garno)
  • 在 SetTVITEMforNotify() 中将 (mask | TVIS) 更正为 (mask & TVIS) (感谢 Doug Garno)
2002年9月13日
  • GetChildItem(NULL) 返回根项而不是 NULL (感谢 Doug Garno)
2002年12月9日
  • 在编辑时没有 WM_CHAR 提示音 (感谢 Doug Garno)
  • EndEditLabelNow() 只发送一个 TVN_ENDLABELEDIT (感谢 Doug Garno)
  • 在 OnEditLabel() 中，SetTVITEMforNotify() 使用 lParam 而不是 ptms->hItemEditing (感谢 Doug Garno)
  • 字体处理更简洁。
2003年3月28日
  • 为未处理的事件调用 MessageBeep() 到 OnKeyDown()，效果更好 (但仍未达到 1:1)，请参见 文章评论。
  • hBoldFont 在 OnPaint() 中按需获取，并从 WM_GETFONT 而不是 hOldFont 派生。
2003年12月17日
  • 修复了在零尺寸窗口中插入项时的滚动问题 (_ScrollAbsolutelyDownWhenRequired)
  • 在 OnKeyDown() 中增加了新情况 (感谢 Doug Garno)

请在文章评论中查找实际的代码更新。

© . All rights reserved.