What data structure is this?

[MK27]

Take a list of key-value pairs, or an array of value-value pairs. By "key" I mean a value which is unique, whereas a normal value may be duplicated. So a value-value pair would indicated neither value is necessarily unique within the context of the list.

I'm now thinking of a linked list that orders by both values, so eg:

struct node {
    int A;
    int B;
    struct node *nextA;
    struct node *nextB;
};

A list like this would have two heads and an insertion would place the node in ordered sequence based on both values (meaning there are two distinct sequences). The list could then be walked according to either ordering. Eg, given...

...can't use set notation outside code tags >_<
{2,3}, {666,-11} and {1024,0}:

Order A        Order B
{2,3}         {666,-11}
{666,-11}     {1024,0}
{1024, 0}     {2,3}

When I've done that before, it's been fine to just concoct order B on the fly when needed, but I'm surprised I've never heard of a generic data structure which spends some memory to maintain both orders.

It must have a name? (If not, I kind of like n-braid, because this could have any number of orders beyond 2).

[phantomotap]

You have heard of such a data structure, but you don't realize it because few handy names exist for the algorithms involved. (The names aren't like "linked list" or "b-tree"; those names are of the form "Designer1-Designer2...DesignerN". That said, most seem based on arrangements of "b+trees" and shadowing techniques.)

What you have there is a database table having three rows of two unnamed columns sorted by two indexes. (I'm not talking about an SQL database. That is an option, but SQL is a layer that lives on the database techniques used in a lot of other areas.)

The cost of creating and maintaining your "n-braid" (I like that name too. ^_^) as "n" grows is prohibitive. (Yes, homogenous data for table columns can live in a linear buffer like a vector allowing simple row sorting by index. Data structures designed for that purpose just perform better.) If you put the work into storing values for column entries in a shared container that the index references you'll very likely be satisfied for small values of "n". If you expect to work with larger values of "n" you'll be kicking yourself later if you don't try a database system like "BerkleyDB" or possibly a "SQL". (Of course, this only applies to the implied implementation which you may have already changed. The idea itself is ubiquitous.)

I can find the names of my favorite books on database algorithms and data structures if you want.

Soma

[bernt]

There is also Boost.MultiIndex (which is modeled after database ideas, but with a more STL-like interface).

[MK27]

There is also Boost.MultiIndex (which is modeled after database ideas, but with a more STL-like interface).

Looks nice! At a glance, this is exactly what I had in mind, ultimately -- a generic/OO interface that allows for "ordered indices...classified into unique, which prohibit two elements to have the same key value, and non-unique indices, which allow for duplicates" (from Tutorial: Basics). It might also be useful to reject nodes that are identical (ie, don't enforce unique keys, but unique nodes).

Anyone who's made use of MultiIndex got a comment?

Also interested to learn that this is intimately involved in database design.

You have heard of such a data structure, but you don't realize it because few handy names exist for the algorithms involved. (The names aren't like "linked list" or "b-tree"; those names are of the form "Designer1-Designer2...DesignerN". That said, most seem based on arrangements of "b+trees" and shadowing techniques.)

Trees would obviously be better than lists, esp. since I think the list ends up needing prev and next pointers for each order, which might as well be left and right. What's "shadowing techniques"?

The cost of creating and maintaining your "n-braid" (I like that name too. ^_^) as "n" grows is prohibitive.

No doubt. I think most uses for this would be n = 2, because sorting a key-value pair by value is common. But if it were opened up, maybe I would start to see applications for n = 3, n = 4. Beyond that, like you say, I'd be nervous (not to mention, exhausted), and would thank creation for relational databases.

I know almost nothing about quantum computing, but I wonder if this is something that would fly particularly well there?

I can find the names of my favorite books on database algorithms and data structures if you want.

Sure. I probably won't be reading rushing out to the library this week (the original motivation is a simple n = 2 thing and more or less complete now) but stuff like that sticks in my memory.

[CornedBee]

I know almost nothing about quantum computing, but I wonder if this is something that would fly particularly well there?

No. Quantum computing is about taking many computation paths at once, not overlaying different data structures.

I'd call your data structure "two intrusive, ordered linked lists sharing nodes". N-braid sounds pretty cool, though.

I've used MultiIndex. Error messages are hell, compile time suffers, and updating nodes is annoying, but other than that it's pretty cool.

[brewbuck]

Ah. You've implemented a resource mesh. This is used to implement such things as WaitForMultipleObjects() in Windows, or select() in UNIX.

The mesh has a head row and a head column. The head row represents all processes who wait for resources, the head column represents all resources on which processes are waiting. A node in the mesh represents a specific process waiting for a specific resource. By navigating the mesh column-wise, you can, from one process/resource pair, find the next resource on which the process waits. Or by navigating row-wise, from one process/resource pair, find the next process who waits on the resource.