CODEWITHSUNDEEP
c++design-patterns
user152508
user152508

Reputation: 3131

Searching childs

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 ?

Upvotes: 0

Views: 113

Answers (4)

fabmilo
fabmilo

Reputation: 48330

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

Upvotes: 1

Bj&#246;rn Pollex
Bj&#246;rn Pollex

Reputation: 76848

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.

Upvotes: 0

Dialecticus
Dialecticus

Reputation: 16759

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.

Upvotes: 0

Nim
Nim

Reputation: 33645

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.

Upvotes: 0

Related Questions