STL 컴포넌트 개요

STL에는 여섯 가지의 주요 컴포넌트 즉, 컨테이너(container), 제네릭 알고리즘(generic algorithm), 반복자(iterator), 함수 객체(function object), 어댑터(adaptor), 할당기(allocator)가 포함되어 있다.

 

 

1. 컨테이너(container)

객체들의 컬렉션(collection)을 저장하고 있는 객체를 STL에서는 컨테이너(container)라고 부른다.

STL에는 두 가지 종류의 컨테이너가 있는데, 하나는 시퀀스 컨테이너(sequence container)이고,

다른 하나는 정렬 연관 컨테이너(sorted associative container)이다.

 

1-1 시퀀스 컨테이너(sequence container)

시퀀스 컨테이너는 타입이 동일한 객체들을 선형으로 구성한 컬렉션이다.

STL의 시퀀스 컨테이너에는 다음 세 가지 종류가 있다.

- vector<T>  가변 길이 시퀀스를 임의 접근(random access) 할 수 있으며, 시퀀스 맨 끝에서 수행되는 삽입과삭제는 아모타이즈드 상수시간에 수행이 가능하다.(여기서, 임의 접근(random access)이 가능하다는 것은 시퀀스의 i 번째 원소를 접근하는데 걸리는 시간이 상수 시간이라는 것을 의미한다. 이는 다시 말해, i 값에 상관없이 소요 시간은 항상 일정하다는 뜻이다). - deque<T> 이것 또한 가변 길이 시퀀스를 임의 접근할 수 있으며, 시퀀스 맨 앞과 맨 끝에서 수행되는 삽입과 삭제는 모두 아모타이즈드 상수 시간에 수행이 가능하다. - list<T> 가변 길이 시퀀스에 대해서 선형 시간 접근만이 가능하며(즉, 소요 시간은 O(N), 여기서 N은 시퀀스의 현재 길이),  삽입과 삭제는 시퀀스 내에서라면 어디서든지 상수 시간 내에 수행이 가능하다.

 

한 가지 명심해야 할 것이 있는데, 그것은 우리가 일반적으로 사용하는 C++ 배열 타입에 해당하는 T a[N]도 시퀀스 컨테이너와 동일하게 취급할 수 있다는 점이다. 이는 STL 제네릭 알고리즘이 배열에 대해서도 여타 다른 시퀀스 타입의 경우와 동일하게 동작할 수 있도록 설계되었기 때문이다.

그리고 또 하나, 라이브러리에서 제공하는 타입 중에 문자들의 시퀀스를 표현하는 string타입 (<string> 헤더에 속해 있음)도 STL 알고리즘과 함께 사용이 가능하며, STL에 적용되는 대부분의 규칙들이 그대로 적용된다.

 

1-2 정렬 연관 컨테이너(sorted associative container)

정렬 연관 컨테이너는 주어진 키로 컬렉션에서 객체를 신속하게 찾을 수 있는 기능을 제공한다.

컬렉션의 사이즈는 실행시에 변할 수 있다.

STL은 네 가지 타입의 정렬 연관 컨테이너를 제공한다.

- set<Key> 유일키(unique key)를 지원하며(주어진 키 값에 해당하는 원소는 단 한개이다), 원하는 키를 신속하게 찾아낸다. - multiset<Key> 중복키(duplicate key)를 지원하며(동일한 키 값을 가지는 복사본을 여러 개 담을 수 있다), 원하는 키를 신속하게 찾아낸다. - map<Key, T> 유일키(타입은 Key)를 지원하며, 주어진 키로 원하는 객체(타입은 T)를 신속하게 찾아낸다. - multimap<Key, T> 중복키(타입은 Key)를 지원하며, 주어진 키로 원하는 객체(타입은 T)를 신속하게 찾아낸다.

 

STL에서 컨테이너를 다루는 방식은 기존의 C++ 컨테이너 클래스 라이브러리와는 많이 다르다.

즉, STL 컨테이너에서는 컨테이너에 담긴 데이터 객체들을 다룰 때 멤버 함수 대신에 제네릭 알고리즘을 주로 이용한다.

 

 

2. 제네릭 알고리즘

STL에서 가장 간단한 제네릭 알고리즘 두개를 꼽으라면 find 와 merge를 들 수 있다.

 

