python으로 "순서가 있는" set 자료형을 만들어 보신분?

set같은 자료구조가 필요한데 set은 아이템을 무순서적(?)으로 저장해서 쓸 수 없습니다.

직접 만들어서 쓸 수 밖에 없을 것 같은데 어디서부터 시작해야될지 모르겠습니다 힌트좀 주세요 ㅜㅜ

1답변

  • 좋아요

    0

    싫어요
    채택취소하기

    구글링을 해보니

    import collections
    
    class OrderedSet(collections.MutableSet):
    
        def __init__(self, iterable=None):
            self.end = end = [] 
            end += [None, end, end]         # sentinel node for doubly linked list
            self.map = {}                   # key --> [key, prev, next]
            if iterable is not None:
                self |= iterable
    
        def __len__(self):
            return len(self.map)
    
        def __contains__(self, key):
            return key in self.map
    
        def add(self, key):
            if key not in self.map:
                end = self.end
                curr = end[1]
                curr[2] = end[1] = self.map[key] = [key, curr, end]
    
        def discard(self, key):
            if key in self.map:        
                key, prev, next = self.map.pop(key)
                prev[2] = next
                next[1] = prev
    
        def __iter__(self):
            end = self.end
            curr = end[2]
            while curr is not end:
                yield curr[0]
                curr = curr[2]
    
        def __reversed__(self):
            end = self.end
            curr = end[1]
            while curr is not end:
                yield curr[0]
                curr = curr[1]
    
        def pop(self, last=True):
            if not self:
                raise KeyError('set is empty')
            key = self.end[1][0] if last else self.end[2][0]
            self.discard(key)
            return key
    
        def __repr__(self):
            if not self:
                return '%s()' % (self.__class__.__name__,)
            return '%s(%r)' % (self.__class__.__name__, list(self))
    
        def __eq__(self, other):
            if isinstance(other, OrderedSet):
                return len(self) == len(other) and list(self) == list(other)
            return set(self) == set(other)
    
    
    if __name__ == '__main__':
        s = OrderedSet('abracadaba')
        t = OrderedSet('simsalabim')
        print(s | t)
        print(s & t)
        print(s - t)
    

    이런식으로 만들어진 오픈소스가 있더라고요. 라이브러리 같은데 그냥 이 클래스를 가져다 써도 될것같아서 가져와 봤습니다.

ᕕ( ᐛ )ᕗ
로그인이 필요합니다

작성한 답변에 다른 개발자들이 댓글을 작성하거나 댓글에 좋아요/싫어요를 할 수 있기 때문에 계정을 필요로 합니다.