[C++][STL] 컨테이너(Container)

컨테이너란(Container)?

STL 구성 요소

• STL의 구성 요소(반복자, 컨테이너, 알고리즘) 중 하나.
  • STL은 Standard Template Library의 약자로, C++에서 템플릿을 이용해 정리해 둔 표준 라이브러리를 말한다.
• 컨테이너는 같은 타입의 데이터를 저장하는 자료구조 클래스이다.
• STL에서 제공하는 컨테이너는 클래스 템플릿(class template)의 형태로 구현되어 있기 때문에 임의의 타입을 가진 객체(원소)들을 저장할 수 있다.

컨테이너 원소에 접근하는 법

• 컨테이너는 자신이 보관하는 원소(elememt)들의 메모리를 관리하며, 각각의 원소에 접근할 수 있도록 멤버 함수를 제공한다.
• 컨테이너 상에서 원소에 접근하는 방법으론 크게 2가지로,
  • 하나는 멤버 함수를 직접 호출하여 접근하는 것이고,
  • 다른 하나는 반복자(iterator)를 이용해서 접근하는 것이다.

---

STL 컨테이너 종류

• 시퀀스 컨테이너(Sequence Containers)
  • vector, list, deque, array 등
• 연관 컨테이너(Associative Containers)
  • set, map, multiset, multimap, unordered_set, unordered_map 등
• 컨테이너 어뎁터(Container Adapters)
  • stack, queue, priority_queue 등

---

시퀀스 컨테이너(Sequence Containers)

• 시퀀스 컨테이너는 순서(Sequence)를 유지하면서 데이터를 저장하는 컨테이너다.
• 원소들을 인덱스(index)나 반복자(iterator)를 통해 순차적으로 접근할 수 있으며, 위치를 기준으로 삽입 / 삭제가 가능하다.

 

시퀀스 컨테이너 종류

컨테이너	내부 구조	특징
std::vector	동적 배열	빠른 임의 접근(O(1)), 끝에서 삽입/삭제 O(1), 중간 삽입/삭제 O(N)
std::deque	동적 배열 + 리스트 구조	앞뒤 삽입/삭제 O(1), 중간 삽입/삭제 O(N)
std::list	이중 연결 리스트	중간 삽입/삭제 O(1), 임의 접근 O(N)
std::forward_list	단일 연결 리스트	메모리 절약, 중간 삽입/삭제 O(1), 역방향 탐색 불가
std::array	정적 배열 (C++11)	고정 크기, 임의 접근 O(1), 크기 변경 불가

 

---

연관 컨테이너(Associative Containers)

• 연관 컨테이너는 키(key)와 값(value)을 연관 지어 데이터를 저장하는 컨테이너이다.
• 빠른 검색에 특화된 자료 구조이며, 정렬을 유지하는 컨테이너는 O(logN), 정렬을 유지하는 컨테이너는 O(1)의 시간복잡도를 가진다.
• 많은 양의 자료를 검색하는데 용이하다.

 

연관 컨테이너 종류

컨테이너	내부 구조	키 중복 허용 여부	정렬 여부
std::set	이진 탐색 트리(RB-Tree)	❌ 중복 불가	✅ 자동 정렬
std::multiset	이진 탐색 트리(RB-Tree)	✅ 중복 가능	✅ 자동 정렬
std::map	이진 탐색 트리(RB-Tree)	❌ 중복 불가	✅ 자동 정렬 (key 기준)
std::multimap	이진 탐색 트리(RB-Tree)	✅ 중복 가능	✅ 자동 정렬 (key 기준)
std::unordered_set	해시 테이블(Hash Table)	❌ 중복 불가	❌ 정렬되지 않음
std::unordered_map	해시 테이블(Hash Table)	❌ 중복 불가	❌ 정렬되지 않음

 

---

컨테이너 어뎁터(Container Adapters)

• 컨테이너 어뎁터는 기존 컨테이너(deque, vector, list 등)를 감싸서 "특정 용도로 변형한" 컨테이너이다.

여기서 어뎁터(Adapters)란?
    - 기존 클래스나 시스템을 수정하지 않고, 새로운 인터페이스에 맞춰 변환하는 디자인 패턴을 말한다.

• 컨테이너 어뎁터는 내부 컨테이너의 특성을 따라간다.
  • 예를 들어 deque를 감쌌다면, deque의 특성(높은 메모리 사용량)을 따라간다.
  • 내부 컨테이너는 원한다면, 기본 컨테이너가 아닌 다른 컨테이너(vector, list)로 변경할 수 있다.
• 컨테이너 어뎁터는 새로운 인터페이스를 제공한다. 새로운 인터페이스는 1) 내부 컨테이너의 일부 기능을 제한하거나, 2) 현재 컨테이너에 맞게 변형된 기능을 제공한다.

 

컨테이너 어뎁터 종류

컨테이너	내부 컨테이너 (기본)	특징
std::stack	deque	LIFO(Last In, First Out), push(), pop(), top() 지원
std::queue	deque	FIFO(First In, First Out), push(), pop(), front(), back() 지원
std::priority_queue	vector (힙)	최대 힙 구조 (기본), 가장 큰 요소를 빠르게 가져옴

 

---

참고 자료

https://modoocode.com/174

https://modoocode.com/223

https://en.cppreference.com/w/cpp/container