views:

726

answers:

8

I'm looking for the most ideal data structure (for performance and ease of use) from which values can be retrieved by string key or index. Dictionary doesn't work because you can't really retrieve by index. Any ideas?

A: 

My original answer of hash table is incorrect. It cannot have indexes. Move along.

David Sokol
Hashtables cannot have indexes.
FlySwat
You sir, are incredibly correct. I answered out of impulse because i thought Hashtable.Values was indexable.
David Sokol
A: 

Hash based collections (Dictionary, Hashtable, HashSet) are out because you won't have an index, since you want an index, I'd use a nested generic:

List<KeyValuePair<K,V>>

Of course, you lose the O(1) Key lookup that you get with hashes.

FlySwat
This is hideous. A List gives you O(n) retrieval whereas either a SortedList or SortedDictionary give you O(log n).
Ben Hoffstein
A sortedList also means that the index is worthless. Also, GetByIndex is a O(N) lookup.
FlySwat
A: 

There's System.Collections.ObjectModel.KeyedCollection< string,TItem>, which derives from Collection< TItem>. Retrieval is O(1).

class IndexableDictionary<TItem> : KeyedCollection<string, TItem>
 { Dictionary<TItem, string> keys = new Dictionary<TItem, string>();

   protected override string GetKeyForItem(TItem item) { return keys[item];}

   public void Add(string key, TItem item) 
    { keys[item] = key;
      this.Add(item);
    }
 }
Mark Cidade
KeyedCollection is an abstract class, he would have to implement a Key/Value collection ontop of it.
FlySwat
You only need to implement GetKeyForItem() for a KeyedCollection
Mark Cidade
Using KeyedCollection is almost certainly the best choice if the object contains its key, because you encapsulate the logic of extracting the key in one function rather than everywhere the collection is used.
Greg Beech
A: 

You are looking for something like the SortedList class (here's the generic version as well).

Ben Hoffstein
There's no numeric indexer, so you'll have to use list.Values[i]
Mark Cidade
Or you can just use the GetByIndex() method.
Ben Hoffstein
Right. I was looking at the generic version.
Mark Cidade
SortedList won't preserve the original order of the items, it will sort them in order of the key. This doesn't seem like the semantics the original poster is looking for, though I could be wrong as the question is somewhat ambiguous in this regard.
Greg Beech
He asked for something which can be accessed by key or by index. There was no mention about the order. I am really surprised by some of the answers on this one.
Ben Hoffstein
GetByIndex is O(N), and the index is worthless as it can't be trusted. I can guarantee that the reason he wants index access also means that the index should not randomly change.
FlySwat
+7  A: 

You want the OrderedDictionary class. You will need to include the System.Collections.Specialized namespace:

    OrderedDictionary od = new OrderedDictionary(); 
    od.Add("abc", 1); 
    od.Add("def", 2); 
    od.Add("ghi", 3); 
    od.Add("jkl", 4); 

    // Can access via index or key value:      
    Console.WriteLine(od[1]);       
    Console.WriteLine(od["def"]);
Mitch Wheat
This is not generic. Please check out either the SortedList or SortedDictionary generic classes for best performance.
Ben Hoffstein
OrderedDictionary meets all the requirements stated in the question, if the performance is adequate, and that can only be determined after implementation.
Jeffrey L Whitledge
Ok, but it's hard to imagine why someone would choose this over a generic option unless they were using .NET 1.0 or .NET 1.1.
Ben Hoffstein
Good find, this appears to be the only key/value collection that retains its index.
FlySwat
+2  A: 

One word of warning. The OrderedDictionary has really bad performance characteristics for most operations except insertion and lookup: Both removal and modification of a value may require a linear search of the whole list, resulting in runtime O(n). (For modification, this depends on whether access occurred by index or by key.)

For most operations with reasonable amounts of data, this is completely inacceptable. Furthermore, the data structure stores elements both in a linear vector and in a hash table, resulting in some memory overhead.

If retrieval by index doesn't happen too often, a SortedList or SortedDictionary will have much better performance characteristics (access by index can be achieved through the ElementAt extension method).

If, on the other hand, access by index is the norm, then stop using dictionary data structures alltogether and simply store your values in a List<KeyValuePair<TKey, TValue>>. Although this means a linear search for access by key, all other operations are very cheap and overall performance is hard to beat in practice.

/EDIT: Of course, the latter is also a dictionary data structure in the theoretical sense. You could even encapsulate it in a class implementing the appropriate interface.

Konrad Rudolph
Whats the point of having an index if he has to have an O(N) lookup time to get at it?
FlySwat
System.Collections.ObjectModel.KeyedCollection uses a Dictionary<T>
Mark Cidade
A: 

A Dictionary could work with linq. Although i dont know about possible performance issues. Dictionary.ElementAt(index);

mattlant
AFter thinking about it, it could be bad as i guess it would need to enumerate up to that index.
mattlant
A: 

I recommend using SortedDictionary<string, TValue> or SortedList<string, TValue>. Both have O(log n) search performance.

The differences are, as quoted from the MSDN library:

SortedList<(Of <(TKey, TValue>)>) uses less memory than SortedDictionary<(Of <(TKey, TValue>)>).

SortedDictionary<(Of <(TKey, TValue>)>) has faster insertion and removal operations for unsorted data: O(log n) as opposed to O(n) for SortedList<(Of <(TKey, TValue>)>).

If the list is populated all at once from sorted data, SortedList<(Of <(TKey, TValue>)>) is faster than SortedDictionary<(Of <(TKey, TValue>)>).

In my experience SortedDictionary is more adequate for most typical business scenarios, since the data is usually initially unsorted when using structures like this, and the memory overhead of SortedDictionary is seldom critical. But if performance is key for you, I suggest you implement both and do measurements.

Magnus Akselvoll
You cannot trust the index to remain constant in a sortedList or sortedDictionary.What good is an index that may change midway through a data operation?
FlySwat