[STL] STL 소개

‘뇌를 자극하는 C++ STL - 공동환’ 책 및 c++ reference를 참고하여 작성한 포스트입니다.

STL이란

• Standard Template Library의 약자이다.
• 프로그램에 필요한 자료구조와 알고리즘을 템플릿으로 제공하는 라이브러리이다.
• 효율성, 일반화 프로그램(재사용성), 확장성에 중점을 두고 만들어졌다.

컨테이너

같은 타입을 저장, 관리할 목적으로 만들어진 클래스. 컨테이너는 두 가지로 나뉘며 총 일곱 가지이다.

• 표준 시퀀스 컨테이너
  • 컨테이너 원소가 자신만의 삽입 위치(순서)를 가지는 컨테이너
  • vector, deque, list
  • 선형적
• 표준 연관 컨테이너
  • 저장 원소가 삽입 순서와 다르게 특정 정렬 기준에 의해 자동 정렬되는 컨테이너
  • set, multiset, map, multimap
  • 비선형적

또한 다음과 같이 두 가지로 나눌 수도 있다.

• 배열 기반 컨테이너
  • 데이터 여러 개가 하나의 메모리 단위에 저장됨
  • vector, deque
• 노드 기반 컨테이너
  • 데이터 하나가 하나의 메모리 단위에 저장됨
  • list, set, multiset, map, multimap
• 시퀀스 컨테이너는 컨테이너 끝에 데이터 추가 제거하기 위한 push_back(), pop_back() 함수가 있다.
• 또한 operator[] 연산자를 이용해 일반 배열처럼 컨테이너 원소에 접근 가능하다.
• 모든 컨테이너는 원소의 개수를 반환하는 size() 멤버 함수를 가진다.

반복자

포인터와 비슷하게 동작하며, 컨테이너에 저장된 원소를 순회하고 접근하는 일반화된 방법을 제공한다. 컨테이너와 알고리즘이 하나로 동작하게 묶어주는 인터페이스 역할을 한다.

• 반복자는 컨테이너 내부의 원소(객체)를 가리키고 접근할 수 있어야 함(*연산자 제공)
• 반복자는 다음 원소로 이동하고 컨테이너의 모든 원소를 순회할 수 있어야 함(++연산자 제공, ≠, == 비교 연산자 제공)
• STL의 모든 컨테이너는 자신만의 반복자를 제공하며, 멤버함수 begin()과 end()가 순차열의 시작과 끝을 가리키는 반복자를 반환한다.
• 주의할 점은 순차열의 시작과 끝에서 끝은 실제 원소가 아닌 끝을 표시(past-the-end)하는 원소라는 점이다.
• 이 begin과 end를 구간(range)이라 하며, [begin,end)로 표기한다.
• 순차열은 순서 있는 원소의 집합이므로 구간 [begin, iter)와 구간 [iter, end) 등도 모두 순차열이다.

vector<int> v = {1, 2, 3, 4, 5};
vector<int>::iterator iter;
for(iter = v.begin(); iter != v.end(); ++iter) {
	cout << *iter << endl;
}

• forward iterator(순방향 반복자)
  • 순방향으로 이동 가능한 재할당될 수 있는 반복자
• bidirectional iterator(양방향 반복자)
  • 현 위치의 원소를 읽고 쓸 수 있으며 순방향 혹은 역방향으로 이동이 가능한 재할당될 수 있는 반복자
• random access iterator(임의 접근 반복자)
  • 양방향 반복자 기능에 +, -, +=, -=, [] 연산이 가능한 반복자

모든 컨테이너는 양방향 반복자 이상을 제공하며 배열 기반 컨테이너인 vector와 deque는 임의 접근 반복자를 제공함

• iter[i]
  • iter+i번째 원소에 접근(역참조)함
  • arr[i] 와 같다..
• iter + n : iter를 n만큼 이동함
• iter2 = iter - n: iter위치에 -n한 위치의 반복자를 iter2에 대입함

알고리즘

