[STL] 요약 : container, iterator, algorithm, 함수자(functor), adaptor, allocator

컨테이너(container)

C 언어의 배열처럼 동일한 요소들을 모아놓은 집합을 뜻합니다. 구조체는 각기 다른 자료형을 내부적으로 유지하지만, 컨테이너는 반드시 동일한 요소로 구성되어 있어야 합니다.

컨테이너에는 순차 컨테이너(sequence container)와 정렬 연관 컨테이너(sorted associative container)가 있습니다. STL에 들어 있는 모든 컨테이너는 고정된 크기를 갖는 것이 아니라 동적으로 크기를 언제든지  변경할 수 있습니다.

*  순차 컨테이너(sequence container)

순차 컨테이너는  동일한 객체가 선형으로 구성된 집합(collection)으로, 실행시에 동적으로 크기를 변경할 수 있습니다. 순차 컨테이너에는 다음과 같은 컨테이너가 포함되어 있습니다.

순차 컨테이너 종류 (컨테이너 / 호칭 / 설명)

vector / 벡터 /

1. 구성 요소에 임의로 접근할 수 있습니다. (모든 요소에 접근할 때의 소요 시간이 동일합니다.)

2. 집합 끝에서 발생하는 삽입과 삭제는 신속히 처리하지만, 처음과 중간에 대해서는 해당 위치 다음에 있는 요소들의 개수에 비례해서 처리됩니다.

deque / 덱 /

1. 구성 요소에  임의로 접근할 수 있습니다. (모든 요소에 접근할 때의 소요  시간이 동일합니다.)

2. 집합의 양 끝(시작과 끝)에서 발생하는 삽입과 삭제를 신속히 처리하지만, 중간에  대해서는 해당 위치 다음에 양쪽에 있는 요소들의 개수에 비례해서 처리됩니다.

list  / 리스트 /

1. 구성 요소에 선형적으로 접근합니다. (요소의 개수에 따라서 접근 소요 시간이 늘어나고, 요소 위치에 따라서 소요 시간이 다릅니다.)

2. 집합 내의 어디에서나 구성 요소의 삽입과 삭제가 동일한 시간으로 신속히 처리됩니다.

* 정렬 연관 컨테이너(sorted associative container)

정렬 연관 컨테이너는 키(key)를 사용해서 데이터를 신속하게 찾아낼 수 있는 집합으로, 순차 컨테이너와 마찬가지로 실행 시에 동적으로 크기를 변경할 수 있습니다. 정렬 연관 컨테이너에는 다음과 같은 컨테이너가 포함되어 있습니다.

정렬 연관 컨테이너 종류 (컨테이너 / 호칭 / 설명)

set / 셋 /

1. 집합에는 키만 저장할 수 있습니다.

2. 중복되지 않는 키를 지원합니다. 따라서, 동일한 키가 두 개 존재할 수 없습니다.

3. 원하는 키를 신속하게 찾아냅니다.

multiset  / 멀티셋 /

1. 집합에는 키만 저장할 수 있습니다.

2. 중복 키를 지원합니다.  따라서, 여러 개의 복사본을 가질 수 있습니다.

3. 원하는 키를 신속하게 찾아냅니다.

map / 맵 /

1. 집합에는 키와 데이터를 함께 저장합니다.

2. 중복되지 않는 키를 지원합니다. 따라서, 동일한 키가 두 개 존재할 수 없습니다.

3. 키를 사용해서 원하는 객체를 신속하게 찾아줍니다.

multimap / 멀티맵 /

1. 집합에는 키와 데이터를 함께 저장합니다.

2. 중복  키를 지원합니다.  따라서, 여러 개의 복사본을 가질 수 있습니다.

3. 키를 사용해서 원하는 객체를 신속하게 찾아줍니다.

반복자(iterator)

