Generic OrderedDictionary<TKey, TValue> See http://stackoverflow.com/a/15146898/801189 for details.

OrderedDictionary<TKey, TValue>

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

namespace Data
{
    [Serializable]
    public class OrderedList<TKey, TValue> : IDictionary<TKey, TValue>, IDictionary
    {
        private Dictionary<TKey, int> _order;
        private int _lastOrder;
        private readonly SortedList<TKey, TValue> _internalList;

        private readonly bool _sorted;
        private readonly OrderComparer _comparer;

        private readonly object _lockObject = new Object();

        public OrderedList(IEnumerable<KeyValuePair<TKey, TValue>> pairedCollection, bool sorted = false)
        {
            _sorted = sorted;

            if (pairedCollection == null) pairedCollection = new Dictionary<TKey, TValue>();

            if (_sorted)
            {
                _internalList = new SortedList<TKey, TValue>(
                    (pairedCollection as Dictionary<TKey, TValue>) ?? pairedCollection.ToDictionary(i => i.Key, i => i.Value)
                );
            }
            else
            {
                _order = new Dictionary<TKey, int>();
                _comparer = new OrderComparer(ref _order);
                _internalList = new SortedList<TKey, TValue>(_comparer);
                // keep prder of the IDictionary
                foreach (var kvp in pairedCollection)
                {
                    Add(kvp);
                }

            }

        }

        public bool Sorted
        {
            get { return _sorted; }
        }

        private class OrderComparer : Comparer<TKey>
        {
            public Dictionary<TKey, int> Order { private get; set; }

            public OrderComparer(ref Dictionary<TKey, int> order)
            {
                Order = order;
            }

            public override int Compare(TKey x, TKey y)
            {
                var xo = Order[x];
                var yo = Order[y];
                return xo.CompareTo(yo);
            }
        }

        private void ReOrder()
        {
            var i = 0;
            _order = _order.OrderBy(kvp => kvp.Value).ToDictionary(kvp => kvp.Key, kvp => i++);
            _comparer.Order = _order;
            _lastOrder = _order.Values.Max() + 1;
        }

        public void Add(TKey key, TValue value)
        {
            lock (_lockObject)
            {
                if (!_sorted)
                {
                    _order.Add(key, _lastOrder);
                    _lastOrder++;
                    //very rare event
                    if (_lastOrder == int.MaxValue) ReOrder();
                }

                _internalList.Add(key, value);
            }
        }

        public bool Remove(TKey key)
        {
            lock (_lockObject)
            {
                var result = _internalList.Remove(key);
                if (!_sorted) _order.Remove(key);
                return result;
            }
        }

        // Other IDictionary<> + IDictionary members implementation wrapping around _internalList
        // ...
        //    }
        //}

        public bool ContainsKey(TKey key)
        {
            return _internalList.ContainsKey(key);
        }

        public bool TryGetValue(TKey key, out TValue value)
        {
            return _internalList.TryGetValue(key, out value);
        }

        public TValue this[TKey key]
        {
            get { return _internalList[key]; }
            // key remains at its place
            set { _internalList[key] = value; }
        }

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

        ICollection IDictionary.Values
        {
            get { return (_internalList as IDictionary).Values; }
        }

        ICollection IDictionary.Keys
        {
            get { return (_internalList as IDictionary).Keys; }
        }

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

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

        public void Remove(object key)
        {
            (_internalList as IDictionary).Remove(key);
        }

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

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

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

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

        public void Add(object key, object value)
        {
            (_internalList as IDictionary).Add(key, value);
        }

        public void Clear()
        {
            lock (_lockObject)
            {
                _internalList.Clear();
                if (!_sorted) _order.Clear();
            }
        }

        IDictionaryEnumerator IDictionary.GetEnumerator()
        {
            return (_internalList as IDictionary).GetEnumerator();
        }

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

        public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
        {
            (_internalList as IDictionary<TKey, TValue>).CopyTo(array, arrayIndex);
        }

        public bool Remove(KeyValuePair<TKey, TValue> item)
        {
            lock (_lockObject)
            {
                var result = (_internalList as IDictionary<TKey, TValue>).Remove(item);
                if (!_sorted) _order.Remove(item.Key);
                return result;
            }
        }

        public void CopyTo(Array array, int index)
        {
            (_internalList as IDictionary).CopyTo(array, index);
        }

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

        public object SyncRoot
        {
            get { return (_internalList as IDictionary).SyncRoot; }
        }

        public bool IsSynchronized
        {
            get { return (_internalList as IDictionary).IsSynchronized; }
        }

        public bool IsReadOnly
        {
            get { return (_internalList as IDictionary<TKey, TValue>).IsReadOnly; }
        }

        public bool IsFixedSize
        {
            get { return (_internalList as IDictionary).IsFixedSize; }
        }
    }

}