티스토리 뷰

Programming/자료구조 & STL

STL - 컨테이너

황금표정 2012. 1. 31. 04:34
1. 컨테이너의 종류

컨테이너에는 종류가 있는데 시퀀스 컨테이너, 연관 컨테이너, 어댑터 컨테이너가 있다.
컨테이너가 종류별로 나누어져 있는 이유는 각각에 특성이 있기 때문이다.


2. 시퀀스 컨테이너

삽입과 삭제의 규칙이 존재하지 않는 컨테이너이다.

시퀀스 컨테이너에는 Vector, List, Deque가 있다.

- Vector -
#include <vector>를 추가해야 사용가능.
입력된 순서대로 저장함.
동적 배열로 되어있기 때문에 삽입과 삭제가 느리다.
랜덤 액세스(Random Access)가 빠르다.
삽입, 삭제시 반복자 무효화 현상이 일어날 수 있다.

- List -
#include <list>를 추가해야 사용가능.
순서가 있는 리스트
벡터와 유사하지만 중간에서 자료를 추가하는 연산이 효율적이다.
삽입, 삭제가 빠르다.
랜덤 액세스(Random Access)가 느리다. (List 구조는 랜덤 액세스를 지원하지않기 때문에)

- Deque -
#include <deque>를 추가해야 사용가능.
양쪽 끝에서 입력과 출력이 가능.
벡터와 유사하지만 앞에서도 자료들이 추가 될 수 있음.
랜덤 액세스(Random Access)가 Vector보다 약간 느리다.
중간에 자료를 추가하는 연산은 비효율적이다.


3. 어댑터 컨테이너

기존 컨테이너의 기능 중 일부만을 공개하여 기능이 제한되거나 변형된 컨테이너
어댑터 컨테이너에는 Stack, Queue, Priority Queue(우선순위큐)가 있다.

- Stack -
#include <stack>를 추가해야 사용가능.
후입선출(FILO)의 구조이다.
먼저 입력된 데이터가 나중에 출력되는 자료구조.


- Queue -
#include <queue>를 추가해야 사용가능.
선입선출(FIFO)의 구조이다.
데이터가 입력된 순서대로 출력되는 자료구조.

- Priority Queue -
#include <queue>를 추가해야 사용가능.
큐의 일종으로 큐의 요소들이 우선순위를 가지고 있고, 우선순위가 높은 요소가 먼저 출력되는 자료구조.





4. 연관 컨테이너

데이터가 들어갈때 정렬되서 들어가는 컨테이너
연관 컨테이너에는 Map, Set, MultiMap, MultiSet이 있다.
Multi가 붙은건 중복을 허용하고 붙지않은건 중복을 허용하지 않는다.

- Map -
#include <map>를 추가해야 사용가능.
사전과 같은 구조.
Key와 Value를 가진다.
Key가 제시되면 해당되는 값을 찾을 수 있다.
중복을 허용하지 않음.
[] 연산자가 오버로딩 되어있어서 []로 키값을 넣을 수 있다.
[] 연산자는 양방향으로 순회하여 찾는식으로 지정되어 있다. (로직이 다르다.)

- MultiMap -
#include <map>를 추가해야 사용가능.
사전과 같은 구조.
Key와 Value를 가진다.
중복을 허용함.
[] 연산자가 지정되어 있지 않다.

- Set -
#include <set>를 추가해야 사용가능.
수학에서의 집합 구현.
원소를 하나를 가진다.
중복없는 자료들이 정렬되어서 저장된다.

- MultiSet -
#include <set>를 추가해야 사용가능.
Set과 유사하지만 중복이 허용된다.


5. 컨테이너의 공통적인 특징 및 동작

1. 컨테이너에 삽입이 이루어질 경우 내부적으로 복사본을 생성한다.
모든 STL 컨테이너의 원소들은 복사되어 질 수 있어야 한다.

2. 일반적으로 모든 원소들은 순서를 가지고 있다.
각각의 컨테이너는 자신의 원소를 순회할 수 있다록 자신만의 반복자를 제공함.

3. 대부분의 경우, STL자체는 예외를 발생 시키지 않는다. ( 내부적으로 예외처리를 해놓지 않았음 )
그렇기 때문에 안정성이 떨어진다. 따라서 동작에 대한 인자(parameter)를 제공하는 것을 보장해 주어야 한다.




참고 사이트 :
http://skmagic.tistory.com/210
http://tsuba79.tistory.com/119

'Programming > 자료구조 & STL' 카테고리의 다른 글

<자료구조> 큐, Queue의 개념  (0) 2012.06.10
<자료구조> 스택, Stack의 개념  (0) 2012.06.10
STL - 컨테이너  (3) 2012.01.31
댓글
댓글쓰기 폼