STL의 모든 연산은 컨테이너에 대해서 적용될 수 있도록 고안되었습니다. 그래서, 컨테이너의 요소 하나, 일정 범위의 구간, 전체에 대해서 연산을 적용할 수 있도록 세분화되어 있습니다. 반복자는 컨테이너로부터 값을 읽어 올 수 있는 방법을 제공해 줍니다. 벡터와 같은 컨테이너는 []연산자를 통해서도 값을 읽어 올 수 있지만, 모든 컨테이너에 대해서 사용할 수 있는 방법은 아닙니다. 따라서, 우리는 모든 컨테이너에 대해서 동일하게 동작할 수 있도록 값을 읽어 오는 방법을 익혀야 합니다.

"반복자는 포인터이다"라고 생각하면 좋습니다. 포인터를 제대로 다룰 줄 알면 더 바랄 것이 없습니다. 그러나, 실제로는 포인터가 반복자의 일부입니다. 단지, C++라는 언어가 포인터라는 개념을 이미 갖고 있었고, 기존의 프로그래머들이 모두 능숙하게 포인터를 다룰 수 있기 때문에, C++ 표준 위원회는 STL의 개념이 포인터가 갖고 있는 몇 가지 특징들을 포함하도록 했습니다.

STL은 이미 알려진 자료 구조를 템플릿을 사용해서 구현한 코드입니다. 누구나 리스트와 맵이라는 자료 구조를 구현할 줄 알고 있습니다. 그러나, 실제로 구현했을 경우 코드 또한 완전히 같을 수 있을까요? 그렇지는 않을 겁니다. 성능을 향상시킨다고 나름대로 많은 기교를 부릴 게 틀림없습니다. 그래서, 우리는 벡터가 일반 배열처럼 동작한다는 것은 알지만, 어떻게 구현했는지는 알 수 없습니다. "이렇게 구현했겠지"하고 추측하는 것만큼 위험한 것은 없습니다. 컴파일러를 제작하는 회사마다 다릅니다.

이렇게 각기 다르게 구현된 컨테이너에 대해서 제대로 동작하려면, 반복자에 대해서도 몇 가지 제한이 필요합니다. 가령, "벡터 컨테이너의 반복자는 어떠어떠한 기능을 지원해야 한다"입니다. 셋의 경우도 순차적으로 진행되는 컨테이너가 아니기 때문에, 벡터에서 지원하는 [] 연산자를 지원하지 않습니다. 지원할 수도 있지만, 일반적으로 셋을 표현하는 자료 구조의 환경 때문에, [] 연산자를 적용했을 경우 효율이 떨어질 뿐더러 별로 의미가 없습니다. 모든 컨테이너는 어떠한 기능의 반복자가 필요한지 STL 규정에 이미 정해 두었습니다.

반복자의 종류

반복자 / 설명

입력 : Input /

1. 두 개의 반복자, first와 last에 대해서  first != last 라는 식에 대해서 참을 반환해야 합니다.

2. ++first 연산을 수행하면, 반복자 first 다음 요소의 위치를 반환해야 합니다.

3. *first 연산을 수행하면, 반복자 first가 가리키는 값을 반환해야 합니다.

그러나, 다음 코드는 사용할 수 없습니다. 입력 반복자는 읽기 전용입니다.

*first = 5;

4. 컨테이너의 요소를 검색하는 find 알고리즘에서 사용됩니다.

출력 : output /

1. ++first 연산을 수행하면, 반복자 first 다음 요소의 위치를 반환해야 합니다.

2. *first 연산을 수행하면, 반복자 first가 가리키는 곳에 값을 저장합니다.

그러나, 다음 코드는 사용할 수 없습니다. 출력 반복자는 쓰기 전용입니다.

N = *first

3. 컨테이너의 요소를 복사하는 copy 알고리즘에서 사용됩니다.

순방향 : forward /

1. 입력 반복자와 출력 반복자의 모든 기능을 포함합니다.

2. 한 쪽 방향으로만 순회할 수 있습니다.

3. 반복자의 위치를 저장해 두었다가 저장한 위치부터 다시 순회할 수 있습니다.

