none
BijectiveDictionary RRS feed

  • General discussion

  • Hello. I need an advise, how can i make a Dictionary, which's bijective, that mean

    dict[Key] == Value      =>      dict[Value] == Key

    so how? I have 2 realisations, but i don't like them.

    1st

        class BijectiveDictionary<T> : Dictionary<T,T>
        {
            public new void Add(T x, T y)
            {
                base.Add(x,y);
                base.Add(y,x);
            }
     
            public new void Remove(T x)
            {
                base.Remove(this[x]);
                base.Remove(x);
            }
        }

    2nd

        class BijectiveDictionary<T> : Dictionary<T,T>
        {
            public new T this[T index]
            {
                get
                {
                    if (ContainsKey(index))
                        return base[index];
                    if (ContainsValue(index))
                        return this.FirstOrDefault(x => index.Equals(x.Value)).Key;
                    throw new KeyNotFoundException("index");
                }
            }
        }

    Using

    using System;
    using System.Linq;
    using System.Collections.Generic;
    
    namespace DictTest
    {
        class Program
        {
            static void Main()
            {
                var dict = new BijectiveDictionary<char>();
                dict.Add('+','-');
                Console.WriteLine("Inverse of {0} is {1}", '+' ,dict['+']);
                Console.WriteLine("Inverse of {0} is {1}", '-', dict['-']);
                dict.Remove('+');
                Console.ReadKey();
    
            }
        }
    }

    So how to improve this code?



    • Edited by PsilonRus Thursday, January 17, 2013 6:57 PM
    • Changed type Mike FengModerator Monday, February 4, 2013 5:19 AM For more options
    Thursday, January 17, 2013 6:56 PM

All replies

  • I think it really depends on how the collection will be used.

    Do you need to favor speed of lookups, or memory consumption?

    Which will you do more:  iterate over all of the elements of the collection, or add/remove/lookup elements of the collection?


    Reed Kimble - "When you do things right, people won't be sure you've done anything at all"

    Thursday, January 17, 2013 8:38 PM
    Moderator
  • Hi Psilon,

    Would you like to follow up?

    Best regards,


    Ghost,
    Call me ghost for short, Thanks
    To get the better answer, it should be a better question.

    Friday, January 18, 2013 5:02 PM
  • not now, but soon :D
    Friday, January 18, 2013 5:31 PM
  • I dunno how to improve it.
    Saturday, January 26, 2013 9:38 PM
  • Hi Psilon,

    Would you like to answer Reed's question first?

    Have a nice day.


    Ghost,
    Call me ghost for short, Thanks
    To get the better answer, it should be a better question.

    Monday, January 28, 2013 6:17 AM
  • I prefer to left this question opened : both variantes are bads.
    Monday, January 28, 2013 6:23 AM
  • If so, change the thread type to disscussion will be recommended.

    Good luck.


    Ghost,
    Call me ghost for short, Thanks
    To get the better answer, it should be a better question.

    Monday, January 28, 2013 6:47 AM
  • I prefer to left this question opened : both variantes are bads.

    No, not mark an answer, tell us the answer to this question:

    "Which will you do more:  iterate over all of the elements of the collection, or add/remove/lookup elements of the collection?"


    Reed Kimble - "When you do things right, people won't be sure you've done anything at all"

    Monday, January 28, 2013 3:18 PM
    Moderator
  • It's just a trade off, nothing inherently wrong really. The first will be faster, as both key and value are indexed, but seeing as you index both, it costs more memory.

    The second will be slower, but more memory efficient.

    Insertions/removes are faster in 2).

    In short... use the first if you value fast lookups more than memory use, use the second if you value less memory use over lookup performance.


    Tuesday, January 29, 2013 6:53 AM
  • "both variantes are bads."

    That's sort of true but you don't have many options left.

    In fact there's only one remaining option: to implement it from scratch, without using the Dictionary class. But it's a lot more work to do that and the savings in memory usage will be small. Basically the savings come from storing the key/value pair once instead of twice like it happens in case 1 of your post. For the 'char' keys we're talking about saving 4 bytes per key/value pair...

    Also, if you do choose to use a Dictionary to implement this then you should not inherit from Dictionary. In the first case it's very easy to break the bijective property by calling Dictionary's Add/Remove methods instead of calling the "new" ones. In the second case you have a similar problem, using Dictionary's indexer instead of the "new" one will give a different result...

    Tuesday, January 29, 2013 7:31 AM
    Moderator