집합 (추상 자료형)

컴퓨터 과학에서 집합(set)은 고유한 값을 저장할 수 있는 추상 자료형으로, 특별한 순서는 없다. 이는 수학적 개념인 유한 집합의 컴퓨터 구현이다. 대부분의 다른 컬렉션 유형과 달리, 집합에서 특정 요소를 검색하기보다는 일반적으로 값의 집합 포함 여부를 테스트한다.

일부 집합 자료 구조는 구성된 후 변경되지 않는 정적 또는 고정 집합을 위해 설계되었다. 정적 집합은 요소에 대한 쿼리 작업만 허용한다. 예를 들어 주어진 값이 집합에 있는지 확인하거나, 임의의 순서로 값을 열거하는 것 등이다. 동적 또는 가변 집합이라고 불리는 다른 변형은 집합에 요소를 삽입하고 삭제하는 것도 허용한다.

중복집합은 집합에 요소가 여러 번 나타날 수 있는 특별한 종류의 집합이다.

유형 이론

유형 이론에서 집합은 일반적으로 지시 함수(특성 함수)와 동일시된다. 따라서 유형 $A$ 값의 집합은 $2^{A}$ 또는 $𝒫 (A)$ 로 나타낼 수 있다. (부분 유형과 부분 집합은 정제 타입으로 모델링할 수 있으며, 몫집합은 setoid로 대체될 수 있다.) 집합 $S$ 의 특성 함수 $F$ 는 다음과 같이 정의된다.