2-1 제네릭 find 알고리즘

STL 알고리즘의 유연성을 설명하기 위해서, 시퀀스에서 원하는 값을 찾고자 할 때 사용하는 find 알고리즘을 예로 들어보자.

find는 모든 컨테이너에 적용할 수 있다.

컨테이너 대신 배열에 적용할 경우에는 다음과 같이 프로그램을 작성할 수 있다. 

#include <iostream> #include <cassert> #include <algorithm> using namespace std; int main() {     cout<<"Demonstrating generic find algorithm with an array."<<endl;     char s[] = "C++ is a better C";     int len  = strlen(s);     const char* where = find(&s[0], &s[len], 'e');       assert(*where == 'e' && *(where+1) == 't');     cout<<"---OK."<<endl;     return 0; }

이 프로그램은 find를 사용하여 s[0] ,... , s[len-1]의 원소들 중에서 'e'와 일치하는 것이 있는지 검색한다.

 

다음과 같이 find 알고리즘을 호출하면

where = find(first, last, value);

이는 다음과 같은 내용을 의미한다. 

- 반복자 first는 find 알고리즘이 처리를 시작할 시퀀스 내의 위치를 나타낸다. - 반복자 last는 find 알고리즘이 처리를 종료할 위치를 나타낸다.

 

find 알고리즘은 배열, 벡터, 리스트, 덱 뿐만 아니라 모든 STL 컨테이너에서 원하는 값을 찾고자 할 때 사용할 수 있다.

 

find를 비롯한 모든 STL 제네릭 알고리즘에 대해 반드시 알아두어야 할 사실은 이들 알고리즘이 STL에서 제공하는 모든(또는 일부) 컨테이너에 적용될 수 있기 때문에 컨테이너마다 별도로 멤버 함수를 정의할 필요가 없으며, 이로 인해 코드 사이즈가 축소되고, 컨테이너의 인터페이스가 단순해진다는 것이다.

 

2-2 제네릭 merge 알고리즘

STL 제네릭 알고리즘의 유연성은 앞서 find의 예제 보다 훨씬 더 유연하다.

두 개의 정렬된 시퀀스에 속한 원소들을 한 개의 정렬 시퀀스로 합치는 merge 알고리즘의 경우를 살펴보자.

merge를 사용할 때는 보통 다음과 같이 호출한다.

merge(first1, last1, first2, last2, result);

이것의 의미는 다음과 같다.

- fisrt1과 last1은 T타입의 원소들로 구성된 두 개의 입력 시퀀스 중 첫 번째 시퀀스의 시작과 끝을 나타내는 반복자이다. - first2와 last2는 T타입의 원소들로 구성된 두 개의 입력 시퀀스 중 두 번째 시퀀스의 시작과 끝을 나타내는 반복자이다. - 두 개의 입력 시퀀스는 타입 T에 정의되어 있는 < 연산자에 의해 오름차순으로 정렬되어 있다. - result는 결과가 저장될 시퀀스의 맨 앞을 가리킨다.

 

이러한 조건하에서 merge를 호출하고 나면, 두 개의 입력 시퀀스에 속해 있던 원소들이 모두 포함된 오름차순으로 정렬되어 있는 결과 시퀀스를 얻게 된다. 이 인터페이스는 매우 유연하기 때문에 두 개의 입력 시퀀스와 결과 시퀀스가 서로 다른 종류의 컨테이너에 담겨 있어도 상관없다.

다음 예제를 통해 이를 확인해 보자.

#include <iostream> #include <cassert> #include <list> #include <deque> #include <algorithm> using namespace std; template <typename Container> Container make(const char s[]) {     return Container(&s[0], &s[strlen(s)]); } int main() {     cout<<"Demonstrating generic merge algorithm with an array, a list, and a deque."<<endl;          char s[] = "aeiou";     int len = strlen(s);     list<char> list1 = make<list<char>>("bcdfghjklmnpqrstvwxyz");     deque<char> deque1(26, 'x');          merge(&s[0], &s[len], list1.begin(), list1.end(), deque1.begin());     assert(deque1 == make<deque<char>>("abcdefghijklmnopqrstuvwxyz"));     cout<<"---Ok."<<endl;     return 0; }

