What datastructure should I use?

Question

I have an issue where I need to map two inputs to a single output.

I'm aware that a dictionary is a generically typed linear mapping:

for every x (key) there may be a y (value)

What I need is a multi-dimensional mapping:

for every x,y (key) there may be a z (value)

But of course the kicker is that I need it to support generic typing and be dynamically sized.

Does this data-structure exist in C#, or do I have to create a dictionary of dictionaries? I'd rather not reinvent the wheel if I don't have to.

Reinventing the wheel:

using System;
using System.Collections.Generic;
using System.Text;

namespace zlib.Collections
{
    public class Dictionary3D<Tx, Ty, Tz>
    {
        private Dictionary<Tuple<Tx, Ty>, Tz> _dict = new Dictionary<Tuple<Tx, Ty>, Tz>();

        public void Add(Tx x, Ty y, Tz z)
        {
            _dict.Add(Tuple.Create<Tx, Ty>(x, y), z);
        }

        public void Clear()
        {
            _dict.Clear();
        }

        public bool ContainsKey(Tx x, Ty y)
        {
            return _dict.ContainsKey(Tuple.Create<Tx, Ty>(x, y));
        }

        public bool ContainsValue(Tz z)
        {
            return _dict.ContainsValue(z);
        }

        public Dictionary<Tuple<Tx, Ty>, Tz>.Enumerator GetEnumerator()
        {
            return _dict.GetEnumerator();
        }

        public bool Remove(Tx x, Ty y)
        {
            return _dict.Remove(Tuple.Create<Tx, Ty>(x, y));
        }

        public bool TryGetValue(Tx x, Ty y, out Tz z)
        {
            return _dict.TryGetValue(Tuple.Create<Tx, Ty>(x, y), out z);
        }

        public int Count
        {
            get { return _dict.Count; }
        }

        public Dictionary<Tuple<Tx,Ty>,Tz>.KeyCollection Keys
        {
            get
            {
                return _dict.Keys;
            }
        }

        public Dictionary<Tuple<Tx, Ty>, Tz>.ValueCollection Values
        {
            get
            {
                return _dict.Values;
            }
        }

        public Tz this[Tx x, Ty y]
        {
            get
            {
                return _dict[Tuple.Create<Tx, Ty>(x, y)];
            }
            set
            {
                _dict[Tuple.Create<Tx, Ty>(x, y)] = value;
            }
        }
    }
}

It seems like reinventing the wheel is winning out among responses. This is the code I've come up with so far, but I feel like there should be a better way, like a matrix or something.

is the type of key the same for both x and y? can you explain how you need generic typing for a key? heterogeneous key? — DarthVader, Oct 21 '11 at 21:52
@DarthVader, the type for the keys could be the same in some circumstances, but it wont always be. — zzzzBov, Oct 21 '11 at 21:59
I suppose i should also specify, the type of the key will be specific to the instance of the multi-dimensional object. Ideally I'd be able to write `new Dictionary3D();` and have it work just as well as `new Dictionary3D();`. — zzzzBov, Oct 21 '11 at 22:03
http://stackoverflow.com/questions/689940/hashtable-with-multidimensional-key-in-c-sharp, http://stackoverflow.com/questions/1171812/multi-key-dictionary-in-c — zzzzBov, Oct 26 '11 at 14:02

score 4 · Accepted Answer · answered Oct 21 '11 at 21:55

4

what about

   Dictionary<Tuple<T,K>,Tuple<L,J>>

??

answered Oct 21 '11 at 21:55

wiero

2,176
1
19
28

After messing around with creating a custom class that acted as a wrapper, I decided that it really wasn't worth it for the little bit of code needed to create new `Tuples`. – zzzzBov Oct 25 '11 at 20:23

score 1 · Answer 2 · edited Oct 21 '11 at 21:56

1

If I get you right, that is what you need:

class Key<Tx, Ty>
{
    public Tx x;
    public Ty y;

    public Key(Tx x, Ty y)
    {
        this.x = x;
        this.y = y;
    }
}

Dictionary<Key<Tx, Ty>, Tz> d;

And yes, how mentioned in a comment, you gotta implement HashCode and Equals in that Key class.

edited Oct 21 '11 at 21:56

MusiGenesis

74,184
40
190
334

answered Oct 21 '11 at 21:53

mephisto123

1,400
13
38

Ouch, sorry, didn't know about that. – mephisto123 Oct 21 '11 at 22:19

score 1 · Answer 3 · edited May 23 '17 at 11:55

1

Tuple is probably what you want:

var population = new Tuple< string, int>("New York", 7891957);

or for generics:

var population = new Tuple< S, T>("New York", 7891957);

For Tuple a reference look here

Moreover, if you want for example user Dictionary of a Dictionary you can do like this:

using DictOfDict = Dictionary< X, Dictionary< Y, Z>> ;

For a reference look here

edited May 23 '17 at 11:55

Community

1
1

answered Oct 21 '11 at 21:58

Falcon

650
1
8
24

score 1 · Answer 4 · answered Oct 21 '11 at 22:18

The PolyDictionary that Chuck Jazdzewski wrote about awhile back might get you what you want if you use a Tuple<T1, T2> as the key. Really, it's just a wrapper around a Dictionary<object, object> but it does the trick. Check out his blog series on the topic:

score 1 · Answer 5 · answered Oct 21 '11 at 22:44

How about this:

class Dict3D
{
    private Dictionary<KeyValuePair<object,object>, object> innnerDict= new Dictionary<KeyValuePair<object,object>, object>();

    public object Get(object key1, object key2)
    {
        KeyValuePair<object,object> bigKey = new KeyValuePair<object, object>(key1, key2);
        if (innnerDict.ContainsKey(bigKey))
        {
            return innnerDict[bigKey];
        }
        return null;
    }

    public void Set(object key1, object key2, object somevalue)
    {
        KeyValuePair<object, object> bigKey = new KeyValuePair<object, object>(key1, key2);
        if (innnerDict.ContainsKey(bigKey))
        {
            innnerDict[bigKey] = somevalue;
        }
        else
        {
            innnerDict.Add(bigKey, somevalue);
        }
    }
}

You could make it a generic also, but this is a simple version.

I guess the answers mean that if you want a clean solution, you (or someone else) probably does have to reinvent the wheel.

score 0 · Answer 6 · answered Oct 21 '11 at 22:02

I think you will need a type safe heterogeneous container, which is backed by a dictionary. In this case, you will have to override IDictionary and have your own impl. Unfortunately there is no class that you can use unless you follow other answers or find a work around i guess.

See Joshua bloch in this case, you can basically store any type as the key. however you can restrict that as well.

What datastructure should I use?

Reinventing the wheel:

6 Answers6