Composite pattern in C++ problem

Question

Hello! I have to work with an application in C++ similar to a phone book: the class Agenda with an STL list of Contacts.Regarding the contacts hierarchy,there is a base-class named Contact(an abstract one),and the derived classes Friend and Acquaintance(the types of contact).

These classes have,for instance, a virtual method called getName,which returns the name of the contact.

Now I must implement the Composite pattern by adding another type of contact,Company(being derived from Contact),which also contains a collection of Contacts(an STL list as well),that can be either of the "leaf" type(Friends or Acquaintances),or they can be Companies as well.

Therefore,Company is the Compound type.

The question is: how and where can I implement an STL find_if to search the contact with a given name(via getName function or suggest me smth else) both among the "leaf"-type Contact and inside the Company collection?

In other words,how do I traverse the tree in order to find possible matches there too,using an uniform function definition?

I hope I was pretty clear...

Answer 1

Well, one way to do it:

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

Then:

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

What you're doing is asking each node to find the one you're looking for, without caring what type of node (leaf or otherwise) it is. Each node then checks itself, and, for those with child nodes, their children.

Answer 2

List is the wrong type for a large type of contacts since you might have a O(N) to find the last contact or even to find no contact.
I suggest you to use a hash map (unordered_map from boost/tr1) or a regular map so you will be able to find them by ID or their name using a key.
Also sounds like a company should just be a tree of contacts.
You can find tree implementations here.
You transvase through the tree to find the node you need.