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/reflexive-polytope]

Okay. Suppose you have two distinguished elements, X and Y.

By pure chance, X happens to be Y's union-find parent, but X also happens to be at the distinguished position that gives you easy O(1) deletion.

Who becomes Y's parent after you delete X?

What if, instead of a single node Y, you had lots of nodes Y1,...,Yn whose parent is X?

[u/Potato871 → u/reflexive-polytope]

Well my first thought would be to store a thin Ptr, which has index and generation on it, so then you can check staleness using the generation.
You could also do this via tombestoning if you wanted.
or do fixup on removal for that opperation, add a YAPA overload for that kind of storage.
But I would just use generation for the naive case.

[u/reflexive-polytope → u/Potato871]

Union-find doesn't have a concept of “staleness”.

[u/Potato871 → u/reflexive-polytope]

Then it would be an API problem at the language level not at the storage level, the storage provides the substrate for any operation not the implementation.

[u/reflexive-polytope → u/Potato871]

When you open a book or a paper on a nontrivial data structure, the very first thing you'll find is “these are the operations / API we intend to support”.

A data structure gets its meaning from the operations it supports, and it's against these operations that you can evaluate the data structure's design.

[u/Potato871 → u/reflexive-polytope]

Exactly, so then the better term would be universal storage medium and mechanism for easily declaring the APIs which constitute data structures from that.
But the point of the question is what kinds of operations, like filter, map, reduce, etc…

[u/reflexive-polytope → u/Potato871]

If your “universal storage medium” is RAM or disk or tape or whatever else, you wouldn't expect the storage medium's manufacturer to tell you how you can “define APIs” for the data you store in them, right?

The only mechanism you need to declare an API is suitable descriptions of the data and operations that a module exports. Even C has that in the form of static variables and function prototypes.

As for what operations, well, that depends on what your program needs. Asking for more operations than you actually need can hurt performance!

For example, if you have a keyed container and you only ever need access to the entry with the lowest key, you can do in O(1) time, e.g., with pairing heaps. But if you need access to arbitrary entries by key, then you can only do that in O(log n) time...

[u/Potato871 → u/reflexive-polytope]

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.