Двунаправленный словарь 1 к 1 в C #

98

Я ищу общий, двунаправленный класс словаря 1 к 1 в C # (2), т.е. a, BiDictionaryOneToOne<T, S>который гарантированно содержит только одно из каждого значения и ключа (в любом случае до RefEquals), и поиск в котором можно искать, используя ключ или значение. Кто-нибудь знает об этом, или я должен просто реализовать его сам? Не могу поверить, что я первый, кому это нужно ...

В ответах на этот вопрос есть BiDictionary , но он не для уникальных элементов (а также не реализует RemoveByFirst (T t) или RemoveBySecond (S s)).

Спасибо!

Джоэл ин Гё
источник
связанные: stackoverflow.com/questions/255341/…
nawfal

Ответы:

71

Хорошо, вот моя попытка (основанная на Джоне - спасибо), заархивированная здесь и открытая для улучшения:

/// <summary>
/// This is a dictionary guaranteed to have only one of each value and key. 
/// It may be searched either by TFirst or by TSecond, giving a unique answer because it is 1 to 1.
/// </summary>
/// <typeparam name="TFirst">The type of the "key"</typeparam>
/// <typeparam name="TSecond">The type of the "value"</typeparam>
public class BiDictionaryOneToOne<TFirst, TSecond>
{
    IDictionary<TFirst, TSecond> firstToSecond = new Dictionary<TFirst, TSecond>();
    IDictionary<TSecond, TFirst> secondToFirst = new Dictionary<TSecond, TFirst>();

    #region Exception throwing methods

    /// <summary>
    /// Tries to add the pair to the dictionary.
    /// Throws an exception if either element is already in the dictionary
    /// </summary>
    /// <param name="first"></param>
    /// <param name="second"></param>
    public void Add(TFirst first, TSecond second)
    {
        if (firstToSecond.ContainsKey(first) || secondToFirst.ContainsKey(second))
            throw new ArgumentException("Duplicate first or second");

        firstToSecond.Add(first, second);
        secondToFirst.Add(second, first);
    }

    /// <summary>
    /// Find the TSecond corresponding to the TFirst first
    /// Throws an exception if first is not in the dictionary.
    /// </summary>
    /// <param name="first">the key to search for</param>
    /// <returns>the value corresponding to first</returns>
    public TSecond GetByFirst(TFirst first)
    {
        TSecond second;
        if (!firstToSecond.TryGetValue(first, out second))
            throw new ArgumentException("first");

        return second; 
    }

    /// <summary>
    /// Find the TFirst corresponing to the Second second.
    /// Throws an exception if second is not in the dictionary.
    /// </summary>
    /// <param name="second">the key to search for</param>
    /// <returns>the value corresponding to second</returns>
    public TFirst GetBySecond(TSecond second)
    {
        TFirst first;
        if (!secondToFirst.TryGetValue(second, out first))
            throw new ArgumentException("second");

        return first; 
    }


    /// <summary>
    /// Remove the record containing first.
    /// If first is not in the dictionary, throws an Exception.
    /// </summary>
    /// <param name="first">the key of the record to delete</param>
    public void RemoveByFirst(TFirst first)
    {
        TSecond second;
        if (!firstToSecond.TryGetValue(first, out second))
            throw new ArgumentException("first");

        firstToSecond.Remove(first);
        secondToFirst.Remove(second);
    }

    /// <summary>
    /// Remove the record containing second.
    /// If second is not in the dictionary, throws an Exception.
    /// </summary>
    /// <param name="second">the key of the record to delete</param>
    public void RemoveBySecond(TSecond second)
    {
        TFirst first;
        if (!secondToFirst.TryGetValue(second, out first))
            throw new ArgumentException("second");

        secondToFirst.Remove(second);
        firstToSecond.Remove(first);
    }

    #endregion

    #region Try methods

    /// <summary>
    /// Tries to add the pair to the dictionary.
    /// Returns false if either element is already in the dictionary        
    /// </summary>
    /// <param name="first"></param>
    /// <param name="second"></param>
    /// <returns>true if successfully added, false if either element are already in the dictionary</returns>
    public Boolean TryAdd(TFirst first, TSecond second)
    {
        if (firstToSecond.ContainsKey(first) || secondToFirst.ContainsKey(second))
            return false;

        firstToSecond.Add(first, second);
        secondToFirst.Add(second, first);
        return true;
    }


    /// <summary>
    /// Find the TSecond corresponding to the TFirst first.
    /// Returns false if first is not in the dictionary.
    /// </summary>
    /// <param name="first">the key to search for</param>
    /// <param name="second">the corresponding value</param>
    /// <returns>true if first is in the dictionary, false otherwise</returns>
    public Boolean TryGetByFirst(TFirst first, out TSecond second)
    {
        return firstToSecond.TryGetValue(first, out second);
    }

    /// <summary>
    /// Find the TFirst corresponding to the TSecond second.
    /// Returns false if second is not in the dictionary.
    /// </summary>
    /// <param name="second">the key to search for</param>
    /// <param name="first">the corresponding value</param>
    /// <returns>true if second is in the dictionary, false otherwise</returns>
    public Boolean TryGetBySecond(TSecond second, out TFirst first)
    {
        return secondToFirst.TryGetValue(second, out first);
    }

    /// <summary>
    /// Remove the record containing first, if there is one.
    /// </summary>
    /// <param name="first"></param>
    /// <returns> If first is not in the dictionary, returns false, otherwise true</returns>
    public Boolean TryRemoveByFirst(TFirst first)
    {
        TSecond second;
        if (!firstToSecond.TryGetValue(first, out second))
            return false;

        firstToSecond.Remove(first);
        secondToFirst.Remove(second);
        return true;
    }

