1

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

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

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

因此，Company 是 Compound 类型。

问题是：我如何以及在哪里实现 STL find_if 来搜索具有给定名称的联系人（通过 getName 函数或建议我其他）在“叶子”类型的联系人和公司集合中？

换句话说，如何使用统一的函数定义遍历树以便在那里找到可能的匹配项？

我希望我很清楚...

4

3 回答 3

2

好吧，一种方法：

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;
}

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

于 2010-04-26T18:48:13.623 回答
1

列表对于大量联系人来说是错误的类型，因为您可能需要 O(N) 才能找到最后一个联系人，甚至找不到联系人。
我建议您使用哈希映射（来自 boost/tr1 的 unordered_map）或常规映射，这样您就可以使用键通过 ID 或名称找到它们。
听起来公司应该只是一棵联系人树。您可以在此处
找到树实现。 您遍历树以找到所需的节点。

于 2010-04-26T19:14:48.247 回答
0

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

您可以为 Company 创建一个与 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 上的复合迭代器代码。大多数实现都在 Directory.cpp 中。github 代码用于模拟文件系统的复合模式。类目录是复合的。Class File 是叶类。Class Node 是基础组件类。

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));
于 2014-01-07T19:06:22.853 回答