Is there a better data structure than Dictionary if the values are objects and a property of those objects are the keys?

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.

Grantham

possible duplicate of Is there a dictionary like collection that can use a property of its value as the key? – Sarinasarine

Answer 1

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.

Two

Excellent suggestion. As I mentioned to @Lee this approach has the unwanted side effect of exposing a bunch of other methods I don't want my class to impliment. The worst of these being the Clear method. I need the KeyedCollection to be readonly in this case. – Grantham

Depending on your needs, you can override e.g. ClearItems to simply do nothing (or even throw). – Overbearing

@Brian I think Lookup might be what you want then, because I believe you can't modify it once it's created. I'm not sure it enforces uniqueness of the key though. – Thirdrate

Answer 2

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.

Durrace

Excellent suggestion. However, if I make my container impliment KeyedCollection<int, obj> it exposes a slew of members that I don't want to expose. In particular is the Clear method. – Grantham

Answer 3

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"];

Sarinasarine

Answer 4

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

Proleg