Searching childs

Question

Hello

I have class A. Class A is responsible for managing the lifetime of B objects and it contains container of B objects that is map<BGuid,B>, and each B object contains container of C objects which is map<CGuid,C>.I have one global A object for the entire application.

I have the following problem: I have CGuid object and I want to use it to find my C object. But to that I also need to know the BGuid object which will tell me in which B object I should look my C object. But all I have is the CGuid, which means that I have to check every B object to see if it contains my C object. However I think that this is messy. I thought that maybe I should have another class say M which will contain map of all my C objects , and I can search directly in it just with CGuid, still this means that I need to maintain extra map just for searching.

Also I except in the future my C class to contain map<Dguid,D> so I will have the same problem for the the D objects , this time even worse, I will need Bguid,Cguid, and Dguid to find my D object.

How to solve this problem ?

Answer 1

Do you have any restrictions on memory? If not, I would maintain the reverse lookup tables (maps), so you need one for C->B, when you add D, you need a second D->C, so if you have C, to locate it correctly, you need one lookup to locate B, then from A you can traverse down with a further two lookups. A lot quicker than iterating through all Bs looking for C!

Another alternative, do you have control over the Guid, if so, you could try encondig the "path" information into the guid. Say for example the B guid is "B.1", "B.2", "B.3" etc. the post fix after '.' separator tells you which B it is. When you add C, you can simple add an extra '.', i.e. C 1's guid is (let's assume it's stored at B 1) = "B.1.1", so now to find the object, you parse the key, and voila you have your "path" to C1.

Answer 2

map<BGuid,B>, map<CGuid,pair<B,C>>, map<DGuid,pair<C,D>>

With GUID you get the object and object's parent. With object you get GUID. Recurse from beginning.

Answer 3

You could assign ranges of the children's GUIDs to every parent GUID. Suppose BGuid is in the interval [0, 9], and CGuid in the interval [0, 99]. You could now map ten CGuids to every BGuid with a function like this:

mapGuids(B): CGuid => BGuid = B % 10

Now you will always know which path to take through the tree. You will want to keep your tree balanced for better performance when there are many nodes.

Answer 4

You have a classic relationship of Parent - Children. I suggest you to improve your design by not specifying how is handled (i.e. with maps). use a container to store the childrens, and let the childrens have a pointer to the Parent. In this way is easy to traverse from any point up to the top.

A useful OOP Design pattern for these cases is the CompositePattern