Нет универсальной реализации OrderedDictionary? - PullRequest
Новая
       37

Нет универсальной реализации OrderedDictionary?

126 голосов
/ 13 апреля 2010

В .NET 3.5 нет общей реализации OrderedDictionary (которая находится в пространстве имен System.Collections.Specialized). Я скучаю по одному?

Я нашел реализации для обеспечения функциональности, но удивился, если / почему нет универсальной реализации из коробки, и если кто-нибудь знает, есть ли что-то в .NET 4.0?

Ответы [ 12 ]

2 голосов
/ 26 марта 2019

Для тех, кто ищет «официальный» вариант пакета в NuGet, в .NET CoreFX Lab была принята реализация универсального OrderedDictionary. Если все пойдет хорошо, тип будет в конечном итоге утвержден и интегрирован в основной репозиторий .NET CoreFX.

Существует вероятность того, что эта реализация будет отклонена.

Здесь можно сослаться на подтвержденную реализацию https://github.com/dotnet/corefxlab/blob/57be99a176421992e29009701a99a370983329a6/src/Microsoft.Experimental.Collections/Microsoft/Collections/Extensions/OrderedDictionary.cs

Пакет NuGet, который определенно имеет этот тип, доступный для использования, можно найти здесь https://www.nuget.org/packages/Microsoft.Experimental.Collections/1.0.6-e190117-3

Или вы можете установить пакет в Visual Studio. Найдите пакет «Microsoft.Experimental.Collections» и убедитесь, что установлен флажок «Включить предварительный выпуск».

Обновит этот пост, если и когда тип будет официально доступен.

1 голос
/ 01 марта 2013

Я реализовал общий OrderedDictionary<TKey, TValue>, обернув SortedList<TKey, TValue> и добавив приватный Dictionary<TKey, int> _order. Затем я создал внутреннюю реализацию Comparer<TKey>, передав ссылку на словарь _order. Затем я использую этот компаратор для внутреннего SortedList. Этот класс сохраняет порядок элементов, передаваемых конструктору, и порядок дополнений.

Эта реализация имеет почти те же большие характеристики O, что и SortedList<TKey, TValue>, поскольку добавление и удаление в _order равно O (1). Каждый элемент займет (в соответствии с книгой «C # 4 в двух словах», стр. 292, таблица 7-1) дополнительное пространство памяти в 22 (накладные расходы) + 4 (порядок int) + размер TKey (предположим, 8) = 34 Вместе с издержками SortedList<TKey, TValue> на два байта общая нагрузка составляет 36 байтов, тогда как в той же книге говорится, что неуниверсальный OrderedDictionary имеет заголовок 59 байтов.

Если я передаю sorted=true в конструктор, то _order вообще не используется, OrderedDictionary<TKey, TValue> точно равен SortedList<TKey, TValue> с незначительными накладными расходами для переноса, если вообще имеет смысл.

Я собираюсь хранить не так много больших эталонных объектов в OrderedDictionary<TKey, TValue>, поэтому для меня это ок. Издержки 36 байтов допустимы.

Основной код приведен ниже. Полный обновленный код находится в этом gist . 

public class OrderedList<TKey, TValue> : IDictionary<TKey, TValue>, IDictionary
{
    private readonly Dictionary<TKey, int> _order;
    private readonly SortedList<TKey, TValue> _internalList;

    private readonly bool _sorted;
    private readonly OrderComparer _comparer;

    public OrderedList(IDictionary<TKey, TValue> dictionary, bool sorted = false)
    {
        _sorted = sorted;

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

        if (_sorted)
        {
            _internalList = new SortedList<TKey, TValue>(dictionary);
        }
        else
        {
            _order = new Dictionary<TKey, int>();
            _comparer = new OrderComparer(ref _order);
            _internalList = new SortedList<TKey, TValue>(_comparer);
            // Keep order of the IDictionary
            foreach (var kvp in dictionary)
            {
                Add(kvp);
            }
        }
    }

    public OrderedList(bool sorted = false)
        : this(null, sorted)
    {
    }

    private class OrderComparer : Comparer<TKey>
    {
        public Dictionary<TKey, int> Order { 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)
    {
        if (!_sorted)
        {
            _order.Add(key, _lastOrder);
            _lastOrder++;

            // Very rare event
            if (_lastOrder == int.MaxValue)
                ReOrder();
        }

        _internalList.Add(key, value);
    }

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

    // Other IDictionary<> + IDictionary members implementation wrapping around _internalList
    // ...
}
Страница:
...