C++ STL에는 여러 종류가 있다. 대표적으로 많이 사용하고 중요한 것들 위주로 알아보자.
- vector
- list
- deque(double-ended queue)
- 컨테이너 어댑터
- queue
- priority queue
- stack
- 연관 컨테이너
- 정렬되는 연관 컨테이너
- map
- set
- multiset
- multimap
- 정렬 안되는 연관 컨테이너
- unordered set(hash set)
- unorderd map(hash map)
- 정렬되는 연관 컨테이너
vector
벡터는 배열을 기반으로 만들어졌다. 따라서 배열의 특징을 전부 가지고 있다. 그러나 그냥 배열은 그 크기가 고정적이라는 치명적인 단점이 있다. 그래서 벡터는 이 단점을 해결하기 위해 어떤 방식을 사용한다. 그 방식이란, 배열이 다 찼는데 삽입을 하면 원래 배열보다 더 큰 새로운 배열을 다시 할당하고 새로운 배열에 원래 배열의 내용을 전부 복사해 넣는 것이다. 이 때, 얼마나 더 큰 배열을 새로 할당할 것인지는 상황에 따라 다르다. 보통은 1.5~2배 크기의 배열을 새로 만든다. 너무 크게 만들면 메모리가 낭비되기 쉽고, 너무 작게 만들면 자주 메모리 복사가 일어나 비효율적이다.
- 메모리가 연속된 공간에 할당되어 있다.
- 임의 접근이 매우 빠르다. 인덱스를 통해 메모리 위치만 계산하면 바로 접근이 가능하므로. O(1)
- 중간 삽입이 비효율적이다. 중간에 삽입되면 그 뒤의 아이템들은 모두 한 칸씩 밀어야 하므로. 맨 앞에 삽입할 때가 최악이다. O(n)
- 맨 뒤에 삽입, 삭제가 빠르다.
list
리스트는 양방향 리스트를 기반으로 만들어졌다. 사실 그냥 양방향 리스트 그 자체라고 볼 수 있따. 따라서 리스트의 특성을 전부 가진다. 순차 접근의 경우는 효율이 괜찮지만, 임의 접근의 경우 처음 노드부터 순차적으로 접근해야 하므로 효율이 아주 구리다.
- 임의 접근이 매우 비효율적이다.
- 순차 접근 효율이 좋다.
- 삽입, 삭제가 빠르다. 중간이든 끝이든 빠르다. 노드 사이의 연결 관계만 수정해주면 되므로. O(1)
deque(double-ended queue)
덱은 앞으로도, 뒤로도 아이템을 넣고 뺄 수 있는 자료구조이다. 실행속도를 위해 메모리를 많이 희생한 컨테이너이다. 벡터와 마찬가지로 배열을 기반으로 만들어져있다. 그러나 벡터와는 다른 점이 많다. 덱은 여러 개의 블록(배열과 비슷)을 관리하는 벡터이다. 각 블록에는 배열처럼 여러 개의 아이템이 순차적으로 저장되어 있다. 이미지를 보면 이해가 쉽다.
위와 같은 구조로 인해 그냥 벡터와 비교되는 특징이 있다.
- 뒤쪽 뿐만 아니라 앞쪽에 데이터를 삽입, 삭제하는 작업이 매우 빠르다.
- 모든 아이템이 순차적으로 위치한 것이 아니기 떄문에 각 블록의 위치를 알기 위해 메모리가 낭비된다.
- 블록이 다 차도 다음 블록에 데이터를 삽입하면 되므로 벡터처럼 모든 데이터를 복사해서 옮기는 낭비가 없다.
- 블록 포인터 벡터가 다 차면 다시 더 큰 벡터를 만들어야 한다.
컨테이너 어댑터
컨테이너 어댑터는 특정 컨테이너를 기반으로 만들어진, 그러나 기능이 제한되거나 변형된 컨테이너이다.
대표적으로 stack, queue, priority queue가 있다.
queue
큐는 덱을 기반으로 한 컨테이너 어댑터이다. 리스트를 기반 컨테이너로 사용하도록 지정할 수도 있다. 벡터는 앞에서 빼는 기능을 지원하지 않으므로 불가능하다. 큐는 먼저 들어온 아이템이 먼저 나가는, 선입선출, FIFO 구조이다. 즉 push로 뒤로 아이템을 넣고, pop으로 앞으로 아이템을 빼는 기능만 사용하는 deque이라고 볼 수 있다.
- 선입선출
- 반복자(iterator)사용 안함.
- 임의 접근, 순차 접근, 중간 삽입 등 불가능
priority queue
우선순위 큐라고 한다. 큐와 마찬가지로 컨테이너 어댑터이다. 우선순위 큐는 기본적으로 벡터을 기반으로 만들어졌다. 덱을 기반으로 사용하도록 할 수도 있다. 우선순위 큐는 넣은 아이템들이 내부에서 정렬되어 꺼낼 때에는 우선순위가 높은 것 부터 나오는 구조이다. 기본 우선순위는 값의 내림차순이다. 이는 힙 자료구조와 같은 방식이다.
힙 이란? 완전 이진 트리의 형태이고, 항상 부모의 우선순위가 자식의 우선순위보다 큰 자료구조이다. 자식의 값이 더 큰 경우는 최소 힙 이라고 하고 부모의 값이 더 큰 경우는 최대 힙이라고 한다. 넣을 때에는 아무렇게나 넣어도 꺼낼 때에는 우선순위 대로 나오기 때문에 정렬에 사용되기도 한다. 이를 힙 정렬이라고 한다.
- 넣을 땐 아무렇게나, 나올 땐 정렬된 순서로
- 힙은 완전 이진 트리의 형태이므로 삽입(push), 삭제(pop)의 효율은 완전 이진 트리를 따라간다. (O(logN))
- 큐와 마찬가지로 push, pop의 기능만 있고 반복자가 없다.
stack
스택은 기본적으로 덱을 기반으로 하는 컨테이너 어댑터이다. 벡터를 표준 컨테이너로 사용하도록 지정할 수도 있다. 뒤로 넣고 뒤로 빼는 후입선출, LIFO의 자료구조이다. 큐와 마찬가지로 push, pop을 제외한 기능들은 제한된다. 후입선출이라는 차이점을 빼면 큐와 비슷한 특징을 가진다고 볼 수 있다.
연관 컨테이너
연관 컨테이너란 (key, value)를 하나의 쌍으로 저장하는 컨테이너들입니다.
이들은 정렬되는 연관 컨테이너와 정렬되지 않는 연관 컨테이너로 나뉩니다.
- 정렬되는 연관 컨테이너 : set, map, multi set, multi map
- 특징 : 레드 블랙 트리 기반
- 정렬되지 않는 연관 컨테이너 : unordered가 앞에 붙은 컨테이너들
- 특징 : Hash 기반
map
맵은 레드 블랙 트리를 기반으로 만들어졌다. 레드 블랙 트리는 독특한 규칙을 통해 균형을 맞추는 이진 탐색 트리인 균형 이진 트리이다. 다음과 같은 특징이 있따.
- 삽입, 삭제, 탐색 효율이 나쁘진 않다. O(logN)
- 삽입, 삭제시 매 번 데이터를 정렬하고, 트리의 균형을 맞추기 때문에 마냥 좋지는 않다.
- 각 아이템들이 key, value pair의 형태라는 특징이 있다.
- 기본적으로 key값을 기준으로 오름차순으로 정렬된다. 정렬 기준을 설정할 수도 있다.
- 중복 key를 허용하지 않는다.
set
set은 위에 설명한 map과 같이 레드 블랙 트리를 기반으로 만들어졌다. 때문에 map과 거의 같은 특징을 가지는데, 차이점은 각 아이템들이 key, value pair가 아닌 key 값만 가진다는 점이다. value는 대신 그 key가 존재하는지에 대한 여부(bool)이 들어가있는 느낌으로 사용한다. (e.g) map[key] == true) 그냥 key만 있는 map이라고 생각해도 좋다.
- 삽입, 삭제, 탐색 효율은 map과 동일. O(logN)
- 각 아이템들이 key 라는 점이 map과의 차이점이다.
- 기본적으로 key를 기준으로 오름차순으로 정렬된다. 정렬 기준을 설정할 수도 있다.
- 중복 key를 허용하지 않는다.
multimap, multiset
map과 set에 multi가 붙었다. 이들의 map, set과의 차이점은 중복을 허용한다는 점이다. 그냥 중복을 허용하는 map, set이라고 생각하면 된다. 그 외에는 같은 특징을 가진다.
unorderd map, unordered set
map, set에 unorderd가 붙었다. 이름처럼 데이터들이 정렬되지 않은 map, set처럼 사용하면 된다. 하지만 그냥 map, set과 내부적으로 큰 차이가 있는데, 레드 블랙 트리가 아닌 hash table을 기반으로 만들어졌다는 점이다. (참고로 이 hash table은 list, vector를 기반으로 구현됨.) 따라서 삽입, 삭제, 탐색 등이 O(1) 복잡도로 수행된다는 점이 특징이다. 그래서 일반적인 경우에 그냥 map, set보다 효율적으로 동작한다. 다만 정렬된 데이터가 필요한 경우거나, hash table에 심각한 불균형이 예상되는 경우에는 map, set을 사용하는 것이 좋다.
hash table이란? hash 함수를 사용해 하위 자료구조에 데이터를 저장하는 자료구조를 말한다. 삽입, 삭제, 탐색이 O(1)의 복잡도를 가지는 특징이 있다. 자세한 내용은 링크 참조.
https://ddukddaksudal.tistory.com/53
- 정렬되지 않은 map, set처럼 사용
- 내부 구현이 hash table인 점이 그냥 map, set과의 차이점
- 삽입, 삭제, 탐색이 매우 효율적. O(1) 복잡도
- hash될 key 값의 성질에 따라 효율의 차이가 매우 클 수 있음.
- 클러스터링 현상이 일어나면 메모리 효율이 크게 떨어짐
- hash 값 충돌이 많을 경우, 삽입, 삭제, 탐색의 효율이 O(n) 으로 그냥 map, set 보다 구림.
- hash 함수를 잘 만들면 좋음.