> On Feb 9, 2021, at 11:16 PM, Ville Voutilainen via Lib-Ext <lib-ext_at_[hidden]> wrote:
>
> On Wed, 10 Feb 2021 at 04:17, Jeff Garland via SG14
> <sg14_at_[hidden] <mailto:sg14_at_[hidden]>> wrote:
>>
>>
>>
>> On Feb 9, 2021, at 6:41 PM, Nevin Liber <nevin_at_[hidden]> wrote:
>>
>> 
>> On Tue, Feb 9, 2021 at 7:11 PM Jeff Garland via SG14 <sg14_at_[hidden]> wrote:
>>>
>>> unordered_list
>>> unordered_block_list
>>> unordered_bucket_array_list
>>> unordered_sparse_list
>>> unordered_change_list
>>> unordered_sparse_collection
>>> sparse_agglomeration
>>> sparse_aggregate
>>> sparse_list
>>> sparse_block_list
>>> or
>>> bucket_list ;)
>>
>>
>> I'm not sure what you want us to do with an unordered set of names.
>>
>> You are the one championing changing the name to one of these. My advice is to pick the best name, and write up the justification for why it is better than colony and why it is better than all the other names in your set.
>>
>>
>> It’s brainstorming. If I had to pick one I’d say unordered_sparse_list.
>
> return -ENORATIONALE;
>
> 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.

> 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.
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.

Lists come many special forms in computing with slightly different performance properties for different — single linked, double linked, skip lists, etc. To me, this is the closest description of the base functions it provides to users.

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. 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.

Jeff