Is there a better data structure than Dictionary i

Question

I have a Dictionary<int, object> where the int is a property of obj. Is there a better data structure for this? I feel like using a property as the key is redundant.

This Dictionary<int, obj> is a field in a container class that allows for random indexing into the obj values based on an int id number. The simplified (no exception handling) indexer in the container class would look like:

obj this[int id]
{
     get{ return this.myDictionary[id];}
}

where myDictionary is the aforementioned Dictionary<int, obj> holding the objects.

This may be the typical way of quick random access but I wanted to get second opinions.

Answer 1

You can implement your own KeyedCollection trivially if the extra overhead that comes with the factory settings isn't worth it. The original KeyedCollection in System.Collections.ObjectModel is internally a Dictionary<TKey, TItem> and a List<TItem> which means you can have operations defined on both IList<> and IDictionary<>. For e.g., you can insert, access by index, traverse collection in the inserted order (all which IList<> facilitates) and at the same time you can have quick lookups based on key (with the help of dictionary). This means that when you're adding or removing an item they have to be performed on both underlying collections, apart from the small memory overhead to hold the extra List<> (but the objects are not duplicated as such). Though the addition speeds are not affected much (List<> addition is O(1)), removal speed is affected a little.

If you don't care about insertion order and accessing by index:

public class KeyedCollection<TKey, TItem> : ICollection<TItem>
{
    MemberInfo _keyInfo;
    Func<TItem, TKey> _keySelector;
    Dictionary<TKey, TItem> _dict;

    public TItem this[TKey key]
    {
        get { return _dict[key]; }
    }

    public int Count
    {
        get { return _dict.Count; }
    }

    public bool IsReadOnly
    {
        get { return false; }
    }

    public ICollection<TKey> Keys
    {
        get { return _dict.Keys; }
    }

    private ICollection<TItem> Items
    {
        get { return _dict.Values; }
    }

    public KeyedCollection(Expression<Func<TItem, TKey>> keySelector, IEqualityComparer<TKey> comparer = null)
    {
        var keyExpression = keySelector.Body as MemberExpression;
        if (keyExpression != null)
            _keyInfo = keyExpression.Member;

        _keySelector = keySelector.Compile();
        _dict = new Dictionary<TKey, TItem>(comparer);
    }



    private TKey GetKeyForItem(TItem item)
    {
        return _keySelector(item);
    }

    public bool ContainsKey(TKey key)
    {
        return _dict.ContainsKey(key);
    }

    public bool Contains(TItem item)
    {
        return ContainsKey(GetKeyForItem(item));
    }

    public bool TryGetItem(TKey key, out TItem item)
    {
        return _dict.TryGetValue(key, out item);
    }

    public void Add(TItem item)
    {
        _dict.Add(GetKeyForItem(item), item);
    }

    public void AddOrUpdate(TItem item)
    {
        _dict[GetKeyForItem(item)] = item;
    }

    public bool UpdateKey(TKey oldKey, TKey newKey)
    {
        TItem oldItem;
        if (_keyInfo == null || !TryGetItem(oldKey, out oldItem) || !SetItem(oldItem, newKey))   // important
            return false;

        RemoveKey(oldKey);
        Add(oldItem);
        return true;
    }

    private bool SetItem(TItem item, TKey key)
    {
        var propertyInfo = _keyInfo as PropertyInfo;
        if (propertyInfo != null)
        {
            if (!propertyInfo.CanWrite)
                return false;

            propertyInfo.SetValue(item, key, null);
            return true;
        }

        var fieldInfo = _keyInfo as FieldInfo;
        if (fieldInfo != null)
        {
            if (fieldInfo.IsInitOnly)
                return false;

            fieldInfo.SetValue(item, key);
            return true;
        }

        return false;
    }

    public bool RemoveKey(TKey key)
    {
        return _dict.Remove(key);
    }

    public bool Remove(TItem item)
    {
        return RemoveKey(GetKeyForItem(item));
    }

    public void Clear()
    {
        _dict.Clear();
    }

    public void CopyTo(TItem[] array, int arrayIndex)
    {
        Items.CopyTo(array, arrayIndex);
    }

    public IEnumerator<TItem> GetEnumerator()
    {
        return Items.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

I have implemented ICollection<TItem> to make it more standard compliant - and also you get the nice collection initializer syntax! :)

A sample usage:

var p1 = new Person { Name = "a" };
var p2 = new Person { Name = "b" };

var people = new KeyedCollection<string, Person>(p => p.Name) { p1, p2 };
// p1 == people["a"];
// p2 == people["b"];

Answer 2

C# dynamic properties post seems to show that using a Dictionary was a popular choice. The other posts suggest using a HashTable

Dictionary vs Hashtable

Answer 3

There's no concrete class in the framework that does this. There's an abstract one though, KeyedCollection. You'll have to derive your own class from that one and implement the GetKeyForItem() method. That's pretty easy, just return the value of the property by which you want to index.

That's all you need to do, but do keep an eye on ChangeItemKey(). You have to do something meaningful when the property that you use as the key changes value. Easy enough if you ensure that the property is immutable (only has a getter). But quite awkward when you don't, the object itself now needs to have awareness of it being stored in your collection. If you don't do anything about it (calling ChangeItemKey), the object gets lost in the collection, you can't find it back. Pretty close to a leak.

Note how Dictionary<> side-steps this problem by specifying the key value and the object separately. You may still not be able to find the object back but at least it doesn't get lost by design.

Answer 4

There is a KeyedCollection class.

EDIT: The KeyedCollection can use a dictionary internally, but it cleaner interface for this particular scenario than a raw dictionary since you can lookup by values directly. Admittedly I don't find it very useful in general.