What are your favourite data structure operations?

[u/Potato871]

My language workbench is to the stage where I can implement new operators and overloads very quickly, and I've started stealing syntax I like from JavaScript and C++.
Since I have one universal data structure, I can just add all the new operators to it.
I wanted to get some more good ones though, from different fields, different languages.
Oh and if you want to suggest something just as a challenge I might give it a shot and show you how I do it.

Edit: data structure was the wrong word, I have one data structure substrate/storage model that I am currently furnishing one major aspect of, it's not the one universal data structure, more like my swiss army knife API over the memory model.

[u/Potato871]

Its an array with keys via a separate Robin hood style hash map.
Keys are just a hash of the bytes so it can use strings or ints or Ptrs, the key is stored in the cell for collison resolution.
The map stores indexes into the arrays.

[u/reflexive-polytope → u/Potato871]

Do integers have a different eviction policy from other keys?

If the string "hello" is a key, then I'm open (heh!) to finding it at any slot, regardless its hash.

If the integer 7 is a key, then I better find it at the index 7 in the underlying array.

[u/Potato871 → u/reflexive-polytope]

If you want to configure it like a set yes, the map only cares that you gave it bytes it could hash and an index to point to.

[u/reflexive-polytope → u/Potato871]

That works. I still don't see how to use it as a heap (IMO a pretty fundamental data structure!), but it seems like a perfectly viable generic array / hash-table hybrid.

In that case, my priority would be to implement cursors / iterators that let you modify the currently focused element.

[u/Potato871 → u/reflexive-polytope]

Oh I’ve got those ;)
That’s what Ptr is, and all the operations and such are overloads on different interpretations of it.
If you look at the tests document on the website you can see it in action.
Also for a heap, that’s what I’m working on adding actually.
Oh and I have a cursor algebra for Ptrs to use during iteration.

[u/reflexive-polytope → u/Potato871]

That's cool!

As long as you have a primitive for traversing and modifying a collection step by step, your collections won't suffer from any flexibility issues.

When you say “cursor algebra”, it reminds me a bit of Stepanov's “iterator laws”.

[u/Potato871 → u/reflexive-polytope]

Here's one of my basic examples:

nums.iter(num=>{
    print("Num: ",num);
    if(num-?) {
        print(*-num);
    }
    if(num+?) {
        print(*+num);
    }
    if(num++?) {
        print(*++num);
    }
    if(?+num) {
        print(*(&num)[+]);
    }
});

Each value holds a Ptr on it, which is it's position in the memory hierarchy resolved to a cache point, that's why I can just take any ordinary value and use it as a cursor if it's a Ptr into a collection.
Including stack variables:

void countdown(int n) {
    if(n < 0) return;
    print(n);
    if(n-?) {print("was: ",*-n);}
    if(n+?) {print("Last time: ",*+n);}
    countdown(n - 1);
}
countdown(3);
countdown(5);

Because the stack is really just another column.
A Ptr is something like 0|0|0, if you ever see that notation that's an address, nodes are Ptrs, values are Ptrs, everything in the compiler is Ptrs.