STL 컨테이너 - Queue, Stack, Set, List

Queue

• 선입 선출 (First-in first-out, FIFO) 자료구조 -> 배열이기 때문에, Vector 와 장단점이 비슷하다.

Queue 만들기

Stack

• 후입 선출(Last-in first-out, LIFO) 자료구조

Stack 만들기

Set

• 맵의 키와 같이 정렬되는 컨테이너이다. -> 맵에서 사용되는 키와 동일하다.

• 중복되지 않는 키를 요소로 저장한다.

• 역시 이진 탐색 트리 기반이다. -> 오름차순

• 장단점 또한 Map 과 같다.

List

List 만들기

List 장단점

장점

• 삽입과 제거에 걸리는 시간이 O(1)

• 어느 위치든 삽입 / 제거 가능

단점

• 탐색이 느린 편

• 임의적으로 접근 불가

• 메모리가 불연속적 -> CPU 캐시와 잘 동작하지 못한다. -> 대부분의 경우 Vector 가 더 효과적으로 동작한다.