순서가 있는 집합(Ordered Set)

Ordered Set을 구현하는 방법을 살펴보자.

아래는 Ordered Set이 어떻게 동작하는지 보여주는 예제다.

let s = AppleOrderedSet<Int>()

s.add(1)
s.add(2)
s.add(-1)
s.add(0)
s.insert(4, at: 3)

print(s.all()) // [1, 2, -1, 4, 0]

s.set(-1, at: 0) // 이미 인덱스 2에 -1이 있으므로 아무 작업도 수행하지 않음

print(s.all()) // [1, 2, -1, 4, 0]

s.remove(-1)

print(s.all()) // [1, 2, 4, 0]

print(s.object(at: 1)) // 2

print(s.object(at: 2)) // 4

여기서 중요한 차이점은 배열이 정렬되지 않는다는 것이다. 배열에 삽입된 요소들은 그대로 유지된다. 중복 없이 O(logn) 또는 O(1) 검색 시간을 가진 배열을 상상해 보자.

이 아이디어는 O(1) 또는 O(logn) 시간 복잡도를 제공하는 데이터 구조를 사용하는 것이다. 따라서 해시 테이블을 떠올리기 쉽다.

var indexOfKey: [T: Int]
var objects: [T]

indexOfKey는 요소의 인덱스를 추적하는 데 사용된다. objects는 요소를 담는 배열이다.

몇 가지 주요 함수의 세부 사항을 살펴보자.

추가

indexOfKey를 업데이트하고 objects의 끝에 엘리먼트를 삽입한다.

// O(1)
public func add(_ object: T) {
	guard indexOfKey[object] == nil else {
		return
	}

	objects.append(object)
	indexOfKey[object] = objects.count - 1
}

삽입

배열의 임의 위치에 삽입할 때 O(n) 시간이 소요된다.

// O(n)
public func insert(_ object: T, at index: Int) {
	assert(index < objects.count, "인덱스는 객체 개수보다 작아야 함")
	assert(index >= 0, "인덱스는 0보다 커야 함")

	guard indexOfKey[object] == nil else {
		return
	}

	objects.insert(object, at: index)
	indexOfKey[object] = index
	for i in index+1..<objects.count {
		indexOfKey[objects[i]] = i
	}
}

// O(1)
public func set(_ object: T, at index: Int) {
    assert(index < objects.count, "인덱스는 객체 개수보다 작아야 함")
    assert(index >= 0, "인덱스는 0보다 커야 함")

    guard indexOfKey[object] == nil else {
        return
    }

    indexOfKey.removeValue(forKey: objects[index])
    indexOfKey[object] = index
    objects[index] = object
}

제거

배열에서 엘리먼트를 제거하는 작업은 O(n)의 시간 복잡도를 가진다. 이때, 제거된 엘리먼트 이후의 모든 엘리먼트의 인덱스를 업데이트해야 한다.

// O(n)
public func remove(_ object: T) {
	guard let index = indexOfKey[object] else {
		return 
	}

	indexOfKey.removeValue(forKey: object)
	objects.remove(at: index)
	for i in index..<objects.count {
		indexOfKey[objects[i]] = i
	}
}

작성자: Kai Chen