4. 컨테이너의 요소를 읽고 쓰는 replace 알고리즘에 사용됩니다.

양방향 : bidirectional /

1. 순방향 반복자의 모든 기능을 포함한다.

2. 양쪽 방향으로의 순회가 가능합니다.

따라서, --first 연산을 수행하면, 이전 요소의 위치를 반환해야 합니다.

3. 컨테이너의 요소들을 뒤집을 수 있는 reverse 알고리즘에서 사용됩니다.

임의접근 : random access /

1. 양방향 반복자의 모든 기능을 포함합니다.

2. 컨테이너의 모든 요소에 접근 소요 시간이 동일합니다.

3. +, -, +=, -=, [] 연산자를 지원해야 합니다.

4. <, >, <=, >= 연산자를 지원해야 합니다.

5. 컨테이너의 요소를 이진 검색하는 binary_search 알고리즘에서 사용됩니다.

반복자에는 위의 표에서 나열한 것 외에, 편리를 위해서 제공되는 반복자가 몇 개 더 있습니다.

1. 삽입 반복자(insert iterator)

* 후위 삽입 반복자 : back_insert_iterator

컨테이너의 push_back 함수를 사용해서, 컨테이너의 마지막에 요소를 자동으로 삽입하는 반복자로, 축약해서 back_insertor로 쓸 수 있습니다.

* 전위 삽입 반복자 : front_insert_iterator

컨테이너의 push_front 함수를 사용해서, 컨테이너의 처음에 요소를 자동으로 삽입하는 반복자로, 축약해서 front_insertor로 쓸 수 있습니다.

* 삽입 반복자 : insert_iterator

컨테이너의 insert 함수를 사용해서, 컨테이너의 중간에 요소를 자동으로 추가해 주는 반복자로, 축약해서 insertor로 쓸 수 있습니다.

2. 스트림 반복자(stream iterator)

* 입력 스트림 반복자(istream_iterator)

입력 반복자의 한 종류로, 스트림으로부터 한 쪽 방향으로 읽어나갈 수 있습니다. 따라서, cin과 같은 표준 입력 스트림(키보드)으로부터 입력을 받을 수 있습니다.

istream_iterator<Type>()는 입력 스트림의 끝을 나타내는 반복자, 컨테이너의 멤버 함수인 end 함수와 같은 역할을 합니다.

* 출력 스트림 반복자(ostream_iterator)

출력 반복자의 한 종류로, 스트림으로부터 한 쪽 방향으로 출력해 나갈 수 있습니다. 따라서, cou과 같은 표준 출력 스트림(모니터)으로 출력을 할 수 있습니다.

3. 참조 반복자(reference iterator)

* 수정 반복자(mutable iterator)

반복자를 사용해서 값을 변경할 수 있는 반복자로, 일반 반복자인 vector<int>::iterator등이 여기에 해당됩니다.

* 상수 반복자(const_iterator)

반복자를 사용해서 값을 변경할 수 없는 반복자로, vector<int>::const_iterator로 생성할 수 있습니다. 상수 반복자 it에 대해서 다음 코드는 에러입니다.

set<int> set1;

set1.insert(3);

set<int>::iterator it = set1.begin();

*it = 5; // 에러. it는 상수 반복자.

위의 코드는 아래와 같이 변경되어야 합니다. 셋을 구현할 자료 구조의 특성 때문에. 셋은 항상 상수 반복자만을 제공합니다.

set1.erase(it);

set1.insert(5);

알고리즘(algorithm)

컨테이너에 대해서 적용할 수 있는 기능들을 체계적으로 정리해 놓은 함수들을 말합니다. 알고리즘에 속한 함수는 모두 일반적(generic)이기 때문에, 어떤 하나의 컨테이너가 아니라 여러 컨테이너에 대해서 동작합니다. 여기서 모든 컨테이너가 아니라 여러 컨테이너인 것은 기능의 효율성 때문에, 적합하지 않은 컨테이너(자료구조)에 대해서는 지원하지 않기 때문입니다.

