Segmentmap

A generic collection that preserves the order of items at all cost. Removing an item never restructures, keys/indices are unique per item. Internally uses a HashMap of arrays containing the items. Also tested with an internal BTreeMap, but results were worse. Iterator is stable, using a linked-list-like structure.

Using an array size >128 makes the segmentmap significantly slower when inserting (>10%). Similar when you use a small array size (like 16). The smaller the array, the more similar it is to an indexmap, The larger the array, the more similar it is to an array (duh). (but in both cases it will still preserve order when removing, without restructuring).

More of a PoC than something you should start using.

Benchmarking

These are the results of some very basic benchmarking I did (cargo run) against common collections. Listed are the durations of doing 1 million operations sequentially, so to get the average just divide by 1M.