Python에서 순서화된 사전 구현에 대한 자세한 소개(코드 포함)

이 글은 Python에서 (코드 포함) 순서화된 사전을 구현하는 방법을 자세히 소개합니다. 도움이 필요한 친구들이 참고할 수 있기를 바랍니다.

키 값의 삽입 순서를 저장할 수 있는 사전을 어떻게 구현하나요?

두 가지 주요 사항이 있습니다:

사전 키 값의 삽입 순서를 기록하는 데 사용되는 이중 연결 목록 ​​

키와 연결 목록 노드 간의 매핑, 주로 키에 해당하는 노드를 찾는 데 사용됩니다. 키 삭제

Python 코드 구현

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)

[관련 권장 사항: python 튜토리얼]

위 내용은 Python에서 순서화된 사전 구현에 대한 자세한 소개(코드 포함)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!