    /// <summary>
    /// Remove the record containing second, if there is one.
    /// </summary>
    /// <param name="second"></param>
    /// <returns> If second is not in the dictionary, returns false, otherwise true</returns>
    public Boolean TryRemoveBySecond(TSecond second)
    {
        TFirst first;
        if (!secondToFirst.TryGetValue(second, out first))
            return false;

        secondToFirst.Remove(second);
        firstToSecond.Remove(first);
        return true;
    }

    #endregion        

    /// <summary>
    /// The number of pairs stored in the dictionary
    /// </summary>
    public Int32 Count
    {
        get { return firstToSecond.Count; }
    }

    /// <summary>
    /// Removes all items from the dictionary.
    /// </summary>
    public void Clear()
    {
        firstToSecond.Clear();
        secondToFirst.Clear();
    }
}
Джоэл ин Гё
источник
1
В качестве предложения я думаю, что для большей надежности вам нужно рассматривать все операции как эквивалент транзакции SQL. Например, что происходит с общим состоянием словаря в Add (), если firstToSecond.Add () вызывает исключение?
Peter M
К сожалению, это должно было быть о том, что произойдет, если secondToFirst, Add () завершится ошибкой / вызовет исключение.
Peter M
1
Я счел полезным добавить атрибут [Serializable] (например, для сохранения в сеансе)
Майкл Фрейдгейм,
6
Пожалуйста, загрузите в NuGet!
Шимми Вайцхандлер
1
@aolszowka лучше заплатить штраф, чем использовать исключения в качестве логического механизма. Правило - ловить исключения следует в исключительных случаях. Кстати, в случае, если исключения перехватываются несколько раз в цикле, проверка существования выполняется быстрее .
nawfal
16

Более полная реализация двунаправленного словаря:

  • Поддерживает практически все оригинальные интерфейсыDictionary<TKey,TValue> (кроме инфраструктурных):
    • IDictionary<TKey, TValue>
    • IReadOnlyDictionary<TKey, TValue>
    • IDictionary
    • ICollection<KeyValuePair<TKey, TValue>> (этот и ниже являются базовыми интерфейсами вышеупомянутых)
    • ICollection
    • IReadOnlyCollection<KeyValuePair<TKey, TValue>>
    • IEnumerable<KeyValuePair<TKey, TValue>>
    • IEnumerable
  • Сериализация с использованием SerializableAttribute.
  • Просмотр отладки с использованием DebuggerDisplayAttribute(с информацией о количестве) и DebuggerTypeProxyAttribute(для отображения пар ключ-значение в часах).
  • Обратный словарь доступен как IDictionary<TValue, TKey> Reverseсвойство, а также реализует все упомянутые выше интерфейсы. Все операции с одним из словарей изменяют оба.

Использование:

var dic = new BiDictionary<int, string>();
dic.Add(1, "1");
dic[2] = "2";
dic.Reverse.Add("3", 3);
dic.Reverse["4"] = 4;
dic.Clear();

Код доступен в моей частной платформе на GitHub: BiDictionary (TFirst, TSecond) .cs ( постоянная ссылка , поиск ).

Копия:

[Serializable]
[DebuggerDisplay ("Count = {Count}"), DebuggerTypeProxy (typeof(DictionaryDebugView<,>))]
public class BiDictionary<TFirst, TSecond> : IDictionary<TFirst, TSecond>, IReadOnlyDictionary<TFirst, TSecond>, IDictionary
{
    private readonly IDictionary<TFirst, TSecond> _firstToSecond = new Dictionary<TFirst, TSecond>();
    [NonSerialized]
    private readonly IDictionary<TSecond, TFirst> _secondToFirst = new Dictionary<TSecond, TFirst>();
    [NonSerialized]
    private readonly ReverseDictionary _reverseDictionary;

    public BiDictionary ()
    {
        _reverseDictionary = new ReverseDictionary(this);
    }

    public IDictionary<TSecond, TFirst> Reverse
    {
        get { return _reverseDictionary; }
    }

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

    object ICollection.SyncRoot
    {
        get { return ((ICollection)_firstToSecond).SyncRoot; }
    }

    bool ICollection.IsSynchronized
    {
        get { return ((ICollection)_firstToSecond).IsSynchronized; }
    }

    bool IDictionary.IsFixedSize
    {
        get { return ((IDictionary)_firstToSecond).IsFixedSize; }
    }

    public bool IsReadOnly
    {
        get { return _firstToSecond.IsReadOnly || _secondToFirst.IsReadOnly; }
    }

    public TSecond this [TFirst key]
    {
        get { return _firstToSecond[key]; }
        set
        {
            _firstToSecond[key] = value;
            _secondToFirst[value] = key;
        }
    }

    object IDictionary.this [object key]
    {
        get { return ((IDictionary)_firstToSecond)[key]; }
        set
        {
            ((IDictionary)_firstToSecond)[key] = value;
            ((IDictionary)_secondToFirst)[value] = key;
        }
    }

    public ICollection<TFirst> Keys
    {
        get { return _firstToSecond.Keys; }
    }

    ICollection IDictionary.Keys
    {
        get { return ((IDictionary)_firstToSecond).Keys; }
    }

    IEnumerable<TFirst> IReadOnlyDictionary<TFirst, TSecond>.Keys
    {
        get { return ((IReadOnlyDictionary<TFirst, TSecond>)_firstToSecond).Keys; }
    }

    public ICollection<TSecond> Values
    {
        get { return _firstToSecond.Values; }
    }

    ICollection IDictionary.Values
    {
        get { return ((IDictionary)_firstToSecond).Values; }
    }

