Maintenance script: Repair batch-0001 pages from live compare

2026-03-26T23:56:00Z

Repair batch-0001 pages from live compare

← Older revision		Revision as of 23:56, 26 March 2026
Line 49:		Line 49:
	vec_sz mid = size/2;		vec_sz mid = size/2;

	return size % 2 == 0 ? (v[mid] + v[mid-1]) / 2 : v[mid]; // double, int에는 유효, string은 operator / 가 없기 때문에 무효		return size % 2 == 0 ? (v[mid] + v[mid-1]) / 2 : v[mid]; // double, int에는 유효, string은 operator / 가 없기 때문에 무효
	}		}
	#endif		#endif
Line 71:		Line 71:
	\| D의 인자의 형을 기준으로 [B, E)를 비교하여 값을 모은다. 리턴값이 D의 자료형에 영향을 받기 때문에 문제의 발생소지가 존재한다.		\| D의 인자의 형을 기준으로 [B, E)를 비교하여 값을 모은다. 리턴값이 D의 자료형에 영향을 받기 때문에 문제의 발생소지가 존재한다.
	\|}		\|}
	~~~cpp~~ ex) accumulate(v.begin(), v.end(), 0.0); // 만약 0:int를 사용했다면 올바른 동작을 보장할 수 없다.		<code>ex) accumulate(v.begin(), v.end(), 0.0); // 만약 0:int를 사용했다면 올바른 동작을 보장할 수 없다.</code>

	'''max 함수의 구현'''		'''max 함수의 구현'''
Line 240:		Line 240:
	iter j = find_if(i, str.end(), space);		iter j = find_if(i, str.end(), space);

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

imported>Unknown at 05:22, 7 February 2021

2021-02-07T05:22:25Z

New page

{| class="wikitable"
|-
| [[AcceleratedC++/Chapter7]]
| [[AcceleratedC++/Chapter9]]
|}

{| class="wikitable"
|-
| __TOC__
|}

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

== 8.1 What is a generic function? ==
WikiPedia:Generic_function : 함수의 호출시 인자 타입이나 리턴타입을 사용자가 알 수없다. ex)find(B,E,D)
함수의 호출시 함수의 매개변수를 operand로 하여 행해지는 operator의 유효성을 컴파일러가 조사. 사용 가능성을 판단
union(A:string, " is...") (O), concaternate("COL", " is...") (X)
그렇다면 어떻게 함수가 어떠한 자료구조를 만족 시키는지 판단할 수 있는가?
반복자를 생각해보자. 만약 특정 자료구조가 반복자를 리턴하는 멤버함수를 갖는 다면 반복자를 인자로 받는 function들에 대해서 그 자료구조는 유효하다고 판단할 수 있다.
=== 8.1.1 알려지지 않은 타입의 중앙 값 ===
'''template'''
서로 다른 타입의 객체이라도 하더라도 각각의 객체를 가지고 행하는 행동양식은 공통의 행동양식을 갖는다.
Runtime이 아니라 Compile 타임에 실제로 타입이 변화하는 객체를 적절히 작성하면 올바른 동작을 보장한다.
//median.h
#ifndef GUARD_median_h
#define GUARD_median_h

#include <algorithm>
#include <stdexcept>
#include <vector>

using std::domain_error;
using std::sort;
using std::vector;
template <class T> // type 매개변수의 지정, 이 함수의 scope안에서는 데이터 형을 대신한다.
T median(vector<T> v)
{
typedef typename vector<T>::size_type vec_sz; // typename에 대해서 알자

vec_sz size = v.size();
if (size == 0)
throw domain_error("median of an empty vector");

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

vec_sz mid = size/2;

return size % 2 == 0 ? (v[mid] + v[mid-1]) / 2 : v[mid]; // double, int에는 유효, string은 operator / 가 없기 때문에 무효
}
#endif

실제 컴파일시 컴파일러는 프로그래머가 지정한 타입으로 이 함수를 인스턴스화 시켜서 생성하고 바인딩한다.
typename 은 아직 인스턴스화 되지 않은 함수를 컴파일러가 읽어들일때 타입 매개변수와 관계된 타입의 형을 생성할때 앞에 붙여야 하는 키워드 임. ex) vector<T> or vector<T>::size_type

=== 8.1.2 템플릿 인스턴스화 ===
STL은 실제로 함수의 인스턴스화에 관한 표준적인 방식을 제정하지 않았다. 따라서 각 컴파일러마다 서로 다른 방식으로 함수를 인스턴스화한다. 따라서 자신의 컴파일러의 특징을 파악하는 노력이 필요.
* 컴파일 링크 모델 Compiler : 실제로 인스턴스가 만들어지기 전까지는 템플릿 코드의 유효성을 알 수 없다. 에러는 링크시에 발생
* 독자적 방식의 template 모델 Compiler : 최근의 방식. 인스턴스화를 위해서 STL 정의부에 대한 접근이 필요.

