안동민 개발노트

템플릿은 데이터 타입에 독립적인 코드를 작성하여 코드의 재사용성과 유연성을 극대화하는 C++의 핵심 기능입니다.

이제 이 템플릿을 기반으로 구축된 C++의 가장 강력하고 유용한 기능 중 하나인 표준 템플릿 라이브러리(Standard Template Library, STL) 에 대해 알아보겠습니다.

STL은 C++ 표준 라이브러리의 핵심 부분으로, 프로그래밍에서 자주 사용되는 자료구조(컨테이너)와 알고리즘, 그리고 이들을 연결하는 반복자(이터레이터) 등을 템플릿 형태로 제공합니다.

STL을 사용하면 복잡한 자료구조나 알고리즘을 직접 구현할 필요 없이, 이미 검증되고 효율적인 코드를 손쉽게 활용할 수 있습니다.

이번 장에서는 STL의 세 가지 주요 구성 요소 중 하나인 컨테이너(Containers) 에 대해 전반적으로 살펴보겠습니다.

STL의 주요 구성 요소

STL은 크게 세 가지 주요 구성 요소로 이루어져 있습니다.

컨테이너 (Containers): 다양한 종류의 데이터를 저장하고 관리하는 객체입니다. 데이터를 체계적으로 저장하는 자료구조 역할을 합니다.
알고리즘 (Algorithms): 컨테이너에 저장된 데이터를 처리하는 일반화된 함수들의 집합입니다. (정렬, 검색, 복사 등)
반복자 (Iterators): 컨테이너의 요소들에 접근하고 순회할 수 있게 해주는 포인터와 유사한 객체입니다. 컨테이너와 알고리즘을 연결하는 다리 역할을 합니다.

이 외에도 함수 객체(Functors), 어댑터(Adapters), 할당자(Allocators) 등 다양한 보조 구성 요소들이 있습니다.

컨테이너(Containers)란 무엇인가?

컨테이너는 데이터를 저장하고 관리하는 객체입니다. 즉, 자료구조(Data Structure)를 템플릿화하여 구현한 것입니다. std::vector<int>, std::list<std::string>, std::map<int, double>과 같이 특정 타입의 요소를 저장할 수 있도록 템플릿으로 정의되어 있습니다.

컨테이너의 주요 특징

템플릿 기반: 어떤 데이터 타입이든 저장할 수 있도록 일반화되어 있습니다. (예: std::vector<int>, std::vector<MyObject>)
타입 안전성: 저장하는 데이터의 타입을 컴파일 시점에 검사하므로 타입 불일치로 인한 런타임 오류를 방지합니다.
메모리 관리: 대부분의 컨테이너는 내부적으로 메모리를 동적으로 관리하여, 필요에 따라 크기를 자동으로 조절합니다. (사용자가 직접 new/delete를 호출할 필요 없음)
표준화된 인터페이스: 각 컨테이너는 공통적인 멤버 함수(예: size(), empty(), clear(), begin(), end())를 제공하여 일관된 방식으로 사용할 수 있습니다.
효율성: 각 컨테이너는 특정 작업(삽입, 삭제, 검색 등)에 최적화된 자료구조로 구현되어 있습니다.

컨테이너의 종류

STL 컨테이너는 크게 세 가지 범주로 나눌 수 있습니다.

시퀀스 컨테이너 (Sequence Containers)
- 요소들이 선형적인 순서로 정렬되어 저장됩니다.
- 삽입 순서가 유지됩니다.
- 특정 위치에 삽입하거나 삭제하는 연산에 강합니다.
- std::vector
  - 동적 배열(Dynamic Array)입니다.
  - 대부분의 상황에서 가장 권장되는 컨테이너입니다.
  - 임의 접근(Random Access)이 매우 빠릅니다. (O(1))
  - 요소 삽입/삭제 시 (특히 중간에) 비용이 많이 들 수 있습니다. (O(N))
  - 메모리를 연속적으로 할당합니다.
  - 헤더: <vector>
- std::deque (Double-ended Queue)
  - 앞/뒤에서 빠른 삽입/삭제가 가능한 큐(Queue)입니다. (O(1))
  - 임의 접근도 가능합니다. (O(1))
  - vector와 list의 중간 형태라고 볼 수 있습니다.
  - 헤더: <deque>
- std::list
  - 이중 연결 리스트(Doubly Linked List)입니다.
  - 요소 삽입/삭제가 매우 빠릅니다. (O(1))
  - 임의 접근은 불가능하며, 순차 접근만 가능합니다. (O(N))
  - 메모리 오버헤드가 vector보다 큽니다.
  - 헤더: <list>
- std::forward_list (C++11부터)
  - 단일 연결 리스트(Singly Linked List)입니다.
  - std::list보다 메모리 사용량이 적고, 삽입/삭제가 더 빠릅니다.
  - 뒤에서 접근하거나 삽입/삭제하는 기능은 없습니다.
  - 헤더: <forward_list>
