STL 라이브러리_ 자료형

C++의 대표적인 라이브러리인 STL(Standard Template Library)는

말 그대로, C++의 문법인 Template을 활용하여 구현한 자료구조들이다.

 

이러한 Template을 활용하여 내부에는 다양한 자료구조인 컨테이너들을 지원한다

크게 다음의 3 가지 종류의 컨테이너들이 존재한다.

 

1. 순차 컨테이너 (Sequence Container) :

• Vector(벡터) : 대표적인 순차 컨테이너로 순차성을 보장하는 동적 배열이다. 임의 접근과 원소 추가(push_back)은 O(1)을 보장하고 있다
• Deque(덱) :  벡터와 유사한 동적 배열로, 임의 접근과 앞뒤의 원소 추가는 O(1)을 보장하고 있다
• List(리스트) : 리스트는 노드 기반의 시퀀스 컨테이너로, 이중 연결리스트를 기반으로 구현되어 있다.

2. 연관 컨테이너 (Associative Container) 

• Set(집합) : 순차성을 보장하지는 않지만 관련 있는 자료들의 중복 없이 관리할 수 있다. AVL 트리와 같은 형태로 접근, 삽입, 삭제는 O(log N)을 보장하고 있다.
• Map(맵) : Set과 형태가 유사하지만 key 뿐 아니라 value 또한 보관하는 딕셔너리 형 자료구조이다. 접근, 삽입, 삭제는 O(log N)을 보장하고 있다.
• Multiset/map : 여러 키를 가질 수 있는 Set, Map 자료형이다.
• Unordered Set/Map : 정렬되어 정리되는 Set, Map과 달리 정렬되지 않은 형태로 저장한다. 단 해쉬를 통해 접근하기에 거의 O(1)에 가까운 연산 속도를 보장받을 수 있다.

3. 컨테이너 어댑터 (Container Adaptor)

• Stack(스택) : 입출력이 같은 공간에서 일어나는 순차형 컨테이너(LIFO)
• Queue(큐) : 입출력이 반대 공간에서 일어나는 순차형 컨테이너(FIFO)
• Priority_Queue(우선순위 큐, 힙) : 자료들을 우선순위에 맞춰 저장하고 관리하는 큐이다. 이진 트리와 같은 형태로 관리하며 O(LogN)의 연산속도를 보장 받을 수 있다.