알고리즘에 포함된 함수는 모두 4개지로 분류할 수 있습니다.

* 변경 불가 순차 알고리즘(nonmutating sequence algorithm)

* 변경 가능 순차 알고리즘(mutating sequence algorithm)

* 정렬 관련 알고리즘(sorting-related  algorithm)

* 범용 수치 알고리즘(generalized numeric algorithm)

변경 불가 순차 알고리즘(nonmutating sequence algorithm) 종류

함수 / 설명

find / 원하는 요소를 검색합니다.

find_if / 조건자를 true가 되게 하는 첫 번째 요소를 검색합니다.

adjacent_find / 동일한 두 개의 원소가 이웃하고 있는 쌍을 검색합니다.

count / 특정 값과 일치하는 요소의 개수를 반환합니다.

count_if / 조건자를 true가 되게 하는 요소의 개수를 반환합니다.

for_each / 인자로 넘어간 함수를, 요소 전체에 대해서 호출합니다. for문과 같은 반복문을 대신 해서 사용할 수 있습니다.

equal / 두 개의 구간이 일치하면, true를 반환합니다.

mismatch / 두 개의 구간이 일치하지 않으면, true를 반환합니다.

search / 구간 내에 포함된 하위 구간을 검색합니다.  C 함수의 strstr 함수와 비슷한 역할을 합니다.

변경 가능 순차 알고리즘(mutating seqence algorithm)종류

함수 / 설명

copy / 특정 구간에 속하는 원소를 다른 구간으로 복사합니다. 구간이 중복될 경우, 왼쪽으로의 이동만 허용합니다.

copy_backward / 특정 구간에 속하는 원소를 다른 구간으로 복사합니다. 구간이 중복될 경우, 오른쪽으로의 이동만 허용합니다.

fill / 구간에 속하는 모든 원소를 주어진 값으로 채웁니다.

fill_n / 시작 위치에서부터 n 개의 요소를 주어진 값으로 채웁니다.

generate / 구간에 들어 있는 요소 각각에 대해 인자로 넘어간 함수를 호출하고, 그 결과로 다시 요소를 채웁니다. 구간 내의 요소는 함수의 결과값으로 채워집니다.

partition / 구간 내에서 주어진 값보다 작은 요소는 앞쪽에, 큰 요소는 뒤쪽에 오도록 재배치합니다.

stable_partition / 구간 내에서 주어진 값보다 작은 요소는 앞쪽에, 큰 요소는 뒤쪽에 오도록 재배치하면서, 최초의 상대적인 위치를 그대로 유지합니다.

random_shuffle / 구간 내의 요소를 난수로 채웁니다.

remove / 주어진 값과 일치하는 구간 내의 모든 요소를 삭제합니다. 그러나, 실제로 삭제되는 것이 아니고, 가장 뒤쪽으로 자리르 변경합니다. 실제 삭제는 erase 함수를 사용합니다.

replace / 주어진 값과 일치하는 구간 내의 요소들을 지정한 값으로 치환합니다.

reverse / 구간 내의 모든 요소들을 거꾸로 뒤집어서 재배치합니다.

rotate / 구간 내의 모든 요소를 주어진 위치를 중심으로 한 바퀴 돌립니다.

swap / 두 개의 값을 교환합니다.

swap_ranges / 두 구간에 속하는 값들을 교환합니다.

transfrom / 구간에 속하는 요소 각각에 대하여, 인자로 넘어간 함수를 호출한 결과를 다른 구간에 저장합니다.

unique  / 구간 내에 속한 모든 중복된 요소를 제거함으로써, 해당 요소가 유일하도록 만듭니다. remove 함수처럼, 실제로 삭제가 일어나는 것이 아니고, 구간의 맨 뒤로 이동시켜 놓기 때문에, 컨테이너의 크기에는 변화가 없습니다.

정렬 관련 알고리즘(sorting-related algorithm) 종류

함수 / 설명

sort / 구간을 정렬합니다. (quick-sort)