    IEnumerable<TSecond> IReadOnlyDictionary<TFirst, TSecond>.Values
    {
        get { return ((IReadOnlyDictionary<TFirst, TSecond>)_firstToSecond).Values; }
    }

    public IEnumerator<KeyValuePair<TFirst, TSecond>> GetEnumerator ()
    {
        return _firstToSecond.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator ()
    {
        return GetEnumerator();
    }

    IDictionaryEnumerator IDictionary.GetEnumerator ()
    {
        return ((IDictionary)_firstToSecond).GetEnumerator();
    }

    public void Add (TFirst key, TSecond value)
    {
        _firstToSecond.Add(key, value);
        _secondToFirst.Add(value, key);
    }

    void IDictionary.Add (object key, object value)
    {
        ((IDictionary)_firstToSecond).Add(key, value);
        ((IDictionary)_secondToFirst).Add(value, key);
    }

    public void Add (KeyValuePair<TFirst, TSecond> item)
    {
        _firstToSecond.Add(item);
        _secondToFirst.Add(item.Reverse());
    }

    public bool ContainsKey (TFirst key)
    {
        return _firstToSecond.ContainsKey(key);
    }

    public bool Contains (KeyValuePair<TFirst, TSecond> item)
    {
        return _firstToSecond.Contains(item);
    }

    public bool TryGetValue (TFirst key, out TSecond value)
    {
        return _firstToSecond.TryGetValue(key, out value);
    }

    public bool Remove (TFirst key)
    {
        TSecond value;
        if (_firstToSecond.TryGetValue(key, out value)) {
            _firstToSecond.Remove(key);
            _secondToFirst.Remove(value);
            return true;
        }
        else
            return false;
    }

    void IDictionary.Remove (object key)
    {
        var firstToSecond = (IDictionary)_firstToSecond;
        if (!firstToSecond.Contains(key))
            return;
        var value = firstToSecond[key];
        firstToSecond.Remove(key);
        ((IDictionary)_secondToFirst).Remove(value);
    }

    public bool Remove (KeyValuePair<TFirst, TSecond> item)
    {
        return _firstToSecond.Remove(item);
    }

    public bool Contains (object key)
    {
        return ((IDictionary)_firstToSecond).Contains(key);
    }

    public void Clear ()
    {
        _firstToSecond.Clear();
        _secondToFirst.Clear();
    }

    public void CopyTo (KeyValuePair<TFirst, TSecond>[] array, int arrayIndex)
    {
        _firstToSecond.CopyTo(array, arrayIndex);
    }

    void ICollection.CopyTo (Array array, int index)
    {
        ((IDictionary)_firstToSecond).CopyTo(array, index);
    }

    [OnDeserialized]
    internal void OnDeserialized (StreamingContext context)
    {
        _secondToFirst.Clear();
        foreach (var item in _firstToSecond)
            _secondToFirst.Add(item.Value, item.Key);
    }

    private class ReverseDictionary : IDictionary<TSecond, TFirst>, IReadOnlyDictionary<TSecond, TFirst>, IDictionary
    {
        private readonly BiDictionary<TFirst, TSecond> _owner;

        public ReverseDictionary (BiDictionary<TFirst, TSecond> owner)
        {
            _owner = owner;
        }

        public int Count
        {
            get { return _owner._secondToFirst.Count; }
        }

        object ICollection.SyncRoot
        {
            get { return ((ICollection)_owner._secondToFirst).SyncRoot; }
        }

        bool ICollection.IsSynchronized
        {
            get { return ((ICollection)_owner._secondToFirst).IsSynchronized; }
        }

        bool IDictionary.IsFixedSize
        {
            get { return ((IDictionary)_owner._secondToFirst).IsFixedSize; }
        }

        public bool IsReadOnly
        {
            get { return _owner._secondToFirst.IsReadOnly || _owner._firstToSecond.IsReadOnly; }
        }

        public TFirst this [TSecond key]
        {
            get { return _owner._secondToFirst[key]; }
            set
            {
                _owner._secondToFirst[key] = value;
                _owner._firstToSecond[value] = key;
            }
        }

        object IDictionary.this [object key]
        {
            get { return ((IDictionary)_owner._secondToFirst)[key]; }
            set
            {
                ((IDictionary)_owner._secondToFirst)[key] = value;
                ((IDictionary)_owner._firstToSecond)[value] = key;
            }
        }

        public ICollection<TSecond> Keys
        {
            get { return _owner._secondToFirst.Keys; }
        }

        ICollection IDictionary.Keys
        {
            get { return ((IDictionary)_owner._secondToFirst).Keys; }
        }

        IEnumerable<TSecond> IReadOnlyDictionary<TSecond, TFirst>.Keys
        {
            get { return ((IReadOnlyDictionary<TSecond, TFirst>)_owner._secondToFirst).Keys; }
        }

        public ICollection<TFirst> Values
        {
            get { return _owner._secondToFirst.Values; }
        }

        ICollection IDictionary.Values
        {
            get { return ((IDictionary)_owner._secondToFirst).Values; }
        }

        IEnumerable<TFirst> IReadOnlyDictionary<TSecond, TFirst>.Values
        {
            get { return ((IReadOnlyDictionary<TSecond, TFirst>)_owner._secondToFirst).Values; }
        }

        public IEnumerator<KeyValuePair<TSecond, TFirst>> GetEnumerator ()
        {
            return _owner._secondToFirst.GetEnumerator();
        }

        IEnumerator IEnumerable.GetEnumerator ()
        {
            return GetEnumerator();
        }

        IDictionaryEnumerator IDictionary.GetEnumerator ()
        {
            return ((IDictionary)_owner._secondToFirst).GetEnumerator();
        }

        public void Add (TSecond key, TFirst value)
        {
            _owner._secondToFirst.Add(key, value);
            _owner._firstToSecond.Add(value, key);
        }

        void IDictionary.Add (object key, object value)
        {
            ((IDictionary)_owner._secondToFirst).Add(key, value);
            ((IDictionary)_owner._firstToSecond).Add(value, key);
        }

        public void Add (KeyValuePair<TSecond, TFirst> item)
        {
            _owner._secondToFirst.Add(item);
            _owner._firstToSecond.Add(item.Reverse());
        }

        public bool ContainsKey (TSecond key)
        {
            return _owner._secondToFirst.ContainsKey(key);
        }

        public bool Contains (KeyValuePair<TSecond, TFirst> item)
        {
            return _owner._secondToFirst.Contains(item);
        }

        public bool TryGetValue (TSecond key, out TFirst value)
        {
            return _owner._secondToFirst.TryGetValue(key, out value);
        }

        public bool Remove (TSecond key)
        {
            TFirst value;
            if (_owner._secondToFirst.TryGetValue(key, out value)) {
                _owner._secondToFirst.Remove(key);
                _owner._firstToSecond.Remove(value);
                return true;
            }
            else
                return false;
        }

        void IDictionary.Remove (object key)
        {
            var firstToSecond = (IDictionary)_owner._secondToFirst;
            if (!firstToSecond.Contains(key))
                return;
            var value = firstToSecond[key];
            firstToSecond.Remove(key);
            ((IDictionary)_owner._firstToSecond).Remove(value);
        }

        public bool Remove (KeyValuePair<TSecond, TFirst> item)
        {
            return _owner._secondToFirst.Remove(item);
        }

        public bool Contains (object key)
        {
            return ((IDictionary)_owner._secondToFirst).Contains(key);
        }

        public void Clear ()
        {
            _owner._secondToFirst.Clear();
            _owner._firstToSecond.Clear();
        }

        public void CopyTo (KeyValuePair<TSecond, TFirst>[] array, int arrayIndex)
        {
            _owner._secondToFirst.CopyTo(array, arrayIndex);
        }

        void ICollection.CopyTo (Array array, int index)
        {
            ((IDictionary)_owner._secondToFirst).CopyTo(array, index);
        }
    }
}

internal class DictionaryDebugView<TKey, TValue>
{
    private readonly IDictionary<TKey, TValue> _dictionary;

