5장 STL 소개

5-1. STL이란

표준 C++ 라이브러리 일부분으로, 필요한 자료구조와 알고리즘을 템플릿으로 제공한다.

각 자료구조와 알고리즘은 반복자로 연결이 되어있다.

구성요소	설명
컨테이너	객체를 저장하는 객체로 컬렉션 or 자료구조라 부른다.
반복자	포인터와 비슷한 개념으로 컨테이너의 원소를 가리키고, 다음 원소 또한 가리키게함.
알고리즘	정렬, 삭제, 검색, 연산 등을 해결하는 일반화된 방법을 제공하는 함수 템플릿
함수객체	함수처럼 동작하는 객체로 opeartor() 연산자를 오버로딩한 객체다.
어댑터	구성 요소의 인터페이스를 변경해 새로운 인터페이스를 갖는 구성요소로 변경함.
할당기	컨테이너의 메모리 할당 정책을 캡슐화한 클래스 겍체, 모든 컨테이너는 자신만의 기본 할당기를 갖는다.

STL 주요 구성 요소

STL은 효율성, 재사용성, 확장성의 특징을 중점을 두고 개발된 라이브러리다.

 

5-2. STL을 한눈에

• 컨테이너

같은 타입을 저장, 관리할 목적으로 만들어진 클래스다.

이름	설명	예시
표준 시퀀스 컨테이너	컨테이너 원소가 자신만의 삽입 위치(순서)를 가진다.	선형적: 백터, 디큐, 리스트
표준 연관 컨테이너	저장 원소가 삽입 순서와 다르게 자동으로 정렬된다.	비선형적: 셋, 멀티셋, 맵, 멀티 맵

※ String 컨테이너

시퀀스 컨테이너의 일종이지만, 문자만을 저장하는 컨테이너로 표준 컨테이너 요구사항은 만족하지 못했다.

이를 근사 컨테이너(내장 배열, valarray)라고 부른다.

또한, 컨테이너는 데이터를 하나의 연속한 메모리 단위로 저장하는가에따라 나뉜다.

이름	설명	예시
배열 기반의 컨테이너	데이터 여러 개가 하나의 메모리 단위에 저장된다.	백터, 디큐
노드 기반 컨테이너	데이터 하나를 하나의 메모리 단위에 저장한다.	리스트, 셋, 멀티셋, 맵, 멀티맵

※ 배열 기반의 컨테이너는 [] 연산자로 접근이 가능하다. 

• 반복자

컨테이너에 저장된 원소를 순회, 접근하는 일반화된 방법을 제공한다.

반복자는 컨테이너와 알고리즘이 하나로 동작(알고리즘과 컨테이너는 독립적)하게 묶어주는 인터페이스 역할이다.

• 반복자는 컨테이너 내부의 원소를 가리키고 접근(* 연산자)할 수 있어야 한다.
• 반복자는 다음과 모든 원소에 이동(++, !=, ==)을 할 수 있어야 한다. 

// 반복자 선언
vector<int>::iteartor iter;

// ++ 증가 연산자로 순회
// != 비교 연산자로 끝 지점 판단
for(iter = v.begin(); iter != v.end(); ++iter)
{
    cout << *iter << endl; // * 연산자로 반복자가 가리키는 원소를 반환
}

• 순차열: 컨테이너 원소의 집합으로 순차열의 끝은 실제 원소가 아닌 끝지점을 가리킨다.

반복자와 순차열

• [begin, end) 순차열: A, B, C, D, E
• [begin, iter) 순차열: A, B
• [iter, end) 순차열: C, D, E

※ [p, q]에서 p==q이면 순차열은 없다.

반복자는 5가지 범주로 나뉜다.

이름	설명	예시
입력 반복자	현 위치의 원소를 1번만 읽기 가능	istream
출력 반복자	한 위치의 원소를 1번만 쓰기 가능	ostream
순방향 반복자	입출력 반복자 + 순방향 이동(++)
양방향 반복자	순방향 반복자 + 역방향 이동(--)	list, set, multiset, map, multimap
임의 접근 반복자	양방향 반복자 기능 + (+, -, +=, -=, []) 연산자 추가	vector, deque

vector<int> v;

// v = {1, 2, 3, 4, 5}
for(int i=0; i<5; ++i)
    v.push_back(i+1);

