Method to access the `nth` inserted element in a map

馃挕 Ideas
1

For example:

const map = new Map();
map.set(1, 2);
map.set(3, 4);
console.log(map.nth(1)); // [3, 4]

Preserved insertion order is a handy feature of Maps. It makes them more useful for building caches with eviction policies. For example, you can build an LRU cache by deleting and re-inserting items when they are accessed.

While implementing the SIEVE algorithm in JS, I noticed that an .nth() method would be handy. Without it, I need to track insertion order in a seperate array, OR copy the keys into an array ([...map.keys()][i]).

This is how simple it would be w/ an .nth method (I think this is wrong but pls ignore :bowing_man:)

  evict() {
    let hand = this.hand;
    if (hand == null) {
      hand = this.items.size - 1;
    }
    while (this.items.nth(hand).visited) {
      this.items.nth(hand).visited = false;
      hand--;
      if (hand < 0) {
        hand = this.items.size - 1;
      }
    }
    this.items.delete(this.items.nth(hand).key);
    this.hand = hand - 1;
  }

This would use less memory than is currently possible (AFAICT).

Unsure of the feasibility of this feature as I do not understand how insertion order is typically tracked today.

Apologies for sloppy writing, writing this quickly before leaving the office :)

2

The purpose of preserving insertion order is to enable deterministic operation across implementations, not to provide fast indexed access.

With the iterator helpers proposal you can write .nth(hand) as .keys().drop(hand).next().value. It's a bit verbose, but explicit on what's actually happening.
(See also the discussions on .at() at Array.prototype.at compatibility? 路 Issue #148 路 tc39/proposal-iterator-helpers 路 GitHub and This seems to be missing `at()`? 路 Issue #279 路 tc39/proposal-iterator-helpers 路 GitHub)

3

Different implementations use different strategies, but I don't think any of them afford efficient indexing. (Firefox and Chrome use something like this, while Safari uses a linked list.)

And if getting the nth item takes linear time, it's not worth providing a method for it - for example, your code snippet would take quadratic time, which is bad.

4

Yeah, my understanding of those implementations is that while there is an ordered list, there are also tombstones so can't directly index.

5

Will note that such an "at" method, while not constant-time, would still see a perf boost as it doesn't require actually reading intermediate values, only what's minimally necessary to know if a tombstone is reached. For large maps, this could easily use SIMD.

However, I'm struggling to see other use cases here.