F (x) = {\begin{matrix} 1, & if x \in S \\ 0, & if x \in̸ S \end{matrix}

이론적으로 다른 많은 추상 자료 구조는 추가 연산 및 표준 연산에 부과된 추가 공리를 가진 집합 구조로 볼 수 있다. 예를 들어, 추상 힙은 가장 작은 값의 요소를 반환하는 `min(S)` 연산을 가진 집합 구조로 볼 수 있다.

연산

핵심 집합 이론 연산

집합의 대수 연산을 정의할 수 있다.

`union(S,T)`: 집합 S와 T의 합집합을 반환한다.
`intersection(S,T)`: 집합 S와 T의 교집합을 반환한다.
`difference(S,T)`: 집합 S와 T의 차집합을 반환한다.
`subset(S,T)`: 집합 S가 집합 T의 부분집합인지 테스트하는 술어이다.

정적 집합

정적 집합 구조 S가 제공할 수 있는 일반적인 연산은 다음과 같다.

`is_element_of(x,S)`: 값 x가 집합 S에 있는지 확인한다.
`is_empty(S)`: 집합 S가 비어 있는지 확인한다.
`size(S)` 또는 `집합의 크기(S)`: S의 요소 수를 반환한다.
`iterate(S)`: 호출될 때마다 S의 값을 임의의 순서로 하나씩 더 반환하는 함수를 반환한다.
`enumerate(S)`: S의 요소를 임의의 순서로 포함하는 목록을 반환한다.
`build(x₁,x₂,…,x_n,)`: 값 x₁,x₂,...,x_n을 가진 집합 구조를 생성한다.
`create_from(collection)`: 주어진 컬렉션의 모든 요소 또는 주어진 반복자가 반환하는 모든 요소를 포함하는 새 집합 구조를 생성한다.

동적 집합

동적 집합 구조는 일반적으로 다음을 추가한다.

`create()`: 새로운, 초기 비어있는 집합 구조를 생성한다.
- `create_with_capacity(n)`: 새로운 집합 구조를 생성하며, 초기에는 비어 있지만 최대 n개의 요소를 담을 수 있다.
`add(S,x)`: 요소 x가 S에 없으면 S에 추가한다.
`remove(S, x)`: 요소 x가 S에 있으면 S에서 제거한다.
`capacity(S)`: S가 담을 수 있는 최대 값의 수를 반환한다.

일부 집합 구조는 이러한 연산 중 일부만 허용할 수 있다. 각 연산의 비용은 구현에 따라 다르며, 집합에 저장된 특정 값과 삽입 순서에 따라 달라질 수 있다.

추가 연산

위의 연산을 통해 (원칙적으로) 정의할 수 있는 다른 많은 연산이 있다.

`pop(S)`: S의 임의의 요소를 반환하고 S에서 삭제한다.^[1]
`pick(S)`: S의 임의의 요소를 반환한다.^[2]^[3]^[4] 기능적으로, 변경자 `pop`은 선택자 쌍 `(pick, rest)`로 해석될 수 있는데, 여기서 `rest`는 임의의 요소를 제외한 모든 요소로 구성된 집합을 반환한다.^[5] `iterate`로 해석될 수 있다.^[a]
`map(F,S)`: 함수 F를 S의 각 요소에 적용하여 얻은 고유한 값들의 집합을 반환한다.
`filter(P,S)`: 주어진 술어 P를 만족하는 S의 모든 요소를 포함하는 부분 집합을 반환한다.
`fold(A₀,F,S)`: 어떤 이항 연산 F에 대해 S의 각 요소 e에 대해 `A_i+1 := F(A_i, e)`를 적용한 후의 값 A_|S|를 반환한다. F는 잘 정의되기 위해 결합 법칙과 교환 법칙을 만족해야 한다.
`clear(S)`: S의 모든 요소를 삭제한다.
`equal(S₁', S₂')`: 주어진 두 집합이 동일한지 (즉, 모든 동일한 요소만 포함하는지) 확인한다.
`hash(S)`: 정적 집합 S에 대한 해시 값을 반환하며, `equal(S₁, S₂)`이면 `hash(S₁) = hash(S₂)`가 된다.

특수 유형의 요소를 가진 집합에 대해 다른 연산을 정의할 수 있다.

`sum(S)`: "합"의 정의에 따라 S의 모든 요소의 합을 반환한다. 예를 들어, 정수나 실수에서는 `fold(0, add, S)`로 정의될 수 있다.
`collapse(S)`: 집합의 집합이 주어지면 합집합을 반환한다.^[6] 예를 들어, `collapse({{1}, {2, 3}}) == {1, 2, 3}`. 일종의 `sum`으로 간주될 수 있다.
`flatten(S)`: 집합과 원자 요소(집합이 아닌 요소)로 구성된 집합이 주어지면, 원래 최상위 집합의 원자 요소 또는 포함된 집합의 요소를 요소로 하는 집합을 반환한다. 즉, `collapse`와 유사하게 한 단계의 중첩을 제거하지만 원자를 허용한다. 이는 한 번만 수행하거나, 재귀적으로 평탄화하여 원자 요소만으로 구성된 집합을 얻을 수 있다.^[7] 예를 들어, `flatten({1, {2, 3}}) == {1, 2, 3}`.
`nearest(S,x)`: x와 값에서 가장 가까운 S의 요소를 반환한다 (어떤 거리에 의해).
`min(S)`, `max(S)`: S의 최소/최대 요소를 반환한다.

구현

집합은 다양한 자료 구조를 사용하여 구현될 수 있으며, 이는 다양한 연산에 대해 다른 시간 및 공간 트레이드오프를 제공한다. 일부 구현은 `nearest` 또는 `union`과 같은 매우 특화된 연산의 효율성을 향상시키기 위해 설계되었다. "범용"으로 설명되는 구현은 일반적으로 `element_of`, `add`, `delete` 연산을 최적화하려고 노력한다. 간단한 구현은 리스트를 사용하는 것으로, 요소의 순서를 무시하고 중복 값을 피하도록 주의한다. 이는 간단하지만 비효율적이다. 집합 멤버십 또는 요소 삭제와 같은 연산은 전체 목록을 스캔해야 하므로 O(n)이다.^[b] 집합은 종종 대신 더 효율적인 자료 구조, 특히 다양한 종류의 트리, 트라이, 또는 해시 테이블을 사용하여 구현된다.

집합은 (지시 함수에 의해) 일종의 맵으로 해석될 수 있으므로, 집합은 일반적으로 (부분) 맵(연관 배열)과 동일한 방식으로 구현된다. 이 경우 각 키-값 쌍의 값은 단위 타입 또는 센티넬 값(예: 1)을 갖는다. 즉, 정렬된 집합에는 자가 균형 이진 탐색 트리 틀:Definition needed (대부분의 연산에 대해 O(log n)을 가짐) 또는 정렬되지 않은 집합에는 해시 테이블 (대부분의 연산에 대해 평균적으로 O(1)이지만 최악의 경우 O(n)을 가짐)을 사용한다. 정렬된 선형 해시 테이블^[8]은 결정적으로 정렬된 집합을 제공하는 데 사용될 수 있다.

또한 맵은 지원하지만 집합은 지원하지 않는 언어에서 집합은 맵을 사용하여 구현될 수 있다. 예를 들어, 펄에서 배열을 해시로 변환하여 센티넬 값 1을 값으로 사용하고 집합으로 사용하는 일반적인 프로그래밍 관용구는 다음과 같다.

my %elements = map { $_ => 1 } @elements;

다른 인기 있는 방법으로는 배열이 있다. 특히 1..n 정수의 부분 집합은 n비트 비트 배열로 효율적으로 구현될 수 있으며, 이는 또한 매우 효율적인 합집합 및 교집합 연산을 지원한다. 블룸 필터는 매우 간결한 표현을 사용하지만 쿼리에서 작은 확률의 오탐 위험을 감수하면서 집합을 확률적으로 구현한다.

부울 집합 연산은 더 기본적인 연산(`pop`, `clear`, `add`)으로 구현될 수 있지만, 특수화된 알고리즘은 더 낮은 점근적 시간 복잡도를 제공할 수 있다. 예를 들어, 집합이 정렬된 리스트로 구현된 경우 `union(S,T)`의 단순한 알고리즘은 S의 길이 m에 T의 길이 n을 곱한 시간에 비례하는 시간이 걸린다. 반면 병합 알고리즘의 변형은 m+n에 비례하는 시간 내에 작업을 수행한다. 또한 서로소 집합 자료 구조와 같이 하나 이상의 이러한 연산에 최적화된 특수 집합 자료 구조가 있다 (다른 연산의 희생을 감수한다).

언어 지원

집합을 지원한 초기 언어 중 하나는 파스칼이었고, 이제 많은 언어가 핵심 언어 또는 표준 라이브러리에 집합을 포함하고 있다.

C++에서는 표준 템플릿 라이브러리 (STL)가 set 템플릿 클래스를 제공하는데, 이는 일반적으로 이진 탐색 트리(예: 레드-블랙 트리)를 사용하여 구현된다. SGI의 STL은 또한 해시 테이블을 사용하여 집합을 구현하는 hash_set 템플릿 클래스를 제공한다. C++11은 해시 테이블을 사용하여 구현되는 unordered_set 템플릿 클래스를 지원한다. 집합에서는 요소 자체가 키이며, 시퀀스 컨테이너와 달리 요소는 (상대적 또는 절대적) 위치를 사용하여 접근된다. 집합 요소는 엄격한 약한 순서를 가져야 한다.
러스트 표준 라이브러리는 일반적인 HashSet 및 BTreeSet 유형을 제공한다.
자바는 집합을 지원하기 위해 Set 인터페이스를 제공하고 (HashSet 클래스는 해시 테이블을 사용하여 구현), 정렬된 집합을 지원하기 위해 SortedSet 서브 인터페이스를 제공한다 (TreeSet 클래스는 이진 탐색 트리를 사용하여 구현).
애플의 Foundation 프레임워크 (Cocoa의 일부)는 오브젝티브-C 클래스 NSSet, NSMutableSet, NSCountedSet, NSOrderedSet 및 NSMutableOrderedSet을 제공한다. CoreFoundation API는 C에서 사용할 CFSet 및 CFMutableSet 유형을 제공한다.
파이썬은 2.4부터 내장 set 및 frozenset 유형을 가지고 있으며, Python 3.0 및 2.7부터는 중괄호 구문을 사용하여 비어 있지 않은 집합 리터럴을 지원한다 (예: {x, y, z}). 빈 집합은 set()을 사용하여 생성해야 하는데, Python은 {}를 빈 딕셔너리를 나타내는 데 사용하기 때문이다.
닷넷 프레임워크는 일반적인 HashSet 및 SortedSet 클래스를 제공하며, 이는 일반적인 ISet 인터페이스를 구현한다.
스몰토크의 클래스 라이브러리에는 포함 테스트를 위해 동등성 및 동일성을 사용하는 Set 및 IdentitySet이 포함되어 있다. 많은 방언은 압축 저장소(NumberSet, CharacterSet), 정렬(OrderedSet, SortedSet 등) 또는 약한 참조(WeakIdentitySet)를 위한 변형을 제공한다.
루비의 표준 라이브러리에는 해시 테이블을 사용하여 집합을 구현하는 Set 및 SortedSet 클래스를 포함하는 set 모듈이 포함되어 있으며, 후자는 정렬된 순서로 반복을 허용한다.
OCaml의 표준 라이브러리에는 이진 탐색 트리를 사용하여 함수형 집합 자료 구조를 구현하는 Set 모듈이 포함되어 있다.
GHC의 하스켈 구현은 이진 탐색 트리를 사용하여 불변 집합을 구현하는 Data.Set 모듈을 제공한다.^[9]
Tcl의 Tcllib 패키지는 TCL 리스트를 기반으로 하는 집합 자료 구조를 구현하는 set 모듈을 제공한다.
스위프트 표준 라이브러리는 Swift 1.2부터 Set 유형을 포함한다.
자바스크립트는 ECMAScript 2015^[10] 표준과 함께 Set을 표준 내장 객체로 도입했다.
얼랭의 표준 라이브러리에는 sets 모듈이 있다.
클로저는 해시 집합에 대한 리터럴 구문을 가지고 있으며, 정렬된 집합도 구현한다.
LabVIEW는 2019 버전부터 집합에 대한 네이티브 지원을 제공한다.
에이다는 Ada.Containers.Hashed_Sets 및 Ada.Containers.Ordered_Sets 패키지를 제공한다.

이전 섹션에서 언급했듯이, 집합을 직접 지원하지 않지만 연관 배열을 지원하는 언어에서는 연관 배열을 사용하여 집합을 에뮬레이트할 수 있다. 요소를 키로 사용하고 무시되는 더미 값을 값으로 사용한다.

중복집합

집합 개념의 일반화는 중복집합 또는 백이다. 이는 집합과 유사하지만 반복되는 ("동일한") 값(중복)을 허용한다. 이는 두 가지 다른 의미로 사용된다. 동일한 값을 동일한 것으로 간주하고 단순히 개수를 세거나, 동일한 값을 동등한 것으로 간주하고 별개의 항목으로 저장하는 것이다. 예를 들어, 사람 목록(이름 기준)과 나이(연령 기준)가 주어진 경우, 나이 중복집합을 구성할 수 있으며, 이는 주어진 나이의 사람 수를 단순히 세는 것이다. 또는, 사람 중복집합을 구성할 수 있으며, 이 경우 두 사람은 나이가 같으면 동등한 것으로 간주된다 (그러나 다른 사람이고 이름이 다를 수 있음). 이 경우 각 쌍 (이름, 나이)를 저장해야 하며, 주어진 나이를 선택하면 주어진 나이의 모든 사람을 얻는다.

형식적으로 컴퓨터 과학에서 객체는 어떤 동치 관계 하에서는 "동일"한 것으로 간주될 수 있지만, 다른 관계 하에서는 여전히 별개일 수 있다. 일부 유형의 중복집합 구현은 별개의 동일한 객체를 자료 구조에 별도의 항목으로 저장하는 반면, 다른 구현은 이를 하나의 버전(처음 발견된 버전)으로 축소하고 요소의 중복도를 양의 정수 카운트로 유지한다.

집합과 마찬가지로 중복집합은 해시 테이블이나 트리를 사용하여 자연스럽게 구현될 수 있으며, 이는 다른 성능 특성을 제공한다.

유형 T에 대한 모든 백의 집합은 표현식 bag T로 주어진다. 만약 중복집합에서 동일한 항목을 동일한 것으로 간주하고 단순히 개수를 센다면, 중복집합은 입력 도메인에서 음이 아닌 정수(자연수)로의 함수로 해석될 수 있으며, 집합을 지시 함수와 동일시하는 것을 일반화한다. 어떤 경우에는 이 계산 의미의 중복집합이 파이썬과 같이 음수 값을 허용하도록 일반화될 수 있다.

C++의 표준 템플릿 라이브러리는 정렬된 중복집합과 정렬되지 않은 중복집합을 모두 구현한다. 이는 연관 컨테이너의 일종인 multiset 클래스를 정렬된 중복집합에 제공하며, 이는 자가 균형 이진 탐색 트리를 사용하여 이 중복집합을 구현한다. 이는 정렬되지 않은 연관 컨테이너의 일종인 unordered_multiset 클래스를 정렬되지 않은 중복집합에 제공하며, 이는 해시 테이블을 사용하여 이 중복집합을 구현한다. 정렬되지 않은 중복집합은 C++11부터 표준이며, 이전에는 SGI의 STL이 복사되어 결국 표준화된 hash_multiset 클래스를 제공했다.
자바의 경우, 서드파티 라이브러리가 중복집합 기능을 제공한다.
- 아파치 커먼즈 컬렉션은 Bag 및 SortedBag 인터페이스를 제공하며, HashBag 및 TreeBag과 같은 구현 클래스를 포함한다.
- 구글 구아바는 Multiset 인터페이스를 제공하며, HashMultiset 및 TreeMultiset과 같은 구현 클래스를 포함한다.
애플은 Cocoa의 일부로 NSCountedSet 클래스를 제공하며, CoreFoundation의 일부로 CFBag 및 CFMutableBag 유형을 제공한다.
파이썬의 표준 라이브러리에는 중복집합과 유사한 collections.Counter가 포함되어 있다.
스몰토크에는 포함 테스트를 위한 술어로 동일성 또는 동등성을 사용하도록 인스턴스화할 수 있는 Bag 클래스가 포함되어 있다.

중복집합 자료 구조를 사용할 수 없는 경우, 해결 방법은 일반적인 집합을 사용하되, 항목의 동등성 술어를 항상 별개의 객체에 대해 "같지 않음"을 반환하도록 재정의하거나 (그러나 이러한 경우 동일한 객체의 여러 발생을 저장할 수 없음) 값을 정수 다중도에 매핑하는 연관 배열을 사용하는 것이다 (이 경우 동일한 요소를 전혀 구별할 수 없음).

백에 대한 일반적인 연산:

`contains(B, x)`: 요소 x가 백 B에 존재하는지 (최소 한 번) 확인한다.
`is_sub_bag(B₁, B₂)`: 백 B₁의 각 요소가 B₁에 나타나는 횟수가 백 B₂에 나타나는 횟수보다 많지 않은지 확인한다. 때때로 B₁ ⊑ B₂로 표기한다.
`count(B, x)`: 요소 x가 백 B에 나타나는 횟수를 반환한다. 때때로 B # x로 표기한다.
`scaled_by(B, n)`: 자연수 n이 주어지면, 백 B와 동일한 요소를 포함하는 백을 반환한다. 단, B에 m번 나타나는 모든 요소는 결과 백에 n * m번 나타난다. 때때로 n ⊗ B로 표기한다.
`union(B₁, B₂)`: 백 B₁ 또는 백 B₂에 나타나는 값만 포함하는 백을 반환한다. 단, 결과 백에 값 x가 나타나는 횟수는 (B₁ # x) + (B₂ # x)와 같다. 때때로 B₁ ⊎ B₂로 표기한다.

SQL의 중복집합

관계형 데이터베이스에서 테이블은 일부 열에 대한 고유성 제약 조건의 존재 여부에 따라 (수학적) 집합 또는 중복집합이 될 수 있다 (이는 후보 키로 바뀐다).

SQL은 관계형 테이블에서 행을 선택하는 것을 허용한다. 이 연산은 일반적으로 중복집합을 산출한다. DISTINCT 키워드를 사용하여 행을 모두 다르게 강제하거나 선택에 기본 키(또는 후보 키)가 포함되지 않는 한 말이다.

ANSI SQL에서 MULTISET 키워드는 서브쿼리를 컬렉션 표현식으로 변환하는 데 사용될 수 있다.

SELECT expression1, expression2... FROM table_name...

는 다른 더 일반적인 쿼리의 서브쿼리 표현식으로 사용될 수 있는 일반적인 SELECT이다. 반면

MULTISET(SELECT expression1, expression2... FROM table_name...)

는 서브쿼리를 컬렉션 표현식으로 변환하며, 이는 다른 쿼리나 적절한 컬렉션 유형의 열에 할당하는 데 사용될 수 있다.

같이 보기

내용주

↑
예를 들어, Python에서 `pick`은 내장 `set`의 파생 클래스에서 다음과 같이 구현될 수 있다.
```
class Set(set):
    def pick(self):
        return next(iter(self))
```
↑ 요소 삽입은 끝에 삽입하여 O(1) 시간에 수행할 수 있지만, 중복을 피하려면 O(n) 시간이 걸린다.

각주

↑ Python: pop()
↑ Management and Processing of Complex Data Structures: Third Workshop on Information Systems and Artificial Intelligence, Hamburg, Germany, February 28 - March 2, 1994. Proceedings, ed. Kai v. Luck, Heinz Marburger, p. 76
↑ Python Issue7212: Retrieve an arbitrary element from a set without removing it; see msg106593 regarding standard name
↑ Ruby Feature #4553: Add Set#pick and Set#pop
↑ Inductive Synthesis of Functional Programs: Universal Planning, Folding of Finite Programs, and Schema Abstraction by Analogical Reasoning, Ute Schmid, Springer, Aug 21, 2003, p. 240
↑ Recent Trends in Data Type Specification: 10th Workshop on Specification of Abstract Data Types Joint with the 5th COMPASS Workshop, S. Margherita, Italy, May 30 - June 3, 1994. Selected Papers, Volume 10, ed. Egidio Astesiano, Gianna Reggio, Andrzej Tarlecki, p. 38
↑ Ruby: flatten()
↑ Wang, Thomas (1997), 《Sorted Linear Hash Table》, 2006년 1월 12일에 원본 문서에서 보존된 문서
↑ Stephen Adams, "Efficient sets: a balancing act", Journal of Functional Programming 3(4):553-562, October 1993. Retrieved on 2015-03-11.
↑ “ECMAScript 2015 Language Specification – ECMA-262 6th Edition” (영국 영어). 《www.ecma-international.org》. 2017년 7월 11일에 확인함.

[6] 예를 들어, Python에서 `pick`은 내장 `set`의 파생 클래스에서 다음과 같이 구현될 수 있다.
class Set(set): def pick(self): return next(iter(self))

[9] 요소 삽입은 끝에 삽입하여 O(1) 시간에 수행할 수 있지만, 중복을 피하려면 O(n) 시간이 걸린다.

[1] Python: pop()

[2] Management and Processing of Complex Data Structures: Third Workshop on Information Systems and Artificial Intelligence, Hamburg, Germany, February 28 - March 2, 1994. Proceedings, ed. Kai v. Luck, Heinz Marburger, p. 76

[3] Python Issue7212: Retrieve an arbitrary element from a set without removing it; see msg106593 regarding standard name

[4] Ruby Feature #4553: Add Set#pick and Set#pop

[5] Inductive Synthesis of Functional Programs: Universal Planning, Folding of Finite Programs, and Schema Abstraction by Analogical Reasoning, Ute Schmid, Springer, Aug 21, 2003, p. 240

[7] Recent Trends in Data Type Specification: 10th Workshop on Specification of Abstract Data Types Joint with the 5th COMPASS Workshop, S. Margherita, Italy, May 30 - June 3, 1994. Selected Papers, Volume 10, ed. Egidio Astesiano, Gianna Reggio, Andrzej Tarlecki, p. 38

[8] Ruby: flatten()

[10] Wang, Thomas (1997), 《Sorted Linear Hash Table》, 2006년 1월 12일에 원본 문서에서 보존된 문서

[11] Stephen Adams, "Efficient sets: a balancing act", Journal of Functional Programming 3(4):553-562, October 1993. Retrieved on 2015-03-11.

[12] “ECMAScript 2015 Language Specification – ECMA-262 6th Edition” (영국 영어). 《www.ecma-international.org》. 2017년 7월 11일에 확인함.

[1]

[2]

[3]

[4]

[5]

[a]

[6]

[7]

[b]

[8]

[9]

[10]

v t e 자료형
공통	비트 바이트 트리트(삼진법) 트라이트 워드
수치	정수형 고정소수점 부동소수점 Complex Bignum 구간 십진 연산
플레인 텍스트	문자 문자열
포인터	주소 참조
복합 자료형	대수적 자료형 (GADT) 배열 연관 배열 클래스 리스트 객체 옵션 타입 프로덕트 타입 레코드 집합 공용체
기타	불리언 자료형 보텀형 수집 열거형 예외 처리 함수형 불투명 자료형 재귀 자료형 세마포어 스트림 톱형 타입 클래스 유닛형 Void
관련 항목	추상 자료형 자료 구조 인터페이스 원시 자료형 파생형 탬플릿 형 구성체 다형성

v t e 자료 구조
유형	컬렉션 컨테이너
추상	연관 배열 우선순위 덱 덱 리스트 멀티맵 우선순위 큐 큐 집합 멀티셋 분리 집합 스택
배열	비트 배열 환형 배열 동적 배열 해시 테이블 해시드 어레이 트리 희소 배열(Sparse array)
연결형	연관 리스트 연결 리스트
트리	B 트리 이진 탐색 트리 AA AVL 레드-블랙 자가 균형 스플레이 힙 이진 힙 피보나치 R 트리 R* R+ 힐버트 트리 해시 트리
그래프	이진 결정 다이어그램
자료 구조의 목록