indexmap icon indicating copy to clipboard operation
indexmap copied to clipboard

Update readme to mention `shift_remove`

Open Venryx opened this issue 2 years ago • 3 comments

Currently, the readme contains the following text:

A pure-Rust hash table which preserves (in a limited sense) insertion order. [...] [...] It preserves insertion order (except after removals) [...]

Some of those features were translated to Rust, and some were not. The result was indexmap, a hash table that has following properties:

  • Order is independent of hash function and hash values of keys.
  • Fast to iterate.
  • Indexed in compact space.
  • Preserves insertion order as long as you don't call .remove().
  • Uses hashbrown for the inner table, just like Rust's libstd HashMap does.

The lines in bold keep mentioning the fact that if you call remove, then the preservation of the insertion-order is lost.

At first, that made me disregard the library because I was looking for a HashMap implementation that is able to preserve its insertion order even after removals.

After looking at other crates, I eventually found a thread that mentioned that indexmap was updated to have a new shift_remove function, which apparently does what I want.

That's great! But the fact that the readme did not mention this anywhere, made me unnecessarily search around for an alternative, when all I needed to do was call shift_remove instead of remove/swap_remove.

Because of this, I request that the readme be updated to make clear mention of the fact that insertion-order can be preserved -- even after removing entries -- so long as you use the shift_remove function to do so.

Venryx avatar Mar 17 '22 23:03 Venryx

You make a reasonable point. I'm pretty sure that line exists from before shift_remove existed, and probably while the crate was still called ordermap. There is also still a caveat that shift_remove does disrupt the actual indices following the removal point, which is important if you're relying on the indexing properties.

Would you care to make a pull request with changes that make sense from your view as a prospective user?

cuviper avatar Mar 21 '22 20:03 cuviper

Yes, I'm up for writing a suggested readme change for this. (can't at this moment, but I have starred the notification email for it)

There is also still a caveat that shift_remove does disrupt the actual indices following the removal point, which is important if you're relying on the indexing properties.

By this you just mean that the index->value pairing of the later entries shifts by one, correct? If so, that seems natural given the name of the function. (it would be odd for it to be called "shift remove" if none of the entries were shifted by the operation!)

Venryx avatar Mar 21 '22 20:03 Venryx

Yeah, I meant the shift by one. Maybe that's self-explanatory, but I'm trying to imagine this from fresh eyes. :)

cuviper avatar Mar 21 '22 21:03 cuviper