STL (Standard Template Library)
프로그램에 필요한 자료구조와 알고리즘을 템플릿으로 제공하는 C++ 표준 라이브러리.
STL의 구성 요소로 컨테이너, 반복자, 알고리즘, 함수 객체, 어댑터, 할당기가 있음.
구성 요소
컨테이너 (Container)
객체를 저장하는 객체로서 자료구조라고도 함.
반복자 (Iterator)
컨테이너의 원소를 가리키며, 포인터와 비슷한 개념.
알고리즘 (Algorithm)
삭제, 검색, 연산 등을 해결하는 일반화된 방법을 제공하는 함수 템플릿.
함수 객체 (Function Object)
함수처럼 동작하는 객체로서 () 연산자를 오버로딩한 객체.
어댑터 (Adaptor)
구성 요소의 인터페이스를 변경.
할당기 (Allocator)
컨테이너의 메모리 할당 정책을 캡슐화한 클래스 객체.
컨테이너는 자신만의 기본 할당기를 가지고 있으며, 대부분의 프로그램에서는 기본 할당기만으로 충분.
컨테이너 (Container)
객체를 저장하는 자료구조
- 컨테이너에 저장된 데이터를 원소라고 부름.
- 컨테이너는 원소 저장 방식과 메모리 사용 방식에 따라 종류가 나뉨.
원소 저장 방식에 따른 분류
표준 시퀀스 컨테이너 (Standard Sequence Container)
컨테이너에 원소가 삽입되는 순서대로 저장됨. (선형적)
Ex) vector, list, deque
표준 연관 컨테이너 (Standard Associative Container)
컨테이너에 원소가 삽입되는 순서에 상관없이, 특정 정렬 기준에 따라 저장됨. (비선형적)
Ex) set, multiset, map, multimap
메모리 사용 방식에 따른 분류
배열 기반 컨테이너 (Array-Based Container)
데이터 여러 개가 하나의 연속된 메모리에 저장됨.
Ex) vector, deque
노드 기반 컨테이너 (Node-Based Container)
데이터 하나를 하나의 메모리 단위에 저장.
Ex) list, set, multiset, map, multimap
반복자 (Iterator)
컨테이너의 원소를 가리키는 포인터처럼 동작하며, 컨테이너 원소를 순회하고 접근하는 일반화된 방법을 제공.
- 컨테이너 종류에 상관없이, 모든 컨테이너에서 사용하는 방법이 동일함. (일반화)
- 반복자가 일반화 되어 있기 때문에, 컨테이너와 알고리즘이 하나로 동작하게 묶어주는 인터페이스 역할을 함.
반복자의 특징
- 컨테이너 내부의 원소(객체)를 가리키고 접근 가능해야 함. (*연산자 제공)
- 다음 원소로 이동하고 컨테이너의 모든 원소를 순회할 수 있어야 함. (++, !=, == 연산자 제공)
반복자 종류
- 반복자는 아래 처럼 다섯 범주로 나뉨.
- 모든 컨테이너는 양방향 반복자 이상을 제공.
- 배열 기반 컨테이너는 임의 접근 반복자를 제공.
입력 반복자 (Input Iterator)
현 위치의 원소를 한번만 읽을 수 있는 반복자
출력 반복자 (Output Iterator)
현 위치의 원소를 한번만 쓸 수 있는 반복자
순방향 반복자 (Forward Iterator)
입력, 출력 반복자 기능에 순방향(++)으로 이동이 가능한 반복자.
양방향 반복자 (Bidirectional Iterator)
순방향 반복자 기능에 역방향(--)으로 이동이 가능한 반복자
임의 접근 반복자 (Random Access Iterator)
양방향 반복자 기능에 +, -, +=, -=, [] 연산이 가능한 반복자.
순차열 (Sequence)
컨테이너 원소의 순서있는 집합.
- 순차열은 하나의 시작과 하나의 끝을 가짐.
- 반복자는 순차열의 한 원소를 가리킴.
- 모든 컨테이너는 자신만의 반복자를 가지고 있으며, 멤버 함수 begin(), end()를 사용하여 순차열의 시작과 끝을 가리키는 반복자를 반환.
- !순차열의 끝은 실제 마지막 원소가 아닌, 마지막 원소의 다음을 가리킴.
반복자 예제
컨테이너의 반복자를 사용하여 원소들을 출력하는 예제.
코드
#include <iostream>
#include <vector> // vector 컨테이너 사용.
using namespace std;
int main()
{
vector<int> v; // vector<int> 컨테이너 v 생성.
v.push_back(10); // v의 맨 뒤에 "10" 데이터 추가.
v.push_back(20); // v의 맨 뒤에 "20" 데이터 추가.
v.push_back(30); // v의 맨 뒤에 "30" 데이터 추가.
v.push_back(40); // v의 맨 뒤에 "40" 데이터 추가.
v.push_back(50); // v의 맨 뒤에 "50" 데이터 추가.
vector<int>::iterator iter; // vector<int> 컨테이너 반복자 생성.
for (iter = v.begin(); iter != v.end(); iter++)
{
cout << *iter << endl; // 반복자가 현재 가리키는 원소 반환.
}
return 0;
}결과
알고리즘 (Algorithm)
순차열의 원소를 조사, 변경, 관리, 처리할 목적으로 사용.
특정 컨테이너나 원소 타입에 상관없이 사용 가능.
- 알고리즘은 한 쌍의 반복자(begin, end)를 필요로함.
- 대부분의 알고리즘은 순방향 반복자를 요구하지만, 몇몇 알고리즘은 임의 접근 반복자를 요구.
find 알고리즘
순차열에서 특정 조건에 맞는 원소를 찾음.
찾은 경우 해당 원소의 위치를 반환, 못 찾은 경우 순차열의 마지막(end()) 위치를 반환.
순방향 반복자를 요구하기 때문에, 순방향 반복자를 지원하는 컨테이너라면 find 알고리즘 사용 가능.
코드
#include <iostream>
#include <vector> // vector 컨테이너 사용.
#include <algorithm> // 알고리즘 사용.
using namespace std;
int main()
{
vector<int> v; // vector 컨테이너 v 생성.
v.push_back(10); // v의 맨 뒤에 "10" 데이터 추가.
v.push_back(20); // v의 맨 뒤에 "20" 데이터 추가.
v.push_back(30); // v의 맨 뒤에 "30" 데이터 추가.
v.push_back(40); // v의 맨 뒤에 "40" 데이터 추가.
v.push_back(50); // v의 맨 뒤에 "50" 데이터 추가.
vector<int>::iterator iter; // 반복자 생성.
iter = find(v.begin(), v.end(), 20); // 순차열에서 20 찾기.
cout << *iter << endl; // 현재 반복자가 가리키는 원소(20) 출력.
iter = find(v.begin(), v.end(), 314); // 순차열에서 314 찾기.
if (iter == v.end()) // 못찾으면 순차열의 마지막을 반환.
cout << "못찾음" << endl;
return 0;
}결과
함수 객체 (Function Object)
클라이언트가 정의한 동작을 다른 구성 요소에 반영하려 할 때 사용.
많은 STL 알고리즘들이 함수 객체, 함수, 함수 포인터 등의 함수류를 인자로 받아 알고리즘을 유연하게 동작시킴.
less와 greater 함수 객체
- less : (<) 기준으로 원소 정렬. (오름차순)
- greater : (>) 기준으로 원소 정렬. (내림차순)
함수 객체 적용
sort 알고리즘(정렬)에 less, greater 함수 객체 적용.
sort 알고리즘에 함수 객체 미사용시, less를 기본적으로 사용.
코드
#include <iostream>
#include <vector> // vector 컨테이너 사용.
#include <algorithm> // 알고리즘 사용.
using namespace std;
int main()
{
vector<int> v; // vector 컨테이너 v 생성.
v.push_back(50); // v의 맨 뒤에 "50" 데이터 추가.
v.push_back(10); // v의 맨 뒤에 "10" 데이터 추가.
v.push_back(30); // v의 맨 뒤에 "30" 데이터 추가.
v.push_back(20); // v의 맨 뒤에 "20" 데이터 추가.
v.push_back(40); // v의 맨 뒤에 "40" 데이터 추가.
vector<int>::iterator iter; // 반복자 생성.
sort(v.begin(), v.end(), less<int>()); // v의 원소 오름차순 정렬.
for (iter = v.begin(); iter != v.end(); iter++) // v의 원소들 출력.
{
cout << *iter << endl;
}
cout << endl;
sort(v.begin(), v.end(), greater<int>()); // v의 원소 내림차순 정렬.
for (iter = v.begin(); iter != v.end(); iter++) // v의 원소들 출력.
{
cout << *iter << endl;
}
return 0;
}결과
어댑터 (Adaptor)
구성요소의 인터페이스를 변경.
컨테이너 어댑터 (Container Adaptor)
일반 컨테이너를 다른 방식의 컨테이너로 변경.
Ex) stack, queue, priority-queue
예제1
기본 stack 컨테이너 사용하기.
- 스택은 기본 컨테이너로 deque를 사용하여 stack 컨테이너로 변환함.
- 모든 시퀀스 컨테이너는 stack에 필요한 인터페이스(멤버 함수)를 가지므로, stack으로 변환 가능.
코드
#include <iostream>
#include <stack> // stack 컨테이너 사용.
using namespace std;
int main()
{
stack<int> st; // stack 컨테이너 st 생성.
st.push(10); // stack에 데이터 "10" 추가.
st.push(20); // stack에 데이터 "20" 추가.
st.push(30); // stack에 데이터 "30" 추가.
cout << st.top() << endl; // stack의 가장 위에 있는 값 출력.
st.pop(); // stack의 가장 위에 있는 값 삭제.
cout << st.top() << endl; // stack의 가장 위에 있는 값 출력.
st.pop(); // stack의 가장 위에 있는 값 삭제.
cout << st.top() << endl; // stack의 가장 위에 있는 값 출력.
st.pop(); // stack의 가장 위에 있는 값 삭제.
if (st.empty()) // stack이 비어있는지 확인.
cout << "데이터 없음" << endl;
return 0;
}결과
예제2
vector 컨테이너를 stack 컨테이너로 변경하기.
코드
#include <iostream>
#include <vector> // vector 컨테이너 사용.
#include <stack> // stack 컨테이너 사용.
using namespace std;
int main()
{
stack<int, vector<int>> st; // vector컨테이너를 stack 컨테이너로 변경한 st 생성.
st.push(10); // stack에 데이터 "10" 추가.
st.push(20); // stack에 데이터 "20" 추가.
st.push(30); // stack에 데이터 "30" 추가.
cout << st.top() << endl; // stack의 가장 위에 있는 값 출력.
st.pop(); // stack의 가장 위에 있는 값 삭제.
cout << st.top() << endl; // stack의 가장 위에 있는 값 출력.
st.pop(); // stack의 가장 위에 있는 값 삭제.
cout << st.top() << endl; // stack의 가장 위에 있는 값 출력.
st.pop(); // stack의 가장 위에 있는 값 삭제.
if (st.empty()) // stack이 비어있는지 확인.
cout << "데이터 없음" << endl;
return 0;
}결과
- 기본적으로 사용하던 deque 컨테이너가 vector로 바뀌었을 뿐, 나머지는 다르지 않음.
반복자 어댑터 (Iterator Adaptor)
일반 반복자의 동작 방식을 변경.
Ex) reverse_iterator, back_insert_iterator, front_insert_iterator, insert_iterator
예제1
reverse_iterator를 사용하여, vector의 일반 반복자를 역방향 반복자로 변경하기.
- 모든 컨테이너는 rbegin(), rend() 멤버 함수로, 순차열의 시작과 끝을 가리키는 역방향 반복자 사용 가능.
코드
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);
v.push_back(50);
// 일반 반복자. (순방향 반복자)
for (vector<int>::iterator iter = v.begin(); iter != v.end(); iter++)
{
cout << *iter << endl;
}
cout << endl;
// 역방향 반복자.
vector<int>::reverse_iterator riter(v.rbegin()); // rbegin() 멤버 함수로 riter 초기화.
for (; riter != v.rend(); riter++) // rend() 멤버 함수로 역방향 반복자가 마지막 원소 판별.
{
cout << *riter << endl;
}
return 0;
}결과
역방향 반복자 추가 내용
역방향 반복자가 가리키는 실제 원소는, 현재 가리키고 있는 원소의 다음(++) 원소.
정방향 반복자를 역방향 반복자로 변경하여 사용할 때 호환성을 위해 이렇게 설계됨.
함수 어댑터 (Function Adaptor)
함수 객체의 동작 방식을 변경
Ex) 바인더, 부정자, 함수 포인터 어댑터
예제1
함수 어댑터 not2를 사용해서 이상 조건자 less 함수 동작 변경하기
- not2 = 조건자 함수 객체를 반대 의미로 변경.
- not1은 단항 조건자, not2는 이항 조건자에 사용.
코드
#include <iostream>
#include <functional>
using namespace std;
int main()
{
// 임시 less 함수 객체 사용.
cout << less<int>()(10, 20) << endl;
cout << less<int>()(20, 20) << endl;
cout << less<int>()(20, 10) << endl;
cout << "==============" << endl;
// 임시 less 함수 객체에 not2 적용.
cout << not2(less<int>())(10, 20) << endl;
cout << not2(less<int>())(20, 20) << endl;
cout << not2(less<int>())(20, 10) << endl;
cout << endl;
// less 함수 객체 l 사용.
less<int> l;
cout << l(10, 20) << endl;
cout << l(20, 20) << endl;
cout << l(20, 10) << endl;
cout << "==============" << endl;
// less 함수 객체 l에 not2 적용.
cout << not2(l)(10, 20) << endl;
cout << not2(l)(20, 20) << endl;
cout << not2(l)(20, 10) << endl;
return 0;
}결과