    [DebuggerBrowsable (DebuggerBrowsableState.RootHidden)]
    public KeyValuePair<TKey, TValue>[] Items
    {
        get
        {
            var array = new KeyValuePair<TKey, TValue>[_dictionary.Count];
            _dictionary.CopyTo(array, 0);
            return array;
        }
    }

    public DictionaryDebugView (IDictionary<TKey, TValue> dictionary)
    {
        if (dictionary == null)
            throw new ArgumentNullException("dictionary");
        _dictionary = dictionary;
    }
}

public static class KeyValuePairExts
{
    public static KeyValuePair<TValue, TKey> Reverse<TKey, TValue> (this KeyValuePair<TKey, TValue> @this)
    {
        return new KeyValuePair<TValue, TKey>(@this.Value, @this.Key);
    }
}
Атари
источник
К сожалению, ваша ссылка на github не работает.
Иван Кочуркин
Я получаю ошибку компиляции в ваших item.Reverseстроках. Какие-либо конкретные требования к версии?
Николас Рауль
@NicolasRaoul Вы не скопировали KeyValuePairExtsкласс в нижней части фрагмента кода.
Athari
11

Вопрос, на который вы ссылаетесь, также показывает в этом ответе индивидуальную реализацию . Добавление RemoveByFirst и RemoveBySecond было бы тривиальным - как и реализация дополнительных интерфейсов и т. Д.

Джон Скит
источник
Хорошо, честно, я так и сделал. Я добавлю его к ответам, когда закончу юнит-тесты ...
Джоэл ин Го
3

Это то же самое, что и принятый ответ, но я также предоставил Updateметоды и, в общем, немного уточнил:

public class BiDictionary<TKey1, TKey2> : IEnumerable<Tuple<TKey1, TKey2>>
{
    Dictionary<TKey1, TKey2> _forwards;
    Dictionary<TKey2, TKey1> _reverses;

    public int Count
    {
        get
        {
            if (_forwards.Count != _reverses.Count)
                throw new Exception("somewhere logic went wrong and your data got corrupt");

            return _forwards.Count;
        }
    }

    public ICollection<TKey1> Key1s
    {
        get { return _forwards.Keys; }
    }

    public ICollection<TKey2> Key2s
    {
        get { return _reverses.Keys; }
    }

    public BiDictionary(IEqualityComparer<TKey1> comparer1 = null, IEqualityComparer<TKey2> comparer2 = null)
    {
        _forwards = new Dictionary<TKey1, TKey2>(comparer1);
        _reverses = new Dictionary<TKey2, TKey1>(comparer2);
    }



    public bool ContainsKey1(TKey1 key)
    {
        return ContainsKey(key, _forwards);
    }

    private static bool ContainsKey<S, T>(S key, Dictionary<S, T> dict)
    {
        return dict.ContainsKey(key);
    }

    public bool ContainsKey2(TKey2 key)
    {
        return ContainsKey(key, _reverses);
    }

    public TKey2 GetValueByKey1(TKey1 key)
    {
        return GetValueByKey(key, _forwards);
    }

    private static T GetValueByKey<S, T>(S key, Dictionary<S, T> dict)
    {
        return dict[key];
    }

    public TKey1 GetValueByKey2(TKey2 key)
    {
        return GetValueByKey(key, _reverses);
    }