=== 8.1.3 제네릭 함수와 타입 ===
실제 제네릭 함수의 사용에서 가장 문제시 되는 것은 함수내부의 연산을 매개변수 타입이 지원을 하는 가이다.
{| class="wikitable"
|-
| 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 함수의 구현'''
template <class T>
T max(const T& left, const T& right)
{
return left > right ? left : right;
}

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

== 8.2 Data-structure independence ==
{| class="wikitable"
|-
| find(c.begin(), c.end(), val)
| 일반적인 함수의 작성 가능. 반복자를 통해서 반복자가 제공하는 방식으로 동작가능
|-
| c.find(val)
| 특정형의 인스턴스인 c를 통해서만 접근가능. 내장배열에 적용 불가능
|-
| find(c, val)
| 범위 지정이 불가능하고, 유용성이 첫번째의 경우보다 적다.
|}
* 1의 방식으로 작성된 함수으이 rbegin() 같은 템플릿 멤버 함수를 이용해서 역순 검색도 가능하게 작성된다.

=== 8.2.1 알고리즘과 반복자 ===
STL 함수를 보면 인자로 받는 반복자(iterator)에 따라서 컨테이너의 함수 사용 유효성을 알 수 있다.
예를 들자면 find(B, E, D)같은 함수의 경우 ''아주 단순한 제한적 연산만을 이용''하기 때문에 대부분의 컨테이너에 대해서 사용이 가능하다. 그러나 sort(B, E)같은 경우에는 ''기본적인 사칙연산들을 반복자에 대해서 사용''하기 때문에 이런 연산을 지원하는 string, vector 만이 완벽하게 지원된다.

STL은 이런 분류를 위해서 5개의 '''반복자 카테고리(iterator category)'''를 정의하여 반복자를 분류한다. 카테고리의 분류는 반복자의 요소를 접근하는 방법에따른 분류이며, 이는 알고리즘의 사용 유효성 여부를 결정하는데 도움이 된다.

=== 8.2.2 순차적 읽기-전용 접근 ===
'''''※ 모든 순차반복자에서는 -- 연산을 할 수 없다.'''''

'''find 구현 1'''
while(begin != end && *begin != x)
++begin:
return begin;
}

'''find 구현 2'''
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)'''''라고 함.

=== 8.2.3 순차적 쓰기-전용 접근 ===
'''copy 구현'''
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의 특성을 가진다.

=== 8.2.4 순차적 읽기-쓰기 접근 ===
'''replace 구현'''
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)'''''라고 함.

=== 8.2.5 역방향 접근 ===
'''reverse 구현'''
template <class Bi> void reverse(Bi begin, Bi end) {
while (begin != end) {
--end;

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

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

=== 8.2.6 임의 접근 ===
'''binary search 구현'''
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;
}

참고자료) WikiPedia:Binary_search 바이너리 서치
임의 접근 반복자의 경우 '''양방향 반복자의 모든 특성'''과 함께 다음과 같은 연산을 만족한다.
{| class="wikitable"
|-
| condition p:iterator, q:iterator, n:integer
|-
| p+n, p-n, n+p, p+q, p[n], p<q, p>q, p<=q, p>q
|}

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

=== 8.2.7 반복자 범위 및 끝 지난 값 ===
반복자의 끝값으로 컨테이너의 마지막 요소에서 한개가 지난 값을 사용하는 이유
* 마지막 요소를 범위의 끝으로 사용함으로써 발생하는 특별한 처리를 없애는 것이 가능. (실수가 줄어듬)
* 마지막 요소를 범위의 끝으로 정할 경우 범위안에 찾는 것이 없을때 이를 알려주는 수단이 부재하다.
* 단순히 != 연산으로 범위의 순회를 마치는 조건으로 이용이 가능하다. <>와 같은 크기 연산자가 불필요하다.
* 두번째 인자로 하나가 지난 값을 갖도록함으로써 자연스럽게 out-of-range의 상황을 파악하는 것이 가능하다.
c.end() == c.begin() + c.size() // this is true

== 8.3 Input and output iterators ==
입출력 반복자는 컨테이너의 반복자이외의 존재하는 반복자를 표현하기 때문에 순방향 반복자와 구별시킴.
istream, ostream 의 반복자를 얻음으로써 입출력 스트림을 제어하는 것이 가능하다.
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; 에서도 타입에 따라서 다른 일을 한다.

== 8.4 Using iterators for flexibility ==
#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++]]

AcceleratedC++/Chapter8 - Revision history

Maintenance script: Repair batch-0001 pages from live compare

imported>Unknown at 05:22, 7 February 2021