코드를 읽고 설명하면, 합격합니다
이 레슨과 관련된 학습 키워드
C++ 프로그래밍 — 성능과 추상화의 균형 → 모던 C++
오늘은 STL 컨테이너가 왜 필요한지 살펴보겠습니다.
C++ 표준 라이브러리 STL은 검증된 범용 데이터 구조 모음입니다.
벡터, 맵, 언오더드맵, 리스트 등 20여 종의 컨테이너를 제공합니다.
직접 구현하면 어떤 문제가 생길까요?
첫째, 배열 경계 검사를 빠뜨리면 버퍼 오버플로가 발생합니다.
이는 CVE 보안 취약점의 가장 많은 원인이 됩니다.
둘째, 팀마다 인터페이스가 달라 코드 리뷰 비용이 폭증합니다.
셋째, STL은 빅오 복잡도를 표준으로 보장해 성능 비교를 쉽게 해줍니다.
그림 가운데를 보세요.
STL은 컨테이너·이터레이터·알고리즘 세 축으로 설계되어 있습니다.
이터레이터는 두 축을 연결하는 범용 커서 역할을 합니다.
USB 포트 비유처럼, 키보드를 바꿔도 컴퓨터는 그대로 작동합니다.
그림 왼쪽을 보시면 컨테이너 종류가 정리되어 있습니다.
벡터는 연속 메모리, 리스트는 양방향 연결 구조입니다.
맵과 셋은 정렬을 유지하며 로그 엔 탐색을 보장합니다.
언오더드맵은 해시 기반으로 평균 오원 탐색이 가능합니다.
오른쪽에는 소트, 파인드, 트랜스폼 등 알고리즘이 나와 있습니다.
그런데 벡터와 리스트에 동일한 소트를 쓸 수 없는 이유가 있습니다.
그림 중간을 보시면 이터레이터 종류별 차이가 보입니다.
벡터는 랜덤 액세스 이터레이터라 임의 접근이 가능합니다.
그래서 표준 소트 적용 시 오 엔 로그 엔 인트로소트가 동작합니다.
반면 리스트는 앞뒤 이동만 가능해 소트 적용 시 컴파일 에러가 납니다.
리스트는 자체 정렬 함수를 따로 사용해야 합니다.
하단 왼쪽을 보시면 벡터 뒤 삽입이 왜 분할상환 오원인지 설명됩니다.
용량 초과 시 두 배 확장 후 복사하는데, n번 삽입의 복사 총합은 약 2n입니다.
2n을 n으로 나누면 평균 비용은 오원, 이것이 분할상환 오원의 의미입니다.
하단 오른쪽 사용 사례도 살펴보겠습니다.
순차 접근과 캐시 효율이 중요하면 벡터, 양쪽 삽입이 잦으면 덱을 씁니다.
키-값 빠른 조회엔 언오더드맵, 구글 검색 인덱스가 대표적인 예입니다.
컨테이너를 바꿔도 알고리즘은 그대로, 이것이 STL이 30년간 C++ 근간인 이유입니다.