    public bool TryGetValueByKey1(TKey1 key, out TKey2 value)
    {
        return TryGetValue(key, _forwards, out value);
    }

    private static bool TryGetValue<S, T>(S key, Dictionary<S, T> dict, out T value)
    {
        return dict.TryGetValue(key, out value);
    }

    public bool TryGetValueByKey2(TKey2 key, out TKey1 value)
    {
        return TryGetValue(key, _reverses, out value);
    }

    public bool Add(TKey1 key1, TKey2 key2)
    {
        if (ContainsKey1(key1) || ContainsKey2(key2))   // very important
            return false;

        AddOrUpdate(key1, key2);
        return true;
    }

    public void AddOrUpdateByKey1(TKey1 key1, TKey2 key2)
    {
        if (!UpdateByKey1(key1, key2))
            AddOrUpdate(key1, key2);
    }

    // dont make this public; a dangerous method used cautiously in this class
    private void AddOrUpdate(TKey1 key1, TKey2 key2)
    {
        _forwards[key1] = key2;
        _reverses[key2] = key1;
    }

    public void AddOrUpdateKeyByKey2(TKey2 key2, TKey1 key1)
    {
        if (!UpdateByKey2(key2, key1))
            AddOrUpdate(key1, key2);
    }

    public bool UpdateKey1(TKey1 oldKey, TKey1 newKey)
    {
        return UpdateKey(oldKey, _forwards, newKey, (key1, key2) => AddOrUpdate(key1, key2));
    }

    private static bool UpdateKey<S, T>(S oldKey, Dictionary<S, T> dict, S newKey, Action<S, T> updater)
    {
        T otherKey;
        if (!TryGetValue(oldKey, dict, out otherKey) || ContainsKey(newKey, dict))
            return false;

        Remove(oldKey, dict);
        updater(newKey, otherKey);
        return true;
    }

    public bool UpdateKey2(TKey2 oldKey, TKey2 newKey)
    {
        return UpdateKey(oldKey, _reverses, newKey, (key1, key2) => AddOrUpdate(key2, key1));
    }

    public bool UpdateByKey1(TKey1 key1, TKey2 key2)
    {
        return UpdateByKey(key1, _forwards, _reverses, key2, (k1, k2) => AddOrUpdate(k1, k2));
    }

    private static bool UpdateByKey<S, T>(S key1, Dictionary<S, T> forwards, Dictionary<T, S> reverses, T key2,
                                          Action<S, T> updater)
    {
        T otherKey;
        if (!TryGetValue(key1, forwards, out otherKey) || ContainsKey(key2, reverses))
            return false;

        if (!Remove(otherKey, reverses))
            throw new Exception("somewhere logic went wrong and your data got corrupt");

        updater(key1, key2);
        return true;
    }

    public bool UpdateByKey2(TKey2 key2, TKey1 key1)
    {
        return UpdateByKey(key2, _reverses, _forwards, key1, (k1, k2) => AddOrUpdate(k2, k1));
    }

    public bool RemoveByKey1(TKey1 key)
    {
        return RemoveByKey(key, _forwards, _reverses);
    }

    private static bool RemoveByKey<S, T>(S key, Dictionary<S, T> keyDict, Dictionary<T, S> valueDict)
    {
        T otherKey;
        if (!TryGetValue(key, keyDict, out otherKey))
            return false;

        if (!Remove(key, keyDict) || !Remove(otherKey, valueDict))
            throw new Exception("somewhere logic went wrong and your data got corrupt");

        return true;
    }

    private static bool Remove<S, T>(S key, Dictionary<S, T> dict)
    {
        return dict.Remove(key);
    }

    public bool RemoveByKey2(TKey2 key)
    {
        return RemoveByKey(key, _reverses, _forwards);
    }

    public void Clear()
    {
        _forwards.Clear();
        _reverses.Clear();
    }

    public IEnumerator<Tuple<TKey1, TKey2>> GetEnumerator()
    {
        if (_forwards.Count != _reverses.Count)
            throw new Exception("somewhere logic went wrong and your data got corrupt");

        foreach (var item in _forwards)
            yield return Tuple.Create(item.Key, item.Value);
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

Подобно моему ответу здесь

Несколько замечаний:

  1. Я реализовал только IEnumerable<>. Я не думаю, ICollection<>что здесь имеет смысл, поскольку все имена методов могут отличаться для этой специальной структуры коллекции. Что должно быть внутри - решать вам IEnumerable<>. Итак, теперь у вас тоже есть синтаксис инициализатора коллекции, например

    var p = new BiDictionary<int, string> { 1, "a" }, { 2, "b" } };
  2. Я попытался создать некоторые странные исключения здесь и там - просто для целостности данных. Просто чтобы быть в безопасности, чтобы вы знали, есть ли в моем коде ошибки.

  3. Производительность: Вы можете поиск для Valueлибо из Keys, что средства Getи Containsметод требуют только один поиска (O (1)). Addтребуется 2 просмотра и 2 добавления. Updateтребуется 1 поиск и 2 добавления. Removeзанимает 3 просмотра. Все похоже на принятый ответ.

науфал
источник
Похоже, IEnumerable также может быть реализован, отражая реализацию члена, как этот ответ
crokusek
Я использовал IEnumerator<Tuple<TKey1, TKey2>>здесь. Нет IEnumerator<KeyValuePair<TKey1, TKey2>>, поэтому я думаю, что не могу сделать это с моей функцией GetEnumerator. Я правильно понял?
nawfal
Теперь я вижу Tuple, объявленный в наследовании интерфейса. Сразу отметим, что стандартный словарь использует KVP.
crokusek 01
Стандартный словарь должен использовать kvp, потому что это карта ключей и значений. Он лучше передает смысл. Если двунаправленный словарь использует kvp, то он подразумевает только отношение «ключ к значению», а не наоборот. Я признаю, что кортеж здесь не самый лучший, поскольку он не подразумевает никакой связи между value1 и value2, но я считаю, что он все же лучше, чем kvp, поскольку он менее запутан.
nawfal 01
2

Я создал такой класс, используя классы коллекции C5.

public class Mapper<K,T> : IEnumerable<T>

{
    C5.TreeDictionary<K,T> KToTMap = new TreeDictionary<K,T>();
    C5.HashDictionary<T,K> TToKMap = new HashDictionary<T,K>();


