Data-Structure with mult. keys

Please specify the language of interest.

If it's C++...
You can do this with a key containing many fields, in an ordinary std::map. I've used use NULL to mean 'match any', and have provided a comparison operator which will always match NULLs with anything.
I'm only storing int's as the object to be looked up, but you could obviously store anything.
You'll perhaps want to use a nicer string class, or at least make sure you take care of memory allocation in a real program. I'm just relying on storing pointers to static constant strings.

struct keydata {    LPCSTR keys[3];    keydata() {        keys[0] = keys[1] = keys[2] = NULL;    }    keydata(LPCSTR k1) {        keys[0] = k1;        keys[1] = keys[2] = NULL;    }    keydata(LPCSTR k1, LPCSTR k2) {        keys[0] = k1;        keys[1] = k2;        keys[2] = NULL;    }    keydata(LPCSTR k1, LPCSTR k2, LPCSTR k3) {        keys[0] = k1;        keys[1] = k2;        keys[2] = k3;    }    bool operator < {const keydata &rhs) const {        for (int i=0; i<sizeof(keys)/sizeof(keys[0]); ++i)            if (keys != NULL && rhs.keys != NULL)                return strcmp(keys, rhs.keys) < 0;        return false;    }};int main(){    typedef std::map<keydata, int> myMapT;    myMapT mymap;//Insertion    mymap[keydata("key1", NULL, "key3")] = 7;    mymap[keydata(NULL, "key2")] = 42;//Lookup    myMapT::iterator lookup1 = mymap.find(keydata("key1", NULL, "key3"));    if (lookup1 != mymap.end())        cout << lookup1->second;    myMapT::iterator lookup2 = mymap.find(keydata(NULL, "key2", NULL));    if (lookup2 != mymap.end())        cout << lookup2->second;}

However, I'm not sure what would happen if you search for a key of all NULLs, as it would match anything, but you would probably get any random match from the map, rather than just the first. The same goes for any search which has more than one possible answer - the result is undefined.
Disclaimer: I have not tested the above code.

Edit: Aw crap, the above two inserted keys would compare as equal so this isn't going to work with a map, may need a multimap. Well hopefully it presents some useful ideas anyway.
How do you wish to handle the possibility that the lookup may have more than 1 successful match anyway?

[Edited by - iMalc on December 9, 2005 1:12:40 PM]

Thanks for the reply, I'm not sure if this works? I want to implement the data-structure by hand using C. So I need a hint what algorithm to use.

The problem is that every key-component of a node may be a wildcard.
So in your example the keys ("key1", "whatever", "key3") or ("key1", "foo", "key3") or ("key1", "hello world", "key3") would match ("key1", NULL, "key3") where NULL means "match any string without comparing".
If there are more than one matches, all of them should be returned.
I.e.
("a" , "b" , "c") should match (return) the nodes ("a" , NULL , "c") and (NULL , NULL , "c") and ("a" , "b" , "c")

bye
Chris

I would suggest using a "dictionary" (probably a balanced tree or hash map) of keys where each key has a list (probably of the linked variaty, dynamic array would also do) containing all the nodes & position of the key
Nodes then become lists of pointers to keys.

Doing a lookup is as easy as doing N lookups into your dictionary.

For your example:

dictionary:

(id, key, node list)0, "key1", {{0,0}}1, "key2", {{1,0}2, "key3", {{0,2}}

nodes:

(id, members)0, {0, 2}1, {1}

say we want to lookup ["key1", "key2", "fish stick"]
Then we do:
lookup "key1" and examine it's node list for entries where it's first, that gives node 0.

lookup "key2" in the same way, that gives us node 1.

"fish stick" not found in dictionary, or no matchin node so ignore.

Then we have the node-set {0,1}.

You probably want to keep the nodelists sorted to avoid a linear search through them when doing positional matching.

Thanks, I'll try it!