vector<int>::iterator iter = v.begin();

// [] 연산자
cout << iter[0] << endl; // 1 출력

// += 연산자
iter += 2;
cout << *iter << endl; // 3 출력

// + 연산자
vector<int>::iterator iter2 = iter + 2;
cout << *iter2 << endl; // 5출력

※ 디큐도 똑같이 된다.

• 알고리즘

순차열의 원소를 조사, 변경, 관리, 처리한다.

알고리즘은 1쌍의 반복자([begin, end))가 필요하며, 대부분 순방향 반복자이지만 임의 접근이 요구될 때 가 있다.

• 원소를 수정하지 않는 알고리즘
• 원소를 수정하는 알고리즘
• 제거 알고리즘
• 변경 알고리즘
• 정렬 알고리즘
• 정렬된 범위 알고리즘
• 수치 알고리즘

vector<int>::iterator iter

iter = find(v.begin(), v.end(), 20); // v의 [begin,end)에서 20을 찾는다. 값이 있으면 *iter, 없으면 v.end()

if(iter == v.end()) // 해당 값이 없다!
{
    ...
}

else // 값이 있다!
{
    ...
}

순차열을 정렬하는 sort 알고리즘은 임의 접근 반복자를 요구하므로 vector와 deque에서만 가능하다.

그리고 나머지는 자체적으로 정렬 기준으로 자동 정렬을 한다.

sort(v.begin(), v.end(), less<int>()); // 오름차순 정렬

• 어댑터

구성 요소의 인터페이스를 변경한다.

이름	예시
컨테이너 어댑터	stack(대표), queue, priority_queue
반복자 어댑터	reverse_iterator(대표), back_insert_iterator, front_insert_iterator, insert_iterator
함수 어댑터	바인더, 부정자(not2 대표), 함수 포인터 어댑터

• 컨테이너 어댑터

시퀀스 컨테이너는 모두 인터페이스(멤버 함수)를 가지므로 stack 컨테이너 어댑터의 컨테이너로 이용할 수 있다.

// 멤버함수 종류
empty()		// 비었는가?
size()		// 크기
push_back()	// 원소 추가
pop_back()	// 원소 삭제
back()		// 맨 뒷값, 스택에서는 top()

스택 컨테이너의 디폴트 컨테이너는 deque 컨테이너이다.

• 반복자 어댑터

for(vector<int>::iteartor iter = v.begin(); iter != v.end(); ++iter) // -> 정방향
{
    ...
}

// 역방향 반복자
reverse_iterator<vector<int>::iterator> riter = v.end(); // 시작점
reverse_iterator<vector<int>::iterator> end_riter = v.begin(); // 끝점

for(; riter != end_riter; ++riter) // <- 역방향
{
    ...
}

// 더 간단한 rbegin()과 rend()
vector<int>::reverse_iterator riter(v.rbegin()); // rbegin: 시작점(백터의 맨끝)
for; riter != v.rend(); ++riter) // rend: 끝점(백터의 맨앞)
{
    ...
}

 

※ 역방향의 장점: 정방향 역방향 둘다 ++연산자를 이용한다. 대부분의 알고리즘은 ++에 구현되어있기 때문

• 함수 어댑터 not2

조건자 함수 객체를 반대 의미의 조건자 함수 객체로 변경한다.

• not1: 단한 조건자
• not2: 이항 조건자

cout << less<int>()(10, 20) << endl; // 1 출력 // less<int>()(10, 20) 임시객체 생성
cout << not2(less<int>())(10, 20) << endl; // 0 출력 // 기존 '<' 연산자가 '>=' 연산자로 바뀜

• 할당기

컨테이너의 메모리 할당 정보와 정책을 캡슐화한 STL의 구성요소다.

사용자가 직접 메모리 할당 방식을 제어할 수 있다.

대게 다중 스레드에 최적화 되고 안전한 사용자 메모리 할당 모델 필요, 컨테이너에 맞는 할당 모델 설계, 특정 구현 환경에서 최적화된 메모리 할당때 사용한다.

// vector<typename T, typename Alloc = allcator<T>> // 방식으로 구현된다.
vector<int, allocator<int>> v;
set<int, less<set, allocator<int>> s;