    /// <summary>
    /// Initializes a new instance of the Mapper class.
    /// </summary>
    public Mapper()
    {
        KToTMap = new TreeDictionary<K,T>();
        TToKMap = new HashDictionary<T,K>();
    }


    public void Add(K key, T value)
    {
        KToTMap.Add(key, value);
        TToKMap.Add(value, key);
    }

    public bool ContainsKey(K key)
    {
        return KToTMap.Contains(key);
    }

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


    public K this[T obj]
    {
        get
        {
            return TToKMap[obj];
        }
    }

    public T this[K obj]
    {
        get
        {
            return KToTMap[obj];
        }
    }

    public IEnumerator<T> GetEnumerator()
    {
        return KToTMap.Values.GetEnumerator();
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return KToTMap.Values.GetEnumerator();
    }
}
Томаш Пайонк
источник
3
зачем вам словарь дерева и словарь хешей? в чем отличия?
nawfal
1
что происходит, когда оба типа одинаковы, и вы пытаетесь восстановить значение? Пример: var primes = new Mapper <int, int> (); primes.Add (1, 2); простые числа.Добавить (2, 3); int сюрприз = простые числа [2];
Daniel Santos
2

Еще одно расширение принятого ответа. Он реализует IEnumerable, поэтому с ним можно использовать foreach. Я понимаю, что с реализацией IEnumerable есть больше ответов, но здесь используются структуры, поэтому он удобен для сборщика мусора . Это особенно полезно в движке Unity (проверено профилировщиком).

/// <summary>
/// This is a dictionary guaranteed to have only one of each value and key. 
/// It may be searched either by TFirst or by TSecond, giving a unique answer because it is 1 to 1.
/// It implements garbage-collector-friendly IEnumerable.
/// </summary>
/// <typeparam name="TFirst">The type of the "key"</typeparam>
/// <typeparam name="TSecond">The type of the "value"</typeparam>
public class BiDictionary<TFirst, TSecond> : IEnumerable<BiDictionary<TFirst, TSecond>.Pair>
{


    public struct Pair
    {
        public TFirst  First;
        public TSecond Second;
    }


    public struct Enumerator : IEnumerator<Pair>, IEnumerator
    {

        public Enumerator(Dictionary<TFirst, TSecond>.Enumerator dictEnumerator)
        {
            _dictEnumerator = dictEnumerator;
        }

        public Pair Current
        {
            get
            {
                Pair pair;
                pair.First = _dictEnumerator.Current.Key;
                pair.Second = _dictEnumerator.Current.Value;
                return pair;
            }
        }

        object IEnumerator.Current
        {
            get
            {
                return Current;
            }
        }

        public void Dispose()
        {
            _dictEnumerator.Dispose();
        }

        public bool MoveNext()
        {
            return _dictEnumerator.MoveNext();
        }

        public void Reset()
        {
            throw new NotSupportedException();
        }

        private Dictionary<TFirst, TSecond>.Enumerator _dictEnumerator;

    }

    #region Exception throwing methods

    /// <summary>
    /// Tries to add the pair to the dictionary.
    /// Throws an exception if either element is already in the dictionary
    /// </summary>
    /// <param name="first"></param>
    /// <param name="second"></param>
    public void Add(TFirst first, TSecond second)
    {
        if (_firstToSecond.ContainsKey(first) || _secondToFirst.ContainsKey(second))
            throw new ArgumentException("Duplicate first or second");

        _firstToSecond.Add(first, second);
        _secondToFirst.Add(second, first);
    }

    /// <summary>
    /// Find the TSecond corresponding to the TFirst first
    /// Throws an exception if first is not in the dictionary.
    /// </summary>
    /// <param name="first">the key to search for</param>
    /// <returns>the value corresponding to first</returns>
    public TSecond GetByFirst(TFirst first)
    {
        TSecond second;
        if (!_firstToSecond.TryGetValue(first, out second))
            throw new ArgumentException("first");

        return second;
    }

    /// <summary>
    /// Find the TFirst corresponing to the Second second.
    /// Throws an exception if second is not in the dictionary.
    /// </summary>
    /// <param name="second">the key to search for</param>
    /// <returns>the value corresponding to second</returns>
    public TFirst GetBySecond(TSecond second)
    {
        TFirst first;
        if (!_secondToFirst.TryGetValue(second, out first))
            throw new ArgumentException("second");

        return first;
    }


    /// <summary>
    /// Remove the record containing first.
    /// If first is not in the dictionary, throws an Exception.
    /// </summary>
    /// <param name="first">the key of the record to delete</param>
    public void RemoveByFirst(TFirst first)
    {
        TSecond second;
        if (!_firstToSecond.TryGetValue(first, out second))
            throw new ArgumentException("first");

        _firstToSecond.Remove(first);
        _secondToFirst.Remove(second);
    }

    /// <summary>
    /// Remove the record containing second.
    /// If second is not in the dictionary, throws an Exception.
    /// </summary>
    /// <param name="second">the key of the record to delete</param>
    public void RemoveBySecond(TSecond second)
    {
        TFirst first;
        if (!_secondToFirst.TryGetValue(second, out first))
            throw new ArgumentException("second");

        _secondToFirst.Remove(second);
        _firstToSecond.Remove(first);
    }

