How to iterate in reverse through an OrderedDictionary

Question

How can I iterate through an OrderedDictionary in reverse and access its keys?

Since it doesn't have any support for LINQ extensions, I have tried the following:

var orderedDictionary= new OrderedDictionary();
orderedDictionary.Add("something", someObject);
orderedDictionary.Add("another", anotherObject);

for (var dictIndex = orderedDictionary.Count - 1; dictIndex != 0; dictIndex--)
{
    // It gives me the value, but how do I get the key?
    // E.g., "something" and "another".
    var key = orderedDictionary[dictIndex];
}

It doesn't matter if you iterate it in reverse or normal order because as documentations states, *The elements of an OrderedDictionary are not sorted by the key, unlike the elements of a SortedDictionary class.* — Ivan Stoev, Jan 18 '17 at 10:53
The insertion order is the reason why I'm using OrderDictionary, I need to iterate it accordingly (in reverse). — pelican_george, Jan 18 '17 at 10:57
You can always iterate through the keys property of a dictionary. — jdweng, Jan 18 '17 at 10:57
@jdweng but I need to iterate the dictionary according to the insertion order, in reverse. During that iteration I need to pick the keys to do other operations. — pelican_george, Jan 18 '17 at 11:00
I see. Unfortunately the class is overencapsulated. The [implementation](https://referencesource.microsoft.com/#System/compmod/system/collections/specialized/ordereddictionary.cs,c5cedabdfd3ba6b2,references) of the indexer is like this `return ((DictionaryEntry)objectsArray[index]).Value;` and you need a method like this `return ((DictionaryEntry)objectsArray[index]);` which does not exist. — Ivan Stoev, Jan 18 '17 at 11:08

Patrick Hofman · Answer 1 · 2017-01-18T10:55:37.687

3

May I suggest to use SortedDictionary<K, V>? It does support LINQ and it is type safe:

var orderedDictionary = new SortedDictionary<string, string>();
orderedDictionary.Add("something", "a");
orderedDictionary.Add("another", "b");

foreach (KeyValuePair<string, string> kvp in orderedDictionary.Reverse())
{
}

Also, as Ivan Stoev pointed out in a comment, the returned items of the OrderedDictionary aren't ordered at all, so SortedDictionary is what you want.

edited Jan 18 '17 at 10:55

answered Jan 18 '17 at 10:53

Patrick Hofman

153,850
22
249
325

I need to keep the insertion order intact, if I'm not mistaken, SortedDictionary won't keep the insertion order. – pelican_george Jan 18 '17 at 10:55
Then use a `Dictionary` – Patrick Hofman Jan 18 '17 at 10:57
1

I don't believe a Dictionary keeps the insertion order as discussed here: http://stackoverflow.com/questions/16694182/ordereddictionary-and-dictionary – pelican_george Jan 18 '17 at 10:58
1

If the order is that important, why not make it the key? – Patrick Hofman Jan 18 '17 at 11:03
1

I want to use the dictionary for fast lookups based on a string key. The dictionary serves 2 purposes, being able to iterate it in regards its insertion order and on a different process to do fast lookups. – pelican_george Jan 18 '17 at 11:06
2

Personally I would separate that in two: a list and a dictionary. The other option of casting can get very expensive when you iterate over it a lot or when you have a lot of items. – Patrick Hofman Jan 18 '17 at 11:10
2

Yeah, this problem's complexity would be greatly lessened if alongside the dictionary you also kept a list of keys as you add them. You could even create a custom class to facilitate this for you. – Abion47 Jan 18 '17 at 11:14
FWIW, a list of keys is just as expensive as a list of items. – Patrick Hofman Jan 18 '17 at 11:16
This should work : sDict.Keys.AsEnumerable().OrderByDescending(x => x).Select(x => sDict[x]) – jdweng Jan 18 '17 at 11:23
It works but it is very expensive on the performance. @jdweng – Patrick Hofman Jan 18 '17 at 11:28
2

@PatrickHofman *Personally I would separate that in two: a list and a dictionary.* This is exactly what the class in question does internally - keeping `ArrayList` and `HashTable` :) MS didn't create a generic version of it, but it's quite easy to roll your own, which I would do if I needed it w/o any over encapsulation or restrictions - there was absolutely no problem to expose what OP wants, not counting the fact that `Keys` and `Values` could have indexers as well. – Ivan Stoev Jan 18 '17 at 11:44
Any linq method is expensive since it will iterate through all the keys. A simple FOR loop is better since you can break out of loop when you find a match instead of checking every key. – jdweng Jan 18 '17 at 12:08

