Is there any implementation of this library as a multimap?
Tony
Craig Silverstein
it, but I'm not quite sure how it would work; multimaps are not a good
fit for internal chaining, which is what the sparsehash package does.
There are somewhat hacky and inefficient ways to do it, but I don't
know if it's worth it to implement things that way.
The best I can suggest is to store a vector of items as the value of
your sparse_hash_map. I know it's not a perfect solution.
craig
ShaunJ
A map of vectors is a good solution, but uses quite a bit more memory.
On a 64-bit machine (GNU C++), a vector is 24 bytes. For the case
where most keys have a single element, a slight improvement is to use
a list rather than a vector, which is only 16 bytes. The STL list is a
double-linked list. A single-linked list would take only 8 bytes.
A pointer to a simple array of elements would also be only 8 bytes.
Adding elements to the list would require realloc'ing the pointer.
This doesn't store the number of elements in the list however, so it
would have to be terminated with a sentry, which probably eliminates
the benefit, unless something tricky is done to store the number of
elements.
For the case where most keys have a single element, can anyone suggest
a memory-efficient solution for a sparsehash-based multimap?
Cheers,
Shaun
Craig Silverstein
} suggest a memory-efficient solution for a sparsehash-based multimap?
That's tricky. What items are you putting in the sparsemap? Do they
have a bit to spare? If so, you could save space by making your
hash-value be a union of your object and a pointer, using that bit to
distinguish the two parts of the union (you'd want to make it the low
bit, and just mask it off to get the real pointer, which will always
have 0 in its bottom two bits).
For the common case of one object per key, you just put the object in;
if more objects, you have a pointer to an array of objects. Once
you're in the array, you can use your extra bit to indicate whether or
not the item is the last item in the array.
This is about as space-efficient as you can get, but is very ugly, and
probably pretty fragile.
What methods would you need to call on this multimap? I assume
equal_range()? If all you needed to do was iterate over the resulting
map, then it's easier to add to sparse_hash_map. But equal_range() is
hard, because there's no way to guarantee items with the same key will
be next to each other in the hashtable.
craig
ShaunJ
the sparsemap is a (multi)map of fixed-length string (24 bytes) to
integer (8 bytes). It would be possible to allocate a spare bit in the
key. equal_range is necessary and called a lot, so performance is
important.
Cheers,
Shaun