Like Tree1Likes
  • 1 Post By MK27

What data structure is this?

This is a discussion on What data structure is this? within the Tech Board forums, part of the Community Boards category; Take a list of key-value pairs, or an array of value-value pairs. By "key" I mean a value which is ...

  1. #1
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300

    What data structure is this?

    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:

    Code:
    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...

    Code:
    ...can't use set notation outside code tags >_<
    {2,3}, {666,-11} and {1024,0}:
    Code:
    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).
    Last edited by MK27; 01-23-2012 at 06:18 AM.
    stahta01 likes this.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  2. #2
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,262
    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

  3. #3
    Just a pushpin. bernt's Avatar
    Join Date
    May 2009
    Posts
    426
    There is also Boost.MultiIndex (which is modeled after database ideas, but with a more STL-like interface).
    Last edited by bernt; 01-23-2012 at 12:17 PM.
    Consider this post signed

  4. #4
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by bernt View Post
    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.

    Quote Originally Posted by phantomotap View Post
    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"?

    Quote Originally Posted by phantomotap
    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.
    Last edited by MK27; 01-23-2012 at 03:07 PM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  5. #5
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    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.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  6. #6
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,244
    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.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. difference between data object and data structure?
    By c_lady in forum C++ Programming
    Replies: 2
    Last Post: 02-22-2011, 11:30 AM
  2. Data structure for storing serial port data in firmware
    By james457 in forum C Programming
    Replies: 4
    Last Post: 06-15-2009, 09:28 AM
  3. data structure design for data aggregation
    By George2 in forum C# Programming
    Replies: 0
    Last Post: 05-20-2008, 06:43 AM
  4. C data structure
    By chen1279 in forum C Programming
    Replies: 4
    Last Post: 09-04-2006, 06:32 PM
  5. Appropriate data structure
    By gazsux in forum Game Programming
    Replies: 3
    Last Post: 03-19-2003, 12:26 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21