#C++ #알고리즘

STL 컨테이너

STL은 Standard Template Library의 약자로 C++ 에서 자료구조와 알고리즘의 Generic Programming (일반화 프로그래밍) 개념을 구현하기 위해 개발 된 C++ 라이브러리입니다. 이러한 STL 라이브러리의 종류와 컨데이너의 특성 및 사용법등을 정리해두려 합니다.

구성요소

반복자 : STL 컨테이너의 원소들을 가리키는 포인터
컨테이너: 데이터를 저장 및 관리를하는 클래스
알고리즘 : STL에서 제공하는 함수

STL 컨테이너 종류

시퀀스 컨테이너
1. 데이터를 선형적으로 저장합니다.
2. vector, list, dequeue …
연관 컨테이너
1. 일정 규칙에 따라 조직화된 컨테이너입니다.
2. set, multiset, map …
어뎁터 컨테이너
1. 시퀀스나 연관 컨테이너를 변형하여 정해진 방식으로 관리합니다.
2. stack, queue …

시퀀스 컨테이너

시퀀스 컨테이너는 데이터를 선형적으로 저장하고 삽입된 요소의 순서가 그대로 유지됩니다.

벡터 (vector)

일반적인 배열은 배열의 길이가 정적인 특징의 단점을 극복하기 위한 컨테이너로 요소가 추가되거나 삭제될때 자동으로 메모리를 재할당 하고 크기를 동적으로 바꿉니다.

문법

1 2	#include <vector> vector<Type> name(초기크기);

vector의 초기 크기를 지정하지 않으면 빈 백터를 생성합니다.

함수

size() : 컨테이너에 저장된 요소의 개수를 반환
push_front() : 맨 처음에 원소를 추가
push_back() : 맨 끝에 원소를 추가
pop_front() : 첫번째 원소를 제거
pop_back() : 마지막 원소를 제거
begin() : 컨테이너의 첫 요소를 가리키는 반복자를 반환
end() : 컨테이너의 마지막 요소 바로 다음을 가리키는 반복자를 반환
empty() : 컨테이너가 비었는지 확인

데크(deque)

dequeue는 양방향 큐를 의미하며, 양쪽에 끝이 있는 큐입니다. 이 컨테이너를 이용하면 양끝에서 삽입과 삭제를 빠르게 할 수 있습니다. vector와 마찬가지로 동적길이를 갖습니다.

문법

1 2	#include <deque> deque<Type> name(초기크기);

함수

size() : 컨테이너에 저장된 요소의 개수를 반환
front() : 첫번째 원소에 접근
back() : 마지막 원소에 접근
push_front() : 맨 처음에 원소를 추가
push_back() : 맨 끝에 원소를 추가
pop_front() : 첫번째 원소를 제거
pop_back() : 마지막 원소를 제거
begin() : 컨테이너의 첫 요소를 가리키는 반복자를 반환
end() : 컨테이너의 마지막 요소 바로 다음을 가리키는 반복자를 반환
empty() : 컨테이너가 비었는지 확인

리스트(list)

리스트 컨테이너는 이중연결 리스트를 구현한 클래스 입니다.

문법

1 2	#include<list> list<Type> name;

함수

size() : 컨테이너에 저장된 요소의 개수를 반환
front() : 첫번째 원소에 접근
back() : 마지막 원소에 접근
push_front() : 맨 처음에 원소를 추가
push_back() : 맨 끝에 원소를 추가
pop_front() : 첫번째 원소를 제거
pop_back() : 마지막 원소를 제거
begin() : 컨테이너의 첫 요소를 가리키는 반복자를 반환
end() : 컨테이너의 마지막 요소 바로 다음을 가리키는 반복자를 반환
empty() : 컨테이너가 비었는지 확인

연관 컨테이너

연관 컨테이너는 Key, Value 와 같이 관련있는 데이터를 하나의 쌍으로 저장하는 컨테이너 입니다. 연관 컨테이너는 보통 균형 이진 트리나 해시 테이블을 사용하여 구현됩니다. 아래의 컨테이너들은 균형 이진 트리중 하나인 레드블랙 트리를 이용합니다.

집합(set) / 멀티 집합(multiset)

집합 컨테이너는 저장하는 데이터 그 자체를 키로 사용하는 연관 컨테이너 입니다. 내부적으로 정렬되어 있어 빠른 검색속도를 가집니다.

set은 중복을 허용하지 않지만, multiset은 중복을 허용합니다.

문법

1 2	#include<set> set<Type> name;

함수

find() : 해당 요소를 가리키는 반복자를 반환
size() : 컨테이너에 저장된 요소의 개수를 반환
insert() : 요소를 컨테이너에 추가
erase() : 요소를 컨테이너에서 제거
begin() : 컨테이너의 첫 요소를 가리키는 반복자를 반환
end() : 컨테이너의 마지막 요소 바로 다음을 가리키는 반복자를 반환
empty() : 컨테이너가 비었는지 확인

맵(map) / 멀티맵(multimap)

맵 컨테이너는 Key와 Value의 쌍으로 데이터를 관리하는 연관 컨테이너 입니다. 맵 컨테이너도 빠른 검색 속도를 가집니다. map은 중복을 허용하지 않지만, multimap은 중복을 허용합니다.

문법

1 2	#include<map> map<KType, VType> name;

함수

find() : 해당 요소를 가리키는 반복자를 반환
size() : 컨테이너에 저장된 요소의 개수를 반환
insert() : 요소를 컨테이너에 추가
erase() : 요소를 컨테이너에서 제거
begin() : 컨테이너의 첫 요소를 가리키는 반복자를 반환
end() : 컨테이너의 마지막 요소 바로 다음을 가리키는 반복자를 반환
empty() : 컨테이너가 비었는지 확인

어댑터 컨테이너

어댑터 컨테이너는 기존 컨테이너의 인터페이스를 제한하거나 변형하여 만든 컨테이너 입니다. 하지만 반복자를 지원하지 않아 STL 알고리즘을 이용할 수 없습니다.

스택(stack)

vector클래스의 인터페이스를 제한해 구현한 스택 구조를 가지는 클래스 입니다.

문법

1 2	#include <stack> stack<Type> name;

함수

size() : 컨테이너에 저장된 요소의 개수를 반환
top() : 스택의 최 상단의 요소의 참조를 반환
push() : 스택 최상단에 요소 추가
pop() : 스택 최상단에서 요소를 제거
empty() : 컨테이너가 비었는지 확인

큐(queue)

큐는 deque클래스를 이용하여 큐를 구현한 클래스 입니다.

문법

1 2	#include <queue> queue<Type> name;

함수

size() : 컨테이너에 저장된 요소의 개수를 반환
front() : 첫번째 원소에 접근
back() : 마지막 원소에 접근
push() : 큐에 맨 마지막에 요소를 추가
pop() : 큐의 맨 앞의 요소를 제거
empty() : 컨테이너가 비었는지 확인

우선순위 큐(priority_queue)

우선순위 큐는 vector클래스를 이용하여 힙을 구현해 우선순위큐를 구현한 클래스 입니다.

문법

1 2	#include <queue> priority_queue<Type> name;

함수

size() : 컨테이너에 저장된 요소의 개수를 반환
push() : 우선순위 큐에 요소를 추가
top() : 우선순위 큐에서 맨위의 요소에 접근
pop() : 우선순위 큐에서 맨위의 요소 제거
empty() : 컨테이너가 비었는지 확인