stable_sort / 구간을 정렬합니다. 동등한 요소의 상대적인 위치를 유지합니다. (merge-sort)

partial_sort / 구간을 정렬합니다. 동등한 요소의 상대적인 위치를 유지하지 않습니다. (heap-sort)

nth_element / 구간이 정렬되었을 경우, N번째 위치에 놓이게 될 요소만 놓고, 나머지 요소들은 N보다 작은 값들을 왼쪽에, 큰 값들을 오른쪽에 배치한다

binary_search / 정렬되어 있는  구간으로부터 요소를 검색합니다. (이진 검색)

lower_bound / 이진 검색을 사용해서 정렬된  구간을 검색한 후, 동일한 값들이 연속되어 있을 경우 맨 앞의 요소를 반환합니다.

upper_bound / 이진 검색을 사용해서 정렬된 구간을 검색한 후, 동일한 값들이 연속되어 있을 경우 맨 마지막의 요소를 반환합니다.

equal_range / 이진 검색으로 검색한 값이 동일하게 연속된 구간을 반환합니다. lower_bound와 upper_bound 함수의 결과를 합한 결과가 반환됩니다.

merge / 두 개의 정렬된 구간을 병합해서, 중복되지 않는 구간에 결과를 저장합니다.

inplace_merge 두 개의 정렬된 구간을 병합해서, 중복되지 않는 구간에 결과를 저장합니다.

includes / 주어진 정렬된 구간의 요소들이 다른 구간에 속하는지를 반환합니다.

set_union / 정렬된 두 개 구간의 합집합을 다른 구간에 저장합니다.

set_difference / 정렬된 첫 번째 구간에 속한 요소들 중에서 정렬된 두 번째 구간에 속하지 않는 요소들을 다른 구간에 저장합니다.

set_intersection / 정렬된 두 개의  구간에 공통으로 속한 요소들을 다른 구간에 저장합니다.

set_symmetric_defference / 정렬된 두 개의 구간에서, 한 쪽 구간에만 속해있는 요소들을 다른 구간에 저장합니다.

make_heep / 구간 내의 요소들을  힙(heep)으로 재구축 합니다.

sort_heep / 힙에 저장된 원소들을 정렬합니다.

push_heap / 주어진 구간을 힙으로 유지하면서, 새로운 요소를 힙에 추가합니다.

pop_heap / 주어진 구간을 힙으로 유지하면서, 가장  큰 요소를 삭제합니다.

min / 두 개의 요소 중, 작은 값을 반환합니다.

max / 두 개의 요소 중, 큰 값을 반환합니다.

lexicographical_compare / 두 개의 구간을 사전 순서로 비교해서 결과를 반환합니다.

next_permutation / 주어진 구간을 사전 순서에 기초해서, 다음 순열로 변경합니다.

prev_permutation / 주어진 구간을 사전 순서에 기초해서, 이전 순열로 변경합니다.

범용 수치 알고리즘(generalized numeric algorithm) 종류

함수 / 설명

accumulate / 주어진 구간에 속하는 요소들의 합계를 구합니다.

partial_sum / 주어진 구간의 요소를 기초로, 부분합을 구합니다.

adjacent_difference / 주어진 구간의 요소를 기초로, 이웃하는 요소의 차이를 구합니다.

inner_product / 주어진 두 구간의 내적(inner product)을 구합니다.

함수자(functor)

함수 객체(function object)라고도 부르며, 0개 이상의 인자를 받아서 알고리즘의 기본 동작을 변형하거나 확장시켜 주는 객체를 얘기합니다. 따라서, 우리가 지금까지 사용해 오던 함수도 함수자에 속합니다. 함수 포인터를 인자로 받아서, 알고리즘 내부에서 해당 함수를 사용할 경우, 알고리즘이 확장될 수 있기 때문입니다.

