(C++)STL

STL(Standard Template Library)는 자료구조와 알고리즘을 템플릿으로 제공하는 라이브러리이다.

 

STL의 구성요소

- 컨테이너 : 객체들을 저장하는 객체

- 반복자 : 컨테이너의 원소를 가리키고 STL내의 자료구조와 알고리즘을 연결시킴

- 알고리즘 : 정렬, 삭제, 연산 등을 해결하는 함수 템플릿

- 함수 객체 : 함수처럼 동작하는 객체. (less(), greater())

- 어댑터 : deque의 인터페이스를 변경해 stack으로 만든것처럼 기존의 구성요소의 인터페이스를 변경해 새로운 구성요소로 만드는것

- 할당기(Allocator) : 컨테이너의 메모리 할당 정책을 캡슐화한 클래스

 

컨테이너

- 시퀀스 컨테이너 : vector, deque, list처럼 원소가 삽입되는 순서에 따라 원소의 위치가 결정나는 컨테이너

- 연관 컨테이너 : set,multiset, map, multimap 처럼 원소가 삽입순서가 아닌 다른 정렬기준에 따라 원소의 위치가 결정나는 컨테이너

- 배열 컨테이너 : vetor, deque 처럼 데이터 여러개가 하나의 메모리 단위에 저장

- 노드기반 컨테이너 : list,set, multiset, map, multimap 처럼 데이터 하나를 하나의 메모리 단위에 저장

 

반복자

보통 해당 컨테이너의 원소를 가리키는 반복자를 반환하는 함수가 있고(begin(), end(), rbegin(), rend()) 해당 함수로 반환한 포인터를 반복자 객체가 받아서 원소를 순회하는 역활을 한다.

 

배열 컨테이너인 vector와 deque는 반복자 포인터의 ++,--연산 뿐아니라 [],-=.+=연산도 지원하여 임의로 원소 접근이 가능하다. 

아래는 vector 컨테이너를 반복자를 활용해 순회한 코드이다.

int main()
{
	vector<int> vec;
	vec.push_back(1);
	vec.push_back(2);
	vec.push_back(3);

	vector<int>::iterator it = vec.begin();

	for (;it!=vec.end();it++)
	{
		cout << *it << endl;
	}
}

알고리즘 

알고리즘에는 원소를 수정, 제거, 정렬 등을 하는 함수들이 들어있다.

 

아래는 find 알고리즘으로 vector 컨테이너의 원소 2를 찾고 오름차순으로 정렬하는 sort 알고리즘을 사용한 코드이다. 

int main()
{
	vector<int> vec;
	vec.push_back(1);
	vec.push_back(4);
	vec.push_back(2);
	vec.push_back(3);
	vector<int>::iterator it = find(vec.begin(), vec.end(), 2);

	cout << *it << endl;

	sort(vec.begin(), vec.end());

	for (it=vec.begin();it!=vec.end(); it++)
	{
		cout << *it << endl;
	}
	
}

 

이런식으로 algorithm 라이브러리안에 있는 알고리즘 함수들에 해당 컨테이너의 반복자를 연결시키면 컨테이너에 알고리즘이 적용된다.

 

함수객체

STL의 구성요소를 유연하게 사용할 수 있는것으로 여러 STL 알고리즘이 함수객체, 함수, 함수 포인터 등을 인자로 받아 알고리즘을 유연하게 동작 시킨다.

 

아래는 sort 알고리즘에 greater함수 객체를 인자로 넣어 컨테이너의 원소를 내림차순으로 정렬 시키는 코드이다.

int main()
{
	vector<int> vec;
	vec.push_back(1);
	vec.push_back(4);
	vec.push_back(2);
	vec.push_back(3);
	vector<int>::iterator it = find(vec.begin(), vec.end(), 2);

	cout << *it << endl;

	sort(vec.begin(), vec.end(),greater<int>());

	for (it=vec.begin();it!=vec.end(); it++)
	{
		cout << *it << endl;
	}
	
}

 

어댑터

구성요소의 인터페이스를 변경한 것으로써 3가지 종류가 있다.

- 컨테이너 어댑터 : stack, queue, priority_queue

- 반복자 어댑터 : reverse_iterator, back_insert_iterator, front_insert_iterator, insert_iterator

- 함수 어댑터 : 바인더, 부정자(negator), 함수포인터 어댑터

 

아래는 reverse_iterator의 코드이다.

int main()
{
	vector<int> vec;
	vec.push_back(1);
	vec.push_back(4);
	vec.push_back(2);
	vec.push_back(3);
	reverse_iterator<vector<int>::iterator> riter(vec.rbegin());

	for (;riter!=vec.rend(); riter++)
	{
		cout << *riter << endl;
	}
	
}

rbegin()은 해당 컨테이너의 마지막 원소를 가리키고 rend()는 컨테이너의 첫번째보다 먼저 있는 원소를 가리킨다.

역행과 순행일때 반복자가 가리키는 위치

reverse_iterator를 쓰면 반복자를 --하지않고 ++만으로 역순회가 가능해진다.