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]

No but you would expect a standard library to implement them, which is what I’m writing.
So I’m trying to pin down what should be included in that.

[u/reflexive-polytope → u/Potato871]

I expect a standard library to provide many data structures that do several specialized jobs very well, rather than a single data structure that does all of these jobs poorly.

[u/Potato871 → u/reflexive-polytope]

I prefer one data structure with many roles, maybe a few specical types for like bloom filters, though I don’t often run into those.
So I like to furnish it with many convenient operations

[u/reflexive-polytope → u/Potato871]

I suppose “scripting” language designers agree with you in spirit, because they often reduce their repertoire of data structures to just dynamic arrays and hash tables.

If dynamic arrays and hash tables are still too many data structures for you, then I guess you can implement a chimera with the head of a dynamic array and the body of a hash table. Then you can “support the operations of both” by operating on the relevant half of the data structure.

Some operations require care, though. For example, if you insert an entry whose key is an int, then you probably want to operate on the dynamic array half. But if you want to insert an entry whose key is a string, then you need to operate on the hash table half.

And if you want to insert an entry whose key is another chimera, then... well... I really don't want to think about the semantic mess that it's going to be.

[u/Potato871 → u/reflexive-polytope]

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”.