How to make a sorted dictionary class?

Question

I am having a hard time writing a class, which should be able to iterate through a sorted dicitonary. My main problem is at the iter-overload. I don't how to get the dic sorted.

class SortedDict():
    def __init__(self, dic = None):
        self.dic = {}
        if len(dic) > 0: self.dic = dic;

    def __iter__(self):
        self.dic = sorted(self.dic.keys())
        self.index = 0
        return self

    def next(self):
        if self.index+1 < len(self.dic):
            self.index += 1
            return self.dic.keys()[self.index]

Do you *need* to create this yourself, or could you use [`collections.OrderedDict`](http://docs.python.org/2/library/collections.html#ordereddict-objects)? — jonrsharpe, Jan 23 '14 at 13:25
You're overwriting the dictionary with the sorted list of its keys, so you lose the values. — chepner, Jan 23 '14 at 13:25

score 5 · Accepted Answer · edited May 23 '17 at 10:31

You don't have to reinvent the wheel. You can simply subclass the dict and implement the SortedDict, like this

class SortedDict(dict):
    def __iter__(self):
        return iter(sorted(super(SortedDict, self).__iter__()))

    def items(self):
        return iter((k, self[k]) for k in self)

    def keys(self):
        return list(self)

    def values(self):
        return [self[k] for k in self]

Thanks Poke and Martijn Pieters, for helping me with this answer.

You can see the difference between collections.OrderedDict, dict and SortedDict.

a = OrderedDict()
a["2"], a["1"], a["3"] = 2, 1, 3
print list(a.items()), a.keys(), a.values()

b = {}
b["2"], b["1"], b["3"] = 2, 1, 3
print list(b.items()), b.keys(), b.values()

c = SortedDict()
c["2"], c["1"], c["3"] = 2, 1, 3
print list(c.items()), c.keys(), c.values()

Output

[('2', 2), ('1', 1), ('3', 3)] ['2', '1', '3'] [2, 1, 3]
[('1', 1), ('3', 3), ('2', 2)] ['1', '3', '2'] [1, 3, 2]
[('1', 1), ('2', 2), ('3', 3)] ['1', '2', '3'] [1, 2, 3]

Could an explanation be added why `items()`, `keys()`, `values()` needs to be re-written? It would seem to me that re-writing `__iter__()` would be sufficient. — NichtJens, Apr 11 '19 at 20:30

score 3 · Answer 2 · answered Jan 23 '14 at 13:26

3

Since you're willing to sort at the point you begin the iteration, all you need is:

def __iter__(self):
    return iter(sorted(self.dic))

__iter__ has to return an iterator, and the builtin function iter() gets one from the sorted list of keys. Job done, no need for a next() function.

answered Jan 23 '14 at 13:26

Steve Jessop

273,490
39
460
699

Very _unlikely_ to be all that's needed to implement a sorted dictionary class. – martineau Jan 30 '15 at 17:37

How to make a sorted dictionary class?

2 Answers2

Linked

Related