score 3 · Accepted Answer · answered Jan 18 '17 at 11:23

You can lessen the complexity of this problem significantly by using a regular Dictionary (or SortedDictionary, depending on your requirements) and keep a secondary List to keep track of the keys' insertion order. You can even use a class to facilitate this organization:

public class DictionaryList<TKey, TValue>
{
    private Dictionary<TKey, TValue> _dict;
    private List<TKey> _list;

    public TValue this[TKey key]
    {
        get { return _dict[key]; }
        set { _dict[key] = value; }
    }

    public DictionaryList()
    {
        _dict = new Dictionary<TKey, TValue>();
        _list = new List<TKey>();
    }

    public void Add(TKey key, TValue value)
    {
        _dict.Add(key, value);
        _list.Add(key);
    }

    public IEnumerable<TValue> GetValuesReverse()
    {
        for (int i = _list.Count - 1; i >= 0; i--)
            yield return _dict[_list[i]];
    }
}

(And of course add whatever other methods you need as well.)

this achieves what I'm aiming for and will have less restrictions for further customizations. — pelican_george, Jan 18 '17 at 12:23

score 2 · Answer 3 · edited Aug 09 '19 at 13:55

2

Since it doesn't have any support for LINQ extensions...

That's because it's a non-generic Enumerable. You can make it generic by casting it to the right type:

foreach (var entry in orderedDictionary.Cast<DictionaryEntry>().Reverse()) {
    var key = entry.Key;
    var value = entry.Value;
}

edited Aug 09 '19 at 13:55

Peter Mortensen

30,738
21
105
131

answered Jan 18 '17 at 11:51

Dennis_E

8,751
23
29

score 1 · Answer 4 · edited Aug 09 '19 at 13:48

1

You can get an element at an index like this:

orderedDictionary.Cast<DictionaryEntry>().ElementAt(dictIndex);

And for getting the Key:

orderedDictionary.Cast<DictionaryEntry>().ElementAt(dictIndex).K‌ey.ToString();

edited Aug 09 '19 at 13:48

Peter Mortensen

30,738
21
105
131

answered Jan 18 '17 at 10:52

Afnan Ahmad

2,492
4
24
44

I'm gonna give it a try, sounds reasonable to me. – pelican_george Jan 18 '17 at 11:03
2

Beware the O(n) complexity of `ElementAt`. Applying this to each element in the collection will therefore give o(n2) complexity (which is probably going to be quite nasty if used in the wrong place) – spender Jan 18 '17 at 11:14
@spender wasn't aware of that fact. thank you for bringing it up. – pelican_george Jan 18 '17 at 11:15
1

Since you're using `Cast()`, it becomes an `IEnumerable`, so you can use linq and foreach. No need for ElementAt() – Dennis_E Jan 18 '17 at 11:28

score 1 · Answer 5 · edited Aug 09 '19 at 13:52

I am not bothered with the order fact. You can get the key by copying the keys to an indexable collection. Also the condition of the loop needed to be changed to dictIndex > -1;.

Please try this:

var orderedDictionary = new OrderedDictionary();
orderedDictionary.Add("something", someObject);
orderedDictionary.Add("another", anotherObject);

object[] keys = new object[orderedDictionary.Keys.Count];
orderedDictionary.Keys.CopyTo(keys, 0);

for (var dictIndex = orderedDictionary.Count-1; dictIndex > -1; dictIndex--)
{
    // It gives me the value, but how do I get the key?
    // E.g., "something" and "another".
    var key = orderedDictionary[dictIndex];

    // Get your key, e.g. "something" and "another"
    var key = keys[dictIndex];
}

score 0 · Answer 6 · edited Aug 09 '19 at 13:50

If you need to use an OrderdDictionary, you can always use a SortedDictionary like below.

var orderedDictionary = new SortedDictionary<int, string>();

orderedDictionary.Add(1, "Abacas");
orderedDictionary.Add(2, "Lion");
orderedDictionary.Add(3, "Zebera");

var reverseList = orderedDictionary.ToList().OrderByDescending(pair => pair.Value);

foreach (var item in reverseList)
{
    Debug.Print(item.Value);
}

How to iterate in reverse through an OrderedDictionary

6 Answers6