그러나, STL에서는 함수자로서 함수를 많이 사용하지 않습니다. 함수 포인터를 인자로 사용했을 경우의 단점은, 반환값과 인자가 동일한 함수에 대해서만 동작하기 때문입니다. 그래서, 범용성이 떨어지게 됩니다. 또한, 함수 포인터를 사용하기 때문에, 매번 함수를 호출할 때마다 포인터를 통해서 접근해야 할 뿐더러 해당 함수를 호출할 때마다 메모리 할당과 해제 또한 책임져야 합니다.

그래서, 성능면에서 많은 문제가 발생합니다.

함수 포인터를 사용했을 경우 발생하게 되는 위의 문제점들을 해결하기 위해, STL은 클래스를 인자로 사용합니다. 함수 대신 사용하는 클래스는 반드시 () 연산자를 재정의해야 합니다. 이렇게 함수를 직접 넘기지 않고 클래스를 통해서 구현된 함수 객체를 넘길 때의 장점은, 지정된 클래스로 형변환될 수 있는 모든 클래스를 인자로 사용할 수 있기 때문에 범용성이 확보된다는 것입니다. 여기서 지정된 클래스로의 변환은, 인자로 사용가능한 클래스를 상속받음으로써 해결할 수 있습니다.

두 번째로 성능과 관련된 문제는, 클래스 내부에서 구현된 () 연산자 오버로딩 함수는, 코드가 짧기 때문에 충분히 인라인(inline) 함수로 구현이 가능하기 때문에, 함수 호출과 관련된 부담에서 벗어날 수 있습니다. 더불어 추가적으로 생기는 장점은, 함수에서 누적되는 등의 용도로 사용하는 어떤 정보가 필요하다면, 함수 포인터의 경우 전역 변수를 사용해야 하지만 클래스는 멤버 변수로 쉽게 관리할 수 있습니다.

함수자의 종류로는 말 그대로 함수자와 함수 어댑터(adaptor)가 있습니다. 함수자는 함수 포인터나 클래스를 사용해서 함수의 기능을 변경하는 것을 말하고, 함수 어댑터는 함수자의 기능을 변형해서 새로운 함수자를 생성합니다.

다음은 STL이 제공하는 연산자를 구현한 클래스 함수자들로, 산술 연산, 비교 연산, 논리 연산에 대한 함수자를 제공합니다.

산술 연산 함수자 종류

연산자 / 이름 / 설명

덧셈(+) / plus / x와 y의 합을 반환합니다. (x + y, 이항 함수자)

뺄셈(-) / minus / x와 y의 차를 반환합니다. (x - y, 이항 함수자)

곱셈(*) / multiplies / x와 y의 곱을 반환합니다. (x * y, 이항 함수자)

나눗셈(/) / divides / x와 y의 몫을 반환합니다. (x / y, 이항 함수자)

나머지(%) / modulus / x와 y의 나머지를 반환합니다. (x % y, 이항 함수자)

부정(-) / negate / x의 부호를 변경한 값을 반환합니다. (-x, 단항 함수자)

비교 연산 함수자 종류

연산자 / 이름 / 설명

같다(==) / equal_to / x가 y와 같은지 비교합니다. (x == y, 이항 함수자)

같지 않다(!=) / not_equal_to / x가 y와 같지 않은지 비교합니다. (x != y, 이항 함수자)

크다(>) / greater / x가 y보다 큰지 비교합니다. (x > y, 이항 함수자)

작다(<) / less / x가 y보다 작은지 비교합니다. (x >= y, 이항 함수자)

작거나 같다 (<=) / less_equal / x가 y보다 작거나 같은지 비교합니다. (x <= y, 이항 함수자)

논리 연산 함수자 종류

연산자 / 이름 / 설명

And(&&) / logical_and / x와 y를 AND 연산합니다. (x && y, 이항 함수자)

OR(||) / logical_or / x와 y를 OR 연산합니다. (x || y, 이항 함수자)

NOT(!) / logical_not / x를 NOT 연산합니다. (!x, 단 항 함수자)

함수 어댑터(function adaptor)

* 바인터(binder)

