임의 타입의 객체를 보관하는 자료구조 객체
C++ STL 컨테이너에는 크게 네종류가 있음
- 시퀀스 컨테이너
- 연관 컨테이너
- 해시 컨테이너
- 컨테이너 어댑터
1. 시퀀스 컨테이너(Sequence containers)
1) 개념
- 선형 자료구조로 데이터들을 연속적으로 보관함
다만 array와 vector를 제외하면 메모리상에 꼭 연속적으로 존재하지는 않을 수 있고
값들 사이에 순서가 있다 정도로 생각하는게 맞음
- 중복된 데이터를 허용함
- 원소 자체를 보관하는 목적이 강함
2) 종류
- array : 기본 배열과 같은 고정된 크기의 선형구조
- vector : 뒷쪽으로 자료를 추가할 수 있는 동적으로 크기 조절이 되는 선형구조
- list : 이중 연결 리스트
- forward_list : 단일 연결 리스트
- deque : 앞, 뒷쪽 양쪽으로 자료를 추가할 수 있는 동적으로 크기 조절이 되는 선형구조
기본적으로 vector를 사용하되
중간에 값을 넣고 빼는 경우가 많으면 list를 쓰고
앞뒤 양끝에 값을 자주 넣고 빼는 경우엔 deque를 쓴다
2. 연관 컨테이너(Associative Containers)
1) 개념
- 트리구조로 구현되며, key-value 구조
- 데이터를 컨테이너에 넣는 순간 정렬됨
- 기본적으로는 중복값을 허용하지 않음(multi로 사용해야 중복값 허용)
- 키가 존재하는가, 혹은 키에 대응하는 값이 무엇인가를 해결하기 위한 목적이 강함
2) 종류
- set : 중복을 허용하지 않고, 값을 정렬해서 보관하며, 데이터 중에 키값이 존재하는지 존재유무에 중점을 둠
- map : 중복을 허용하지 않고, 값을 key 기준으로 정렬해서 보관하며, 데이터 중에 키값이 존재한다면 그에 대응하는 값이 무엇인가에 중점을 둠
- multiset : 중복데이터를 허용하는 set
- multimap : 중복데이터를 허용하는 map
3. 해시 컨테이너(Unordered Associative Containers)
1) 개념
- 해시키를 이용하는 자료구조
- 연관 컨테이너와 달리 데이터를 넣을때 정렬하지 않음
- 연관 컨테이너에 비해 성능이 월등히 좋음
- 단 기본 라이브러리로 제공되는 자료형이 아닌, 직접 구현하는 상황에서는 해시키를 만드는데 주의해야 함
- 속도가 아주 빨라야 하는경우 사용
2) 종류
- unordered_set : set과 비슷하지만 값을 정렬하지 않고, 해시구조이므로 속도가 월등함
- unordered_map : map과 비슷하지만 값을 정렬하지 않고, 해시구조이므로 속도가 월등함
- unordered_multiset : set과 비슷하지만 값을 정렬하지 않고, 중복값을 허용하며, 해시구조이므로 속도가 월등함
- unordered_multimap : map과 비슷하지만 값을 정렬하지 않고, 중복값을 허용하며, 해시구조이므로 속도가 월등함
4. 컨테이너 어댑터(Container Adapters)
1) 개념
- 대표적으로 stack과 queue가 있음
- 기존의 컨테이너인 vector, deque 등을 상속받아 특정 기능들을 추가/제거한 것
- 인터페이스를 제공하기 위한 목적으로 디자인패턴의 어댑터 패턴을 생각하면 이해가 빠름
- 예를들어 stack은 default로 deque로 구현되어 있는데 stack은 deque를 후입선출 방식으로 변환해둔 어댑터와 같음
deque에 stack의 인터페이스인 top, pop, push등의 인터페이스를 사용할 수 있게 되는 것
2) 종류
- stack : deque를 후입선출(List In First Out)로 저장하는 방식으로 변환하는 어댑터 클래스
- queue : deque를 선입선출(First In First Out)로 저장하는 방식으로 변환하는 어댑터 클래스
- priority_queue : vector를 우선순위큐로 변환하는 어댑터 클래스