STL 의 모든것

① 시퀀스 컨테이너(Sequence Container) : 자료의 선형적인 집합이며 자료를 저장하는 기본 임무에 충실한 가장 일반적인 컨테이너이다. 삽입된 자료를 무조건 저장하며 입력되는 자료에 특별한 제약이나 관리 규칙은 없다. 사용자는 시퀀스의 임의 위치에 원하는 요소를 마음대로 삽입, 삭제할 수 있다. STL에는 벡터(vector), 리스트(list), 데크(deque) 세 가지의 시퀀스 컨테이너가 제공된다.

② 연관 컨테이너(Associative Container) : 자료를 무조건 저장하기만 하는 것이 아니라 일정한 규칙에 따라 자료를 조직화하여 관리하는 컨테이너이다. 정렬이나 해시 등의 방법을 통해 삽입되는 자료를 항상 일정한 기준(오름차순, 해시 함수)에 맞는 위치에 저장해 놓으므로 검색 속도가 빠른 것이 장점이다. 표준 STL에는 정렬 연관 컨테이너인 셋(set), 맵(map) 등의 컨테이너가 제공된다.

③ 어댑터 컨테이너 (Adapter Container) : 시퀀스 컨테이너를 변형하여 자료를 미리 정해진 일정한 방식에 따라 관리하는 것이 특징이다. 스택(stack), 큐(queue), 우선 순위 큐(priority_queue) 세 가지가 있는데 스택은 항상 LIFO의 원리로 동작하며 큐는 항상 FIFO의 원리로 동작한다. 자료를 넣고 빼는 순서를 외부에서 마음대로 조작할 수 없으며 컨테이너의 규칙대로 조작해야 한다.

벡터의 생성자는 다음 4 가지가 중복 정의되어 있다. 문서상의 원형에는 생성자의 마지막 인수로 const A& al = A()라는 할당기 인수가 하나 더 있는데 디폴트가 지정되어 있고 보통 생략하므로 원형에 적지 않기로 한다. 실용성도 없는데 괜히 원형만 복잡하게 만들 뿐이다. 이후의 컨테이너도 마찬가지로 할당기는 무시한다.

explicit vector(); 
explicit vector(size_type n, const T& v = T()); 
vector(const vector& x); 
vector(const_iterator first, const_iterator last); 

두 번째 생성자는 정수값 하나만을 취하므로 변환 생성자이다. 그래서 explicit로 선언하여 명시적인 생성만을 허락한다. 만약 이 생성자가 explicit가 아니라면 vi=3 따위로 대입할 때 컴파일러는 정수 3으로부터 크기 3의 벡터를 생성하여 vi에 대입하려고 할 것이다. 또는 벡터를 인수로 취하는 함수에게 정수를 넘겨도 별다른 불만없이 정수로부터 벡터를 만들어 함수를 호출하려고 할 것이다. 정수와 벡터는 호환 타입이 아니므로 명시적으로 지정하지 않는 한 변환하지 않는 것이 바람직하며 그래서 이 생성자가 explicit로 선언되어 있는 것이다.

세 번째 생성자는 복사 생성자인데 다른 벡터로부터 똑같은 벡터를 만들어 낸다. 내부에서는 아마도 깊은 복사를 할 것이다. 네 번째 생성자는 반복자가 지정한 구간의 요소들을 가지는 새로운 벡터를 생성한다. 이때 반복자는 꼭 벡터의 반복자가 아니더라도 상관없다. 정적 배열이나 리스트의 반복자를 전달할 수도 있어 다른 컨테이너로부터 벡터를 초기화할 수 있다. 다음 예제는 벡터의 생성자 4 개를 테스트한다.

함수	설명
size	요소 개수를 조사한다.
max_size	벡터가 관리할 수 있는 최대 요소 개수를 조사한다.
capacity	할당된 요소 개수를 구한다.
resize(n)	크기를 변경한다. 새 크기가 더 클 경우 벡터의 원래 내용은 유지하며 새로 할당된 요소는 0으로 초기화된다.
reserve(n)	최소한의 크기를 지정하며 메모리를 미리 할당해 놓는다. 새 크기가 더 클 경우 벡터의 원래 내용은 유지한다. 새로 할당된 요소는 초기화되지 않는다.
clear(n)	모든 요소를 삭제한다.
empty	비어 있는지 조사한다.

resize는 지정한 크기로 요소 수를 늘리며 새로 생겨난 요소는 타입의 디폴트값으로 초기화되는데 vi는 정수형 벡터이므로 int()값인 0으로 초기화될 것이다.
capacity는 할당되어 있는 메모리양인데 이 크기는 size보다 크거나 같다. 벡터는 메모리가 부족할 경우 현재 용량의 2배씩 메모리를 늘려 나가며 앞으로 추가될 요소를 고려하여 약간의 여유분을 미리 할당해 놓는다.
reserve는 미리 메모리를 할당해 놓는 함수
clear는 벡터를 비우고
empty는 벡터가 비어 있는지 점검한다. empty는 size() == 0 조건을 점검하는데 이 두 조건이 논리적으로는 같지만 실제로는 굉장한 차이가 있을 수도 있다. size는 정확한 개수를 구하므로 요소가 많을 경우 일일이 세어 봐야 한다. 특히 리스트같은 컨테이너는 개수를 구하기 위해서도 순회가 필요하므로 size의 속도는 다소 느리다. 하지만 empty는 0인지 아닌지만을 점검하며 훨씬 더 빠른 속도로 컨테이너가 비어 있는지를 점검해내므로 가급적이면 empty를 사용하는 것이 유리하다.

