Имеет ли C# .NET какую-либо структуру данных, которая удовлетворяет следующим свойствам?

Question

Я пытаюсь решить проблему, и я понял, что сложность моего решения была выше, чем ожидалось из-за того, что Insert для List<T> является O (n) (источник: https://msdn.microsoft.com/en-us/library/sey5k5z4(v=vs.110).aspx).

То, что я хочу, это структура данных, как

• Sequential контейнер
• имеет двоичный метод поиска, который работает, когда элементы в порядке
• лучше, чем O (N) вставки в индексе
• O (1), чтобы получить количество элементов в контейнере
• O (1) поиск по индексу

Другими словами, я хочу что-то вроде List<T>, за исключением более быстрой вставки.

Answer 1

Возможно ли получить дубликаты в списке или вы можете гарантировать, что дважды не увидите одно и то же значение? Вам нужно указать индекс, или вы ожидаете, что вещи будут отсортированы в зависимости от значения элемента?

Если вы знаете, что дубликатов не будет, или вы не хотите хранить значение дважды, когда есть дубликаты, а ваш индекс основан исключительно на том, чтобы положить товар в правильное положение в зависимости от его значения, вы можно посмотреть на тип SortedSet<T>.

Если могут быть дубликаты, но вы хотите указать значение вручную, вы можете посмотреть на SortedDictionary<TKey, TValue>, где значения TKey являются вашими целыми индексами.

Если вы не можете встретить ни одно из этих условий, вы застряли в реализации своего собственного типа. Хорошая новость заключается в том, что вам не нужно начинать с нуля. Тип LinkedList<T> может получить от вас большую часть пути.

Answer 2

Это не совсем встроено, но вы можете попробовать. Коллекции энергии Wintellect имеют BigList<T>, которые будут выполнять эту работу.

https://powercollections.codeplex.com/

Он имеет более быстрый ввод в определенном индексе по сравнению с List<T>. Я не могу сказать вам, как именно он работает, но он поддерживает некоторые смещения вокруг элементов, поэтому с точки зрения памяти он будет более эфессивным.

Вы можете найти его также как пакет самородок.

** EDIT: ** Он имеет индекс O (log n) с индексом доступа, так как @Ryan меня исправил.