How can I implement a dictionary whose value is also a key?

Question

Essentially, I want a data structure that resembles Dictionary, but having a difference that its values are also unique. In another words, it depicts a one to one relationship rather than one to many.

An example should explain better. Suppose I call this new data structure MyMapping, and I want to save names of married couples in it:

        MyMapping<string, string> myMapping = new MyMapping<string, string>();
        myMapping.Add("Joe", "Ann");
        myMapping.Add("Ann", "Joe");// not allowed
        myMapping.Add("Joe", "Mary");// not allowed
        myMapping.Add("William", "Katie");// ok
        string partner = myMapping["Ann"];// result is Joe
        partner = myMapping["Joe"];//result is Ann

Note that in this particular sample it may be better to have `Dictionary` and map both names to the same `Couple` object when you add one... — Alexei Levenkov, Aug 05 '13 at 21:38
+1 to Alexei's answer, but even still, there is more than 1 "Joe" in the world, so you may want something like `Dictionary>` — lukegravitt, Aug 05 '13 at 22:02
As Hans Passant said, use two dictionaries. You can wrap it into one class as shown here http://stackoverflow.com/a/255638/187697 — keyboardP, Aug 05 '13 at 22:17
@lukegravitt but second addition of Joe is disallowed (see Joe, Mary entry). So Joe only gets one mapping. — Amy B, Aug 06 '13 at 01:14
I thought you want to say that:myMapping.Add("Joe", "Ann"); myMapping.Add("newKwy", "Ann");// not allowed as per description — AKS, Aug 06 '13 at 11:15

score 1 · Accepted Answer · edited May 23 '17 at 10:25

1

what you're looking for is also called a Two-way dictionary. Take a look at other SO answers to the same question.

edited May 23 '17 at 10:25

Community

1
1

answered Aug 05 '13 at 21:33

vlad

4,748
2
30
36

After reading the answer I realized that it's a bit different. The data structre he wrote allows myMapping.Add("Joe", "Ann"); myMapping.Add("Ann", "Joe");// not allowed But I can start from there. Thanks! – GoCurry Aug 05 '13 at 21:45

score 1 · Answer 2 · answered Aug 06 '13 at 01:41

I started building a TwoWayDictionary for you based on IDictionary http://msdn.microsoft.com/en-us/library/s4ys34ea.aspx

//only one generic parameter needed, as key and value have same type.
public class TwoWayDictionary<TKey> : IDictionary<TKey, TKey>
{
  private Dictionary<TKey, TKey> _primary;
  private Dictionary<TKey, TKey> _secondary;

  public TwoWayDictionary()
  {
    _primary = new Dictionary<TKey, TKey>();
    _secondary = new Dictionary<TKey, TKey>();
  }

  public int Count {get{return _primary.Count;}}
  public bool IsReadOnly {get{return _primary.IsReadOnly;}}
  public TKey this[TKey key]
  {
    get
    {
      return this.GetValue(key);
    }
    set
    {
      this.Add(key, value);
    }
  }
  public ICollection<TKey> Keys {get {return _primary.Keys;}}
  public ICollection<TKey> Values {get {return _primary.Values;}}

  private TKey GetValue(TKey key)
  {
    if (_primary.ContainsKey(key))
    {
      return _primary[key];
    }
    if (_secondary.ContainsKey(key))
    {
      return _secondary[key];
    }
    throw new KeyNotFoundException("key is not found");
  }

  public void Add(KeyValuePair<TKey, TKey> item)
  {
    this.Add(item.Key, item.Value);
  }

  public void Add(TKey key, TKey value)
  {
    if (key == null || value == null)
    {
      throw new ArguementNullException("key or value is null");
    }
    if (_primary.ContainsKey(key) || _secondary.ContainsKey(key)
      || _primary.ContainsKey(value) || _secondary.ContainsKey(value))
    {
      throw new ArgumentException("Item with same key or value already exists");
    }
    _primary.Add(key, value);
    _secondary.Add(value, key);
  }

  public void Clear()
  {
    _primary.Clear();
    _secondary.Clear();
  }

  public void Contains(KeyValuePair<TKey, TKey> item)
  {
    return _primary.Contains(item) || _secondary.Contains(item);
  }

  public void ContainsKey(TKey key)
  {
    return _primary.ContainsKey(key) || _secondary.ContainsKey(key);
  }

  public void CopyTo(KeyValuePair<TKey, TKey>[] array, int arrayIndex)
  {
    return _primary.CopyTo(array, arrayIndex);
  }

... TODO finish implementing IDictionary

BartoszKP · Answer 3 · 2013-08-06T13:19:07.260

Two dictionaries are not necessary - a dictionary with a HashSet will suffice. The HashSet will of course hold and guard the values.

EDIT: additional explanation regarding question in the comment

The new collection would consist of an instance of a Dictionary and a HashSet, like this:

class UniqueValueDictionary<TKey, TValue>
{
//...
private Dictionary<TKey, TValue> dictionary;
private HashSet<TValue> valueSet;
}

When inserting to the dictionary you verify if the value already exists:

public void Add(TKey key, TValue value)
{
if (valueSet.Contains(value))
{
//throw appropriate exception
}

dictionary.Add(key, value);
valueSet.Add(value);
}

When removing:

public void Remove(TKey key)
{
//check if key exists, throw exception if not
var value = dictionary[key];
dictionary.Remove(key);
valueSet.Remove(value);
}

That hashset will be for each value, or for all values? I mean will you verify value in that hashset before inserting record in Dictionary? — AKS, Aug 06 '13 at 11:23

How can I implement a dictionary whose value is also a key?

3 Answers3