Список, массив или что еще?

Мне нужна структура данных динамической длины с возможностью изменения значений элементов. Порядок элементов не важен.

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

  • Лучше использовать общий список, но процесс изменения действительно сложен: в первую очередь мне нужно удалить элемент, который я хочу изменить - общий список, похоже, не имеет простого метода "Удалить"/"Удалить", поэтому я попробовал "Фильтр" один - затем добавьте модифицированный элемент к голове. Это работает, но это слишком сложно для чего-то такого простого.

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

Источник

2 ответа

Решение

Используйте ResizeArray. Это аббревиатура для типа CLI List(T), которая предлагает необходимые функции, такие как, например, " Удалить".

Из библиотеки MSDN:

Класс List(T) является универсальным эквивалентом класса ArrayList. Он реализует универсальный интерфейс IList(T), используя массив, размер которого динамически увеличивается по мере необходимости.

Такие методы, как Contains, IndexOf, LastIndexOf и Remove, используют средство сравнения равенства для элементов списка. Компаратор равенства по умолчанию для типа T определяется следующим образом. Если тип T реализует универсальный интерфейс IEquatable(T), то средством сравнения равенства является метод Equals(T) этого интерфейса; в противном случае по умолчанию для сравнения равен Object.Equals(Object).

Такие методы, как BinarySearch и Sort, используют упорядочивающий компаратор для элементов списка. Компаратор по умолчанию для типа T определяется следующим образом. Если тип T реализует универсальный интерфейс IComparable(T), тогда компаратором по умолчанию является метод CompareTo(T) этого интерфейса; в противном случае, если тип T реализует неуниверсальный интерфейс IComparable, тогда компаратором по умолчанию является метод CompareTo(Object) этого интерфейса. Если тип T не реализует ни один из интерфейсов, то нет никакого компаратора по умолчанию, и компаратор или делегат сравнения должны быть предоставлены явно.

Список (T) не гарантируется для сортировки. Вы должны отсортировать список (T) перед выполнением операций (таких как BinarySearch), которые требуют сортировки списка (T).

Элементы в этой коллекции могут быть доступны с помощью целочисленного индекса. Индексы в этой коллекции начинаются с нуля.

List(T) принимает нулевую ссылку (Nothing в Visual Basic) в качестве допустимого значения для ссылочных типов и допускает дублирование элементов.

Пример в F#:

open System

// an integer list
let intList =
    let temp = new ResizeArray<int>() in
    temp.AddRange([| 1; 2; 3 |]);
    temp

// print each int using the ForEach member method
intList.ForEach( fun i -> Console.WriteLine(i) )

// unpack items from the resize array
let itemOne = intList.Item(0)
let itemTwo = intList.[1]
Источник

Я бы порекомендовал использовать ResizeArray. В основном это System.Collections.Generic.List<'T>, который идеально подходит для частого изменения количества элементов.

// Add items to a ResizeArray based on a condition
let filterRange predicate (i, j) =
    let results = ResizeArray(j-i+1) // reserve enough memory
    for k = i to j do
        if predicate k then results.Add(k)
    results

Что касается вашего второго беспокойства, вы все еще можете использовать синтаксис arr.[idx] <- e как с Array,

Чтобы избежать сложных манипуляций с ResizeArrayВы можете использовать функции высокого порядка в модуле ResizeArray из F# PowerPack. Эти функции создают новые ResizeArrayТак что производительность не идеальна.

// Use high-order functions to update items
let changeOneToThree (a: ResizeArray<_>) =
   ResizeArray.map (fun x -> if x = 1 then 3 else x) a

Тем не менее, вы всегда можете начать оттуда и оптимизировать, изменяя текущий ResizeArray,

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