(업데이트 및 수정 중.. https://static-jsony.tistory.com/73 )
STL Container
컨테이너란 데이터를 모아서 저장해 둘 수 있는 제네릭 데이터 구조로, 템플릿(template)로 만들어져 있기에 어떤 데이터 타입이든 저장이 가능하다.
std::array와 std::bitset을 제외한 나머지 컨테이너들은 항목의 갯수에 따라 그 크기가 유동적으로 변하기 때문에 융통성 있게 사용할 수 있다.
|
이름 |
Sequence container |
Associative container [이진탐색트리기반/자동정렬] |
Unordered Associative container [해시 테이블] |
Container adaptor |
bitset |
|
종류 |
- array [배열] - vector [가변배열] - list [양방향 연결리스트] - deque [앞뒤로 넣고 빼는 큐] - forward_list [단방향 연결리스트] |
- set [key만 저장] - map [key/value로 구성] - multimap [key 중복 가능] - multiset [key 중복 가능] |
- unordered_map [정렬되지 않은 map] - unordered_multimap [정렬되지 않은 multimap] - unordered_set [정렬되지 않은 set] - unordered_multiset [정렬되지 않은 multiset] |
- stack (LIFO) - queue (FIFO) - priority_queue [우선순위 큐] |
|
|
특징 |
선형적인 집합 자료를 저장하는 기본 임무에 충실한 일반적인 컨테이너 삽입 삭제에 별 제약이 없음 |
자료저장 + 일정 규칙에 따라 자료를 조직화 하여 관리 신속한 검색을 위해 찾기 좋은 위치에 자동 삽입 |
특정 형태의 동작만 수행 반복자를 지원하지 않음 FIFO / LIFO 등 미리 정한 규칙의 통제를 따름 |
||
|
장점 |
|
빠른 검색 속도 |
|
||
|
단점 |
자료를 넣고 빼는 순서를 외부에서 마음대로 조작할수 없음 |
Sequence container
|
array |
|
|
생성시 stack 영역에 메모리 할당 컴파일타임에 생성되며, 고정된 크기를 가지고 생성된다 ( array<int, 10> arr ) C++11 이전에 존재하던 배열(C-Array / int array[2] = {1,2} 형식으로 생성되던 녀석, 이건 C언어에서 쓰이던 배열이다.)에 벡터의 장점을 더해 만들어진 컨테이너(확실치 않음. 조사 중) array<int, 10> arr = {1,2,3} 으로 생성했을 때, arr[2] 이후로는 0으로 자동 초기화되어 생성 |
|
|
장점 |
단점 |
|
랜덤 엑세스 가능
|
중간 삽입 삭제 느림 런타임때는 크기를 변경 할 수 없음(정적 생성이니..)
|
|
vector |
|
|
동적 배열을 확장 시킨 형태의 컨테이너. 생성 시 heap 영역(혹은 free-store라 한다)에 메모리 할당 요소가 추가되거나 삭제될 때마다 자동으로 메모리를 재할당하여 크기를 동적으로 변경 가장 간단한 시퀸스 컨테이너이다. 요소들을 인접한 메모리 위치에 연속적으로 저장하기에 요소를 빠르게 읽고 쓸 수 있다. 읽기 속도가 빠르기에 정렬이나 이분 검색등의 알고리즘에 대단히 효율적이다. 단, 중간에 요소 삽입시 메모리를 밀고 당기는 작업을 해야하기에 삽입/삭제 속도가 deque나 list에 비해 느리다.
메모리 재 할당 후 이전 원소를 복사 |
|
|
장점 |
단점 |
|
적은 양의 자료에 유리 크기 변경 가능 순차 접근 가능 특정원소 직접 접근 가능 |
중간 삽입 삭제 느림 |
|
list / forward_list |
|
|
이중 연결 리스트의 클래스 템플릿 표현 모든 요소에서 양방향 접근, 빠른 삽입 및 삭제가 가능하지만 임의의 접근은 할 수 없음 [forward_list] 순방향에서만 접근 가능(역방향으로는 접근 불가) 따라서 list보다 더 적은 메모리를 요구 기능적으로는 list / 성능면에서는 forward_list가 유리 |
|
|
장점 |
단점 |
|
적은양의 자료에 유리 어느 위치든 원소 추가/삭제 빠름 크기 변경 가능 순차 접근 가능 |
많은 양의 자료에 불리 특정원소 직접 접근 불가 검색 느림 |
|
deque (double-ended queue) |
|
|
동적 배열 확장 + vector의 단점(메모리 할당 크기를 줄임)을 보완함 vector와 비슷하면서 다른 시퀸스 컨테이너. 어떠한 순서로든 원소 순회 가능
메모리 재 할당 후 이전 원소를 복사하는 벡터와는 달리 메모리 부족시 일정 크기의 새로운 메모리 '블럭'을 할당 |
|
|
장점 |
단점 |
|
앞 뒤 추가 삭제 빠름 저장 원소가 많고 메모리 할당이 큰 경우, vector에 비해 확장 비용이 절감된다. |
중간 삽입 삭제 느림 (그래도 vector보단 빠름) vector와는 다르게 요소들이 인접한 메모리에 연속적으로 저장되는 것이 아님. 따라서 vector에서 가능했던 원소들간의 포인터 연산이 불가능. |
Associative container
|
Map |
|
|
|
|
|
장점 |
단점 |
|
|
|