Constant time OrderedSet

OrderedSet.swift

struct OrderedSet<T: Hashable> {
    private class Link {
        var previous: Link?
        var next: Link?
        var value: T
        init(value: T) {
            self.value = value
        }
    }
    
    private var pos : [T:Link] = [:]
    private var head : Link?
    private var tail : Link?
    
    func contains(value: T) -> Bool {
        return pos[value] != nil
    }
    
    mutating func add(value: T) {
        if pos[value] == nil {
            let link = Link(value: value)
            if let head = self.head {
                link.next = head
                head.previous = link
                self.head = link
            } else {
                self.head = link;
            }
            if self.tail == nil {
                self.tail = link
            }
            pos[value] = link
        }
    }
    
    mutating func remove(value: T) {
        if let link = pos[value] {
            if link === self.head && link === self.tail {
                self.head = nil
                self.tail = nil
            } else if link === self.head {
                link.next?.previous = nil
                self.head = link.next
            } else if link === self.tail {
                link.previous?.next = nil
                self.tail = link.previous
            } else {
                link.previous?.next = link.next
                link.next?.previous = link.previous
            }
        }
        pos[value] = nil
    }
    
    var count : Int {
        get {
            return pos.count
        }
    }
    
    var array : [T] {
        get {
            var array : [T] = [];
            var link = tail
            while link != nil {
                guard let current = link else { break }
                array.append(current.value)
                link = current.previous
            }
            return array
        }
    }
    
    init(values: [T] = []) {
        for value in values {
            add(value: value)
        }
    }
}

Using a bidirectional linked list to keep track of order and a dictionary to provide a uniqueness test along with constant time access to arbitrary locations in the linked list, we can have constant time insertion and deletion in an ordered set.