Dictionary with index

Question

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 18-May-11 5:54am

Red&Black

Updated 18-May-11 12:49pm

Dalek Dave

v2

Add a Solution

3 solutions

Solution 3

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

Posted 18-May-11 8:13am

Sergey Alexandrovich Kryukov

Updated 18-May-11 12:34pm

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

Solution 4

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

Posted 18-May-11 13:23pm

Sergey Alexandrovich Kryukov

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

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

dasblinkenlight · Accepted Answer · 2011-05-18T16:03:00

Solution 5

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]).

Posted 18-May-11 16:03pm

dasblinkenlight