STL Containers
컨테이너란?
다른 객체들을(원소) 보관하는 하나의 큰 보관소라고 보면된다. STL 컨테이너는 클래스 템플릿의 형태로 구현되어져 있기 때문에 임의의 타입 원소들을 위한 컨테이너를 만들 수 있다.
1. 시퀀스 컨테이너 (Sequence Container)vector, deque, list
컨테이너 어뎁터 (Container Adaptor)
stack, queue, priority_queue
연관 컨테이너 (Associative Container)
set, multiset, map, multimap, bitset
시퀀스 컨테이너 (Sequence Container)
Vector
vector 는 자동으로 메모리가 할당되는 배열이라고 생각하면 된다. 원소의 삽입과 삭제가 용이하지만 중간값에 대한 삽입과 삭제가 빈번히 일어난다면 비효율적이다.
Deque
vector의 단점을 보완하기 위해 만들어진 컨테이너이다. 배열기반 구조이며 vector와는 다르게 여러개의 메모리 블록을 할당하고 하나의 블록처럼 여기는 기능을 제공한다. deque는 메모리가 부족할 때 마다 일정한 크기의 새로운 메모리 블록을 할당한다.
컨테이너 어뎁터 (Container Adaptor)
List
이중 연결 리스트라 생각하면 되는 컨테이너이다. 임의접근 반복자는 불가능하다.
Stack
LIFO(Last In First Out) 구조의 컨테이너이다. deque를 기반으로 만들어졌다. 하지만 iterator를 통한 접근은 불가능하다.
Queue
FIFO(First in First Out) 구조의 컨데이너이다. Stack과 비슷한 구조이다.
Priority Queue
지정된 우선순위 규칙에 따라 우선순위가 큰 데이터를 먼저 반환하는 자료구조이다. 최대값 또는 최소값을 반환하도록 규칙 자체를 커스텀 할 수도 있다.
내부적으로 힙(heap)이라는 완전 이진트리 형태의 자료구조로 구현이된다.
연관 컨테이너 (Associative Container)
연관 컨테이너는 공통적으로 노드 기반 컨테이너이며 균형 이진트리로 구현되어져있다. 또한 멤버 변수, 생성자 등이 거의 동일하다.
Set
key라 불리는 원소들의 집합으로 이루어진 컨테이너 이다. key값은 중복을 허용하지 않는다. 기본으로 오름차순 정렬된다.
MultiSet
key값 중복이 가는한 set이다.
Map
각 노드가 key와 value 쌍으로 이루어진 트리이다. map은 first, second가 pair로 저장된다. 기본으로 오름차순 정렬된다.
MultiMap
map과 마찬가지이지만 key의 중복을 허용한다.
Bitset
비슷한 vector < bool > 클래스와 달리 클래스에는 bitset 반복기가 없으며 C++ 표준 라이브러리 컨테이너가 아니다. 간단히 정수를 이진수로 변환한 값으로 보여주는 컨테이너라 생각하면 된다.
Iterator
c++ 라이브러리는 반복자(iterator)를 통해 컨테이너레 저장되어 있는 원소를 훑을 수 있도록 하는 포인터와 비슷한 객체를 제공한다.
예시로 각 컨테이너들을 사용하다보면 container.begin(), container.end() 와 같은 멤버 함수가 존재하는데 이는 컨테이너의 iterator를 반환하는 함수이다.
