Sugar coated arrays (dynamically resizable and set any element at random)

Question

I want my cake and to eat it.

I like the way Lists in C# dynamically expand when you go beyond the initial capacity of the array. However this is not enough. I want to be able to do something like this:

int[] n = new int[];    // Note how I'm NOT defining how big the array is.
n[5] = 9

Yes, there'll be some sacrifice in speed, because behind the scenes, .NET would need to check to see if the default capacity has been exceeded. If it has, then it could expand the array by 5x or so.

Unfortunately with Lists, you're not really meant to set an arbitrary element, and although it is possible if you do this, it still isn't possible to set say, the fifth element straight away without initially setting the size of the List, let alone have it expand dynamically when trying.

For any solution, I'd like to be able to keep the simple square bracket syntax (rather than using a relatively verbose-looking method call), and have it relatively fast (preferably almost as fast as standard arrays) when it's not expanding the array.

Answer 1

Note that I don't necessarily advocate inheriting List, but if you really want this:

public class MyList<T> : List<T>
{
    public T this[int i]
    {
        get { 
            while (i >= this.Count) this.Add(default(T));
            return base[i]; 
        }
        set { 
            while (i >= this.Count) this.Add(default(T));
            base[i] = value; 
        }
    }
}

I'll add that if you expect most of the values of your "array" to remain empty over the life of your program, you'll get much greater efficiency by using a Dictionary<int, T>, especially as the size of the collection grows large.

Answer 2

A simple solution to the problem is to inherit from Dictionary<TKey, TValue> and just use the value generic:

public class MyCoolType<T> : Dictionary<int, T> { }

Then you would be able to use it like:

MyCoolType<int> n = new MyCoolType<int>();
n[5] = 9;

And a note on performance.

• For insertions, this is much faster than a list since it does not require you to resize or insert elements at arbitrary positions in an array. List<T> uses an array as a backing field and when you resize it, it is expensive. (Edit: Lists have a default size and its not always that you are resizing it, but when you do, its expensive)
• For look-ups, this is very nearly O(1) (source), so comparable to an Array look-up. Lists are O(n), which get progressively slower as you increase the number of contained elements.
• Sparsely packing is much more memory efficient than using a List with dense packing as it doesn't require you to use empty items just to reach a specific index.

Other Notes:

• In the other solutions, try inserting an item at index 570442959 for example, you'll get an OutOfMemoryException thrown (under 32 bit, but even 64-bit has problems). With this solution you can use any conceivable index that the int type supports, up to int.MaxValue.
• Lists don't allow negative indexes, this will.
• MyCoolType.Count is the equivalent of the array Length property here.

Here are the results of my performance test:

• Inserting 1 million elements into MyList: 29.4294424 seconds
• Inserting 1 million elements into CoolType: 0.127499 seconds
• Looking up 1 million random elements MyList: 1.6330562 seconds
• Looking up 1 million random elements CoolType: 1.304348 seconds

Full source to tests here: http://pastebin.com/kEdLgFaw

Note, to run these tests I had to set to X64 build, debug, and had to add the following to the app.config file:

<runtime>
  <gcAllowVeryLargeObjects enabled="true" />
</runtime>

Answer 3

You can define an extension method on List:

public static class ExtensionMethods {
    public static void Set<T>(this List<T> list, int index, T element) {
        if (index < list.Count) {
            list[index] = element;
        } else {
            for (int i = list.Count; i < index; i++) {
                list.Add(default(T));
            }
            list.Add(element);
        }
    }
}

and call list.Set(12, 1024) if you want the 12th element to be 1024.

Answer 4

Here is your pi

       static public List<int> AddToList(int index,int value,  List<int> input)
        {
            if (index >= input.Count)
            {
                int[] temparray = new int[index - input.Count + 1];
                input.AddRange(temparray);
            }
            return (input[index] = value);
        }