언제 어느 컨테이너를 사용할 것인가?

언제 어느 컨테이너를 사용할 것인가?

기본적으로 Vector를 사용하자 - 간단한 내부 자료구조를 사용하며 랜덤 엑세스를 지원한다.

컨테이너의 앞과 끝부분에 자주 삽입/제거한다면, deque를 사용하자.

제거, 삽입, 이동을 컨테이너의 중간 위치에서 자주 한다면, list 사용을 고려하자.

(but, list는 랜덤 엑세스를 지원하지 않는다.)

원소를 자주 검색해야 한다면 set, multiset을 사용하자.

(why? 복잡하게 뒤얽힌 1000개의 원소에 대해서 원칙적으로 10번의 비교면 가능하다.)

	vector	deque	list	set	multiset	map	multimap
내부자료구조	동적 배열	배열의 배열	이중 링크드 리스트	바이너리 트리	바이너리 트리	바이너리 트리	바이너리 트리
원소	value	value	value	value	value	key/value	key/value
중복 허용 여부	허용	허용	허용	허용 안함	허용	key에 대해서만 허용 안함	허용
랜덤 엑세스 여부	허용	허용	허용 안함	허용 안함	허용 안함	key를 사용하여 가능	허용 안함
반복자 카테고리	랜덤 엑세스	랜덤 엑세스	양방향	양방향(원소는 상수이다)	양방향(원소는 상수이다)	양방향(key는 상수)	양방향(key는 상수)
원소의 검색/찾기	느림	느림	매우 느림	빠름	빠름	key에 대해서 빠름	key에 대해서 빠름
원소의 삽입 및 제거가 빠른 구간	컨테이너의 끝	컨테이너의 앞과 끝	아무곳에서나	-	-	-	-
삽입/제거 동작의 반복자와 레퍼런스, 포인트의 무효화	재할당시	항상	일어나지 않음	일어나지 않음	일어나지 않음	일어나지 않음	일어나지 않음
제거된 원소에 대한 메모리 해제 여부	일어나지 않음	가끔 일어남	항상 일어남	항상 일어남	항상 일어남	항상 일어남	항상 일어남
메모리 예약의 허용 여부	허용	허용 안함	-	-	-	-	-
트랜잭션 안정성(성공하거나 아무런 영향도 없다)	push, pop	push, pop	sort()와 할당 연산자를 제외한 모든 연산들	다중 원소 삽입 제외한 모든 연산	다중 원소 삽입 제외한 모든 연산	다중 원소 삽입 제외한 모든 연산	다중 원소 삽입 제외한 모든 연산

ref : C++ Standard Library 

Josuttis, Nicolai M. 저