알고리즘은 한 쌍의 반복자([begin, end))를 필요로 하며 대부분은 순방향 반복자를 요구하지만, 몇몇 알고리즘은 임의 접근 반복자를 요구한다.
다음과 같이 일곱가지 범주로 분류할 수 있다.

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

iter = find(v.begin(), v.end(), 20);

은 20을 찾아 20원소를 가리키는 iter를 반환하며 찾지 못하면 iter는 끝을 표시하는 v.end()와 같다.
find는 순방향 반복자를 지원하는 컨테이너(순차열)여야 한다

순차열을 정렬하는 sort 알고리즘은 임의 접근 반복자를 요구한다.
따라서 vector와 deque는 sort 알고리즘을 수행할 수 있지만 다른 컨테이너는 불가능함.

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

함수 객체

• STL에서 함수 객체는 클라이언트가 정의한 동작을 다른 구성 요소에 반영하려 할 때 사용된다.
• 함수 객체를 사용하면 STL 구성 요소를 더욱 유연하게 사용할 수 있다.
• 많은 STL 알고리즘이 함수 객체, 함수, 함수 포인터 등의 함수류를 인자로 받아 알고리즘을 유연하게 동작시킨다.

sort(v.begin(), v.end(), less<int>())

less(< 연산)를 기준으로 정렬한다.
less가 디폴트이다.

어댑터

어댑터는 구성 요소의 인터페이스를 변경함

• 컨테이너 어댑터
  • stack, queue, priority_queue
• 반복자 어댑터
  • reverse_iterator, back_insert_iterator, front_insert_iterator, insert_iterator
• 함수 어댑터
  • 바인더(binder), 부정자(negator), 함수 포인터 어댑터(adaptor for pointers to functions)

대표적인 컨테이너 어댑터가 stack임. 일반 컨테이너를 LIFO(Last-In First_Out) 방식의 스택(Stack) 컨테이너로 변환함. 디폴트는 deque 컨테이너임.

대표적인 반복자 어댑터는 reverse_iterator이다. 일반 반복자의 동작 방식을 반대로 동작시키게 함.

대표적인 함수 어댑터는 부정자 not2임. 조건자 함수 객체(이항)를 NOT(반대)으로 변환함. 조건자는 bool 타입을 반환하는 함수류.

stack 컨테이너 어댑터의 컨테이너로 vector를 적용하려면

stack<int, vector<int>> st;
// vector 컨테이너를 이용한 stack 컨테이너 생성

반복자 어댑터의 예시를 보자

reverse_iterator<vector<int>::iterator> riter(v.end());
reverse_iterator<vector<int>::iterator> end_riter(v.begin());

for( ; riter != end_riter ; ++riter)
	cout << *riter << " ";

주의할 점은 역방향 반복자는 반복자가 가리키는 원소와 실제 가리키(참조)는 값이 다르다는 점이다. 반복자가 가리키는 원소 다음 원소의 값을 참조한다. 이유는 순차열의 구간이 반개 구간([begin, end))으로 알고리즘 수행 시 정방향 반복자와 호환되도록 하기 위해서임.

모든 컨테이너는 자신의 역방향 반복자를 typedef 타입으로 정의하며 rbegin()과 rend() 멤버 함수로 순차열의 시작과 끝 원소를 가리키는 반복자 쌍을 반환함. 즉, 굳이 역방향 반복자를 생성하지 않아도 됨.

대부분의 알고리즘이 ++ 연산자만으로 구현되어 있으므로 역방향 반복자를 사용하면 좋대.

not2는 조건자 함수 객체를 반대 의미의 조건자 함수 객체로 변경하는 어댑터이며 not1은 단항 조건자에, not2는 이항 조건자에 사용됨.

not2(less<int())(10, 20)
// less<int>()(10, 20): 함수 객체의 operator()(10, 20) 연산자 함수를 실행함

할당기

할당기는 컨테이너의 메모리 할당 정보와 정책(메모리 할당 모델)을 캡슐화한 STL 구성 요소이다. 할당기는 템플릿 클래스이며 모든 컨테이너는 기본 할당기를 사용함.

기본 할당기는 allocator임. 자세한건 필요하면..