이 예제는 배열 s와 list1을 머지한 결과를 덱에 담는 프로그램이다. s와 list1에 담긴 문자 시퀀스들은 미리 오름차순으로 정렬되어 있어야 하며, deque1에 담기게 되는 merge의 결과 시퀀스도 오름차순으로 정렬되어 있다는 점을 명심하기 바란다.

 

 

3. 반복자

STL 프레임 워크에 관해 충분히 이해하고 STL을 가장 잘 사용하는 방법을 배우려면, 반복자에 관한 이해가 필수적이다. STL 제네릭 알고리즘은 반복자 인자로 작성되어 있고, STL 컨테이너 알고리즘 "소켓"에 플러그인되는 반복자를 제공한다.

범용 컴포넌트들은 여러 가지 다양한 방식으로 "서로 플러그될" 수 있도록 설계되었기 때문에, 다른 라이브러리에 비해서 세부적으로 특화된 컴포넌트들을 훨씬 많이 만들어 낼 수 있다. 컴포넌트를 서로 연결하기 위해서 주로 사용하는 방식은 반복자를 이용하는 방법이다.  반복자에는 일반 C++ 포인터도 포함되지만, 포인터가 아닌 반복자도 있을 수 있다. 그러나 포인터가 아닌 다른 종류의 반복자들도 포인터와 비슷하게 동작해야한다. 다시 말해서, 반복자에 대해서도 ++와 *과 같은 연산자를 적용할 수 있어야 하고, 포인터에 작용했을 때와 유사하게 동작해야 한다.

 

STL 제네릭 함수인 accumulate를 살펴보자. 두 개의 반복자 first, last와 init를 인자로 하여 다음과 같이 호출하면,

accumulate(first, last, init);

init 값과 first와 last 사이에 존재하는 값들의 총합을 결과로 얻게 된다.(last에 위치한 값은 총합에서 제외된다.)

 

입력반복자와 출력 반복자 이외에도 STL은 추가로 세 가지 부류의 반복자 즉, 순방향 반복자(forward iterator), 양방향 반복자(bidirectianal iterator), 임의 접근 반복자(random access iterator)를 제공한다. 입력 반복자와 출력 반복자를 제외한 모든 반복자 부류들 간에는 계층 관계를 이루고 있다. 즉, 각각의 반복자 부류는 자신의 앞쪽에 위치한 반복자 부류가 지니고 있는 요구 사항에, 새로운 요구 조건들을 추가하여 가지고 있으며, 결과적으로 뒤쪽에 위치한 반복자 부류는 앞쪽에 위치한 반복자 부류에 포함되게 된다. 양방향 반복자는 순방향 반복자이며, 임의 접근 반복자는 양방향 반복자인 동시에 순방향 반복자가 되는 것이다.

 

accumulate, find, merge와 같이 입력 반복자를 사용하는 알고리즘은 임의 접근 반복자를 사용하는 sort와 같이 더 많은 기능을 지닌 반복자를 사용하는 알고리즘보다 훨씬 더 제네릭하다. 예를 들어, sort는 STL 리스트 컨테이너에 사용할 수 없는데, 그 이유는 리스트 반복자가 임의 접근 반복자가 아니라 양뱡향 반복자이기 때문이다. 그 대신에 STL은 양방향 반복자를 사용할 수 있는 리스트 멤버 함수를 제공하기 때문에 리스트를 정렬할 때는 sort 제네릭 알고리즘 대신에 리스트의 sort 멤버 함수를 사용하면 된다.

STL은 라이브러리의 효율성(efficiency)을 위해서 일부 제네릭 알고리즘에의 범용성(generality)을 어느 정도 제한하고 있으며, 반복자를 여러 범주로 분류한 것도 이러한 목적을 달성하기 위한 일환의 하나이다.

 

 

4. 함수 객체(function object)

accumulate 함수는 반복자를 사용하는 방식에서 보면 매우 범용적인 함수라고 할 수 있다. 하지만 accumulate 함수는 반복자가 참조하는 값의 타입(반복자의 값 타입(value type)이라고 부른다)이 충족시켜야 하는 조건들이 있는데, 이러한 측면에서 보자면 이 함수는 그다지 범용적이지 못하다고도 볼 수 있다. accumulate 함수의 정의를 살펴보면 아래 문장에서 + 연산자를 사용하였는데, 이는 accumulate 함수로 넘겨진 반복자의 값 타입에 + 연산자가 정의되어 있을 것이라고 가정한 것이다.