연관 컨테이너 (Associative Containers)
- 요소들이 정렬된 순서나 해시된 순서로 저장됩니다.
- 데이터를 키(Key)와 값(Value)의 쌍으로 저장하며, 키를 기반으로 빠르게 검색하는 데 최적화되어 있습니다.
- 내부적으로 트리를 사용하거나 해시 테이블을 사용합니다.
- std::set
  - 고유한(Unique) 키만 저장하는 정렬된 컨테이너입니다.
  - 중복을 허용하지 않으며, 삽입 시 자동으로 정렬됩니다.
  - 빠른 검색, 삽입, 삭제를 제공합니다. (O(log N))
  - 헤더: <set>
- std::multiset
  - std::set과 유사하지만, 중복된 키를 허용합니다.
  - 헤더: <set>
- std::map
  - 고유한 키와 값의 쌍(Key-Value Pair)을 저장하는 정렬된 컨테이너입니다.
  - 데이터를 사전(Dictionary)처럼 키를 통해 값에 접근합니다.
  - 빠른 검색, 삽입, 삭제를 제공합니다. (O(log N))
  - 헤더: <map>
- std::multimap
  - std::map과 유사하지만, 중복된 키를 허용합니다.
  - 헤더: <map>
비정렬 연관 컨테이너 (Unordered Associative Containers) (C++11부터)
- 해시 테이블(Hash Table)을 기반으로 구현됩니다.
- 요소들이 특정 순서로 정렬되지 않습니다.
- 평균적으로 매우 빠른 검색, 삽입, 삭제를 제공합니다. (O(1))
- 최악의 경우 성능이 저하될 수 있습니다. (O(N))
- std::set, std::multiset, std::map, std::multimap과 기능적으로 유사하지만, 정렬되지 않고 해시 기반이라는 차이가 있습니다.
- std::unordered_set
  - 해시 기반으로 고유한 키를 저장합니다.
  - 헤더: <unordered_set>
- std::unordered_multiset
  - 해시 기반으로 중복된 키를 허용합니다.
  - 헤더: <unordered_set>
- std::unordered_map
  - 해시 기반으로 고유한 키와 값의 쌍을 저장합니다.
  - 헤더: <unordered_map>
- std::unordered_multimap
  - 해시 기반으로 중복된 키를 허용합니다.
  - 헤더: <unordered_map>

컨테이너 어댑터 (Container Adapters)

컨테이너 어댑터는 기존 STL 컨테이너(주로 deque나 list)를 기반으로 하여, 특정 자료구조의 기능(인터페이스)만 제공하도록 제한하는 것입니다.

직접적인 자료구조가 아니라, 기존 컨테이너의 기능을 "어댑팅"하여 새로운 행동을 정의합니다.

std::stack: LIFO(Last-In, First-Out) 자료구조입니다.
- push(), pop(), top() 등의 함수를 제공합니다.
- 기본적으로 std::deque를 사용하여 구현됩니다.
- 헤더: <stack>
std::queue: FIFO(First-In, First-Out) 자료구조입니다.
- push(), pop(), front(), back() 등의 함수를 제공합니다.
- 기본적으로 std::deque를 사용하여 구현됩니다.
- 헤더: <queue>
std::priority_queue: 우선순위 큐입니다. 항상 가장 큰(또는 작은) 요소가 먼저 제거됩니다.
- 기본적으로 std::vector를 기반으로 std::heap 알고리즘을 사용하여 구현됩니다.
- 헤더: <queue>

어떤 컨테이너를 선택해야 하는가?

컨테이너의 선택은 프로그램의 성능에 큰 영향을 미칩니다.

다음 질문들을 고려하여 적절한 컨테이너를 선택해야 합니다.

데이터 접근 방식: 임의 접근(인덱스로 바로 접근)이 필요한가요? (Yes: vector, deque / No: list, set, map 등)
삽입/삭제의 빈도와 위치: 중간에 삽입/삭제가 빈번하게 발생하는가요? (Yes: list, map, set / No: vector가 유리)
데이터의 순서: 요소의 삽입 순서가 중요하거나 정렬된 상태를 유지해야 하는가요? (Yes: vector, deque, list, set, map / No: unordered_set, unordered_map)
중복 허용 여부: 동일한 값을 여러 번 저장할 수 있어야 하는가요? (Yes: vector, list, multiset, multimap, unordered_multiset, unordered_multimap / No: set, map, unordered_set, unordered_map)
키-값 쌍 저장 여부: 데이터를 키를 통해 검색해야 하는가요? (Yes: map, multimap, unordered_map, unordered_multimap)
메모리 사용량: 메모리 오버헤드가 중요한가요? (vector는 효율적, list는 포인터 때문에 오버헤드 큼)

대부분의 경우 std::vector가 가장 좋은 기본 선택입니다. 특정 요구사항이 있을 때 다른 컨테이너를 고려하는 것이 좋습니다.

컨테이너 개요

STL의 주요 구성 요소

컨테이너(Containers)란 무엇인가?

컨테이너의 종류

컨테이너 어댑터 (Container Adapters)

어떤 컨테이너를 선택해야 하는가?

On this page