[C++ STL] 컨테이너

컨테이너의 종류와 선택법

표준 라이브러리에서 제공하는 컨테이너는 다음과 같다.

• 순차 컨테이너: vector, list, forward_list, deque, array, string
• 컨테이너 어댑터: queue, priority_queue, stack
• 정렬 연관 컨테이너: set, multiset, map, multimap
• 비정렬 연관 컨테이너: unordered_set, unordered_multiset, unordered_map, unordered_multimap

연속 메모리(Contiguous memory) 컨테이너는 동적 할당된 하나 이상의 메모리에 데이터를 순차적으로 저장하는 컨테이너이다. 새 데이터가 삽입되거나 이미 존재하는 데이터가 지워지면 주변 메모리에 있던 다른 데이터들은 앞 혹은 뒤로 밀려나면서 새 데이터가 삽입될 공간을 만들든지 지워진 공간을 채운다. 이러한 데이터 이동 때문에 수행 성능에 영향을 미칠 수 있고 예외 안전성(exception safety)에 영향을 미친다. STL에서는 vector, deque, string, string이 있다.

노드 기반(Node-based) 컨테이너는 동적 할당된 하나의 메모리에 하나의 데이터만을 저장한다. 컨테이너에 데이터를 삽입 혹은 삭제하더라도 노드의 포인터만 영향을 받고, 노드의 내용은 그대로 유지된다. 따라서 삽입 혹은 삭제가 일어나도 나머지 요소들이 이동하지 않는다. STL에서는 list, forward_list이 있다.

상황에 따라 적절한 컨테이너를 사용해야 접근, 연산 속도를 줄일 수 있다.