List, Array or what else?

Question

I need a dynamic length data structure with the capability of changing the element values. The order of the elements is not important.

If I use an array I can modify my elements, but I have problems with the length. The solution is to create a new array of the correct size and copy all the elements into the new one each time. Not a great idea because the number of elements changes often.
It's better to use a generic list, but the modify process is really complicated: first of all I need to remove the element I want to change- the generic list doesn't seem to have a simple "Remove"/"Delete" method, so I tried the "Filter" one- then add the modified element to the head. It works but it's a bit too complicated for something so easy.

Is there a data structure that allows me to dynamically change the length and modify the elements such as a modifiable list or a dynamically-sized array?

What's the importance of the head if the element order does not matter? If you add a property datetime modified to your object and make sure this changes when the object does, then the sorteddictionary should work. — Mike Miller, Jun 11 '12 at 10:52
As others said, `ResizeArray` matches your requirements, although that is usually sign of too imperative F# code. However, you did not say _why_ you need such data structure, so maybe there is an alternative solution to your actual problem that would be more functional. Can you give some details about that? — Tomas Petricek, Jun 11 '12 at 14:20
@Tomas - I don't like the implication that everyone who uses imperative code in F# needs to be coached out of it, and that functional is always better. — Brian, Jun 11 '12 at 17:09
@Brian - I definitely did not want to imply that. I use mutable collections all the time :-) and I think the pragmatic style of F# is really valuable. However, I think it is good to use less mutation when learning F# as you can better appreciate functional concepts that way. I should have added this context in my first comment. — Tomas Petricek, Jun 11 '12 at 22:24

gliderkite · Accepted Answer · 2012-06-11T12:09:56.313

Use ResizeArray. It's an abbreviation for the CLI type List(T) which offers the features you require, like Remove for example.

From MSDN Library:

The List(T) class is the generic equivalent of the ArrayList class. It implements the IList(T) generic interface using an array whose size is dynamically increased as required.

Methods such as Contains, IndexOf, LastIndexOf, and Remove use an equality comparer for the list elements. The default equality comparer for type T is determined as follows. If type T implements the IEquatable(T) generic interface, then the equality comparer is the Equals(T) method of that interface; otherwise, the default equality comparer is Object.Equals(Object).

Methods such as BinarySearch and Sort use an ordering comparer for the list elements. The default comparer for type T is determined as follows. If type T implements the IComparable(T) generic interface, then the default comparer is the CompareTo(T) method of that interface; otherwise, if type T implements the nongeneric IComparable interface, then the default comparer is the CompareTo(Object) method of that interface. If type T implements neither interface, then there is no default comparer, and a comparer or comparison delegate must be provided explicitly.

The List(T) is not guaranteed to be sorted. You must sort the List(T) before performing operations (such as BinarySearch) that require the List(T) to be sorted.

Elements in this collection can be accessed using an integer index. Indexes in this collection are zero-based.

List(T) accepts a null reference (Nothing in Visual Basic) as a valid value for reference types and allows duplicate elements.

An example in 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]

pad · Answer 2 · 2012-06-11T12:03:21.903

I would recommend to use ResizeArray. It is basically System.Collections.Generic.List<'T> which is perfect to use if number of elements changes frequently.

// 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

Regarding your second concern, you still can use the syntax arr.[idx] <- e as with Array.

To avoid complicated manipulation of ResizeArray, you could use high-order functions in ResizeArray module from F# PowerPack. These functions create new ResizeArrays so performance is not ideal.

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

However, you can always start from there and optimize by mutating current ResizeArray.

List, Array or what else?

2 Answers2