Click here to Skip to main content
15,891,136 members
Please Sign up or sign in to vote.
3.00/5 (4 votes)
See more:
Hello everyone,

I need a dictionary type which has an index as well.

This means that besides the word and the meaning of it, each entry must have an index through which I can also access the definition.

Could someone help me create such a type?
Posted
Updated 18-May-11 12:49pm
v2

If you insert relatively infrequently, your keys support ordering, and O(log N) access is OK for your purposes, you can try SortedList[^]: it supports both indexed retrieval (mySortedList.Values[myIndex]) and retrieval by key (mySortedList[myKey]).
 
Share this answer
 
This is alternative solution:

C#
class IndexedDictionary<KEY, VALUE> : System.Collections.Generic.Dictionary<KEY, VALUE> {
    public VALUE this[int index] { get { return GetValueByIndex(index); } }
    VALUE GetValueByIndex(int index) {
        int current = 0;
        foreach (VALUE value in Values) {
            if (current == index)
                return value;
            ++index;
        }
        throw new System.IndexOutOfRangeException();
    } //GetByIndex */
} //IndexedDictionary


This solution is simpler, it does not use any redundancy and does not slow down Add/Remove/Clear but is slow on this indexer — as slow as O(N) (see http://en.wikipedia.org/wiki/Big_O_notation[^]).

—SA
 
Share this answer
 
Here is the solution:

C#
class IndexedDictionary<KEY, VALUE> : System.Collections.Generic.Dictionary<KEY, VALUE> {
    public VALUE this[int index] { get { return Index[index]; } }
    new public void Add(KEY key, VALUE value) {
        base.Add(key, value);
        RebuildIndex();
    } //Add
    new public void Remove(KEY key) {
        base.Remove(key);
        RebuildIndex();
    } //AddRange
    new public void Clear() {
        base.Clear();
        RebuildIndex();
    } //Clear
    void RebuildIndex() {
        Index = new VALUE[this.Keys.Count];
        if (this.Values.Count > 0)
            this.Values.CopyTo(Index, 0);
    } //RebuildIndex
    KEY[] Index = new KEY[0];
} //IndexedDictionary


This solution is effective when you read it a log but update less, as Add/Remove/Clear is a bit costly. Pay attention for the importance of new specifier; it helps to remove the warning. If you want you can modify this code to return KeyValuePair or KEY.

—SA
 
Share this answer
 
v4
Comments
yesotaso 18-May-11 14:23pm    
I think,
class IndexedDictionary<TKey,TValue> : System.Collections.Generic.Dictionary<TKey,TValue>
{
public TValue this[int index] {
get
{
if (typeof(TKey) != typeof(int))
{
if (index >= this.Count)
throw new IndexOutOfRangeException();
return this.Values.ElementAt(index);
}
else
{
var x = this.Where(p => p.Key.Equals(index));
if (x.Count() == 0)
throw new ArgumentOutOfRangeException();
return x.First().Value;
}
}
}
}

Edit: This should work as well, the "else" part requires a little re-work.
Sergey Alexandrovich Kryukov 18-May-11 17:57pm    
Good idea, but this is not expected indexing. It will work only if consecutive integer keys are used. Can you see it?

Besides, I think the "else" section is redundant; why returning first value? But this is philosophical question.
I though about it but decided to implement only the universal solution without specialization.

I have in mind one more solution without building the Index, but it needs Reflection (only at construction, so the implementation will be generally faster) and some research. I did not want to spend time on it.

--SA
Sergey Alexandrovich Kryukov 18-May-11 18:34pm    
Code simplified, see my update.
--SA

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900