STL Container - 개요
C++를 주로 사용하는 개발자라면 빼놓을 수 없는 것이 바로 STL의 Container입니다.
자료구조를 배워본 사람이라면 각 컨테이너마다 어떤 특징이 있고, 무엇을 기반으로 해당 컨테이너가 개발되었는지 대략적으로 파악할 수 있을 것입니다.
본문에서는 컨테이너에 대한 기본적인 개요와 종류를 알아보고, 향후 각 컨테이너에 대한 자세한 설명과 특징, 장단점 등을 정리해 보겠습니다.
컨테이너?
컨테이너는 STL 알고리즘과 결합하여 다양한 데이터 구조를 표현할 수 있도록 설계된 자료형입니다.
각 컨테이너는 자신만의 특징을 가지고, 개발자는 자신이 구현하고자 하는 목적에 맞는 컨테이너를 채택하여 프로그램의 효율성을 높일 수 있습니다.
닭잡는데 소잡는 칼을 사용할 필요는 없습니다
효율성?
효율성을 수치화할 수 있는 가장 대표적인 수단입니다. Big-O 표기법에 의거하여 우리는 해당 컨테이너가 얼마의 성능을 가질 수 있는지 나타낼 수 있습니다.
| 유형 | 표기법 |
|---|---|
| Constant | O(1) |
| Linear | O(n) |
| Logarithmic | O(log(n)) |
| n-log-n | O(n ∗ log(n)) |
| Quadratic | O(n²) |
자세한 내용은 아래 포스트에 상세하게 설명되어 있습니다.
컨테이너의 종류
컨테이너는 대표적으로 4가지 유형을 갖습니다.
- Sequence
- Associative
- Adaptor
- Unordered
Sequence
모든 요소가 특정 위치를 갖는 정렬된 컨테이너입니다. 시퀀스 컨테이너는 순차적으로 엑세스 할 수 있는 데이터 구조가 특징입니다.
대표적인 시퀀스 컨테이너로는 vector가 있습니다.
Associative
연관 컨테이너는 탐색에 최적화된 정렬된 컨테이너입니다. 이것은 O(log N)의 효율성을 가지며 대표적인 연관 컨테이너로는 map이 있습니다.
Associative Container 더 알아보기
Unordered associative containers
C++11 이후부터 추가된 연관 컨테이너의 확장 버전으로, 대표적인 타입으로는 unordered map이 있습니다.
이것은 비정렬을 통하여 더욱 빠른 탐색 속도를 보여주지만 삽입 및 삭제의 순서가 보장되지 않습니다.
예를들어 부분 압축 파일을 unordered map에 저장하여 호출할 경우, 압축 파일의 순서가 보장되지 않기 때문에 기대하지 않은 동작이 호출될 수 있습니다.
반면 독립적인 압축 파일을 여러 개 다룬다고 가정할 때, 각 압축 파일은 상호 종속성이 없기 때문에 map보다 효율적인 데이터 구조를 가질 수 있습니다.
Unordered associative containers 더 알아보기
Container adaptors
컨테이너 어뎁터의 경우 직접적으로 사용할 수 있지만, 주로 위 3개의 컨테이너를 구현하기 위한 베이스 템플릿으로 사용되는 구조입니다.
알고리즘에 자주 등장하는 queue 또는 stack이 이것에 해당됩니다.
또는 C++23 버전에서 컨테이너 어뎁터 종류 중 4종의 flat 자료형이 추가되었습니다.
flat에 대한 자세한 내용은 여기를 참고하세요.