Можно ли использовать SortedList<>/SortedDictionary<> с правильно реализованным компаратором для гарантии порядка вставки?

Если цель состоит в том, чтобы создать общий словарь, доступный только для чтения, который сохраняет порядок вставки, можно ли реально использовать SortedList<,> или SortedDictionary<,> с IComparer<>, который пытается поддерживать порядок вставки, выполняя что-то похожее на следующее?

class OrderedComparer<T> : IComparer<M>
{
    public int Compare(M x, M y)
    {
        return x.Equals(y) ? 0 : -1;//or 1
    }
}
SortedList<M> orderedList = new SortedList<M>(new OrderedComparer<T>());

(Интересно, что в случае SortedDictionary вышеупомянутый метод должен возвращать 0 или 1, чтобы предотвратить сортировку элементов в обратном порядке вставки).

Источник

3 ответа

Решение

Сравнитель должен подчиняться закону

Compare(a, b) == -Compare(b, a) //assuming only possible values are -1, 0, 1

Это свойство симметрии. Ваш пример кода не подчиняется этому. Поэтому коллекции BCL не дают вам никакой гарантии. Вы нарушили документально подтвержденный договор.

Вы не можете сделать это.

Вместо этого вы можете добавить новое поле в M где вы храните порядок вставки как int, Затем вы можете использовать это поле в компараторе.

Источник

Тот Compare реализация не следует правилам симметрии, как это должно быть. Это не правильный способ пойти по этому поводу.

Для списка, упорядоченного по порядку вставки, просто используйте List<T>как реализация. С Dictionary<,> с другой стороны, "порядок, в котором элементы возвращаются, не определен". Вы могли бы сделать свой собственный IDictionary<,> реализация, которая использует эти два класса вместе, чтобы сделать то, что вы пытаетесь сделать.

public class MyInsertionOrderDictionary<TKey, TValue> : IDictionary<TKey, TValue>
{
    private List<TKey> keysList;
    private Dictionary<TKey, TValue> dict;

    public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
    {
        foreach (TKey key in keysList)
        {
            TValue value = dict[key];
            yield return new KeyValuePair<TKey, TValue>(key, value);
        }
    }

    // TODO implement interface
    // when adding:
    // keysList.Add(key);
    // dict.Add(key, value);

    // when removing:
    // keysList.Remove(key);
    // dict.Remove(key);

    // you could also implement an indexer property like
    public KeyValuePair<TKey, TValue> this[int index] { get { ... } }
}

Этот класс внешне очень похож на OrderedDictionary класс, но общий. Существуют и другие общие реализации.

Источник

Нет сомнений в том, что вы должны делать такую ​​ужасную вещь. Вы не должны определенно, по разным причинам, например:

  • Не используйте отсортированные контейнеры для несортированных данных
  • Это не то, как вы используете компаратор
  • Избегайте зависимости от деталей реализации библиотек, которыми вы не владеете

Теперь, чтобы действительно узнать, можно ли сохранить порядок вставки в SortedList, взломав компаратор, есть только один способ: посмотреть на реализацию. Декомпилируйте байт-код и посмотрите, будет ли он работать.

Оказывается, SortedList использует бинарный поиск, и SortedDictionary использует красно-черное дерево.

Дурачить бинарный поиск легко. Компаратор используется только для сравнения новых элементов (если вы ничего не удаляете). Всегда возвращайте либо 1, либо -1, я всегда забываю, какой, и у вас есть несортированный список.

Для красно-черного дерева я не уверен, работает ли тот же трюк. Я не помню, должен ли такой тип дерева использовать компаратор, когда он сам себя восстанавливает. Если это произойдет, неспособность вашего компаратора обеспечить значимый результат приведет к ошибкам во время выполнения, возможно, в лучшем случае, к потере сложности. Но, может быть, это на самом деле хорошо. За исключением того, что вы все равно получите максимальное количество ребалансировки, я думаю.

Источник
Другие вопросы по тегам