On Sat, Sep 25, 2010 at 2:10 PM, Brian Wood <woodbrian77@gmail.com> wrote:
Beman Dawes:
I'm going to attack variable-length keys/data in several steps.
1) Via a very simple string class that has a fixed maximum length, and has a sizeof() that maximum length + 1. Although this wouldn't be suitable for really demanding applications, it should be fine for a lot of every day programming. It is totally non-invasive, so is available right now. See http://github.com/Beman/Boost-Btree/blob/master/boost/btree/detail/fixstr.hp..., or use your own if you've already got such an animal.
Just fyi, I've been experimenting with a similar string -- http://webEbenezer.net/misc/lil_string.hh .
If an operation would result in a string with length more than 255, an exception is thrown. This allows the length of the string to be marshalled with one byte. As you mention this limitation is not a problem in many circumstances. I'd quibble a little with it not being suitable for demanding applications. I think it is fine to use it in that context, but that you might need to also use other string classes.
Why not use a compressed uint type? Google's Protocol Buffers compressed uint compresses an uint just fine, below 128 will be represented in one byte, etc..., it works very simply, by just having the MSB be a marker indicating the last byte of the integer if it is zero, thus it is base 128 instead of base 256 per byte, so as an example: hex -> compressed bits 0 -> 0000 0000 1 -> 0000 0001 300 -> 1010 1100 0000 0010 And so forth, and if you have looked in the protocol buffer source it decodes each byte very quickly and efficiently. So if you are worried about space, you could use this (especially since I have many use cases where strings would exceed 255 characters, and we need a 'bytestream' type or so too).