두개의 인자를 필요로 하는 이항 함수 객체의 인자 하나를 고정시켜서, 인자를 하나만 요구하는 단항 함수 객체로 변환시켜 줍니다.

* 부정자(negator)

함수 인자로 사용되는 조건자의 의미를 반대로 변환시켜 줍니다.

* 함수 포인터 어댑터(adaptors for pointers to functions)

단항이나 이항 함수 포인터를 라이브러리가 제공하는 함수 어댑터와 사용할 수 있도록 도와줍니다.

* 멤버 함수 포인터 어댑터(adaptors for pointers to member functions)

단항이나 이항 멤버 함수 포인터를 라이브러리가 제공하는 함수 어댑터와 사용할 수 있도록 도와줍니다.

바인더(binder) 어댑터

* bind1st

함수자에 전달되는 두 개의 인자 중, 첫 번째 인자를 고정값으로 사용할 수 있도록 도와주는 바인더

* bind2nd

함수자에 전달되는 두 개의 인자 중, 두 번째 인자를 고정값으로 사용할 수 있도록 도와주는 바인더

부정자(negator) 어댑터

* not1 / 인자로 전달된 단항 조건자의 의미를 반대로 변환합니다.

* not2 / 인자로 전달된 이항 조건자의 의미를 반대로 변환합니다.

함수 포인터 어댑터(adaptors for pointers to functions)

* ptr_fun / 단항 함수를 함수 어댑터처럼 사용할 수 있도록 지원합니다.

* ptr_fun / 이항 함수를 함수 어댑터처럼 사용할 수 있도록 지원합니다.

멤버 함수 포인터 어댑터(adaptors for pointers to member functions)

* mem_fun / 인자가 없는 멤버 함수를 함수 어댑터처럼 사용할 수 있도록 지원합니다.

* mem_fun / 단항 멤버 함수를 함수 어댑터처럼 사용할 수 있도록 지원합니다.

* mem_fun_ref / 인자가 없는 멤버 함수를 함수 어댑터처럼 사용할 수 있도록 지원합니다. 인자가 없는 멤버 함수 어댑터인 mem_fun의 레퍼런스(&) 버전입니다.

* mem_fun_ref / 단항 멤버 함수를 함수 어댑터처럼 사용할 수 있도록 지원합니다. 단항 멤버 함수 어댑터인 mem_fun의 레퍼런스(&) 버전입니다.

* mem_fun / 인자가 없는 const 멤버 함수를 함수 어댑터처럼 사용할 수 있도록 지원합니다. 인자가 없는 멤버 함수 어댑터인 mem_fun의 상수(const) 버전입니다.

* mem_fun / 인자가 없는 const 멤버 함수를 함수 어댑터처럼 사용할 수 있도록 지원합니다. 단항 멤버 함수 어댑터인 mem_fun의 상수(const) 버전입니다.

* mem_fun_ref / 인자가 없는 const 멤버 함수를 함수 어댑터처럼 사용할 수 있도록 지원합니다. 인자가 없는 멤버 함수 어댑터인 mem_fun_ref의 상수(const) 버전입니다.

* mem_fun_ref / 단항 const 멤버 함수를 함수 어댑터처럼 사용할 수 있도록 지원합니다. 단항 멤버 함수 어댑터인 mem_fun의 상수(const) 버전입니다.

어댑터(adaptor)

어댑터는 컨테이너의 인터페이스 또는 함수자의 기능을 변경하는 컴포넌트를 말합니다. 가령, 기존의 컨테이너를 사용해서 스택을 꾸미고 싶을 때는 스택 어댑터(stack adaptor)를, 함수자의 의미를 변경할 때는 바인더(binder)나 부정자(negator) 등을 사용합니다.

어댑터의 종류

1. 컨테이너 어댑터(container adaptor)

* 스택 어댑터(stack adaptor)

- 스택(stakc) 자료구조를 표현하는 어댑터를, 스택 인터페이스로 변환합니다.