    #endregion

    #region Try methods

    /// <summary>
    /// Tries to add the pair to the dictionary.
    /// Returns false if either element is already in the dictionary        
    /// </summary>
    /// <param name="first"></param>
    /// <param name="second"></param>
    /// <returns>true if successfully added, false if either element are already in the dictionary</returns>
    public bool TryAdd(TFirst first, TSecond second)
    {
        if (_firstToSecond.ContainsKey(first) || _secondToFirst.ContainsKey(second))
            return false;

        _firstToSecond.Add(first, second);
        _secondToFirst.Add(second, first);
        return true;
    }


    /// <summary>
    /// Find the TSecond corresponding to the TFirst first.
    /// Returns false if first is not in the dictionary.
    /// </summary>
    /// <param name="first">the key to search for</param>
    /// <param name="second">the corresponding value</param>
    /// <returns>true if first is in the dictionary, false otherwise</returns>
    public bool TryGetByFirst(TFirst first, out TSecond second)
    {
        return _firstToSecond.TryGetValue(first, out second);
    }

    /// <summary>
    /// Find the TFirst corresponding to the TSecond second.
    /// Returns false if second is not in the dictionary.
    /// </summary>
    /// <param name="second">the key to search for</param>
    /// <param name="first">the corresponding value</param>
    /// <returns>true if second is in the dictionary, false otherwise</returns>
    public bool TryGetBySecond(TSecond second, out TFirst first)
    {
        return _secondToFirst.TryGetValue(second, out first);
    }

    /// <summary>
    /// Remove the record containing first, if there is one.
    /// </summary>
    /// <param name="first"></param>
    /// <returns> If first is not in the dictionary, returns false, otherwise true</returns>
    public bool TryRemoveByFirst(TFirst first)
    {
        TSecond second;
        if (!_firstToSecond.TryGetValue(first, out second))
            return false;

        _firstToSecond.Remove(first);
        _secondToFirst.Remove(second);
        return true;
    }

    /// <summary>
    /// Remove the record containing second, if there is one.
    /// </summary>
    /// <param name="second"></param>
    /// <returns> If second is not in the dictionary, returns false, otherwise true</returns>
    public bool TryRemoveBySecond(TSecond second)
    {
        TFirst first;
        if (!_secondToFirst.TryGetValue(second, out first))
            return false;

        _secondToFirst.Remove(second);
        _firstToSecond.Remove(first);
        return true;
    }

    #endregion        

    /// <summary>
    /// The number of pairs stored in the dictionary
    /// </summary>
    public Int32 Count
    {
        get { return _firstToSecond.Count; }
    }

    /// <summary>
    /// Removes all items from the dictionary.
    /// </summary>
    public void Clear()
    {
        _firstToSecond.Clear();
        _secondToFirst.Clear();
    }


    public Enumerator GetEnumerator()
    {
        //enumerator.Reset(firstToSecond.GetEnumerator());
        return new Enumerator(_firstToSecond.GetEnumerator());
    }

    IEnumerator<Pair> IEnumerable<Pair>.GetEnumerator()
    {
        return GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }



    private Dictionary<TFirst, TSecond> _firstToSecond  = new Dictionary<TFirst, TSecond>();
    private Dictionary<TSecond, TFirst> _secondToFirst  = new Dictionary<TSecond, TFirst>();

}
Лукас З.
источник
Суть
starbeamrainbowlabs
1

Немного поздно, но вот реализация, которую я написал некоторое время назад. Он обрабатывает несколько интересных пограничных случаев, например, когда ключ переопределяет проверку равенства для выполнения частичного равенства. Это приводит к хранению основного словаря, A => 1но к обратному хранению 1 => A'.

Вы получаете доступ к обратному словарю через Inverseсвойство.

var map = new BidirectionalDictionary<int, int>();
map.Add(1, 2);
var result = map.Inverse[2]; // result is 1

//
// BidirectionalDictionary.cs
//
// Author:
//   Chris Chilvers <chilversc@googlemail.com>
//
// Copyright (c) 2009 Chris Chilvers
//
// Permission is hereby granted, free of charge, to any person obtaining
// a copy of this software and associated documentation files (the
// "Software"), to deal in the Software without restriction, including
// without limitation the rights to use, copy, modify, merge, publish,
// distribute, sublicense, and/or sell copies of the Software, and to
// permit persons to whom the Software is furnished to do so, subject to
// the following conditions:
//
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
// LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
//

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

namespace Cadenza.Collections
{
    public class BidirectionalDictionary<TKey, TValue> : IDictionary<TKey, TValue>
    {
        private readonly IEqualityComparer<TKey> keyComparer;
        private readonly IEqualityComparer<TValue> valueComparer;
        private readonly Dictionary<TKey, TValue> keysToValues;
        private readonly Dictionary<TValue, TKey> valuesToKeys;
        private readonly BidirectionalDictionary<TValue, TKey> inverse;


        public BidirectionalDictionary () : this (10, null, null) {}

        public BidirectionalDictionary (int capacity) : this (capacity, null, null) {}

        public BidirectionalDictionary (IEqualityComparer<TKey> keyComparer, IEqualityComparer<TValue> valueComparer)
            : this (10, keyComparer, valueComparer)
        {
        }

