In other words - how do I get it without iterating over "GetEnumerator()"s value (O(n))?
for example, lets say I've created the following ordered dictionary (named aOrdDict), which contains the following pairs:
INDEX KEY VALUE
0 testKey1 testValue1
1 testKey2 testValue2
2 keyToDelete valueToDelete
3 testKey3 testValue3
how do i reveal that "testKey3"s' index within aOrdDict.GetEnumerator() is 3, without performing some procedure of the following sort:
int i = 0;
var ListedPairs = aOrdDict.GetEnumerator();
string wantedKey = "testKey3";
for(; i < aOrdDict.Keys.Count; i++)
{
if (ListedPairs.key == wantedKey)
break;
listedPairs.MoveNext();
}
a little elaboration about the scenery that has led to my question, accompanied by a temporary solution I've implemented, (which is similar to what Martin Liversage suggested at the comments) :
I basically work on some bi-directional client<->server mediator. after a server-->client message enters the mediator & processed, upon feeding it forward to the client, both it's body & the DateTime.Now() value (down to ms) taken that moment should be stored at the mediator in asociation to one another, get packed, and then sent to the client.
later on, the client sends requests to the server, each marked by a specific time-stamp.
it expects to receive some span of stored values which are adjacent & chronologically prior to the input time stamp. at that stage, the ordered Dictionary was supposed to come in handy by allowing me to address the value that was stored at 'timeStamp' by key (hence - the need for a dict), then iterate backwards, value by value, at the opposite order to that in which they were inserted. (hence - the need for a List)
eventually - I used a :
ConcurrentDictionary<string, int> aIndicesDict
for a {timeStamp, index} couple, and a
List<Tuple<string, someObject>> aSomeObjectsList
for a (timestamp, messageBody) couple,
storing the incoming values within both collections every time a new message is sent from the server to the client.
then, upon an incoming request from the client to the server, we get the index related to the input timeStamp (from aIndicesDict - O(1)), allowing us to start iterating backwards from the relevant index of the list of tuples (within aSomeObjectsList - O(1) to get straight to the relevant List Entry).
as I wrote in the comments - I would still like to find a bit more efficient solution (memory wise).
OrderedDictionary
does not provide the functionality that you want. Internally, there is no mapping from key to index. Instead you can map from either key or index to the actual value.
You can build you own ordered dictionary where you internally keep a list and an array: The list maps from index to key and the dictionary maps from key to value. This will provide a way to get the index from the key in O(1) but reading a value by index (and iterating in sequence) would be more costly because of the extra indirection. If you build your own collection you can also use generics which the ancient OrderedDictionary
doesn't do.
However, why do you need to get the index from the key? If you use keys to lookup values and the index really is an ordering then you can perhaps include the "index" (really, the order) in the value?