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

用于遍历树的 C++ 模板类

Nandagopal
starIconstarIconstarIcon
emptyStarIcon
starIcon
emptyStarIcon

3.86/5 (7投票s)

2003年4月2日

3分钟阅读

viewsIcon

67384

downloadIcon

837

一篇关于在编写树遍历器时使用模板的文章

引言

模板类 walker 仅捕获遍历算法，并依赖于 ContextType（模板参数类型）来实现上下文相关的功能。基于上下文的信息包括上下文标识符类型、过滤器类型、上下文项、打开上下文和保留上下文。 ContextType 模板参数应支持所需的 typedef 和内部类 CItem 和 COpenContext。

在进一步讨论实现细节之前，我想先谈谈对这种类的需求。我们使用各种看起来像或就是树的结构进行编程，有时我们需要重复遍历算法，仅仅是因为结构上的一点小变化。重复这样的算法有很多我们知道的问题，这就是为什么 stl 有 for_each 算法。就像 stl 的目标一样，一个算法应该独立于数据结构。遍历算法对数据结构的依赖被转移到 ContextType 类。该类应该有类型 ContextIdentifierType，ContentFilterType，CItem 和 COpenContext，并应支持一个 static 函数 IsReserved(const CItem*)。

CItem 应该有以下接口：-

bool IsAContext() const

COpenContext 应该有以下接口

构造函数
析构函数
const CItem* GetNext()
const CItem* Get() const
bool GetNewContextId(ContextIdentifierType& newId) const

对于 ContextIdentifierType 和 ContentFilterType，没有接口规范。没有任何函数可以抛出异常。

使用代码

一个类可以从这个模板的特定实例化派生，并重写 bool OnContextChange(UserDataType*, const ContextType::CItem&, const ContextType::ContextIdentifierType& , bool bMovedToNewOrBackToOld). 当进入或离开上下文时，WalkI 私有方法会调用它。

参数是：-

  • 通过引用传递的用户数据，允许任何修改
  • 项，这是新的上下文
  • 当前（旧）/新上下文标识符
  • 进入/退出上下文

并且有 void OnItemFound(UserDataType,const ContextType::CItem&,const ContextType::ContextIdentifierType&). 当找到新项时，WalkI 私有方法会调用此方法。即使新上下文是当前上下文中的一个项，也只会调用 OnContextChange。

  • 通过值传递的用户数据。
  • 项
  • 当前上下文标识符

这两种方法都是私有的。 这是模板的代码

template <class UserDataTypeT,class ContextTypeT>
class CWalker
{
public:
    typedef ContextTypeT ContextType;
    typedef UserDataTypeT UserDataType;
    typedef CWalker<UserDataType,ContextType> MyType;

    CWalker():m_bStopped(false)
    {}

    // Will walk through the specified context
    //
    int Walk(UserDataType userData,
        const ContextType::ContextIdentifierType& iContext
        )
    {
        ContextType::ContentFilterType filter = m_filter;
        int nRet = WalkI(userData,iContext,filter,m_bStopped);
        m_bStopped = false;
        return nRet;
    }
    // To set the content filter
    //
    void SetContentFilter(const ContextType::ContentFilterType& filter)
    {
        m_filter = filter;
    }

    void StopWalking()
    {
        m_bStopped = true;
    }

private:

    int WalkI(UserDataType userData,
        const ContextType::ContextIdentifierType& iContext,
        const ContextType::ContentFilterType& filter,
        bool& bStopped
        )
    {
        if(bStopped) return stopped;

        ContextType::COpenContext openContext(iContext,filter);

        const ContextType::CItem *item = openContext.Get();

        if(!item) return fail;

        if(!item->IsAContext())
        {
            this->OnItemFound(userData,*item,iContext);
        }
        else 
        {
            if(!ContextType::IsReserved(*item))
            {
                ContextType::ContextIdentifierType newContext;
                openContext.GetNewContextId(newContext);

                if(this->OnContextChange(&userData,*item,newContext,true))
                {
                    WalkI(userData,newContext,filter,bStopped);
                    if(bStopped) return stopped;
                    this->OnContextChange(&userData,*item,iContext,false);
                }
            }
            else this->OnItemFound(userData,*item,iContext);
        }

        while(true)
        {
            if(bStopped) return stopped;
            const ContextType::CItem *item = openContext.GetNext();
            if(!item)
                break;

            if(!item->IsAContext())
            {
                this->OnItemFound(userData,*item,iContext);
            }
            else 
            {
                if(!ContextType::IsReserved(*item))
                {
                    ContextType::ContextIdentifierType newContext;
                    openContext.GetNewContextId(newContext);

                    if(this->OnContextChange(&userData,*item,newContext,true))
                    {
                        WalkI(userData,newContext,filter,bStopped);
                        if(bStopped) return stopped;
                        this->OnContextChange(&userData,*item,iContext,false);
                    }
                }
                else this->OnItemFound(userData,*item,iContext);
            }
        }
        return success;
    }

