[C++] 표준 템플릿 라이브러리(STL)

---

STL

 

STL(Standard Template Library)은 C++에서 제공하는 표준 템플릿 라이브러리로, 다양한 자료구조와 알고리즘을 템플릿 형태로 제공한다.

STL은 효율적이고 재사용 가능한 코드를 작성할 수 있도록 돕는 강력한 라이브러리로, 크게 컨테이너, 반복자(iterator), 알고리즘의 세 가지 주요 구성 요소로 이루어져 있다.

 

---

STL container

 

• vector

#include <vector>

벡터는 가변 크기의 배열을 일반화한 클래스로 다양한 자료형을 담을 수 있다. 원소의 저장, 삭제, 검색 등 다양한 멤버 함수를 지원하며 인덱스를 통해 접근 가능하다. 아래와 같이 선언하여 사용한다.

vector<datatype> vector_name;

주요 멤버 함수는 다음과 같다.

push_back(element)	벡터 마지막에 element 추가
at(int index)	index 위치의 원소에 대한 참조 반환
begin()	벡터 첫 원소를 가리키는 iterator 반환
end()	벡터 끝, 즉 마지막 원소 다음을 가리키는 iterator 반환
empty()	벡터가 비어있으면 true 반환
erase(iterator it)	벡터에서 it 가 가리키는 원소 삭제 후 자동 벡터 조절
insert(iterator it, element)	벡터 내 it 위치에 element 삽입
size()	벡터에 들어 있는 원소의 개수 반환
operator[]()	지정된 원소에 대한 참조 반환
operator=()	벡터를 다른 벡터에 치환

 

• stack

#include <stack>

스택은 후입선출 방식으로 동작하는 컨테이너로 다양한 자료형을 담을 수 있다. 함수 호출 관리, 연산 순서 제어 등에서 유용하게 사용된다. 최상위 원소에 대한 삽입 삭제만 지원한다는 특징이 있다. 아래와 같이 선언하여 사용한다.

stack<datatype> stack_name;

주요 멤버 함수는 다음과 같다.

push(element)	스택 가장 위 element를 추가
pop()	스택 가장 위 원소를 제거
top()	스택 가장 위 원소에 대한 참조 반환
empty()	스택이 비어 있으면 true 반환
size()	스택에 들어 있는 원소 개수 반환

 

• queue

#include <queue>

큐는 선입선출 방식으로 동작하는 컨테이너로 다양한 자료형을 담을 수 있다. 전열에 대한 제거와 후열에 대한 추가만을 지원한다는 특징이 있다. 아래와 같이 선언하여 사용한다.

queue<datatype> queue_name;

주요 멤버 함수는 다음과 같다.

push(element)	큐 마지막에 element 추가
pop()	큐 처음 원소 삭제
front()	큐 처음 원소에 대한 참조 반환
back()	큐 마지막 원소에 대한 참조 반환
emtpy()	큐가 비어 있으면 true 반환
size()	큐에 들어 있는 원소 개수 반환

 

• deque

#include <deque>

덱은 양 끝에서 삽입 및 삭제가 가능하고 빠른 시퀀스 컨테이너이다. 벡터와 유사하게 인덱스를 통한 임의 접근이 가능하지만, 양 끝을 통한 삽입, 삭제가 빠른 것이 더 중요한 강점이다. 아래와 같이 선언하여 사용한다.

deque<datatype> deque_name;

주요 멤버 함수는 다음과 같다.

push_back(element)	덱 마지막에 element 추가
push_front(eletment)	덱 처음에 element 추가
pop_back()	덱 마지막 원소 삭제
pop_front()	덱 처음 원소 삭제
at(int index)	index 위치의 원소에 대한 참조 반환
begin()	덱 첫 원소를 가리키는 iterator 반환
end()	덱 끝, 즉 마지막 원소 다음을 가리키는 iterator 반환
empty()	덱이 비어 있으면 true 반환
erase(iterator it)	덱에서 it가 가리키는 원소 삭제 후 자동 리스트 조절
insert(iterator is, element)	덱 내 it 위치에 element 삽입
size()	덱에 들어 있는 원소 개수 반환
clear()	덱 모든 원소 삭제
operator[]()	지정된 원소에 대한 참조 반환

 

• list

#include <list>

리스트는 양방향 연결 리스트를 일반화한 클래스로 다양한 자료형을 담을 수 있다. 삽입, 삭제에서 효율적이지만, 인덱스를 통한 임의접근이 불가능하기 때문에 양방향 탐색만 사용 가능하여 배열이나 벡터보다 비효율적이다. 아래와 같이 선언하여 사용한다.

list<datatype> list_name;

주요 멤버 함수는 다음과 같다.

