7. The C++ Libraries I (STL: 컨테이너 · 반복자 · 알고리즘 · 어댑터)

목표

표준 라이브러리(일명 STL)의 3대 축: 컨테이너(Container) · 반복자(Iterator) · 알고리즘(Algorithm)을 연결해서 이해한다.

시퀀스 컨테이너(vector, deque, list)의 차이와 선택 기준을 설명한다.

반복자 카테고리와 const/비-const, 역방향/삽입/스트림 반복자를 활용한다.

핵심 알고리즘(find, count, sort, unique, remove, transform, accumulate 등)을 람다/프레디케이트와 함께 사용한다.

erase–remove idiom, back_inserter, ostream/istream_iterator 등 어댑터를 능숙히 쓴다.

0) 한 장 요약

컨테이너: 데이터를 담는 상자 (vector/deque/list …)
반복자: 컨테이너 원소를 가리키고 이동하는 “포인터 같은” 것
알고리즘: 반복자 구간(first, last)에 대해 동작하는 함수들
어댑터: 인터페이스를 바꿔주는 도우미 (컨테이너/반복자/함수 어댑터)

[컨테이너] ←→ [반복자] ←→ [알고리즘]
         (back_inserter 등 어댑터로 연결 최적화)

1) 시퀀스 컨테이너 비교: 언제 무엇을 쓰나?

컨테이너	특징	장점	주의/단점	사용 예
`vector<T>`	연속 메모리(배열 유사), 임의접근 O(1)	대부분의 경우 가장 빠르고 범용	중간 삽입/삭제 비용 큼(이동/재할당)	수집·정렬·탐색 기본 구조
`deque<T>`	블록 배열, 양끝 삽입/삭제 빠름	`push_front` 효율적, 임의접근 O(1)	중간 삽입/삭제 여전히 비쌈	양끝 큐, 작업 파이프라인
`list<T>`	이중연결리스트, 노드 기반	중간 삽입/삭제 항상 O(1), 반복자 안정적	임의접근 불가(느림), 메모리 오버헤드	자주 중간 삽입/삭제할 때

기본값은 vector: 성능·메모리·호환성의 균형이 가장 좋음. 특별한 이유 있을 때만 다른 컨테이너 선택.

2) 반복자(Iterator) 핵심

2-1. 카테고리(능력치)

Input/Output: 한 방향·한 번 통과
Forward: 한 방향·여러 번 통과
Bidirectional: 앞/뒤로 이동 가능 (list)
Random Access: 임의 접근, 산술/비교 가능 (vector, deque, string)
Contiguous(C++20): 메모리 연속 (vector, string, array)