- 스택 : 한 쪽 끝에서만 삽입과 삭제가 일어나고, 먼저 집어넣은 것을 마지막에 꺼냅니다. (FILO : file-in, last-out)

*큐 어댑터(queue adaptor)

- 큐(queue) 자료구조를 표현하는 어댑터로, 큐 인터페이스로 변환합니다.

= 큐 : 한 쪽 끝에서 삽입이, 반대쪽 끝에서 삭제가 일어나고, 먼저 집어 넣은 것을 먼저 꺼냅니다(first-in, first-out)

* 우선 순위 큐 어댑터(priority queue adaptor)

- 우선 순위 큐(priority queue) 자료구조를 표현하는 어댑터로, 우선 순위 큐 인터페이스로 변환합니다.

- 우선 순위 큐 : 한 쪽 끝에서 삽입이, 반대쪽 끝에서 삭제가 일어나고, 항상 가장 큰 값을 먼저 꺼냅니다.

2. 함수 어댑터(function adaptor)

* 바인더(binder)

- 두 개의 인자를 필요로 하는 이항 함수 객체의 인자 하나를 고정시켜서, 인자를 하나만 요구하는 단항 함수 객체로 변환시켜 줍니다.

* 부정자(negator)

- 함수 인자로 사용되는 조건자의 의미를 반대로 변환시켜 줍니다.

* 함수 포인터 어댑터(adaptor for pointers to functions)

- 단항이나 이항 함수 포인터를 라이브러리가 제공하는 함수 어댑터와 사용할 수 있도록 도와줍니다.

* 멤버 함수 포인터 어댑터(adaptors for pointers to member functions)

- 단항이나 이항 멤버 함수 포인터를 라이브러리가 제공하는 함수 어댑터와 사용할 수 있도록 도와줍니다.

3. 반복자 어댑터(iterator adaptor)

* 역 반복자 어댑터(reverse iterator adaptor)

- 반복자의 인터페이스를 변경합니다.

- 역 반복자 어댑터 하나 밖에 없습니다.

- reverse_iterator 클래스의 base 함수로 구할 수 있습니다.

- 각 컨테이너마다 역 반복자를 제공하기 때문에, 굳이 반복자 어댑터를 사용할 필요는 없습니다.

할당자(allocator)

메모리를 어떻게 할당해야 할지를 결정합니다. 가령, 자신이 만든 컨테이너가 일반적으로 사용하는 malloc이나 VirtualAlloc 함수 또는 new 연산자를 사용해서 동적 메모리를 할당할 수 없을 경우에 사용합니다.

기본 할당자(allocator)

1. 헤더 파일

#include <memory>

2. 선언

template <typename Type> class allocator;

3. 기본 할당자로 지정된 allocator 클래스의 경우, 할당자를 지정하지 않은 모든 컨테이너에 대해 공통적으로 사용됩니다. allocator 클래스는 메모리 할당에 new와 delete 연산자를 사용합니다.

4. 메모리 할당에 많은 시간이 소요되서는 안 되기 때문에, 최소한의 상수 시간내에 할당이 이루어 집니다.

사용자 정의 할당자(custom allocator)

1. 기본 할당자가 갖고 있는 기능에 새로운 기능을 추가하기 위해 사용합니다.

2. 가령, 디버거의 용도로 사용할 수 있는 할당자가 있다면, 코드를 디버깅하기 위한 용도로 STL과 결합할 수 있습니다. 디버거 할당자는 동적으로 할당된 모든 메모리를 보여주고, 누수를 탐지하는 기능을 가질 것입니다.

3. 그러나, 기본 할당자만으로 메모리 할당은 충분하기 때문에, 별도의 할당자를 만들거나 하지 않습니다.

4. 새로운 할당자가 debug_allocator 클래스에 구현되어 있을 경우, 아래 코드처럼 벡터 컨테이너를 비롯한 모든 컨테이너에 대해 적용할 수 있습니다.

vector< int, debug_allocator<int> >v;

출처: 누군가의 네이버 블로그~