표준 컨테이너는 원소를 저장하는 방식이 다르고, 그 차이 때문에 연산 비용이 다르다. 고르는 기준은 문법의 취향이 아니라 어떤 연산이 잦은가다.

C++ 18. 표준 컨테이너를 고르는 법의 핵심 흐름도
그림. 컨테이너는 자주 수행할 연산과 반복자 무효화 규칙으로 고른다.

어디에 무엇을 담나

컨테이너맞을 때
vector임의 위치 읽기가 많고 끝에 추가한다.
deque앞과 뒤 추가가 모두 잦다.
map키가 정렬된 상태로 있어야 한다.
unordered_map키로 찾는 일이 대부분이고 순서는 필요 없다.
array개수가 컴파일 타임에 고정된다.

`map`과 `unordered_map`의 키는 바뀌면 안 된다. 해시에 넣은 뒤 키를 고치면 원소를 찾지 못한다.

무효화

`vector`가 재할당하면 모든 반복자, 포인터, 참조가 무효가 된다. 중간 삭제는 그 뒤의 원소를 가리키던 것도 무효로 만든다. 원소를 지운 뒤 이전 반복자를 증가시키지 말고, `erase`가 돌려주는 다음 반복자를 쓴다.

노드 기반 컨테이너는 지운 원소만 무효가 되는 경우가 많다. 그 대가로 원소마다 할당과 나쁜 지역성이 따른다. 작은 정수 목록에 `list`를 쓰는 일은 드물다.