On Wed, 10 Feb 2021 at 16:45, Jeff Garland
<jeff_at_[hidden]> wrote:
> > Right. But sparse vs. dense matrices are what I think about when I see
> > a suggestion for a sparse list,
> > and I don't see how this std::hive (yay, surreptitious sleight-of-hand
> > in play, caveat emptor :P) is more
> > sparse than a linked list, it seems *less* sparse because there are
> > allocated-but-skipped slots in it.
>
> Ok — if I follow you’re saying a ’sparse matrix’ representation would have less storage per unit size than a ‘dense matrix’. Interesting.

What do you mean "by unit size"? But, well, what I mean is below..

> > I would certainly imagine that a sparse array would try to optimize
> > storage for particular values in it, and I don't
> > think std::hive does that.
>
> Yes, I see.

..here.

> >> Let’s take a look at some of the other ‘analogy names’ that have been suggested. I see ‘hotel’, ‘parking lot’, and ‘hive’. I like ‘hive’ very much. Unfortunately, a hive is random access.
> > If you crack it open. The ones designed to be opened without cracking
> > are nests, not hives. :P
> > (Or so I read from the internets, hives are natural, nests are
> > artificial. Go figure, I don't know whether
> > that difference is correct.). The normal access to either isn't
> > random, though; bees don't just go directly
> > anywhere in the hive or nest, there are some pathways they need to follow.
> Unfortunately the hexagonal slot pattern is burned into the image of a ‘hive’ — very ordered cells.

That doesn't make it random-access from the point of view of how bees
go from outside to cell $foo,
or how they go from cell $foo to outside. There's tunnels and layers
and storage structures, and no
random access because, well, if a bee is looking for a cell that has
$bar amount of honey in it,
there's an access that needs to look at more cells than just going
straight to the right one. Some of
those cells are in a skip list. :P

> That’s fair. The thing is that the ‘fleeting nature’ of elements in a colony is much more like the ‘moving traffic’ that comes and goes than the buildings. Although, to be fair, the use case involves both kinds of elements — some mostly static and some that come and go quickly.
>
> I’m not strongly against ‘hive’ at this point, it’s better than ‘colony’ in my opinion. Just not sure it’s better than block_list or some other function describing variant.

That does seem like an alternative that describes the structure more
than it does describe the purpose. But, then again,
that's somewhat consistent with what we've had before. But also
somewhat inconsistent, an unordered_map is not
a hash_keyed_list_of_buckets.