String based flag list VS. Bit based flag list

I was pondering about this the other night. A string based flag list (that is, something like "dark inside safe") fairly easy to parse and has no max limit of flags. A bit based flag list (using ints) is very fast and relatively easy to manipulate, but it has a maximum capacity (though it can be extended like SMAUG).

My question is thus: which is better? Is the flexibility of the string based list better despite the greater overhead? Do you think the lag would even be noticable for a relatively large world doing string lookups for flags? Or is it worth just running with bitvectors and having an extended system from the start?

String comparison really isn't that slow. So, to answer your question, the time spent comparing strings will be very low, especially if you store them in a fast lookup format (e.g. a tree, or binary search over a sorted list of strings) -- but frankly, even a linked list will be quite fast.

A hybrid solution is to create a runtime correspondence between the flag names and integers, and use those integers to create the numerical bit vectors. If bitvectors are implemented correctly, that is, with no limit on the number of flags you could put in, then you get the speed of numerical comparison with the flexibility you were describing with strings.

But seriously, the string comparisons really aren't that slow... you'd have to be doing a LOT of them to really feel the difference.

If you are doing a lot of them, scanning a long string for names seems to me to be a bit of a slow way. Especially if you have flags with similar names (like "dark" and "darkness") so a simple search for "dark" won't work.

If you are using C++ why not just use the STL and use a set? That gives an unlimited number of flags, and is quick as it has a fast lookup.

Here is an example:



The set here (flags) can have an unlimited number of unique elements, keyed by name. You use "find" to see if a flag is set.

Of course, this is an internal structure, you would need to serialise it (eg. to a comma-delimited string) for saving to disk.

Nice. These would be even more useful than std::bitset flags as far as the ease with which you can check them in code. I might play around a bit with std::set

I know this is something I should probably know, but when you mention serialization, how would one go about that?

You'd have to serialize by hand. You would write a function that took a set of strings and outputted its elements as, for instance, CSV. Then you'd write a function that took a CSV string and created a set of strings.

It's not clear how much more general you can make this without implementing a whole bucketload of Java into C++, by giving all your objects toString() methods -- but if you had those, you could make this rather generic by serializing any set by writing CSV of the elements' toString() results. Of course, you'd have to be clever and escape commas, etc.

On this page:

http://www.gammon.com.au/forum/bbshowpost.php?bbsubject_id=2896

I describe various utilities including VectorToString and StringToVector which are basically what you would need to serialize. This was for vectors but the nice thing about STL is that sets would be virtually identical.

Ah, very nifty. Thanks.