void push_back(const T& x); 
void pop_back(); 

push_front, pop_front 함수는 제공하지 않는다.
꼭 벡터의 중간에 요소를 삽입하고 싶다면 insert 함수를 사용한다. 벡터에 대해 push_front(V)를 하려면 insert(begin(),V)을 대신 호출하면 된다.

iterator insert(iterator it, const T& x = T()); 
void insert(iterator it, size_type n, const T& x); 
void insert(iterator it, const_iterator first, const_iterator last); 

iterator erase(iterator it); 
iterator erase(iterator first, iterator last); 

insert와 erase는 요소를 관리하는 기본 동작이므로 대부분의 컨테이너에 동일한 이름과 형식으로 존재한다.

반복자 무효화 현상
삽입된 위치의 앞쪽은 무효화될 수도 있고 그렇지 않을 수도 있는데 재할당에 의해 메모리 번지가 바뀌면 무효화될 것이고 그렇지 않다면 영향을 받지 않을 것이다. 삽입에 의해 재할당이 자주 발생하지는 않지만 모든 경우에 유효성이 보장된다고 할 수는 없으므로 삽입하면 전 반복자가 무효화된다고 보는 것이 옳다.
삭제시는 삭제 구간의 뒤쪽은 무효화되지만 앞쪽은 영향을 받지 않는다. 삭제는 삽입과는 달리 메모리 재할당이 절대로 일어나지 않으므로 앞쪽 요소는 원래 자리를 항상 그대로 유지하기 때문이다.

컨테이너에 조금이라도 변형을 가했다면 이전에 조사해 놓은 반복자 전체를 믿지 않는 편이 더 확실하다.

대입 연산자는 두 벡터를 완전히 똑같이 만드는데 만약 일부 구간만 복사하고 싶다면 assign 멤버 함수를 사용한다. 항상 이런 식인데 연산자는 전체에 대한 처리를 하며 일부분에 대한 처리는 별도의 멤버 함수가 준비되어 있다. 연산자는 전달받을 수 있는 피연산자 수가 제한되어 있어 부분에 대한 처리를 할만큼 충분한 정보를 제공받을 수 없기 때문이다. assign은 다음 두 개의 버전이 제공된다.

void assign(size_type count, const Type& val); 
void assign(InIt first, InIt last); 

교환

void swap(vector& Right); 

v1.swap(v2);     // 멤버 함수 
swap(v1,v2);     // 알고리즘 함수 

요소 참조

const_reference at(size_type pos) const; 
reference at(size_type pos); 

일반적인 객체는 대단히 클 수 있으므로 벡터에 직접 객체를 저장하는 것보다는 객체의 포인터를 저장하는 것이 성능상 유리하며 훨씬 더 일반적이다.

이정도는 해줘야... 디폴트 생성자, 변환 생성자, 복사 생성자, = 대입 연산자, ==, < 비교 연산자, 가상 파괴자

#include <iostream> 
#include <vector> 
using namespace std; 
  
void main() 
{ 
     vector<bool> vb(32); 
  
     cout << vb[10] << endl; 
     vb[10]=true; 
     cout << vb[10] << endl; 
  
     vector<bool>::reference r=vb[10]; 
     cout << r << endl; 
     r.flip(); 
     cout << r << endl; 
     vector<bool>::iterator it; 
     for (it=vb.begin();it!=vb.end();it++) { 
          cout << *it; 
     } 
} 

explicit list(); 
explicit list(size_type n, const T& v = T()); 
list(const list& x); 
list(const_iterator first, const_iterator last); 

iterator insert(iterator it, const T& x = T()); 
void insert(iterator it, size_type n, const T& x); 
void insert(iterator it, const_iterator first, const_iterator last); 
iterator erase(iterator it); 
iterator erase(iterator first, iterator last); 

다만 처리 속도는 벡터보다 훨씬 빠른데 위치와 요소 개수에 상관없이 상수 시간내에 삽입, 삭제된다. 속도가 빠르다는 것 외에도 반복자가 무효화되지 않는 장점도 있다. (단, 반복자가 가리키는 대상이 삭제되면 당연히 반복자는 무효화 된다.)

void remove(const Type& val); 
void remove_if(UniPred F) 

리스트에는 링크 재배치의 장점을 살릴 수 있는 여러 가지 멤버 함수들이 준비되어 있다.

void swap(list& Right); 
void reverse( ); 
void merge(list& Right); 

void splice(iterator it, list& x); 
void splice(iterator it, list& x, iterator first); 
void splice(iterator it, list& x, iterator first, iterator last); 

전체를 이동시키는 splice(it, x)는 전체 구간을 이동하는 splice(it, x.begin(),x.end())와 동일한 함수라고 할 수 있다.

void sort(); 
void sort(BinPred op); 

다음 멤버 함수는 연속된 중복 요소를 제거하는데 같은 이름의 전역 함수도 있지만 멤버 함수는 리스트의 링크 구조를 활용하도록 구현되어 있다.

void unique(); 
void unique(UniPred op); 

속력 비교

컴파일러	비주얼 C++ 6.0	비주얼 C++ 8.0	Dev-C++
벡터	220	280	891
리스트	2924	1222	3455

