Data structure for two way mapping

Question

Now, before you scold me, I know there's a very similar question:

Best data structure for two way mapping?

In fact, I am looking for a data structure that will accomplish the same thing. Specifically, I have a string that should be mapped to another string, and that other string should also be mapped to the original string.

For instance:

".jpg" -> "image/jpeg"
"image/jpeg" -> ".jpg"

The linked question suggest the use of some kind of hashmap or Dictionary<string,string> to accomplish this.

One would have a custom data type that will hold two dictionaries, each dictionary being one way of mapping. This will provide with O(1), but i find it not scalable at all.

Considering that I have a Dictionary with all the mappings from 200 MIME types to the associated file extension, I would need to create a similar one, with the same content but inversed. This is very prone to typos, or missing keys, and is a lot of duplicated code.

Although the linked question aims for a solution in Java, I am looking for a solution in C#.

Is there a .NET data structure that supports these kind of two way mapping between objects?

If there is not, how can I accomplish this without replicating code (as in the two dictionaries solution)?

In theory you want something like `dictionary.Add(".jpg", "image/jpg")`, and able to use it as `var mime = dictionary[".jpg"]` and `var ext = dictionary["image/jpg"]`? — Dave Zych, Sep 18 '15 at 17:58
seems kind of pointless, because you would still be explicitly mapping those relationships already.. — Brett Caswell, Sep 18 '15 at 18:03
@BrettCaswell I have no problem creating the map manually. However, I don't want to create the map twice — Matias Cicero, Sep 18 '15 at 18:04
I don't know how abstract you're code is going to be, but this pattern is undesireable for me: I'll provide a linq approach. — Brett Caswell, Sep 18 '15 at 18:16
Sometimes simple is better; Assuming the contents of the lookups are runtime static, use code generation to take a source and create the normal/reverse dictionaries. — Trevor Ash, Sep 18 '15 at 18:09

Dave Zych · Accepted Answer · 2015-09-18T18:37:20.763

Why wouldn't a custom type with two dictionaries work? Although it will use double the memory, it allows for O(1) lookup and should work as you want.

However, when it comes to the generic parameters, it can get a bit hairy. If you specify the same type it's not a problem, however if you specify a different type the indexer breaks because you can only get a value out one way. If you overload the indexer and have two, i.e.:

public K this[T value]
public T this[K value]

It will break if you have the same arguments because it won't be able to resolve. In that case, I would suggest having two different classes:

public class TwoWayDictionary<T>
{
    private Dictionary<T, T> _first;
    private Dictionary<T, T> _second;

    public TwoWayDictionary()
    {
        _first = new Dictionary<T, T>();
        _second = new Dictionary<T, T>();
    }

    public void Add(T first, T second)
    {
        _first.Add(first, second);
        _second.Add(second, first);
    }

    public T this[T value]
    {
        get
        {
            if(_first.ContainsKey(value))
            {
                return _first[value];
            }
            if(_second.ContainsKey(value))
            {
                return _second[value];
            }

            throw new ArgumentException(nameof(value));
        }
    }
}

and

public class TwoWayDictionary<T, K>
{
    private readonly Dictionary<T, K> _first;
    private readonly Dictionary<K, T> _second;

    public TwoWayDictionary()
    {
        _first = new Dictionary<T, K>();
        _second = new Dictionary<K, T>();
    }

    public void Add(T first, K second)
    {
        _first.Add(first, second);
        _second.Add(second, first);
    }

    public K this[T value]
    {
        get
        {
            if (_first.ContainsKey(value))
            {
                return _first[value];
            }

            throw new ArgumentException(nameof(value));
        }
    }

    public T this[K value]
    {
        get
        {
            if (_second.ContainsKey(value))
            {
                return _second[value];
            }

            throw new ArgumentException(nameof(value));
        }
    }
}

This will allow you to use it like mentioned in the comments:

var dict = new TwoWayDictionary<string>();
dict.Add(".jpg", "image/jpg");
var mime = dict[".jpg"];
var ext = dict["image/jpg"];

and specify 2 different types if you want:

var dict = new TwoWayDictionary<string, int>();
dict.Add(".jpg", 100);
var number = dict[".jpg"];
var ext = dict[100];

I'm for it. The only thing I don't like is the duality of the indexer. I would rather expose 2 separate methods like `string GetFirst(string second)` and `string GetSecond(string first)` — Ivan Stoev, Sep 18 '15 at 18:10
@IvanStoev exposing two separate indexers would almost defeat the purpose of the class entirely. If doing that, you would have to do a contains/null check outside of the class. In that case, why even have the class - why not just have 2 dictionaries and check for existence in each of them. — Dave Zych, Sep 18 '15 at 18:15
I dont' think so. The main benefit of this class I see is the **encapsulation**. Also imagine you introduce generic arguments like TwoWayDictionary. What will be the signature of your indexer then? Btw, I upvoted your answer, so we are at one and the same side :-) — Ivan Stoev, Sep 18 '15 at 18:20
@IvanStoev I agree with you about the generic types and indexers. That gets hairy. — Dave Zych, Sep 18 '15 at 18:25

Data structure for two way mapping

1 Answers1