    ContextType::ContentFilterType m_filter;

    virtual bool OnContextChange(UserDataType*,const ContextType::CItem&,
        const ContextType::ContextIdentifierType&,bool bMovedToNewOrBackToOld)
    {
        return false;
    }

    virtual void OnItemFound(UserDataType,const ContextType::CItem&,
        const ContextType::ContextIdentifierType&)
    {
    }

    bool m_bStopped;
};

一个示例上下文

例如，我们将创建一个 FolderContext，它将捕获所需的函数和详细信息。标识符类型是字符串，因为文件夹通过它们的名称唯一标识。过滤器类型是字符串，因为文件夹的内容也通过它们的名称唯一标识。 这是 CITem 的编码方式：-

...
class CItem
{
public:
    // Required function
    //
    bool IsAContext() const
    {
        return fileInfo.dwFileAttributes==FILE_ATTRIBUTE_DIRECTORY;
    }

    WIN32_FIND_DATA& GetInfo()
    {
        return fileInfo;
    }

    const WIN32_FIND_DATA& GetInfo() const
    {
        return fileInfo;
    }
private:
    WIN32_FIND_DATA fileInfo;
};
...
如果你能看到，CItem 包装了 WIN32_FIND_DATA，并使用该结构来实现 IsAContext 方法。 这是 COpenContext 的编码方式：-
...
class COpenContext
{
public:
    COpenContext(const ContextIdentifierType& context, 
        const ContentFilterType& filter)
    {
        m_context = context;
        std::string szToSearchFor = context;
        if(!filter.empty())
            szToSearchFor += "\\" + filter;

        m_hFind = ::FindFirstFile(szToSearchFor.data(),&m_folderItem.GetInfo());
    }

    ~COpenContext()
    {
        if(m_hFind!=INVALID_HANDLE_VALUE) ::FindClose(m_hFind);
    }

    const CItem* GetNext()
    {
        if(m_hFind==INVALID_HANDLE_VALUE) return 0;
        if(!::FindNextFile(m_hFind,&m_folderItem.GetInfo()))
            return 0;
        return &m_folderItem;
    }

    const CItem* Get() const
    {
        if(m_hFind==INVALID_HANDLE_VALUE) return 0;
        return &m_folderItem;   
    }

    bool GetNewContextId(ContextIdentifierType& newId) const
    {
        if(m_folderItem.IsAContext())
        {
            newId = m_context + "\\" + m_folderItem.GetInfo().cFileName;
            return true;
        }
        return false;
    }

private:
    CItem m_folderItem;
    HANDLE m_hFind;
    ContextIdentifierType m_context;

    COpenContext(const COpenContext&);
    COpenContext& operator = (const COpenContext&);

};
...

这里上下文是文件夹，因此在创建 COpenContext 对象时，会创建一个文件夹的查找句柄。 在析构函数中，我们关闭该句柄。 GetNext 将使用查找句柄获取当前文件夹中的下一个文件或文件夹。 Get 将返回当前项。 GetNewContextId 将使用当前上下文和项名称将新的上下文 ID 复制到输出参数中。 属性是 CITem，当前上下文标识符和一个查找句柄。 复制构造函数和 = 运算符不是接口规范的一部分，因此它们未实现并设置为私有。 让我们看看 IsReserved 现在是什么样子：-

...
static bool IsReserved(const CItem& item)
{
    if(std::string(".")==item.GetInfo().cFileName || 
        std::string("..")==item.GetInfo().cFileName) return true;
    return false;
}
...
文件夹的保留项是 '.' 目录和 '..' 目录。

关注点

我得到的一个有趣的想法是，为了防止回调函数更改类的属性，可以为实际函数提供一个包装器，其工作是复制所需的属性。 如果你注意到，WalkI 函数不使用任何成员变量。 我能想到的可能用途列表是：-

  • 遍历 MIB (snmp)
  • 遍历二叉树
  • 遍历链表
  • 遍历 xml 文档/元素
© . All rights reserved.