Detaillierte Einführung in die Implementierung eines geordneten Wörterbuchs in Python (mit Code)

Dieser Artikel bietet Ihnen eine detaillierte Einführung in die Implementierung geordneter Wörterbücher in Python (mit Code). Ich hoffe, dass er für Freunde hilfreich ist.

Wie implementiert man ein Wörterbuch, das die Einfügereihenfolge von Schlüsselwerten beibehalten kann?

Es gibt zwei Hauptpunkte:

Eine doppelt verknüpfte Liste, die zum Aufzeichnen der Einfügereihenfolge von Schlüsselwerten im Wörterbuch verwendet wird

Eine Zuordnung von Schlüsseln und verknüpften Listenknoten, die hauptsächlich verwendet werden. Suchen Sie beim Löschen eines Schlüssels den Knoten, der dem Schlüssel entspricht

Python-Code-Implementierung

class Link:
    __slots__ = 'prev', 'next', 'key'


class OrderDict:
    def __init__(self):
        self.root = Link()
        self.map = {}
        self._node_map = {}
        self.root.next = self.root
        self.root.prev = self.root

    def __setitem__(self, key, value):
        if key in self._node_map:
            self.map[key] = value
        else:
            root = self.root
            last = root.prev
            link = Link()
            link.prev, link.next, link.key = last, root, key
            last.next = link
            root.prev = link
            self._node_map[key] = link
            self.map[key] = value

    def __getitem__(self, item):
        return self.map[item]

    def __delitem__(self, key):
        del self.map[key]
        link = self._node_map.pop(key)
        link_prev, link_next = link.prev, link.next
        link_prev.next, link_next.prev = link_next, link_prev
        link.prev, link.next = None, None

    def pop(self):
        """
        LIFO
        :return:
        """
        if not self._node_map:
            raise KeyError('dict is empty')
        root = self.root
        link = root.prev
        link_prev = link.prev
        link_prev.next = root
        root.prev = link_prev
        link.prev, link.next = None, None
        self._node_map.pop(link.key)
        return self.map.pop(link.key)

    def __iter__(self):
        root = self.root
        curr = root.next
        while curr != root:
            yield curr.key
            curr = curr.next

    def values(self):
        root = self.root
        curr = root.next
        while curr != root:
            yield self.map[curr.key]
            curr = curr.next
    def __str__(self):
        root = self.root
        curr = root.next
        out = []
        while curr != root:
            out.append((curr.key, self.map[curr.key]))
            curr = curr.next
        return str(out)


if __name__ == '__main__':
    d = OrderDict()
    d['a'] = '1'
    d['b'] = '2'
    d['c'] = 'c'    
    print(d)

[Verwandte Empfehlungen: Python-Tutorial]

Das obige ist der detaillierte Inhalt vonDetaillierte Einführung in die Implementierung eines geordneten Wörterbuchs in Python (mit Code). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!