연관 컨테이너를 구현하는 방법에는 균형 잡힌 이진 트리를 사용하여 정렬된 상태로 저장하는 방법이 있고 해쉬 테이블에 저장하는 방법이 있다. 해쉬는 해쉬 함수에 의해 한 번에 자료를 찾을 수 있으므로 검색 속도가 거의 순식간이라는 장점이 있지만 성능을 높이기 위해서는 해쉬 테이블이 충분히 커야 하므로 메모리 낭비가 조금 심한 편이다. 또한 검색이 빠르기는 하지만 데이터의 분포 정도에 따라 검색 속도가 운에 좌우되는 경향이 있어 최악의 상황에는 속도가 떨어질 수도 있다.

이진 트리를 사용하는 방법은 메모리의 낭비가 심하지 않고 데이터의 종류에 상관없이 항상 일정한 성능을 보장하므로 훨씬 더 안정적이다.
표준 STL은 이진 트리에 정렬하는 방식으로 구현된 연관 컨테이너만 제공한다. 해쉬 연관 컨테이너는 비록 표준은 아니지만 확장 라이브러리의 형태로 제공되는 것들이 많아 원한다면 언제든지 구해서 사용할 수 있다.

저장 대상	키	키 + 값
중복 불허	셋	맵
중복 허용	멀티셋	멀티맵

연관 컨테이너의 반복자는 모두 양방향 반복자이이다. 자료들이 항상 정렬된 상태를 유지하므로 다시 정렬할 필요가 없으며 검색이 워낙 빠르기 때문에 이분 검색을 할 필요도 없다. 언제든지 순서대로 순회하면 정렬된 결과를 얻을 수 있고 검색은 원래부터 초고속이므로 굳이 임의 접근 반복자가 필요하지도 않다.

연관 컨테이너들이 키와 값의 쌍을 표현하기 위해 사용하는 pair 구조체에 대해 알아보자
둘 이상의 값을 묶어서 관리하거나 리턴할 일이 많기 때문에 pair 구조체를 종종 사용한다.
실제 선언 형태는 컴파일러에 따라 달라진다.

template<class T1, class T2> 
struct pair  
{ 
     typedef T1 first_type; 
     typedef T2 second_type; 
     T1 first; 
     T2 second; 
     pair() : first(T1()), second(T2()) {} 
     pair(const T1& v1, const T2& v2) : first(v1), second(v2) {} 
}; 

알다시피 함수는 한 번에 하나의 값만 리턴할 수 있으며 굳이 두 개의 값을 리턴하고 싶다면 참조 호출을 쓸 수 있지만 번거롭다. 두 값의 쌍을 포함하는 구조체를 정의하면 이 구조체를 리턴함으로써 포함된 값 두 개를 리턴하는 것과 같다. 구조체는 값으로 복사, 대입되므로 함수의 리턴 타입으로 사용할 수 있다.

pair 구조체를 사용하려면 utility 헤더 파일을 포함해야 하는데 STL의 다른 헤더 파일을 인클루드하면 utility 헤더 파일도 자동으로 인클루드된다.

template<class Key, class BinPred = less<Key>, class A = allocator<Key> > 
class set { ... } 

비교 객체와 할당기는 대개의 경우 생략하므로 셋 타입을 만들기 위해 꼭 필요한 것은 키의 타입밖에 없는 셈이다. set<int>는 정수형의 집합이며 set<Time>은 Time 객체의 집합이다. 연관 컨테이너도 시퀀스와 마찬가지로 내부에서 사용하는 타입을 정의하는데 value_type, iterator, const_iterator, reference 등의 같은 이름을 사용한다. 이 외에 다음 세 개의 타입을 추가로 정의한다.

타입	설명
key_type	키의 타입이다. 셋은 키가 곧 값이므로 value_type과 동일하며 맵은 키와 값의 pair 타입으로 정의된다.
key_compare	키를 비교하는 함수 객체 타입이다. 디폴트는 less로 되어 있다.
value_compare	값을 비교하는 함수 객체 타입이다. 셋에서는 key_compare와 동일한 타입으로 정의되며 맵에서는 pair를 비교한다.

explicit set(const BinPred& comp = BinPred()); 
set(const set& x); 
set(InIt first, InIt last, const BinPred& comp = BinPred()); 

pair<iterator, bool> insert(const value_type& val); // 셋의 경우 
iterator insert(const value_type& val); // 멀티셋의 경우 
 
