Set
일련의 값들이 순서를 가지고 (혹은 그 순서는 별로 중요하게 아니더라도) 집합을 이루고 있을 때 사용하는 가장 흔한 자료 구조는 배열이다. 배열은 원소들이 연속적으로 저장된다는 점에 기반하여 임의 원소에 빠르게 액세스할 수 있는 점과 선형적인 구조에 기반한 여러 테크닉들을 적용할 수 있다는 점에서 널리 사용된다.
하지만 배열은 집합과 관련된 문제에 대해서 항상 옳은 선택이 아닐 수 있다. 예를 들어 특정한 값이 집합내에 포함되어 있는지 여부는 contains(_:)
를 통해서 손쉽게 알 수 있지만, 해당 메소드의 시간 복잡도는 $ O_{(n)} $ 이다. 이외에 배열은 두 개 이상의 배열에 대해서 합집합은 원소의 중복을 감안한다면 비교적 쉽게 얻을 수 있으나, 교집합이나 차집합에 대해서는 별도의 로직을 만들어서 이를 구해야하고 이 때의 성능도 거의 항상 $O_{(n)}$일 수 밖에 없다. 즉 개별 원소의 저장소로의 배열보다 집합 자체를 다뤄야 하는 상황이라면 배열보다 더 어울리는 자료구조가 있는데, 그것이 바로 Set
이다.
Set
은 순서없는 원소들의 집합으로 특정 원소의 포함 여부를 효율적으로 확인할 수 있을 때 사용하며, 집합의 원소들의 순서는 상관없을 때 사용한다. 또한, 집합 내 모든 원소는 유일하며 중복되지 않는다. 중복없는 원소를 빠르게 확인하는 것은 해시의 특성으로,Set
의 원소가 되려는 타입 역시Hashable
을 만족해야 하는데, Swift의 기본 타입들은 기본적으로 이를 만족한다.1
생성
Set
은 기본적으로 좌변의 타입이 지정되었을 때 배열 리터럴로 만들 수 있다. 2
var someSet : Set<Int> = [3, 5, 1, 8, 9]
혹은 배열과 비슷하게 init(arrayLiteral:)
이나 init(_:Sequence)
를 이용하는 게 가능하다.
var someSet = Set<Int>(arrayLiteral: 4, 3, 2, 1 9)
배열은 기본적으로 원소의 순서가 없다. 하지만 Collection
프로토콜을 지원하므로 사실, Index
만 알고 있으면 [i]
문법으로 subscript하는 것이 가능하다. 3 대신에 Set
에서 원소와 관련된 연산은 다음과 같은 것들이 주가 되겠다.
- 원소 추가 (
insert(_:)
) - 원소 제거 (
remove(_:)
) 4 - 원소가 있는지 검사 (
contains(_:)
)
var s: Set<Int> = [1, 2, 3, 6, 9, 15]
s.insert(24)
if let r = s.remove(7) { print("removed 7") }
else { print("not found 7") }
if r.contains(9) { print("found 9") }
else { print("not found") }
집합 연산
사실 집합에서는 원소제어보다는 집합 간의 연산이 빛을 발한다. 이는 배열에서는 지원이 사실 좀 미미한 구석도 있고.
포함관계
두 집합 관계를 찾는다. 5
- 동치:
==
로 비교한다. - 포함관계:
isSubset(of:)
,isSuperSet(of:)
로 포함관계를 볼 수 있다. - 엄격한 포함관계:
isStrictSubset(of:)
,isStrictSuperset(of:)
를 이용해서 완전히 포함되는지 여부를 볼 수 있다. isDisjoint(with:)
를 통해서 서로 소 집합인지를 볼 수 있다.
연산
다른 집합을 가져와서 교집합, 합집합, 차집합 및 서로 차집합을 구할 수 있다. 아래의 연산은 모두 새로운 사본을 만드는 것이며, mutating 메소드들은 아래에 다시 기술하겠다.
intersection(_:)
교집합union(_:)
합집합subtract(_:)
차집합symmetricDifference(_:)
대칭차집합
원본을 변경하여 연산하는 메소드는 다음과 같다.
formUnion(_:)
formIntersection(_:)
subtracting(_:)
formSymmetricDifference(_:)
var odds = [1, 3, 5, 7, 9]
var primes = [2, 3, 5, 7, 11]
let u = odds.union(primes) // [1,2,3,5,7,9,11]
let i = odds.intersection(primes) // [3, 5, 7, 9]
let s = odds.subtract(primes) // [1]
let d = odds.formSymmetricDifference(primes) // [1, 11]
그외의 연산
그외의 연산에는 Set
타입이 콜렉션이자 시퀀스임을 기억하면 for in
순회라던지 맵/필터/리듀스를 적용할 수 있는 등의 기능을 지원한다는 것 정도는 알 수 있을 것 같다. 6
let doubleedPrime = primes.map{ $0 * 2 }
// [4, 6, 10, 14, 22]
브릿징
Swift의 Set
이전에 Objective-C 에서는 파운데이션에서 정의한 NSSet
클래스가 있었고, 이 두가지 타입은 브릿징이 되기 때문에 상호간에 바꿔서 쓰는 것이 가능하다. 다만 집합은 1차 타입이 아닌 원소의 타입에 의존하는 2차 타입이기 때문에 다음과 같은 조건을 만족해야 한다. (그리고 이 조건은 Array - NSArray
, Dictionary - NSDictionary
간의 브릿징에서도 동일하게 적용된다.)
Set
의Element
타입이 클래스이거나Element
타입이@objc
지시어에 의해 Objective-C에 노출되게끔 선언되어 있거나- 혹은 파운데이션으로 브릿징되는 타입이어야 한다.
브릿징이 적용될 때 Swift → Objective-C 인 경우에 위의 조건 중 1 혹은 2에 해당하는 경우에는 항상 $O_{(1)}$의 시간/공간 복잡도를 가진다. 3의 경우에는 내부 원소 각각이 브릿징되는 작업이 추가로 필요하므로 $O_{(n)}$ 복잡도를 갖는다.
반대로 Objective-C → Swift의 경우에는 NSSet
이 상수집합으로 넘겨지는 경우에는 상수시간이 소요되지만, mutable한 집합이 되는 경우에는 복사가 일어나야 하며, 이 경우의 시간 복잡도는 정의되지 않았다.
- Apple Developer – Set ↩
- 배열 리터럴이
Array
가 될지Set
이 될지는 좌변의 타입에 의해 결정되므로 좌변에 반드시 변수의 타입을 명시하거나as
를 사용해서 캐스팅해야 한다. ↩ - 해시값에 의해서 각 원소가 저장되는 위치가 정해지므로 subscription은 가능하고 이를 위해서
Index
타입은 필요하지만, 집합내의 각 원소의 위치는 직관적이지는 않으므로 굳이 이게 필요하겠냐 만은… ↩ remove(_:)
는 제거한 원소를 리턴하며, 찾는 원소가 없으면nil
을 리턴한다. 따라서 해당 메소드의 리턴은Element?
타입이다. ↩- 동치관계 연산을 제외하면
Set
외에도Sequence
에 대해서도 연산할 수 있다. ↩ - 물론 원래 타입이
Set
이라 하더라도Sequence
의 맵필터리듀스는 늘 그 리턴타입이[T]
즉,Array
타입이라는 점은 잊지 말자. ↩