C++中的复合模式

Question

我必须使用类似于电话簿的C++中的应用程序来工作：具有STL联系人列表的类Agenda。关于联系人层次结构，有一个名为Contact的基类（抽象类） ，派生类Friend和熟人（联系类型）。

这些类有一个名为getName的虚方法，它返回联系人的名称。

现在我必须通过添加另一种类型的接触的，公司（正从联系派生），其中还包含联系人的集合（一个STL列表以及）实施Composite模式，可以是任一“叶子“类型（朋友或熟人），或者他们也可以是公司。

因此，公司是复合型。

的问题是：如何以及在哪里可以实现一个STL find_if来搜索具有给定名称的接触（通过的getName功能或建议我不服别人）这两个之间的“叶”形的接触，并在公司内部采集？

换句话说，如何使用统一的函数定义来遍历树以找到可能的匹配呢？

我希望我是很清楚......

Answer 1

好了，一个办法做到这一点：

virtual contact* contact::findContact(std::string name) 
{ 
    if(m_name == name) {return this;} 
    return NULL; 
} 

然后：

contact * Company::findContact(std::string name) 
{ 
    if(!contact::findContact(name)) 
    { 
     //For each contact in the contact list, findContact(name) 
     //If we find something, return that. 
     //Otherwise return null. 
    } 
    return this; 
} 

你在做什么是要求每个节点找到你正在寻找的那个，而不关心它是什么类型的节点（叶子或其他）。然后每个节点检查自己，并为那些有子节点的人检查自己的孩子。

Answer 2

列表是大型联系人的错误类型，因为您可能有O（N）找到最后一个联系人，甚至找不到联系人。
我建议你使用哈希映射（boost/tr1中的unordered_map）或常规映射，这样你就可以使用一个键通过ID或他们的名字找到它们。
也听起来像一家公司应该只是一个联系树。
你可以找到树实现here。
您可以通过树来查找您需要的节点。

Answer 3

“现在我必须通过添加另一种类型的联系人，公司（从联系人派生）来实现复合模式，该联系人还包含一组联系人（也是一个STL列表），可以是”叶“类型（朋友或熟人），或者他们也可以是公司”

您可以为公司创建一个stl兼容的复合迭代器。

class Company : public Contact { 
    std::list<Contact *> contactList; 

    //snip...other private members 
    friend class CompanyIterator; 
    friend class ConstCompanyIterator; 
    public: 

    // nested iterator classes 
    class CompanyIterator : public std::iterator<std::forward_iterator_tag, Contact *> { 

      friend class Company; 
      // pair<>.first is the iterator obtain by calling begin() 
      // pair<>.second is the end iterator 
      std::stack< std::pair< std::list<Contact *>::iterator, 
         std::list<Contact *>::iterator> > iters_stack; 

      Contact *pCurrentContact; 
      Company *pCompany; // This is the top level company which will be iterated. 

     public: 

      explicit CompanyIterator(Company &c); 

      // Required forward iterator methods follow 
      CompanyIterator(); 
      CompanyIterator(const CompanyIterator&); 
      CompanyIterator& operator=(const CompanyIterator& other); 
      Contact &operator*() const; 
      Contact *operator->() const; 
      CompanyIterator& operator++(); 
      CompanyIterator operator++(int); 

      bool operator==(const CompanyIterator& x) const; 
      bool operator!=(const CompanyIterator& x) const; 
    }; 

    // nested iterator class 
    class ConstCompanyIterator : public std::iterator<std::forward_iterator_tag, 
      const Contact *> { 

      friend class Company; 
      // We use CompanyIterator to implement ConstCompanyIteraor 
      CompanyIterator inner_iter; // fwd operations here, 
             // using "const_cast<Company *>(this)->method()" 
     public: 

      explicit ConstCompanyIterator(const Company & dir); 

      // This ctor will function as a cast operator, to convert a CompanyIterator 
      // into a ConstCompanyIterator 
      ConstCompanyIterator(const CompanyIterator &iter); 

      // Required forward iterator methods follow 
      ConstCompanyIterator(); 
      ConstCompanyIterator(const ConstCompanyIterator&); 
      ConstCompanyIterator& operator=(const ConstCompanyIterator& other); 

      const Contact &operator*() const; 
      const Contact *operator->() const; 

      ConstCompanyIterator& operator++(); 
      ConstCompanyIterator operator++(int); 

      bool operator==(const ConstCompanyIterator& x) const; 
      bool operator!=(const ConstCompanyIterator& x) const; 
    }; 

    typedef CompanyIterator iterator; 
    typedef ConstCompanyIterator const_iterator; 

    iterator begin(); 
    iterator end(); 

    const_iterator begin() const; 
    const_iterator end() const; 

    // snip... other Company public methods 
}; 

对于上面给出的前向迭代方法的实现，在Github上查看Composite Iterator代码。大部分的实现都在Directory.cpp中。 github代码用于模拟文件系统的复合模式。类目录是组合。类文件是叶类。类节点是基本组件类。

用于find_if函子会是什么样子

FindIfFunctor { 
     std::string name; 
    public: 
    FindIfFunctor(const std::string& n) : name(n) {} 
    bool operator()(const Contact& c) { return c.getName().compare(name); } 
}; 

最后，find_if代码

Company c; 
// snip... stuff gets added to company 
string someName("IBM"); 

find_if(c.begin(), c.end(), FindIfFunctor(someName));