29

I used to code in C++ and now I try to program in C.

Assume I have defined a struct

struct point{
    int x;
    int y;
}

Is there any data structure A in c that can support the following functionality: Given two integers, say i and j, and two points, say p1 and p2. A[i][j][p1][p2] can uniquely determine a value.

It sounds like a 4-d array. However, indexes are no longer a int, but user-defined struct.

Cœur
  • 37,241
  • 25
  • 195
  • 267
user3341338
  • 423
  • 1
  • 4
  • 6
  • Why not just create a hashing function for your points and use that as an index? – ccKep Feb 22 '14 at 18:11
  • There is no fancy data structure in C. You have to reinvent the wheel for yourself or go back to C++ ! – hivert Feb 22 '14 at 18:18
  • There is nothing like this in C. You can't define operators in C. The closest thing you can have is a custom hash function that you use to index into an array, or something similar. The point is: you are pretty much tied to built-in types and have to invent everything yourself. – Filipe Gonçalves Feb 22 '14 at 18:20
  • It looks like a *six*-dimensional array of sorts... – Kerrek SB Feb 22 '14 at 18:24
  • 3
    As others have said: Either go looking for "hashtable code in C", or look up the basics of hashtables and implement one de novo. It isn't that difficult; I've implemented them several times. The main difference from the user's point of view will be that rather than saying `myHashTable.put(key,value)` you'll need to say `putToHashTable(myHashTable,key,value)` and so on. (Unless you want to really reinvent OO and start building method dispatch into your objects -- which is possible but overkill for this simple case.) – keshlam Feb 22 '14 at 18:34

1 Answers1

57

You'll probably have to make your own structure. The C Programming Language by Kernighan and Ritchie has an example of making an associate map in c, and what I'll detail below is based on what I remember from that.

Basically you'll need a struct Map that contains struct Key and struct Value.

struct Map {
    struct Key key;
    struct Value value;
};

struct Key contains elements that determine the value (in your case 2 points and 2 ints)

struct Key {
    struct point p1;
    struct point p2;
    int i;
    int j;
};

struct Value is whatever you want your key to point to (you didn't say)

You now have a struct Map that associates your four inputs with a value, but a single map isn't that useful. You're going to want a whole array of them.

struct Map map[SIZE_OF_MAP];

If you don't want to linearly search the array for the Map struct you're looking for, you can make a hashing function that will bring you directly to it. Just define a function that takes the key and uses its value to assign it an index in the array. Use the hash to place the Map in the array and retrieve it from the array. (Note: I'm unsure if this is a correct example of hashing, please correct if this is completely wrong)

int get_hash(Key *key)
{
    int result;
    /* combine all inputs in some way */
    result = key->i * key->i + (key->p1.x * key->p1.x) - (key->p2.x * key->p2.x)
    /* make sure result isn't out of bounds of the array */
    return (result % SIZE_OF_MAP);
}

If you use the hashing function you'll have to consider collisions (what happens when two keys give the same result for get_hash). When you use your array of Maps you'll need some form of collision resolution.

gslavin
  • 701
  • 6
  • 4