STL컨테이너 2가지(시퀀스 컨테이너/연관 컨테이너)

시퀀스 컨테이너

- 원소가 상대적인 위치(순서)를 유지하므로 가장 앞요소와 뒤 요소를 참조하는 front()/back() 함수 제공

- 컨테이너 끝에 추가/제거 하는 push_back(),pop_back() 멤버함수 제공

 

 

시퀀스 컨테이너 종류

1.vector - 배열기반 

- 원소가 하나의 메모리 블록에 연속하게 저장(연속 메모리기반)

- 원소 추가or삽입 이루어 질때, 메모리 재할당 발생 할 수 있으므로 메모리 할당크기를 알 수 있게 capacity() 멤버함수 제공

- 메모리 크기 예약 reverse() 멤버 함수

- insert()/erase()/push_back() 빈번하게 이루어진다면, 다른 컨테이너 고려

- pop_front()/push_front()는 제공하지 않음. vector에서 매우 비효율적

- at() / [] 연산자는 같은 기능을 수행 at()는 유효 범위 점검 안전ok but 느림/ []는 유효범위 점검 x 그래서 속도 좀 더 빠름

 

2. deque - 배열기반

- 여러 메모리 기반

- vector와 거의 동일하나 앞쪽에 원소를 추가/제거 할 수 있고, 크게 다른점이라면 메모리 할당 정책이다. 원소가 추가 될때 메모리가 부족하면 새로운 메모리 블록을 할당하여 원소를 추가한다.

- 즉 vector는 메모리가 부족하면 이전 메모리 블록을 삭제하고 새로운 메모리 블럭을 재할당하여 이전원소를 모두 복사하지만, deque는 새로운 단위의 메모리 블록을 할당하고 원소를 삽입한다.

- 삽입, 제거 등의 동작은 vector와 같지만 차이점은 vector보다 효율적이라는 것이다.

->at() / [] 연산자는 같은 기능을 수행 at()는 유효 범위 점검 안전ok but 느림/ []는 유효범위 점검 x 그래서 속도 좀 더 빠름

 

3. list - 노드기반- 이중연결리스트

- 원소가 각각의 노드에 저장 되는 이중 연결리스트이다.

- 위 2개와 다르게 at()과 [] 연산자가 없으며 임의 접근 반복자가 아닌 양방향 반복자를 제공. ++/-- 연산을 사용.

- 특징 중 하나 원소를 삽입/제거 하더라도 상수 시간 복잡도의 성능 수행

- 배열기반보다 효율적으로 동작 

 

 

연관 컨테이너 (전부 노드기반/모두 동일한 인터페이스의 멤버 함수사용)

- 특정 정렬 기준(조건자)에 따라 원소를 자동 정렬하는 컨테이너. 정렬 기준은 템플릿 매개변수에 지정가능. 기본은 less조건자

- 균형 이진트리 사용(찾기 연산에 뛰어난 성능. 삽입/찾기 둘다 로그 시간 복잡도)

 

 

1. set 

- 모든 원소가 유일하다 (중복삽입 x)

- 균형 이진트리로 되어 있고, 원소 찾기를 로그 시간복잡도로 수행.

 

2. multiset

- 중복 원소 저장 가능 외에 set과 동일

 

3. map

- 모든 key가 유일하다 (중복삽입 x)

- key와 value 쌍으로 저장.

- 기본 정렬 기준 less

- [] 연산자로 원소 추가가능 (insert() 멤버 함수도 제공)

- map의 원소는 pair 객체로 저장

 

4. multimap

- 중복 key 저장 가능 외에 map과 동일

- [] 연산자 제공하지 않음.

 

배열기반 ->임의 접근 반복자 제공

노드기반 - > 양방향 반복자 제공