It's possible that SceneNodeInfo needs operator== defined for it... possible operator<, too but I can't remember.

You could do it with a map, but it all depends on what you're trying to look up. I'll explain in the context of the data structure, not specifically the jSceneNodeInfo, because I'm not familiar with that code specifically.

So, if you have a function that can look up something via ID, and you want one that looks up via string, you have two choices. std::map<std::string, ID> or std::map<std::string, std::map<jSceneNodeInfo>::iterator>. The second structure here may have the wrong map type, but you get my drift.

Essentially, you can always look up the ID based on the string first, then make a second lookup based on the ID, incurring two O(logN) lookups, or you can insert the iterator to the node in the ID-to-node map associated by the string in your auxiliary map. This is legal in the STL because iterators to elements in an std::map are not invalidated under any operations (except delete of that node). So, you can get it down to a single O(logN) lookup this way. Just be very careful to insert and delete in your external string-to-node lookup every time the Scene's map is modified.

FWIW, most types in STL only need the operator< to be used in data structures, since == can be phrased as !(a<b) && !(b<a). Dunno if that actually answers your question or not.

JH

I know I'm going to get rotten fruit & vegetables thrown at me for this, but what you're proposing is going to be pretty slow in a subsystem that probably can't afford the performance hit. One of the reasons for using id's is because they're fast. A string compare is extremely slow, and doing a nested map of maps of strings will make the compiler cry.

For Barbie, we had class called SeEntity which was the template for our property system. An Entity is something that can do something interesting; the interesting stuff being defined by what properties you give it. Thus, every entity had a map of properties:

When we profiled our code, we found that an amazing amout of time was spent walking those maps map and comparing strings. We ended up changing it into a sorted vector of pairs, and changing the std::string's into something we called StringId's. A StringId is a class that optimizes string compares. It's used for strings that are unique throughout the game, like a property name. When you assign a StringId object some string value, it hunts through the list of strings (actually a std::set which is really a red/black bst under the hood; 0(log n) average case for searching) and finds the one you want. After that initial hit, comparing StringId's is super fast; it's just a pointer compare.

For completenesses sake, here's the final definition which shipped with Barbie:


I'm not sure if this helps you at all, I just wanted to point out a potential performance hit and show you our solution. It ended up working very well for us.

-Rez

I'm not sure if you're responding to me or the parent in this thread, so apologies if you weren't.

I wasn't suggesting a map of maps, or anything like it. It was a map of strings to map::iterators. Big difference. That means he could look something up with a string and not need to convert to an ID first, that's all.

What you describe with a StringId is very common, and has been used for decades in games. My favorite implementation is a StringCRC32, which acts like a constant string, except that upon construction, it computes a CRC32 of itself. During the operator< or operator==, it first checks for equality by comparing CRC's between strings. If they match, you have a very good probability of equality. Then you check the length. If still equal, you're almost certain. If you are worried about it, you do the slower string compare to be absolutely certain. That's only two integer compares. Plenty fast. And you don't need a central repository of strings to do it.

But I can see the advantage of what you describe, because you are guaranteed after first finding the string in the set, equal means equal. If you had some ballpark figure for the number of strings, you could have made that a hash table for a bit better performance. Iterating maps is horrible for cache coherency.

There are also cheaper/faster string hash functions than CRC32. It's just a convenient hash I have laying around. And actually, if you use two different hash functions, and they agree, you can be virtually certain of equality without bothering with string compares.

JH

I was actually responding to the original post. The map of maps of strings scenario is one I saw in our code (eek!), though it was fortunately not in a performance critical area.

I've seen similar solutions to the StringCRC32 approach. My only concern is that it has the potential to create some crazy bugs if you happen to get a bad string compare despite the odds (Murphy's Law ) I'm curious; have you ever seen any problems crop up in your implementations from false matches?

We can be pretty certain how many StringId's there will be because most of them are created during initialization, so throwing them in a hash map is a good idea. Maybe I'll sneak that in.

-Rez

Yes, it definitely happens that CRC32's can collide. It's not the most usual thing, but when it happens, it can be nasty to track down. That's why I mentioned you want to use the checksum as the quick rejection, then use another method (length or another hash function) as a sanity check. And in debug builds, I always degenerate to a full string compare just to be absolutely sure. If you don't have problems in debug, you are pretty safe in release, so I turn the slow string compare part off.

The content of the strings matters, too. CRC was primarily developed to detect line noise, so it is ideal at discovering differences of one bit in two equal length binary blocks. Its probability of producing an identical checksum increases (slowly) as more bits differ. Strings tend to be highly variable, so if one bit is different, usually many more are different. And they tend to vary in length. So, anyone suggesting that the theoretical properties developed in most of the CRC literature apply here is simply wrong. However, it does give us a nice and random hash key.

And the probability that two different hash key functions yield the same result are astronomical...

JH

Astronomical or not, I'm always paranoid about that kind of stuff. The final string compare would definitely solve that problem. What we really need to do is stop using so many strings in Ratrace.

-Rez

I like.

I did something similar actually. It's a general type class that holds a map of unsigned long and strings. Basically, it hashes a string and puts it in a map and hands out const references to the type (so classes are only 4 bytes larger instead of 12, I think).

If you'd like, I can post it here so that you can get a few tips from it.