Есть ли реализация IDictionary, которая хранит ключи в порядке их добавления?(НЕ отсортированный заказ)

Question

Я думаю, все в названии ...

Я знаю, что Dictionary<TKey,TValue> хранит ключи в порядке добавления, но только до тех пор, пока вы их не удалите, и в любом случае это поведение не задокументировано и на него нельзя положиться (см. этот вопрос для деталей).

В основном, какую коллекцию мне следует использовать, если я хочу упорядоченную коллекцию пар ключ / значение, сохраняя при этом время доступа O (1)? (List<KeyValuePair<K,V>> не очень хороший вариант, так как у него будет O (n) время доступа). Я не думаю, что в BCL есть что-то подобное, но я просто хочу быть уверенным, прежде чем я сделаю свой собственный ...

Просто чтобы всем было понятно: я не хочу, чтобы ключи были отсортированы , я просто хочу, чтобы они оставались в порядке следования. Так что SortedList / SortedDictionary не то, что я ищу ...

Answer 1

Не могли бы вы просто сохранить List и Dictionary, которые позволяют вам искать, где ключи находятся в списке?Это позволило бы вам получить пары ключ / значение в порядке сложения, но при этом поддерживать O(1) lookup.

Answer 2

Если вы можете принять неуниверсальное, то System.Collections.Specialized.OrderedDictionary может делать то, что вам нужно. В противном случае мне хотелось бы написать оболочку, которая объединяет список и словарь, используя список для GetEnumerator и словарь для индексатора.

Answer 3

«Порядок добавления», как правило, не является проблемой для словаря, поэтому не ожидайте, что один из библиотеки std.

Это, конечно, возможно, но всегда будет стоить производительности.Если вы считаете, что поиск O (1) важен, я бы предложил оболочку, содержащую Dictionary<K,V> и связанную List<K>.Добавить и удалить станет медленнее.

Answer 4

Итак, вам не нужен ассоциативный контейнер, и порядок полностью основан на порядке вставки ... почему бы вам просто не использовать базовый массив?

Answer 5

Вы можете использовать SortedDictionary с пользовательским IComparer, который поддерживает порядок вставки. Разумеется, хотите ли вы обернуть это в свой более удобный интерфейс.