1. Chapter 8 Writing generic functions ¶

Generic_function : 함수를 호출하기 전까지는 그 함수의 매개변수 타입이 무엇인지 알 수 없는 함수.
Ch9~Ch12 Abstract_data_type (이하 ADT)의 구현을 공부한다.
참고페이지) ParametricPolymorphism

Generic_function : 함수의 호출시 인자 타입이나 리턴타입을 사용자가 알 수없다. ex)find(B,E,D)
함수의 호출시 함수의 매개변수를 operand로 하여 행해지는 operator의 유효성을 컴파일러가 조사. 사용 가능성을 판단

~cpp  ex) union(A, B) { return A+B; }
  union(A:string, " is...") (O), concaternate("COL", " is...") (X)

그렇다면 어떻게 함수가 어떠한 자료구조를 만족 시키는지 판단할 수 있는가?
반복자를 생각해보자. 만약 특정 자료구조가 반복자를 리턴하는 멤버함수를 갖는 다면 반복자를 인자로 받는 function들에 대해서 그 자료구조는 유효하다고 판단할 수 있다.

실제 제네릭 함수의 사용에서 가장 문제시 되는 것은 함수내부의 연산을 매개변수 타입이 지원을 하는 가이다.

find(B, E, D)	D의 인자료 [B, E)를 비교하여 값을 찾는다. 비교를 하는 것은 크게 문제되지 않는다.
accumulate(B, E, D)	D의 인자의 형을 기준으로 [B, E)를 비교하여 값을 모은다. 리턴값이 D의 자료형에 영향을 받기 때문에 문제의 발생소지가 존재한다.

~cpp ex) accumulate(v.begin(), v.end(), 0.0); // 만약 0:int를 사용했다면 올바른 동작을 보장할 수 없다.
max 함수의 구현

~cpp 
template <class T>
T max(const T& left, const T& right)
{	
	return left > right ? left : right;
}
 

인자로 받은 두 값의 타입이 완전히 같아야지만 올바른 동작을 보장받는다. 인자는 operator>(T, T)를 지원해야한다.

• 1의 방식으로 작성된 함수으이 rbegin() 같은 템플릿 멤버 함수를 이용해서 역순 검색도 가능하게 작성된다.
  

STL 함수를 보면 인자로 받는 반복자(iterator)에 따라서 컨테이너의 함수 사용 유효성을 알 수 있다.
예를 들자면 find(B, E, D)같은 함수의 경우 아주 단순한 제한적 연산만을 이용하기 때문에 대부분의 컨테이너에 대해서 사용이 가능하다. 그러나 sort(B, E)같은 경우에는 기본적인 사칙연산들을 반복자에 대해서 사용하기 때문에 이런 연산을 지원하는 string, vector 만이 완벽하게 지원된다.
STL은 이런 분류를 위해서 5개의 반복자 카테고리(iterator category)를 정의하여 반복자를 분류한다. 카테고리의 분류는 반복자의 요소를 접근하는 방법에따른 분류이며, 이는 알고리즘의 사용 유효성 여부를 결정하는데 도움이 된다.

※ 모든 순차반복자에서는 -- 연산을 할 수 없다.
find 구현 1

~cpp template <class In, class X> In find(In begin, In end, const X& x) {
	while(begin != end && *begin != x)
		++begin:
	return begin;
}
 

find 구현 2

~cpp 
template <class In, class X> In find(In begin, In end, const X& x) {
	if (begin == end || *begin == x)
		return begin;
	begin++;
	return find(begin, end, x);
}
 

상기 2개의 구현 모두 begin, end iterator를 순차적으로 접근하고 있음을 알 수 있다. 상기의 함수를 통해서 순차 읽기-전용의 반복자는 ++(전,후위), ==, !=, *를 지원해야한다는 것을 알 수 있다. 덧 붙여서 ->, .와 같은 멤버 참조 연산자도 필요로하다. (7.2절에 사용했떤 연산자이다.)
상기와 같은 반복자를 입력 반복자(input iterator)라고 함.

copy 구현

~cpp 
template <class In, class Out> Out copy(In begin, In end, Out dest) {
	if (begin != end)
		*dest++ = *begin++;
	return dest;
}
 

class In 형의 반복자는 함수가 진행되는 동안 반복자를 통해서 읽기 연산만을 수행한다. class Out 형의 반복자는 *dest++ = *begin++; 의 연산을 통해서 쓰기 연산을 수행한다. 따라서 class Out 반복자는 ++(전,후위). = 연산자만을 평가할수 있으면 된다.
class Out 반복자를 출력에 배타적으로 사용하려면 ++ 연산이 대입문 사이에서 1번이상은 무효가 되도록 만들어 주어야한다.
상기 요구사항을 만족시키는 경우의 반복자를 출력 반복자(Output iterator)라고 함.
모든 컨테이너는 back_inserter(class T)를 통해서 출력 반복자를 리턴시킬 수 있다. 이 반복자는 write-once의 특성을 가진다.

