Steven Schveighoffer <schvei...@yahoo.com> writes: > On 11/20/14 5:30 PM, Jerry Quinn wrote: >> This works nicely for small types, but has gotchas. For example, if >> you've got an AA of ints, what value indicates that this is a value >> folded into the bucket entry vs actually being a pointer? You'll need >> extra space to make sure it's safe. Alignment is another concern. >> Let's say you have bool for the entry/element flag. With ints you've >> doubled the size of the bucket array. > > Hm.. the bucket entry will simply be what a node is now. You are actually > saving space, because you don't need to store that extra pointer to the first > node.
Almost. You do need a way to indicate that the bucket is empty. So you need another flag though it can be smaller than a pointer (for 64 bit). But the overhead is low except for things like ints. > Where it gets dicey is when you rehash. Some of the nodes will be moved into > the bucket space, some will move out of it. But I don't think it's a big deal, > as a rehash doesn't happen very often. True. Umm, that does raise a question - are addresses of AA contents required to be stable? C++11 requires that of its hashtables. But it ties your hands when trying to write customized hash tables.