iterator insert(iterator it, const value_type& val);  
void insert((iterator first, iterator last);  

나머지 3번째 4번째 insert함수는 셋과 멀티셋의 원형이 동일하다.
3번째 함수는 하나를 삽입하는데 위치는 크게 관계가 없다. 단지 빠른 삽입을 위한 힌트 역활을 할 뿐이다.
반환값은 셋의 경우 중복되면 실패하는데 이럴경우 이전에 존재하는 val의 반복자를 반환한다.
성공한다면 당연히 삽입된 val에 대한 반복자를 반환한다.

4번째 함수는 셋의 경우 중간에 실패하더라도 건너띄고 다음놈을 삽입한다.
그외의 경우는 상상에 맡긴다-_- 뻔하자나.

iterator erase(iterator it); 
iterator erase(iterator first, iterator last); 
size_type erase(const Key& key); 

전역 find 함수는 셋의 모든 요소를 순회하면서 순차적으로 검색하지만 find 멤버 함수는 정렬되어 있다는 특성을 이용하여 이진 트리 검색을 하므로 훨씬 더 빠르다.

멀티셋의 경우 find 멤버 함수로 찾으면 중간 중간을 쿡쿡 찔러가며 검색하므로 중복된 키 중 어떤 것이 검색될 지 알 수 없는데 이는 이진 검색의 일반적인 특성이다. 반면 find 전역 함수는 처음부터 순서대로 검색하므로 항상 첫 번째 요소가 검색된다. 중복된 키 중 첫 번째 또는 마지막 요소를 찾고 싶으면 lower_bound, upper_bound 함수를 사용해야 하며 둘을 한꺼번에 조사하고 싶으면 equal_range 멤버 함수를 사용한다. equal_range는 처음과 끝 반복자의 쌍을 조사하여 리턴한다.

 
iterator lower_bound(const Key& _Key); 
iterator upper_bound(const Key& _Key); 
pair <iterator, iterator> equal_range (const Key& _Key); 

함수 객체를 사용할 수도 있는데 처음 생성시 두번째 템플릿 인수로 넣어주면 된다.

set<Time, greater<Time> > Times; // 이런 형식 

객체의 포인터 집합 셋에 임의의 타입을 요소로 저장할 수 있다고 했으므로 객체의 포인터도 셋에 저장할 수 있다. 포인터는 기본적으로 비교 연산을 제공하므로 셋의 요소가 되기 위한 요건을 만족하기는 하지만 객체의 번지를 기준으로 정렬하는 것은 실용성이 없으며 포인터가 가리키는 곳의 실제 객체를 기준으로 정렬해야 한다. 이때도 사용자가 비교 함수 객체를 직접 제공해야 한다.

■ 동일성(equality) : 두 값이 완전히 같은지 검사한다. 객체의 경우 모든 멤버가 일치해야 동일하며 주로 == 연산자를 사용한다.
■ 동등성(equivalance) : 두 값이 같은 값으로 인정되는지 검사한다. 키에 해당하는 값만 비교하며 < 연산자의 조합으로 정의된다.

동등성은 두 값이 집합의 기준에서 볼 때 같다고 인정된다는 뜻이다. STL에서 두 키 a와 b의 동등성은 다음 조건으로 점검한다.

!(a < b) && !(b < a) 

디폴트인 less일 때의 얘기이고 좀 더 일반적으로 얘기하자면 비교 객체가 Comp일 때 다음 조건을 만족해야 두 키가 동등하다고 한다.

!Comp(a,b) && !Comp(b,a) 

순서를 바꿔가며 비교해 봐도 둘 다 거짓일 때만 동등하다. 셋의 insert 함수는 삽입 위치를 결정하기 위해 동등성의 개념을 사용한다.

멤버함수 find()는 동등성을 비교하지만
전역함수 find()는 동일성을 비교한다. 주의하자.

키 변경 불가 원칙
키는 셋이 요소의 순서를 정하기 위해 사용하는 중요한 값이므로 셋에 이미 들어가 있는 키를 변경해서는 안된다.
만약 키를 꼭 바꾸고 싶다면 어떻게 해야 할까? 이때는 원하는 요소를 일단 삭제하고 키를 변경한 후 다시 삽입하는 방법밖에 없다.

OutIt set_union(InIt1 first1,InIt1 llast1, InIt2 first2, InIt2 last2, OutIt result); 
OutIt set_intersection (InIt1 first1,InIt1 llast1, InIt2 first2, InIt2 last2, OutIt result); 
OutIt set_difference (InIt1 first1,InIt1 llast1, InIt2 first2, InIt2 last2, OutIt result); 
OutIt set_sysmmetric_difference (InIt1 first1,InIt1 llast1, InIt2 first2, InIt2 last2, OutIt result); 
bool includes (InIt1 first1,InIt1 llast1, InIt2 first2, InIt2 last2); 

구해진 합집합은 result 반복자가 지정하는 위치에 차례대로 대입되는데 이 반복자도 출력 기능만 제공하면 되므로 임의의 컨테이너에 결과를 저장할 수 있다. 이때 결과를 대입받을 컨테이너는 예상되는 합집합을 저장할만한 충분한 공간을 확보하고 있어야 한다. 아니면 삽입 반복자를 사용하여 입력되는데로 컨테이너의 공간을 재할당하도록 할 수 있는데 주로 끝에 삽입하는 back_inserter가 사용된다.

template<class Key, class T, class BinPred = less<Key>, class A = allocator<T> > 
class map { ... } 

맵이 정의하는 타입은 셋과 동일하되 key_type과 value_type이 다르게 정의되어 있으며 key_compare와 value_compare도 다른 함수 객체이다. 셋은 키만 있고 키가 값을 겸하는 것으로 취급하므로 value_type이 key_type과 같지만 맵은 이 둘이 각각 따로이므로 다른 타입이다. 맵의 value_type은 키와 값의 pair타입으로 정의되며 value_compare는 키값만으로 비교를 수행하는 함수 객체 타입이다. 맵의 생성자는 셋의 생성자와 완전히 동일하다.

explicit map(const BinPred& comp = BinPred()); 
map(const map& x); 
map(InIt first, InIt last, const BinPred& comp = BinPred()); 

pair<iterator, bool> insert(const value_type& val); 
iterator insert(iterator it, const value_type& val); 
void insert((iterator first, iterator last); 

맵에 삽입되는 요소의 타입인 value_type은 키와 값을 쌍으로 가지는 pair객체여야 한다. 미리 pair 객체를 준비해 놓고 삽입할 수도 있겠지만 보통은 pair의 생성자를 호출하여 임시 pair객체를 만들어 곧바로 맵에게 전달한다. 예를 들어 문자열과 정수의 쌍을 삽입한다면 다음과 같이 한다.

m.insert(pair<string, int>("문자열",1234)); 

삽입되는 요소가 pair라는 것만 빼고 사용 방법은 셋의 insert 함수와 완전히 동일하다.

맵은 insert 함수외에 좀 더 편리한 삽입 방법을 제공하는데 [ ] 연산자와 대입 연산자로도 요소를 삽입할 수 있다.

T& operator[](const Key& k); 

위의 insert()문은 밑이 대입문과 동일한 방법이다.

m["문자열"]=1234; 

iterator erase(iterator it); 
iterator erase(iterator first, iterator last); 
size_type erase(const Key& key); 

 
iterator find(const Key& val); 
const_iterator find(const Key& val) const; 

맵의 키를 수정하는 코드는 컴파일 에러로 처리된다. 맵의 요소 타입이 pair(Key, T)가 아니라 pair(const Key, T)로 되어 있어 키는 무조건 수정 불가능하다. 키는 오로지 정렬 기준으로만 사용되므로 일단 삽입되면 절대로 수정할 수 없다.

template<class T, class Cont=deque<T> > 
class stack { ... } 

스택이 제공하는 타입은 size_type, value_type, container_type 세 가지 밖에 없다. 이중 container_type은 스택이 자료 관리를 위해 사용하는 기본 컨테이너의 타입이며 템플릿 인수 Cont와 같은 타입이다. 생성자는 다음 하나밖에 없다.

explicit stack(const allocator_type& al = allocator_type()); 

인수로 할당기를 받을 수 있지만 디폴트가 지정되어 있으므로 결국 이 생성자는 인수를 취하지 않는 디폴트 생성자라고 할 수 있다.

void push(const T& x); 
void pop(); 
value_type& top(); 
const value_type& top() const; 

시스템 스택을 비롯한 일반적인 스택은 값을 읽는 함수와 버리는 함수가 따로 제공되지 않으며 pop 함수를 호출하면 제일 상단의 값을 제거하면서 리턴하도록 되어 있는데 STL의 스택은 읽는 함수와 제거하는 함수가 분리되어 있다.
만약 pop이 상단 요소를 제거함과 동시에 레퍼런스를 리턴한다고 해 보자. 이렇게 되면 이미 제거되어 버린 요소를 가리키는 무효한 레퍼런스를 리턴하는 셈이므로 논리적으로 모순이다.

상단의 값을 읽고 버리려면 일단 top으로 먼저 읽어서 사용하고 pop으로 빼서 버리는 것은 따로 해야 한다.

push, pop : 앞뒤에서 값을 추가하거나 제거한다.
front, back : 앞뒤의 값을 읽는다.

template<class T, class Cont=deque<T> > 
class queue { ... } 

템플릿 선언은 다음과 같다.

template<class T, class Cont = vector<T>, class BinPred = less<Cont::value_type> > 
class priority_queue { ... } 

① 컨테이너의 요소 하나를 가리키는 기본적인 역할을 한다.
② 가리키는 지점의 요소를 읽고 쓸 수 있다. 내용을 읽는 * 연산자가 정의된다.
③ 증감에 의해 주변 요소로 이동할 수 있다. ++, -- 등의 연산자가 정의된다.
④ 반복자끼리 대입, 비교 가능해야 한다. 대입, 비교 연산자가 정의된다.

반복자에 대해 마지막으로 주의해야 할 점은 STL 알고리즘은 반복자의 유효성을 전혀 점검하지 않으며 항상 유효하다고 가정한다는 점이다. 반복자가 틀린 위치를 가리키고 있을 경우의 결과는 정의되어 있지 않은데 재수 없으면 다운될 수도 있다. STL도 결국 범위를 점검하지 않는 C언어의 한계는 벗어나지 못했는데 그 이유는 물론 성능이다. 반복자를 참조할 때마다 범위를 일일이 점검하다가는 엄청난 희생을 감수해야 한다. 그러나 반복자는 보통 증가, 감소에 의해 구간 내에서만 움직이므로 큰 문제가 되지는 않는다.

예)

InIt find(InIt first, InIt last, const T& val); 
void sort(RanIt first, RanIt last); 

전위형, 후위형의 ++ 연산자를 사용하여 다음 요소로 이동하는 기능도 가지고 있으며 같은 타입의 반복자와 상등 비교도 가능하다.

출력 반복자는 * 연산자를 사용하여 요소의 내용을 변경할 수 있는 반복자이다. 쓰기가 가능하다면 보통 읽기도 가능하지만 읽는 기능은 없어도 상관없다. 쓰기만 가능하면 출력 반복자라고 할 수 있으며 읽기 기능이 필수는 아니다. 다음 요소로 이동하는 ++연산자도 지원해야 한다. 그러나 출력은 입력과는 달리 무조건적이어서 범위 점검을 위한 ==, != 연산자는 필수가 아니다. 즉, 전진하면서 기록 가능하다는 조건만 만족하면 출력 반복자라고 할 수 있다.

반복자 구간끼리 복사하는 copy 알고리즘에 입력, 출력 반복자가 동시에 나타난다. 이 함수의 구현 코드는 다음과 같을 것이다. 물론 실제 코드는 컴파일러마다 다르다.

OutIt copy(InIt first, InIt last, OutIt result) 
{ 
     while (first != last)  
     { 
          *result++=*first++; 
     } 
     return result; 
} 

입력, 출력 반복자의 일종인 입출력 스트림 반복자는 콘솔에 연결된 반복자이다. 통상 표준 입출력 객체인 cin, cout에 대해 사용하지만 임의의 스트림 객체에 대한 반복자로도 사용할 수 있다. i(o)stream_iterator 클래스로 정의되어 있으며 이 반복자를 사용하면 표준 입력(키보드)으로 입력받은 내용을 순회하면서 읽어낼 수 있고 표준 출력(모니터)으로 문자를 출력할 수도 있다. 다음 예제는 리스트의 요소들을 화면으로 출력한다.

#include <iostream> 
#include <list> 
using namespace std; 
  
void main() 
{ 
     int ari[]={1,2,3,4,5}; 
     list<int> li(&ari[0],&ari[5]); 
 
     ostream_iterator<int> oit(cout,","); 
     copy(li.begin(),li.end(),oit); 
} 

#include <iostream> 
#include <vector> 
#include <algorithm> 
using namespace std; 
  
template<typename C>  
void dump(const char *desc, C c) 
{ 
     cout.width(12); 
     cout << left << desc << "==> "; 
     copy(c.begin(),c.end(),ostream_iterator<typename C::value_type>(cout," ")); 
     cout << endl; 
} 
  
void main() 
{ 
     vector<int> vi(16); 
     istream_iterator<int> iit(cin); 
     copy(iit,istream_iterator<int>(),vi.begin()); 
     dump("입력 완료 후",vi); 
} 

입출력 스트림 반복자에는 이 외에도 좀 더 저수준의 i(o)strembuf_iterator 클래스도 있는데 버퍼를 직접 조작하며 문자 단위로 입출력을 수행하므로 성능이 훨씬 더 좋다.

양방향 반복자(Bidirectional Iterator)는 역방향으로도 이동이 가능한 반복자이다. 순방향 이동을 위한 ++ 연산자는 물론이고 역방향의 이동을 위한 -- 연산자도 전위형, 후위형으로 각각 구현되어 있다. 역방향으로 검색한다거나 모든 요소의 순서를 반대로 뒤집을 때는 앞뒤로 자유롭게 이동해야 하므로 역방향 반복자가 필요하다. STL 컨테이너 중 이중 연결 리스트로 구현되어 있는 list가 양방향 반복자를 제공한다. 양방향 반복자는 순방향 반복자의 기능을 포함한다.

임의 위치로 곧장 이동할 수 있다는 것은 반복자에 임의의 정수를 더하는 +n 연산을 제공한다는 뜻이다. 포인터에 +n 연산을 적용하면 n*sizeof(타입) 만큼 즉시 이동하는데 임의 접근 연산자가 바로 이 기능을 제공하며 +n에 의해 현재 위치에서 n만큼 떨어진 요소로 곧장 이동할 수 있다.

복합 대입 연산자 +=, -=도 지원되는데 모두 +n으로부터 파생되는 연산들이다.

일반 반복자가 덮어쓰기 모드로 동작하는데 비해 삽입 반복자는 삽입모드로 동작한다.

삽입되는 위치와 내부 호출되는 함수에 따라 3종류의 삽입반복자로 나뉜다.
1. insert_iterator<Container> : 모든 컨테이너에서 사용가능하고 insert() 멤버함수를 사용해 중간에 삽입한다.
2. front_insert_iterator<Container> : 리스트와 덱에 사용가능하고 벡터는 안된다. push_front() 멤버함수를 사용해 선두에 삽입한다.
3. back_insert_iterator<Container> : 모든 컨테이너에서 사용가능하고 push_back() 멤버함수를 사용해 끝에 추가한다.

다음과 같은 예제에서 인덱스 2번위치에 대입연산은 삽입이 된다.

insert_iterator<vector<int> > insit(vi, vi.begin()+2); 
*insit = 99; 
*insit = 100; 

삽입 반복자 선언하는 문장이 다소 복잡하게 느껴진다면 삽입 반복자를 생성하여 리턴하는 템플릿 함수가 있다.

insert_iterator<Container> inserter(Container&Cont, Iterator it); 
front_insert_iterator<Container> front_inserter(Container& Cont); 
back_insert_iterator<Container> back_inserter(Container& Cont); 

비상수는 항상 상수에 대입할 수 있으므로 설사 비상수 컨테이너의 반복자라 하더라도 상수 반복자에 곧바로 대입할 수 있다. 따라서 다음 대입문은 문법적으로 합당하다.

find 함수는 값을 검색하기 위해 읽기만 하므로 상수 반복자와 함께 사용되어도 아무 문제가 없다. 그러나 sort는 값을 교환하기 위해 반복자에 값을 쓰는데 상수 반복자가 이 기능을 제공하지 않으므로 컴파일 에러로 처리된다. 타입이 불일치하므로 잘못된 동작을 컴파일 중에 즉시 알아낼 수 있다.

reverse_iterator 
const_reverse_iterator 

rbegin ~ rend로 역방향 순회를 하려면 rbegin은 끝요소를 가리키고 rend는 첫 요소보다 하나 더 앞쪽을 가리켜야 한다. 물론 rend위치는 실제로 컨테이너의 내부도 아니며 처리 대상에도 포함되지 않는다.

역방향 반복자에는 원래의 순방향 반복자를 리턴하는 base 멤버 함수가 정의되어 있다. 삽입, 삭제 함수들은 역방향 반복자를 받아들이지 않기 때문에 역방향 검색한 위치에 대고 어떤 작업을 하고 싶을 때는 순방향 반복자로 바꾸어야 한다. 또한 역방향 검색 후에 다시 순방향으로 검색하고 싶을 때 base로 언제든지 순방향 반복자를 구할 수 있다. base로 구한 순방향 반복자는 역방향 반복자보다 항상 하나 더 큰 값을 가진다.

이렇게 되어 있는 이유는 순방향 반복자가 역방향 반복자보다 한칸 더 오른쪽에 있으며 이렇게 해야 rbegin의 base가 end가 되기 때문이다. 다음은 역방향 검색 후 다시 순방향으로 검색한다.

vector<char>::reverse_iterator rit; 
vector<char>::iterator bit,it; 
rit=find(vc.rbegin(),vc.rend(),'t'); 
bit=rit.base(); 
it=find(bit,vc.end(),'a'); 

문자열 끝에서부터 't'를 찾기 위해 역방향 검색을 했으며 't' 이후 최초로 나타나는 a를 찾기 위해 순방향 반복자 bit를 rit.base로 구하여 bit이후부터 검색했다.

출력 반복자
*로 쓰기, ++로 전진 이동

순방향 반복자 : (상속) 입력반복자, 출력 반복자
*로 읽고 쓰기
++로 전진 이동

양방향 반복자 : (상속) 양방향 반복자
--로 후진 이동

임의접근 반복자 : (상속) 양방향 반복자
+n, [], +=, -=
반복자끼리 뺄셈 : -
반복자끼리 비교 : <, >

함수	설명
count	조건에 맞는 요소의 개수를 센다.
for_each	각 요소에 대해 지정한 작업을 한다.
equal	구간이 일치하는지 비교한다.
search	일치하는 부분 구간을 검색한다.
copy	구간끼리 복사한다.
fill	일정한 값으로 지정 구간을 채운다.
reverse	구간의 요소들을 반대로 뒤집는다.
random_shuffle	요소들을 무작위로 섞는다.
swap	컨테이너를 교환한다.
binary_search	이분 검색한다.
merge	구간을 병합하여 새로운 구간으로 복사한다.
accumulate	구간의 값을 모두 합한다.

함수객체는 함수 호출 연산자인 ()을 오버로딩한 객체를 의미하는데 이 연산자를 통해 마치 함수를 호출하듯이 객체를 호출할 수 있다.

함수 포인터에 비해 함수객체가 가지는 장점
① 함수객체는 인라이닝되어 클래스 내부의 멤버함수는 호출부의 코드가 실제 생성될때 인라인으로 확장된다. 함수포인터는 번지의 주소값을 가지는 변수이므로 인라인화 될 수 없다.

② 함수객체는 그 자체로 객체이므로 멤버함수 뿐 아리나 멤버변수, 생성자, 소멸자를 통해 추가적인 운용이 가능하다.
멤버들을 순회하며 값을 더하는 방법을 만든다면,

struct accum  
{ 
 int sum; 
 accum() { sum=0;} 
 void operator() (int a) 
 { 
  sum+=a; 
 } 
}; 
... 
 
accum f 
f = for_each(vi.begin(), vi.end(), f); 
cout << "총합 : " << f.sum << endl; 

③ 함수객체는 타입이므로 템플릿의 인수로도 사용될 수 있다.

InIt find_if(InIt first, InIt last, UniPred F); 

함수 객체로 만들 때와 함수 포인터를 쓸 때 인수의 형태가 조금 달라진다. 함수 포인터는 레퍼런스를 전달받는 것이 좋은데 왜냐하면 string같이 덩치가 큰 객체를 전달할 때 값으로 받으면 복사가 발생하며 이 비용이 무시할 수 없을 정도로 커질 수 있기 때문이다. int같은 단순 타입이라면 물론 값으로 전달하나 레퍼런스로 전달하나 전혀 차이가 없지만 말이다. 반면 함수 객체는 크기에 상관없이 값으로 전달받아야 하는데 왜냐하면 인라인으로 삽입되기 때문에 인수 전달 과정이 필요없기 때문이다.

find와 find_if 함수의 이름에 대해 고찰해 보자. 고정 값으로 검색하건 함수 객체를 쓰건 논리적으로 검색이라는 같은 연산을 하므로 두 함수의 이름을 통합하면 좋을 것 같은데 이름이 달라 불편하다. 이렇게 된 원인은 두 함수의 선언문이 사실상 동일하기 때문이다. 두 함수의 원형을 보자.

InIt find(InIt first, InIt last, const T& val); 
InIt find_if(InIt first, InIt last, UniPred F); 

더하기에 대한 함수 객체의 예이다.

struct plus : public binary_function<T, T, T>  
{ 
     T operator()(const T& x, const T& y) const { return (x+y); } 
}; 

함수 객체	연산
minus	두 인수의 차를 계산한다.
multiplies	두 인수의 곱을 계산한다.
divides	두 인수를 나눈 후 몫을 리턴한다.
modulus	두 인수를 나눈 후 나머지를 리턴한다.
negate	인수 하나를 전달받아 부호를 반대로 만든다.
equal_to	두 인수가 같은지 비교하여 결과를 bool타입으로 리턴한다.
not_equal_to	두 인수가 다른지 비교한다.
greater	첫 번째 인수가 두 번째 인수보다 큰지 조사한다.
less	첫 번째 인수가 두 번째 인수보다 작은지 조사한다.
greater_equal	첫 번째 인수가 두 번째 인수보다 크거나 같은지 조사한다.
less_equal	첫 번째 인수가 두 번째 인수보다 작거나 같은지 조사한다.
logical_and	두 인수의 논리곱(&&) 결과를 리턴한다.
logical_or	두 인수의 논리합(	) 결과를 리턴한다.
logical_not	인수 하나를 전달받아 논리부정(!)을 리턴한다.

여기서는 함수객체 어댑터만 다루기로 한다.

(똑같은 말 다시 말하자면...)
함수 객체의 기능을 조금이라도 변경하려면 어댑터를 적용할 수 있도록 만들어야 하는데 이런 함수 객체를 어댑터블(Adaptable) 함수 객체라고 한다. 기능을 변경하는 어댑터는 대상 함수 객체가 취하는 인수의 타입은 무엇인지, 리턴 타입은 무엇인지 등 함수 객체에 대한 충분한 정보를 얻을 수 있어야 한다. 만드는 방법은 아주 쉬운데 functional 헤더 파일에 정의되어 있는 다음 두 템플릿 클래스 중 하나를 상속받으면 된다.

template<class Arg, class Result> 
struct unary_function  
{ 
     typedef Arg argument_type; 
     typedef Result result_type; 
}; 
 
template<class Arg1, class Arg2, class Result> 
struct binary_function  
{ 
     typedef Arg1 first_argument_type; 
     typedef Arg2 second_argument_type; 
     typedef Result result_type; 
}; 

• 클래스는 주로 멤버 변수나 멤버 함수들로 구성되지만 타입이나 상수, 내부 클래스, 가상 함수 테이블 등의 다른 여러 가지 것들도 같이 캡슐화된다는 것을 잊지 말자.
  

어차피 이 클래스들은 크기가 0이므로 상속을 받는다 하여 용량상의 불이익이 발생하는 것도 아니다. 그래서 어댑터를 적용할 계획이든 아니든 함수 객체 클래스를 정의할 때는 일단 상속을 받는 것이 좋다. plus, greater 등의 미리 제공되는 함수 객체들은 모두 이 클래스들로부터 상속받으므로 어댑터를 항상 적용할 수 있다.

사용예

#include <functional> 
 
struct print : public unary_function<int,void>  
{ 
     void operator()(int a) const  
     {  
          printf("%d\n",a);  
     } 
}; 

struct IsMulti : public binary_function<int,int, bool>  
{ 
     bool operator()(int a,int b) const  
     { 
          return (a % b == 0); 
     } 
}; 

template<class Result, class T> 
mem_fun_t<Result, T> mem_fun(Result (T::*Pm)()) 
{ 
     return (mem_fun_t<Result, T>(Pm)); 
} 

template<class Result,class T> 
class mem_fun_t : public unary_function<T *, Result> 
{ 
public: 
     explicit mem_fun_t(Result (T::*Pm)()) : Pmemfun(Pm) {} 
     Result operator()(T *pObj) const  
     { 
          return ((pObj->*Pmemfun)()); 
     } 
 
private: 
     Result (T::*Pmemfun)(); 
}; 

만약 컨테이너가 객체의 포인터가 아니라 객체 그 자체를 저장하고 있다면 이때는 mem_fun_ref를 사용한다. 위 예제를 다음과 같이 변형해도 동일하게 동작한다. 객체의 포인터를 동적으로 생성한 것이 아니므로 delete는 할 필요없다.

template <class Type, class Allocator = allocator<Type> > class vector 

예를 들어 malloc/free를 사용할 수도 있고 COM 인터페이스를 쓸 수도 있고 운영체제의 가상 메모리를 직접 다룰 수도 있다. 할당기를 직접 만들어 쓰는 가장 실용적인 예는 할당, 해제가 아주 빈번하며 필요량이 많을 때 메모리를 미리 왕창 할당하여 메모리 풀을 만들어 놓고 이 메모리를 내부에서 관리하며 번갈아 쓰도록 할 때이다. 운영체제의 간섭에서 벗어나 메모리에 대한 완전한 통제권을 행사하고 싶을 때 이런 방법이 동원된다.

할당기라는 것이 과거 16비트 시절 세그먼트/오프셋 같은 복잡한 메모리 구조를 추상화하기 위한 목적으로 만들어진 것이라 지금은 사용자가 정의할 이유가 딱히 없는 셈이다.

설사 만들어 보고 싶다고 하더라도 기존의 STL 컴포넌트와 완벽하게 잘 조화되는 할당기를 만드는 것이 그다지 간단하지 않음을 직감적으로 느낄 수 있을 것이다. 특별한 이유가 없는 한 디폴트만 사용해도 충분하다. 여기서는 할당기도 STL의 구성 요소중 하나이고 꼭 원할 경우 교체 가능하다는 정도만 상식적으로 알아 두자.