Is there a better data structure than the Dictionary if the values ​​are objects and the properties of these objects are keys?

Question

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

This Dictionary<int, obj> is a field in the container class that allows random indexing in obj values ​​based on the identifier number int . A simplified (without exception) indexer in the container class will look like this:

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

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

This might be a typical quick random access method, but I wanted a second opinion.

Answer 1

There is no concrete class in this structure. There is abstract, but KeyedCollection. You will have to deduce your own class from this and implement the GetKeyForItem () method. It's pretty simple, just return the value of the property you want to index with.

This is all you need to do, but watch out for ChangeItemKey (). You have to do something meaningful when the property that you use as the key changes the value. Easy enough if you make sure that the property is immutable (there is only a getter). But, when you do not, you are embarrassed, the object itself must now be aware that it is stored in your collection. If you do nothing (by calling ChangeItemKey), the object will be lost in the collection, you will not be able to find it. Pretty close to the leak.

Note how Dictionary <> performs this task by setting the key value and object separately. You still can not find the object back, but at least it will not be lost in design.

Answer 2

There is a KeyedCollection class.

EDIT: KeyedCollection can use the dictionary internally, but it is a cleaner interface for this particular scenario than the original dictionary, since you can directly look for values. Admittedly, I do not find this very useful in general.

Answer 3

You can implement your own KeyedCollection trivially if the extra overhead that comes with the factory settings is not worth it. The original KeyedCollection in System.Collections.ObjectModel is an internal a Dictionary<TKey, TItem> and a List<TItem> , which means that you can have operations defined on both IList<> and IDictionary<> . For example, you can insert, access by index, move the collection in the inserted order (all that IList<> makes it easy), and at the same time, you can quickly search based on a key (using a dictionary). This means that when you add or delete an item, they must be executed in both basic sets, in addition to small memory overhead, to store additional List<> (but objects are not duplicated as such). Although the speed of adding is not very dependent ( List<> adding O (1)), the speed of removal is slightly reduced.

If you do not need insertion order and index access:

 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 implemented ICollection<TItem> to make it more standard, and also get the initializer syntax of a good collection! :)

Using an example:

 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 4

C #'s dynamic properties seem to indicate that using a dictionary was a popular choice. Other Posts Suggest Using HashTable

Dictionary vs Hashtable