Subject: Re: [isocpp-lib-ext] std::colony name brainstorming
From: Ville Voutilainen (ville.voutilainen_at_[hidden])
Date: 2021-02-10 07:53:20
On Wed, 10 Feb 2021 at 15:37, Jeff Garland
> I don't understand what the term sparse is supposed to tell me about a
> list. If a list isn't sparse, it's broken.
> I donât think of lists as âsparseâ â they typically have no extra storage. Nodes are allocated and removed as needed. This âlistâ is special in that it doesnât immediately deallocate storage when removing an element. Itâs a âlist of allocated slotsâ. Then it pulls a nifty accounting trick to allow O(N) traversal - a classic time/space trade.
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.
> Colony also doesn't behave like a list performance-wise, considering
> all of its operations, so I don't know
> why we'd suggest that it's a list.
> unordered_map doesnât perform like map either. And as far as I can tell itâs performance properties are unlike any existing container.
Heh, yeah. When pondering about this, I came to a similar conclusion
that unordered_map and unordered_set aren't
very descriptive names in some regards.
> My point was from an âinterfaceâ point of view itâs closest to list. Why is it âlist likeâ? First, itâs NOT random access. You have to traverse it. The iterator stability is maintained on modifications. sparse_array might be a good choice â except the dominate features of arrays in c++ is random access and contagious allocation.
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.
> 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.
>Itâs also a âdata warehouseâ project - Apache Hive â meh, Java. Building a new floor on the hotel for each block doesnât really match either â and again, time scales. Parking lot â hmm, I guess you can define linear traversal? It feels like itâs really random access unless itâs one of the Japanese vending machines where you put a car in and it disappears. Ah, but then you use âa keyâ to get it back â oops.
I have modest disagreement with your time scale problem, because the
time scales are relative to the lifetimes of the elements,
not relative to bullet flight times in a game. Thus I think it's a
mistake to compare a time scale of a building extension to
that bullet flight, rather than comparing, say, the time scale of a
hive growing to a lifetime of an occupant of the hive.
SG14 list run by email@example.com
Older Archives on Google Groups