init = init + *first;

따라서, C++에서 지원하는 모든 수치 관련 타입 뿐만 아니라 + 연산자가 정의되어 있는 모든 사용자 정의 타입 T에 대해서도, accumulate를 사용하여 시퀀스 내에 저장된 값들의 합을 구할 수 있다. 하지만, accumulate라는 단어의 추상적 의미가 덧셈 연산에만 적용되는 것은 아니다.

 

인자를 받아 값을 얻어내거나 계산의 상태를 수정할 수 있는 것이라면 어떠한 것이라도 함수 객체가 될 수 있으며, 이러한 함수 객체는 언제든지 다른 함수의 인자로 넘겨줄 수 있다. 일반적인 함수의 형태를 가지는 함수 객체 외에도, 함수 호출 연산자가 오버로딩되어 있는 클래스나 구조체(struct)로 정의된 타입의 객체도 함수 객체라고 할 수 있다.

 

 

5. 어댑터(adaptor)

컴포넌트의 인터페이스를 변경하는 컴포넌트를 어댑터라고 부른다. 예를 들어, reverse_iterator 컴포넌트를 이용하면 주어진 반복자 타입의 기존 특성들은 그대로 유지하되 순회 방향만 반대로 변경한 새로운 반복자 타입을 만들어낸다. 일반적인 순회 순서로는 특정 연산을 수행하기에 적합하지 않을 수 있는데, 그러한 경우에 이는 매우 유용한 기능이 될 수 있다.

 

STL은 컨테이너 어댑터와 함수 어댑터를 몇 가지 더 정의해 두고 있다. 스택 어댑터(stack adaptor)는 주어진 시퀀스 컨테이너를 후입선출(last-in, first-out) 스택의 인터페이스만 지닌 컨테이너로 변환시킨다. 큐 어댑터(queue adaptor)는 일반 시퀀스 컨테이너를 선입선출(first-in, first-out) 큐로 변환시키고, 우선 순위 큐 어댑터(priority queue adaptor)는 비교 연산자로 결정된 순서에 따라, 접근시 얻게 되는 값이 결정되는 큐를 만들어 낸다.

 

STL에서 제공하는 함수 어댑터에는 부정자, 바인더, 그리고 함수 포인터 어댑터가 있다.

부정자(negator)는 함수 객체의 한 종류로서, 불 값을 리턴하는 조건 함수 객체(predicate function object)의 리턴 값을 반대로 만든다.

바인더(binder)는 이항 함수 객체(binary function object)의 두 인자 중 한 개의 인자를 특정 값으로 바인드하여, 단항 함수 객체(unary function object)로 변환한다.

함수 포인터 어댑터(pointer-to-function adaptor)는 함수 포인터를 함수 객체로 변환한다. 이 어댑터를 사용하면, 일반 함수 객체를 사용했을 때 보다 더 많은 유연성을 지닌 컴파일 코드를 얻을 수 있다.(또한 이 어댑터는 "코드 비대화" 문제를 방지하는데도 도움을 준다).

 

 

6. 할당기(allocator)

모든 STL 컨테이너는 할당기 클래스를 사용하여 프로그램에서 사용하고 있는 메모리 할당 관련 정보를 캡슐화(encapsulation)하고 있다. 메모리 할당 모델에 따라 운영체제로부터 메모리를 획득해 오는 방식들이 각기 다르다. 할당기 클래스는 포인터, 상수 포인터, 레퍼런스, 상수 레퍼런스, 객체의 사이즈, 포인터의 타입, 할당 및 반환 함수 등에 관한 내용들을 캡슐화해 둔다. 할당기에 관련된 모든 연산은 아모타이즈드 상수 시간 연산이어야 한다.

 

메모리 할당 모델과 관련된 정보는 모두 할당기에 캡슐화되어 있기 때문에 STL 컨테이너에서는 할당기만 다른 것으로 바꾸면, 메모리 할당 모델을 바꿀 수 있다.

 

 

 

 

 

- STL 튜토리얼·레퍼런스 가이드 제2판 中 -