I don’t think colony has any kind of first-in-first-out scheme. If you initialize a colony with a lot of elements, then erase an element in the middle, then add an element, the new element isn’t added to the front or the end of the iteration order, but in that empty hole that was just created. Queue and Deque tell you where you can insert efficiently, and the iteration order, neither of which translate well to colony.

From: Jeremy Ong <jeremycong_at_[hidden]>
Sent: Monday, February 8, 2021 11:57 AM
To: sg14_at_[hidden]
Cc: Matt Bentley <mattreecebentley_at_[hidden]>; C++ Library Evolution Working Group <lib-ext_at_[hidden]>; Guy Davidson <guy_at_[hidden]>; Ben Craig <ben.craig_at_[hidden]>
Subject: [EXTERNAL] Re: [SG14] std::colony name brainstorming

Looking at this interface, is it correct to describe "colony" as just a "stable_deque"? The double-ended queue semantics of the contents are preserved by the skip list, and stability in the context of containers refers to memory stability as you point out. I'd like it if all the containers were grouped by suffix (e.g. associative containers are maps, lookup tables are sets, etc.)

On Mon, Feb 8, 2021 at 10:44 AM Ben Craig via SG14 <sg14_at_[hidden]<mailto:sg14_at_[hidden]>> wrote:
The paper talks a lot about the name colony, and that the name “bag” isn’t a good fit. I want to see if we can have other good names (or name pieces) get discussed on the mailing list.

For picking names, I like using a name as a way to compare and contrast against similar choices. Ideally, the name should indicate why you would use one facility over another.

The big reasons I see to prefer colony over another container:

  * Pointer and iterator stability
  * Contiguous block storage for faster iteration (i.e. not a node based container)
  * O(1) inserts and deletes
  * Re-orderable / sortable

Reasons to use other containers:

  * Contiguous elements
  * Sub-linear lookup
  * Sorted by default
  * User control over insert location

I don’t see a good way to tease out the subtle contiguity differences in a short name. The stability aspect isn’t too hard though… “stable_<foo>” can communicate that… assuming we can find a suitable <foo>. The main downside to “stable_” is all the node based containers are already stable, but don’t have the prefix.

I’m leaning towards “stable_bundle”. “bundle” communicates a bit of disorganization. It still sounds like a container (“a bundle of ints”). I don’t think it has strong precedence in CS unlike so many other names. “bundle” as the root is still rather arbitrary though. Neither part of the name communicates that fast iteration is a key aspect of the container.

We could attempt to fill <foo> with something that indicates the expected implementation strategy. I’m less fond of that approach, but it can help communicate the design of the container. I can suggest “stable_skip_array” and “stable_skip_list”. I’m not overly fond of “array” or “list” in the names though, as they suggest layouts that aren’t entirely accurate (single large allocation and individual element allocation respectively). I’m not fond of “bucket” since that has precedence in our hash map apis, though I could live with “stable_bucket”.

A thesaurus item to start from: https://www.thesaurus.com/browse/array?s=t<https://urldefense.com/v3/__https:/www.thesaurus.com/browse/array?s=t__;!!FbZ0ZwI3Qg!90c3YGxVgFdXEkLU6l1MkxJOCLXqB8obiNCsmlcVrS6lgnMkwlvLXHb-rhTh$>. I’ve browsed over list, container, and aggregate for other ideas.

Are there other aspects of the container we should look at for naming? Any suggestions for affixes or roots for a multi-part name?
_______________________________________________
SG14 mailing list
SG14_at_[hidden]<mailto:SG14_at_[hidden]>
https://lists.isocpp.org/mailman/listinfo.cgi/sg14<https://urldefense.com/v3/__https:/lists.isocpp.org/mailman/listinfo.cgi/sg14__;!!FbZ0ZwI3Qg!90c3YGxVgFdXEkLU6l1MkxJOCLXqB8obiNCsmlcVrS6lgnMkwlvLXChAHY6W$>