The Design of Software (CLOSED)

A public forum for discussing the design of software, from the user interface to the code architecture. Now closed.

The "Design of Software" discussion group has been merged with the main Joel on Software discussion group.

The archives will remain online indefinitely.

XML Based object Hierarchy

I have an hierarchy of objects I cache up in memory. If there is a change I will sync up with a XML like file I store locally on the system.

The problem is the hierarchy that I maintain in the cache in memory is damn slow. I use STL map to maintain the hierarchy...

map<key, FirstLevel*>
map<firstLevelKey, SecondLevel*>
map<secondLevelKey, ThirdLevl*>

So if I want to access an object stored in the ThirdLevl, I open up a 3 level nested for loop and use the iterator of the first map to determine the key to second, and get on to the secondLevel iterators to get the key to the third ... hope you got the idea. Imagine doing this for insertion, updation and deletion of the objects.

I was wondering how to attack this with a design that could give a O(n) for insertion, updation and deletion.
Tony Send private email
Monday, March 05, 2007
1. shouldn't have put XML in the subject, this is an in-memory object lookup question.
2. Iterating through maps generally means you're using maps wrong.
3. Can you give each object a unique key? something like level and ID, then combine that into a key and use one map.
Monday, March 05, 2007
you're using a "nested" for loop? Do you mean you have multiple maps at the second and third levels?
Monday, March 05, 2007
What stops you from building a key that goes directly to the item?
son of parnas
Monday, March 05, 2007 you know what O(n) means?  I suspect that is not what you want, otherwise, why use maps? are for some reason using maps as sets, and just iterating through each map to find your target object as your "nested for loops" statement suggests.
Art Send private email
Monday, March 05, 2007
> you know what O(n) means?  I suspect that is not >what you want, otherwise, why use maps?

Yeah that was my point, I don't want maps. This is a inherited code. Somehow people who wrote it were using it as a set. Basically I used O(n) to specify the fact that I want to get the nested forloops out

Sorry I wasn't specific. My question was would you suggest using maps to cache object hirarchy.
Thursday, March 08, 2007
It looks like you want a data structure that is indexed by a key which is a triplet of values (A,B,C) => Data.

If the data is not sparse and the elements of the key are integral, then use a multidimensional array.

If the data is sparse, or the key elements are strings, then you would do best to combine the three key elements to make a single key.  You then have the choice of data structure: either a single map, or a hash table.

A map is typically implemented using a balanced binary tree.  The key must support operator<.  For a key class containing three elements, you can override operator< to perform the comparison.  You must apply an ordering to the element comparisons, e.g.:

bool triplet::operator<(const triplet &other) const
    return a < other.a ||
        a == other.a && b < other.b ||
        a == other.a && b == other.b && c < other.c;

A map implemented as a binary tree with be O(log n).  If you need better, then some versions of the STL provide a hash map.  For a hash map, you will need to define operator== instead of operator<.
David Jones Send private email
Thursday, March 08, 2007
thats it, that is exactly what i wanted. Thank you very much.
Thursday, March 08, 2007

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
Powered by FogBugz