        public BidirectionalDictionary (int capacity, IEqualityComparer<TKey> keyComparer, IEqualityComparer<TValue> valueComparer)
        {
            if (capacity < 0)
                throw new ArgumentOutOfRangeException ("capacity", capacity, "capacity cannot be less than 0");

            this.keyComparer = keyComparer ?? EqualityComparer<TKey>.Default;
            this.valueComparer = valueComparer ?? EqualityComparer<TValue>.Default;

            keysToValues = new Dictionary<TKey, TValue> (capacity, this.keyComparer);
            valuesToKeys = new Dictionary<TValue, TKey> (capacity, this.valueComparer);

            inverse = new BidirectionalDictionary<TValue, TKey> (this);
        }

        private BidirectionalDictionary (BidirectionalDictionary<TValue, TKey> inverse)
        {
            this.inverse = inverse;
            keyComparer = inverse.valueComparer;
            valueComparer = inverse.keyComparer;
            valuesToKeys = inverse.keysToValues;
            keysToValues = inverse.valuesToKeys;
        }


        public BidirectionalDictionary<TValue, TKey> Inverse {
            get { return inverse; }
        }


        public ICollection<TKey> Keys {
            get { return keysToValues.Keys; }
        }

        public ICollection<TValue> Values {
            get { return keysToValues.Values; }
        }

        public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator ()
        {
            return keysToValues.GetEnumerator ();
        }

        IEnumerator IEnumerable.GetEnumerator ()
        {
            return GetEnumerator ();
        }

        void ICollection<KeyValuePair<TKey, TValue>>.CopyTo (KeyValuePair<TKey, TValue>[] array, int arrayIndex)
        {
            ((ICollection<KeyValuePair<TKey, TValue>>) keysToValues).CopyTo (array, arrayIndex);
        }


        public bool ContainsKey (TKey key)
        {
            if (key == null)
                throw new ArgumentNullException ("key");
            return keysToValues.ContainsKey (key);
        }

        public bool ContainsValue (TValue value)
        {
            if (value == null)
                throw new ArgumentNullException ("value");
            return valuesToKeys.ContainsKey (value);
        }

        bool ICollection<KeyValuePair<TKey, TValue>>.Contains (KeyValuePair<TKey, TValue> item)
        {
            return ((ICollection<KeyValuePair<TKey, TValue>>) keysToValues).Contains (item);
        }

        public bool TryGetKey (TValue value, out TKey key)
        {
            if (value == null)
                throw new ArgumentNullException ("value");
            return valuesToKeys.TryGetValue (value, out key);
        }

        public bool TryGetValue (TKey key, out TValue value)
        {
            if (key == null)
                throw new ArgumentNullException ("key");
            return keysToValues.TryGetValue (key, out value);
        }

        public TValue this[TKey key] {
            get { return keysToValues [key]; }
            set {
                if (key == null)
                    throw new ArgumentNullException ("key");
                if (value == null)
                    throw new ArgumentNullException ("value");

                //foo[5] = "bar"; foo[6] = "bar"; should not be valid
                //as it would have to remove foo[5], which is unexpected.
                if (ValueBelongsToOtherKey (key, value))
                    throw new ArgumentException ("Value already exists", "value");

                TValue oldValue;
                if (keysToValues.TryGetValue (key, out oldValue)) {
                    // Use the current key for this value to stay consistent
                    // with Dictionary<TKey, TValue> which does not alter
                    // the key if it exists.
                    TKey oldKey = valuesToKeys [oldValue];

                    keysToValues [oldKey] = value;
                    valuesToKeys.Remove (oldValue);
                    valuesToKeys [value] = oldKey;
                } else {
                    keysToValues [key] = value;
                    valuesToKeys [value] = key;
                }
            }
        }

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

        bool ICollection<KeyValuePair<TKey, TValue>>.IsReadOnly {
            get { return false; }
        }


        public void Add (TKey key, TValue value)
        {
            if (key == null)
                throw new ArgumentNullException ("key");
            if (value == null)
                throw new ArgumentNullException ("value");

            if (keysToValues.ContainsKey (key))
                throw new ArgumentException ("Key already exists", "key");
            if (valuesToKeys.ContainsKey (value))
                throw new ArgumentException ("Value already exists", "value");

            keysToValues.Add (key, value);
            valuesToKeys.Add (value, key);
        }

        public void Replace (TKey key, TValue value)
        {
            if (key == null)
                throw new ArgumentNullException ("key");
            if (value == null)
                throw new ArgumentNullException ("value");

            // replaces a key value pair, if the key or value already exists those mappings will be replaced.
            // e.g. you have; a -> b, b -> a; c -> d, d -> c
            // you add the mapping; a -> d, d -> a
            // this will remove both of the original mappings
            Remove (key);
            inverse.Remove (value);
            Add (key, value);
        }

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

        public bool Remove (TKey key)
        {
            if (key == null)
                throw new ArgumentNullException ("key");

            TValue value;
            if (keysToValues.TryGetValue (key, out value)) {
                keysToValues.Remove (key);
                valuesToKeys.Remove (value);
                return true;
            }
            else {
                return false;
            }
        }

        bool ICollection<KeyValuePair<TKey, TValue>>.Remove (KeyValuePair<TKey, TValue> item)
        {
            bool removed = ((ICollection<KeyValuePair<TKey, TValue>>) keysToValues).Remove (item);
            if (removed)
                valuesToKeys.Remove (item.Value);
            return removed;
        }

        public void Clear ()
        {
            keysToValues.Clear ();
            valuesToKeys.Clear ();
        }


        private bool ValueBelongsToOtherKey (TKey key, TValue value)
        {
            TKey otherKey;
            if (valuesToKeys.TryGetValue (value, out otherKey))
                // if the keys are not equal the value belongs to another key
                return !keyComparer.Equals (key, otherKey);
            else
                // value doesn't exist in map, thus it cannot belong to another key
                return false;
        }
    }
}

Исходники и тесты на github.

Крис Чилверс
источник