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

STL 컨테이너 종류

 

1. 순서(시퀀스) 컨테이너

데이터를 선형으로 저장하는 컨테이너로 연관 컨테이너에 비해 검색 성능이 좋지 않다.

 

1) Vector

가장 기본적인 컨테이너이다.

• 일반 배열처럼 연속적인 메모리에 저장되고 확장/축소가 가능한 동적 배열로 구현되어 있다.
• iterator 뿐만 아니라 index로도 접근이 가능하여 개별 원소에 대한 접근 속도가 빠르다.

 

2) Deque

• vector와 비슷한 컨테이너이지만, 하나의 메모리 블록이 아닌 여러 메모리 블록에 나뉘어 저장된다.
• Random access iterator를 통한 index로 접근이 가능하다.

 

3) List

• 비연속적인 메모리에 저장된다.
• index로 접근이 불가능하다. 접근을 하기 위해서는 선형 탐색이 필요하다.
• 보통 삽입, 삭제하는 연산이 많을 때 사용한다.

 

4) Array

• vector와 비슷한 컨테이너이지만, 정적 배열이다.

 

2. 연관 컨테이너

요소의 위치가 자신의 값과 특정 정렬 기준에 따라 정해지는 컨테이너로 빠른 검색에 용이하다.

 

1) Set

set<key, (orderclass)>의 형태로 key 값을 기준으로 정렬된 상태 유지한다.

• key 값은 중복된 값을 허용하지 않는다.
• orderclass로 정렬 기준을 정할 수 있다. 디폴트는 오름차순이다.

class OrderClass {
public:
	bool operator()(pair<int, int> a, pair<int, int> b) {
		return a.second < b.second;
	}
};

int main()
{
	set<pair<int, int>, OrderClass> s;
}

 

2) Map

map<key, value>의 형태로 key 값을 기준으로 정렬한다.

• key 값은 중복된 값을 허용하지 않는다.
• m[key] = value;의 형태로 원소를 추가 또는 수정이 가능하다.

 

3) Multiset/Multimap

중복된 원소(key)를 허용한다.

 

3. 비정렬 컨테이너

요소의 위치가 중요하지 않고 특정 원소가 이 컨테이너 안에 있는지가 중요하다.

 

1) unordered_set

2) unordered_map

 

4. 컨테이너 어댑터

1) stack

2) queue

 

5. 반복자 (Iterator)

컨테이너 클래스의 모든 데이터를 접근하는 연산자로 * 연산자를 통해 반복자가 가리키는 값을 가져온다.

// 값 찾기
auto iter = find(v.begin(), v.end(), val);
if (iter == v.end())
	cout << "값이 존재하지 않음";

// 최솟값/최댓값 찾기
auto iter = min_element(v.begin(), v.end());
auto iter = max_element(v.begin(), v.end());

// 지우기
auto iter = remove_if(v.begin(), v.end(), [](int a) {
	return a % 3 == 0;
	});
v.erase(iter, v.end());

 

6. 구현

https://baactree.tistory.com/29

STL 정리

 

7. 기타

1) Vector, List, Map 차이점

• Vector: 인덱스로 랜덤 접근 가능하지만 검색 속도가 느리고 중간에 데이터 삽입이나 삭제가 어렵다.
• List: 삽입과 삭제가 쉽지만 반드시 순회해야 원하는 자료를 찾을 수 있다.
• Map: 많은 자료를 정렬할 수 있고 빠른 검색이 가능하지만 삽입과 삭제가 어렵다.

 

2) Map과 HashMap 차이

• Map은 키를 이용해 데이터에 접근하고 내부 자료들을 정렬한다. 이때 Map은 레드 블랙 트리를 이용하여 logN의 속도를 가지지만 HaspMap은 상수 시간 내에 수행할 수 있다. 데이터양이 많을 경우 HaspMap을 사용하는 게 좋다.
• Map은 정렬된 상태로 저장하지만 HashMap은 정렬하지 않는다. 왜냐하면 요소의 위치가 중요하지 않고 특정 원소가 이 자료구조 안에 있는지가 중요하기 때문이다.
• STL의 공식 컨테이너에는 HashMap을 따로 정의하지 않았는데, 대신 거의 동일한 기능을 제공하는 unordered_map을 이용해 사용할 수 있다.