Adding compile time safety to C# list indexers - is this possible?

Question

[Note: This question has attracted solutions with low runtime performance, so it's worth emphasizing here that performance is key, in addition to the type safety. See the note at the end for more performance info.]

I am using a few different instances of List<int> in a fairly complex algorithm.

Some of these lists contain indexes into each other, i.e. they provide a level of indirection.

I've fixed a few bugs caused by the wrong indexer being used while accessing a list. Because all the lists are the same type, i.e. List<int>, the compiler doesn't provide any type safety at all. For example:

// The below statement is wrong - it should be list1[list2[x]], 
// as x is an index into list2, not list1. 
// list2 returns indexes into list1.
// But the compiler is oblivious to this.
//
var f = list1[x]; 

So, I started thinking that it may be possible to add a degree of type safety by using strongly typed indexes into each list that just wrap an integer:

/// An index into the first list
struct Index1
{
    public int Value { get; set; }
}

/// An index into the second list
struct Index2
{
    public int Value { get; set; }
}

Then, declaring variables of the correct index type will catch a class of bugs at compile time. (This is not foolproof, that's not what I'm after - better is enough.)

Unfortunately a generic List<T> does not offer a way to use a custom index type - the indexer is always an int.

Is there another way to accomplish what I'm trying to do? A custom collection comes to mind - I don't mind the effort, which will likely pay for itself. But I can't think of one that can be used as shown. (I could create a separate collection type for each indexer, of course - but I'd like to use a single new collection type if possible - because otherwise code duplication starts to become an issue.)

Performance:: The algorithm was rewritten to use lists for performance. We're even considering using arrays since there is one less bounds check. So any proposed solution should have excellent runtime performance - comparable at least to List<T>.

Therefore the struct (or any other technique) should ideally be optimized out after the compile-time type-safety checks.

Use Cases: The use cases are:

1. Accessing a random element from a list via a type safe indexer.
2. A for loop over a list, also using a type safe indexer.
3. Using foreach over a list. List optimizes its GetEnumerator() to return a struct and so avoid allocations. I'd like to preserve that.

Answer 1

You should be able to use SortedDictionary<TKey, TValue> to do what you want. Make sure to implement Equals and GetHashCode on your custom key types.

SortedDictionary allows fast and type safe random access to elements while preserving order.

If you require list semantics to avoid rewriting too much code, it would not be hard to create a list-like type with the SortedDictionary as the backing storage.

Answer 2

I think the root issue you're running into is that with your structs, there's no way for a collection to take a generic parameter, then get Value without adding some interface on both structs (causing a virtual call), having a Func<TIndex, int> in the collection (like Jacob's answer does), or using a more complex collection that abstracts away the idea of an "index".

The direct approach of implementing a full collection for each Index* doesn't necessarily cause code duplication. A few ways are code generation or IL generation. Here's a design-time T4 template that generates code for each index struct along with a class with an indexer:

<#@ template debug="false" hostspecific="false" language="C#" #>
<#@ assembly name="System.Core" #>
<#@ output extension=".cs" #>
using System.Collections.Generic;

<#
string[] indexTypeNames = { "Index1", "Index2" };

foreach (var name in indexTypeNames)
{
    string collectionName = name + "List";
#>
public struct <#= name #>
{
    public int Value { get; set; }
}

public class <#= collectionName #><T>
{
    private List<T> _inner = new List<T>();

    public T this[<#= name #> index]
    {
        get { return _inner[index.Value]; }
        set { _inner[index.Value] = value; }
    }

    // Other desired IList<T> methods.
}

<#
}
#>

When the T4 template is built, it generates this code file:

using System.Collections.Generic;

public struct Index1
{
    public int Value { get; set; }
}

public class Index1List<T>
{
    private List<T> _inner = new List<T>();

    public T this[Index1 index]
    {
        get { return _inner[index.Value]; }
        set { _inner[index.Value] = value; }
    }

    // Other desired IList<T> methods.
}

public struct Index2
{
    public int Value { get; set; }
}

public class Index2List<T>
{
    private List<T> _inner = new List<T>();

    public T this[Index2 index]
    {
        get { return _inner[index.Value]; }
        set { _inner[index.Value] = value; }
    }

    // Other desired IList<T> methods.
}

Obviously you'll want interface implementations on the collections so they have a natural API, but it's pretty clear how you can add these.

Since the code is generated at design time, the duplication isn't a maintenance issue. However, I would classify code gen and IL gen as workarounds for something that the existing type system can't express, so I would also like to see a better answer using only generics.

Answer 3

Perhaps you could wrap a list-like collection class with something that provides a generic index type:

public class IndexedCollection<TIndex, TValue> : IList<TValue>
{
    private List<TValue> _innerList;
    private Func<TIndex, int> _getIndex;

    public IndexedCollection(Func<TIndex, int> getIndex)
    {
        this._getIndex = getIndex;
        this._innerList = new List<TValue>();
    }

    new public TValue this[TIndex indexObj]
    {
        get 
        {
            var realIndex = this._getIndex(indexObj);
            return _innerList[realIndex];
        }
        set 
        {
            _innerList[this._getIndex(indexObj)] = value;
        }
    }

    // All the other members
}

...then instantiate like this:

var list1 = new IndexedCollection<Index1, Foo>(i => i.Value);
var list2 = new IndexedCollection<Index2, Foo>(i => i.Value);