push_back(element)	리스트 마지막에 element 추가
push_front(eletment)	리스트 처음에 element 추가
pop_back()	리스트 마지막 원소 삭제
spop_front()	리스트 처음 원소 삭제
begin()	리스트 첫 원소를 가리키는 iterator 반환
end()	리스트 끝, 즉 마지막 원소 다음을 가리키는 iterator 반환
empty()	리스트가 비어 있으면 true 반환
erase(iterator it)	리스트에서 it가 가리키는 원소 삭제 후 자동 리스트 조절
insert(iterator is, element)	리스트 내 it 위치에 element 삽입
size()	리스트에 들어 있는 원소 개수 반환
clear()	리스트 모든 원소 삭제
remove(element)	리스트 내 element와 동일한 모든 원소 삭제
splice(iterator is, list &another_list)	리스트 it 위치에 another_list 모든 원소 이동
sort()	리스트 원소를 정렬
reverse()	리스트 원소 순서를 역순으로 변경
operator=()	리스트를 다른 리스트에 치환

 

• set

#include <set>

셋은 고유한 원소를 자동 정렬하여 저장하는 컨테이너로 다양한 자료형을 담을 수 있다. 원소의 중복을 허용하지 않으며 삽입, 삭제, 탐색 등의 연산이 평균적으로 $ \mathcal{O}(\lg n) $ 의 시간복잡도를 가진다. 아래와 같이 선언하여 사용한다.

set<datatype> set_name;

주요 멤버 함수는 다음과 같다.

begin()	셋 첫 원소를 가리키는 iterator 반환
end()	셋 끝, 즉 마지막 원소 다음을 가리키는 iterator 반환
empty()	셋이 비어있으면 true 반환
find(key_type& key)	셋에서 key에 해당하는 원소를 가리키는 iterator를 반환
erase(key_type& key)	셋에서 key와 동일한 원소를 삭제
insert(iterator it, element)	셋 내 it 위치에 element 삽입
size()	셋에 들어 있는 원소의 개수 반환
sclear()	셋 모든 원소 삭제
operator=()	셋을 다른 셋에 치환

 

• map

#include <map>

맵은 키와 값의 쌍을 원소로 저장하는 컨테이너로 키를 넣으면 값이 나온다. 아래와 같이 선언하여 사용된다. 키와 값의 자료형을 각각 설정해주어야 한다.

map<key_datatype, value_datatype> map_name;

map은 키에 대한 값의 중복을 허용하지 않고, 검색, 삽입, 삭제가 $ \mathcal{O}(\lg n) $ 인 레드블랙트리로 구현되어 있다.

주요 멤버 함수는 다음과 같다.

insert(pair<> &element)	맵에 key와 value로 구성된 pair 객체 element 삽입
at(key_type& key)	맵에서 key에 해당하는 값 리턴
begin()	맵 첫 원소에 대한 참조 리턴
end()	맵 끝, 즉 마지막 원소 다음을 기리키는 참조 리턴
emtpy()	맵이 비어 있으면 true 리턴
find(key_type& key)	맵에서 key에 해당하는 value를 가리키는 iterator 리턴
erase(iterator it)	맵에서 it가 가리키는 원소 삭제
size()	맵에 들어있는 원소의 개수 리턴
soperator[key_type& key]()	맵에서 key에 해당하는 value를 찾아 리턴
soprator=()	맵 복사

 

---

STL iterator

 

컨테이너의 원소를 가리키는 포인터로 반복자라고도 부른다. 구체적인 컨테이너를 지정하여 반복자 변수를 생성하여 사용해야 한다.

container_name<datatype>::iterator iterator_name;

반복자 변수를 증가시키면 그 다음 칸으로 이동한다, 즉 다음 칸의 주소를 갖는다. 초기화는 보통 해당 컨테이너 원소의 시작을 가리키도록 설정하는 것이 일반적이다. 즉 begin()과 end()와 같이 사용할 일이 많다.

단항 증감연산자 사용도 가능하고, 포인터이기 때문에 *을 통해 값을 읽고 쓸 수 있다.

 

---

STL algorithm

 

#include <algorithm>

템플릿 전역 함수로 주로 iterator와 함께 사용된다. 기본적인 함수로는 다음이 있다.

find(iterator first, iterator last, value)	지정된 구간 [first, last)에서 주어진 value와 일치하는 첫 번째 원소의 iterator 반환
count(iterator first, iterator last, value)	지정된 구간 [first, last)에서 주어진 value와 일치하는 원소의 개수를 반환
sort(iterator first, iterator last)	지정된 구간 [first, last)에 있는 원소들을 비내림차순으로 정렬
reverse(iterator first, iterator last)	지정된 구간 [first, last)에 있는 원소들의 순서를 뒤집음
copy(iterator first, iterator last, result)	지정된 구간 [first, last)의 원소들을 result에 복사

참고로 구간 [first, last)는 first 이상, last 미만을 말한다.