replace 구현

~cpp 
template <class For, class X> void replace(For begin, For end, const X& x, const X& y) {
	while (beg != end) {
		if (*beg == x)
			*beg = y;
		++beg;
	}
}
 

[begin, end) 의 범위안에서 x를 찾아서 y로 치환한다.
여기서 beg는 입력 반복자, 출력 반복자 2가지의 특성을 모두 만족시켜야 한다.
*, ++(전,후위), ==, =, ., ->와 같은 연산이 가능하다면 순방향 반복자(forward iterator)라고 함.

reverse 구현

~cpp 
template <class Bi> void reverse(Bi begin, Bi end) {
	while (begin != end) {
		--end;

		if (begin != end)
			swap(*begin++, *end);
	}
}
 

begin 과 end 의 요소를 비교하여 다르다면 swap()시킨다.
순방향 연산자의 모든 연산을 지원하고 --연산을 지원한다면 이 반복자는 양방향 반복자(bidirection iterator) 라고 부른다. 표준 라이브러리 컨테이너 클래스들은 모두 양방향 반복자를 지원함.

binary search 구현

~cpp 
template <class Ran, class X> bool binary_search(Ran begin, Ran end, const X& x) {
	while (begin < end) {
		Ran mid = begin + (end - begin ) /2;
		if (x < *mid)
			end = mid;
		else if (*mid < x)
			begin = mid + 1;
		else return true;
	}
	return false;
}
 

참고자료) Binary_search바이너리 서치
임의 접근 반복자의 경우 양방향 반복자의 모든 특성과 함께 다음과 같은 연산을 만족한다.

condition p:iterator, q:iterator, n:integer

p+n, p-n, n+p, p+q, pn, p<q, p>q, p<=q, p>q

임의 접근 반복자르 이용하는 알고리즘은 sort. vector, string 만이 임의 접근 반복자를 지원한다. list는 빠른 데이터의 삽입, 삭제에 최적화 되었기 때문에 순차적인 접근만 가능함.

반복자의 끝값으로 컨테이너의 마지막 요소에서 한개가 지난 값을 사용하는 이유

마지막 요소를 범위의 끝으로 사용함으로써 발생하는 특별한 처리를 없애는 것이 가능. (실수가 줄어듬)

마지막 요소를 범위의 끝으로 정할 경우 범위안에 찾는 것이 없을때 이를 알려주는 수단이 부재하다.

단순히 != 연산으로 범위의 순회를 마치는 조건으로 이용이 가능하다. <>와 같은 크기 연산자가 불필요하다.

두번째 인자로 하나가 지난 값을 갖도록함으로써 자연스럽게 out-of-range의 상황을 파악하는 것이 가능하다.

~cpp 
 c.end() == c.begin() + c.size()    // this is true
 

입출력 반복자는 컨테이너의 반복자이외의 존재하는 반복자를 표현하기 때문에 순방향 반복자와 구별시킴.
istream, ostream 의 반복자를 얻음으로써 입출력 스트림을 제어하는 것이 가능하다.

~cpp 
vector<int> v;
copy(istream_iterator<int>(cin), istream_iterator<int>(), back_inserter(v));
//istream_iterator<int> 는 end-of-file, 에러상태를 가리킨다.

C++의 모든 입출력 연산은 타입 지정연산이다. cin>>s.midterm>>s.final>>s.homework; 에서도 타입에 따라서 다른 일을 한다.

~cpp 
#include <algorithm>
#include <cctype>
#include <string>

using std::find_if;
using std::string;

using std::isspace;

inline bool space(char c)
{
        return isspace(c);
}

inline bool not_space(char c)
{
        return !isspace(c);
}

template <class Out>                             // changed
void split(const string& str, Out os) {          // changed

	typedef string::const_iterator iter;

	iter i = str.begin();
	while (i != str.end()) {
		// ignore leading blanks
		i = find_if(i, str.end(), not_space);

		// find end of next word
		iter j = find_if(i, str.end(), space);

		// copy the characters in `[i,' `j)'
		if (i != str.end())
			*os++ = string(i, j);   // changed

		i = j;
	}
}

Class Out 가 순방향, 임의접근, 출력 반복자의 요구사항을 모두 반족하기 때문에 istream_iterator만 아니라면 어떤 반복자에도 쓰일 수 있다. 즉, 특정변수로의 저장 뿐만아니라 console, file 로의 ostream 으로의 출력도 지원한다. 흠 대단하군..
----
AcceleratedC++