Структура данных, которая имеет O (n) итерацию, O (1) содержит и O (1) получает по ключу

Question

Я ищу структуру данных или их комбинацию, которая может дать мне поведение, удовлетворяющее следующим условиям:

1. O (n) Итерация (не должна быть в порядке)
2. O (1) Содержит
3. O (1) Получить (по ключу, который является int)
4. O (1) Добавить
5. O (1) Удалить

Три решения, которые я придумала, примерно такие, оба являются просто использованием встроенных коллекций в .NET

1. Создайте свой собственный хэш-набор, который предоставляет внешнему миру больше внутреннего хранилища, чем по умолчанию HashSet<T> в .NET

2. Используйте Dictionary<int, T>, так как итерация не должна быть упорядоченной, но это очень высокопроизводительное приложение и мусор, который создается при создании перечислителя каждый раз, когда мне нужно пройти через Коллекция беспокоит меня. Беспокойство по поводу мусора - это не то, что я «придумал», это для симуляции в реальном времени, и любой мусор, который может вызвать сборщик мусора, по сути, не вариант, если его можно избежать.

3. Используйте комбинацию Dictionary<int, int> и T[], в основном сохраняйте ключ + индекс в массиве в словаре и сохраняйте элементы в T[].

Answer 1

Существует универсальная KeyedCollection , которая позволяет индексировать объекты с помощью int и ключа.Ключ должен быть вставлен в значение.

Вы можете использовать for (int i ...) для его перебора без IEnumerable.