[자료구조] STL

 

 

 

Vector

접근성이 좋다

임의 접근이 가능하다

중간 삽입/삭제는 리소스의 낭비가 발생한다

 

임의 접근이 가능하다는 뜻은 vector<> v; 가 있을 때  v[3]으로 접근이 가능하다는 뜻이다

 

 

 

List

주소값으로 연결되어있다

중간 삽입/삭제가 용이하다

순차 접근만 가능하다 (임의 접근 불가능)

   -> Sort()로 정렬 불가능

 

 

Map

레드 블랙 트리로 되어있고, 시간복잡도는 logN

자료들이 자동으로 정렬되어 저장된다

검색이 용이하다

Key-Value로 이루어져있다

빈번한 삽입/삭제는 부적합하다

중복키 사용 불가능하다

 

 

Unordered_map / Hash map

자동으로 정렬되지 않는다

Map보다 검색 속도가 빠르다

Key값이 길고 복잡하거나 유사한 값이 많은 경우 해시 충돌이 발생할 수 있다

 

 

Set

Key만 저장한다

중복키 사용이 불가능하다

자동으로 정렬되어 저장된다

 

 

 

 

 

Stack

LIFO (Last In First Out)

DFS/재귀에 많이 사용된다

 

 

Queue

FIFO (First In First Out)

BFS/캐시에 많이 사용된다

 

 

Deque

양방향 Queue

 

 

Graph

비선형 자료구조

노드(Node), 정점(Vertices), 엣지(Edge)로 이루어진다

 

 

Tree

비선형 자료구조

계층적 자료구조

최상위 노드(Root), 부모(Parent)노드와 자식(Child)노드로 이루어진다