U E D R , A S I H C RSS

AcceleratedC++/Chapter8

1. Chapter 8 Writing generic functions

WikiPedia:Generic_function : ํ•จ์ˆ˜๋ฅผ ํ˜ธ์ถœํ•˜๊ธฐ ์ „๊นŒ์ง€๋Š” ๊ทธ ํ•จ์ˆ˜์˜ ๋งค๊ฐœ๋ณ€์ˆ˜ ํƒ€์ž…์ด ๋ฌด์—‡์ธ์ง€ ์•Œ ์ˆ˜ ์—†๋Š” ํ•จ์ˆ˜.
Ch9~Ch12 WikiPedia:Abstract_data_type (์ดํ•˜ ADT)์˜ ๊ตฌํ˜„์„ ๊ณต๋ถ€ํ•œ๋‹ค.
์ฐธ๊ณ ํŽ˜์ด์ง€) ParametricPolymorphism

1.1. 8.1 What is a generic function?

WikiPedia: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๋“ค์— ๋Œ€ํ•ด์„œ ๊ทธ ์ž๋ฃŒ๊ตฌ์กฐ๋Š” ์œ ํšจํ•˜๋‹ค๊ณ  ํŒ๋‹จํ•  ์ˆ˜ ์žˆ๋‹ค.

1.1.1. 8.1.1 ์•Œ๋ ค์ง€์ง€ ์•Š์€ ํƒ€์ž…์˜ ์ค‘์•™ ๊ฐ’

template
์„œ๋กœ ๋‹ค๋ฅธ ํƒ€์ž…์˜ ๊ฐ์ฒด์ด๋ผ๋„ ํ•˜๋”๋ผ๋„ ๊ฐ๊ฐ์˜ ๊ฐ์ฒด๋ฅผ ๊ฐ€์ง€๊ณ  ํ–‰ํ•˜๋Š” ํ–‰๋™์–‘์‹์€ ๊ณตํ†ต์˜ ํ–‰๋™์–‘์‹์„ ๊ฐ–๋Š”๋‹ค.
Runtime์ด ์•„๋‹ˆ๋ผ Compile ํƒ€์ž„์— ์‹ค์ œ๋กœ ํƒ€์ž…์ด ๋ณ€ํ™”ํ•˜๋Š” ๊ฐ์ฒด๋ฅผ ์ ์ ˆํžˆ ์ž‘์„ฑํ•˜๋ฉด ์˜ฌ๋ฐ”๋ฅธ ๋™์ž‘์„ ๋ณด์žฅํ•œ๋‹ค.

~cpp 
//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

1.1.2. 8.1.2 ํ…œํ”Œ๋ฆฟ ์ธ์Šคํ„ด์Šคํ™”

STL์€ ์‹ค์ œ๋กœ ํ•จ์ˆ˜์˜ ์ธ์Šคํ„ด์Šคํ™”์— ๊ด€ํ•œ ํ‘œ์ค€์ ์ธ ๋ฐฉ์‹์„ ์ œ์ •ํ•˜์ง€ ์•Š์•˜๋‹ค. ๋”ฐ๋ผ์„œ ๊ฐ ์ปดํŒŒ์ผ๋Ÿฌ๋งˆ๋‹ค ์„œ๋กœ ๋‹ค๋ฅธ ๋ฐฉ์‹์œผ๋กœ ํ•จ์ˆ˜๋ฅผ ์ธ์Šคํ„ด์Šคํ™”ํ•œ๋‹ค. ๋”ฐ๋ผ์„œ ์ž์‹ ์˜ ์ปดํŒŒ์ผ๋Ÿฌ์˜ ํŠน์ง•์„ ํŒŒ์•…ํ•˜๋Š” ๋…ธ๋ ฅ์ด ํ•„์š”.
  • ์ปดํŒŒ์ผ ๋งํฌ ๋ชจ๋ธ Compiler : ์‹ค์ œ๋กœ ์ธ์Šคํ„ด์Šค๊ฐ€ ๋งŒ๋“ค์–ด์ง€๊ธฐ ์ „๊นŒ์ง€๋Š” ํ…œํ”Œ๋ฆฟ ์ฝ”๋“œ์˜ ์œ ํšจ์„ฑ์„ ์•Œ ์ˆ˜ ์—†๋‹ค. ์—๋Ÿฌ๋Š” ๋งํฌ์‹œ์— ๋ฐœ์ƒ
  • ๋…์ž์  ๋ฐฉ์‹์˜ template ๋ชจ๋ธ Compiler : ์ตœ๊ทผ์˜ ๋ฐฉ์‹. ์ธ์Šคํ„ด์Šคํ™”๋ฅผ ์œ„ํ•ด์„œ STL ์ •์˜๋ถ€์— ๋Œ€ํ•œ ์ ‘๊ทผ์ด ํ•„์š”.

1.1.3. 8.1.3 ์ œ๋„ค๋ฆญ ํ•จ์ˆ˜์™€ ํƒ€์ž…

์‹ค์ œ ์ œ๋„ค๋ฆญ ํ•จ์ˆ˜์˜ ์‚ฌ์šฉ์—์„œ ๊ฐ€์žฅ ๋ฌธ์ œ์‹œ ๋˜๋Š” ๊ฒƒ์€ ํ•จ์ˆ˜๋‚ด๋ถ€์˜ ์—ฐ์‚ฐ์„ ๋งค๊ฐœ๋ณ€์ˆ˜ ํƒ€์ž…์ด ์ง€์›์„ ํ•˜๋Š” ๊ฐ€์ด๋‹ค.
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.2. 8.2 Data-structure independence

find(c.begin(), c.end(), val) ์ผ๋ฐ˜์ ์ธ ํ•จ์ˆ˜์˜ ์ž‘์„ฑ ๊ฐ€๋Šฅ. ๋ฐ˜๋ณต์ž๋ฅผ ํ†ตํ•ด์„œ ๋ฐ˜๋ณต์ž๊ฐ€ ์ œ๊ณตํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ๋™์ž‘๊ฐ€๋Šฅ
c.find(val) ํŠน์ •ํ˜•์˜ ์ธ์Šคํ„ด์Šค์ธ c๋ฅผ ํ†ตํ•ด์„œ๋งŒ ์ ‘๊ทผ๊ฐ€๋Šฅ. ๋‚ด์žฅ๋ฐฐ์—ด์— ์ ์šฉ ๋ถˆ๊ฐ€๋Šฅ
find(c, val) ๋ฒ”์œ„ ์ง€์ •์ด ๋ถˆ๊ฐ€๋Šฅํ•˜๊ณ , ์œ ์šฉ์„ฑ์ด ์ฒซ๋ฒˆ์งธ์˜ ๊ฒฝ์šฐ๋ณด๋‹ค ์ ๋‹ค.
  • 1์˜ ๋ฐฉ์‹์œผ๋กœ ์ž‘์„ฑ๋œ ํ•จ์ˆ˜์œผ์ด rbegin() ๊ฐ™์€ ํ…œํ”Œ๋ฆฟ ๋ฉค๋ฒ„ ํ•จ์ˆ˜๋ฅผ ์ด์šฉํ•ด์„œ ์—ญ์ˆœ ๊ฒ€์ƒ‰๋„ ๊ฐ€๋Šฅํ•˜๊ฒŒ ์ž‘์„ฑ๋œ๋‹ค.
  • 1.2.1. 8.2.1 ์•Œ๊ณ ๋ฆฌ์ฆ˜๊ณผ ๋ฐ˜๋ณต์ž

    STL ํ•จ์ˆ˜๋ฅผ ๋ณด๋ฉด ์ธ์ž๋กœ ๋ฐ›๋Š” ๋ฐ˜๋ณต์ž(iterator)์— ๋”ฐ๋ผ์„œ ์ปจํ…Œ์ด๋„ˆ์˜ ํ•จ์ˆ˜ ์‚ฌ์šฉ ์œ ํšจ์„ฑ์„ ์•Œ ์ˆ˜ ์žˆ๋‹ค.
    ์˜ˆ๋ฅผ ๋“ค์ž๋ฉด find(B, E, D)๊ฐ™์€ ํ•จ์ˆ˜์˜ ๊ฒฝ์šฐ ์•„์ฃผ ๋‹จ์ˆœํ•œ ์ œํ•œ์  ์—ฐ์‚ฐ๋งŒ์„ ์ด์šฉํ•˜๊ธฐ ๋•Œ๋ฌธ์— ๋Œ€๋ถ€๋ถ„์˜ ์ปจํ…Œ์ด๋„ˆ์— ๋Œ€ํ•ด์„œ ์‚ฌ์šฉ์ด ๊ฐ€๋Šฅํ•˜๋‹ค. ๊ทธ๋Ÿฌ๋‚˜ sort(B, E)๊ฐ™์€ ๊ฒฝ์šฐ์—๋Š” ๊ธฐ๋ณธ์ ์ธ ์‚ฌ์น™์—ฐ์‚ฐ๋“ค์„ ๋ฐ˜๋ณต์ž์— ๋Œ€ํ•ด์„œ ์‚ฌ์šฉํ•˜๊ธฐ ๋•Œ๋ฌธ์— ์ด๋Ÿฐ ์—ฐ์‚ฐ์„ ์ง€์›ํ•˜๋Š” string, vector ๋งŒ์ด ์™„๋ฒฝํ•˜๊ฒŒ ์ง€์›๋œ๋‹ค.
    STL์€ ์ด๋Ÿฐ ๋ถ„๋ฅ˜๋ฅผ ์œ„ํ•ด์„œ 5๊ฐœ์˜ ๋ฐ˜๋ณต์ž ์นดํ…Œ๊ณ ๋ฆฌ(iterator category)๋ฅผ ์ •์˜ํ•˜์—ฌ ๋ฐ˜๋ณต์ž๋ฅผ ๋ถ„๋ฅ˜ํ•œ๋‹ค. ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋ถ„๋ฅ˜๋Š” ๋ฐ˜๋ณต์ž์˜ ์š”์†Œ๋ฅผ ์ ‘๊ทผํ•˜๋Š” ๋ฐฉ๋ฒ•์—๋”ฐ๋ฅธ ๋ถ„๋ฅ˜์ด๋ฉฐ, ์ด๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์‚ฌ์šฉ ์œ ํšจ์„ฑ ์—ฌ๋ถ€๋ฅผ ๊ฒฐ์ •ํ•˜๋Š”๋ฐ ๋„์›€์ด ๋œ๋‹ค.

    1.2.2. 8.2.2 ์ˆœ์ฐจ์  ์ฝ๊ธฐ-์ „์šฉ ์ ‘๊ทผ

    โ€ป ๋ชจ๋“  ์ˆœ์ฐจ๋ฐ˜๋ณต์ž์—์„œ๋Š” -- ์—ฐ์‚ฐ์„ ํ•  ์ˆ˜ ์—†๋‹ค.
    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)๋ผ๊ณ  ํ•จ.

    1.2.3. 8.2.3 ์ˆœ์ฐจ์  ์“ฐ๊ธฐ-์ „์šฉ ์ ‘๊ทผ

    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์˜ ํŠน์„ฑ์„ ๊ฐ€์ง„๋‹ค.

    1.2.4. 8.2.4 ์ˆœ์ฐจ์  ์ฝ๊ธฐ-์“ฐ๊ธฐ ์ ‘๊ทผ

    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)๋ผ๊ณ  ํ•จ.

    1.2.5. 8.2.5 ์—ญ๋ฐฉํ–ฅ ์ ‘๊ทผ

    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) ๋ผ๊ณ  ๋ถ€๋ฅธ๋‹ค. ํ‘œ์ค€ ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ ์ปจํ…Œ์ด๋„ˆ ํด๋ž˜์Šค๋“ค์€ ๋ชจ๋‘ ์–‘๋ฐฉํ–ฅ ๋ฐ˜๋ณต์ž๋ฅผ ์ง€์›ํ•จ.

    1.2.6. 8.2.6 ์ž„์˜ ์ ‘๊ทผ

    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;
    }
     
    ์ฐธ๊ณ ์ž๋ฃŒ) WikiPedia: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๋Š” ๋น ๋ฅธ ๋ฐ์ดํ„ฐ์˜ ์‚ฝ์ž…, ์‚ญ์ œ์— ์ตœ์ ํ™” ๋˜์—ˆ๊ธฐ ๋•Œ๋ฌธ์— ์ˆœ์ฐจ์ ์ธ ์ ‘๊ทผ๋งŒ ๊ฐ€๋Šฅํ•จ.

    1.2.7. 8.2.7 ๋ฐ˜๋ณต์ž ๋ฒ”์œ„ ๋ฐ ๋ ์ง€๋‚œ ๊ฐ’

    ๋ฐ˜๋ณต์ž์˜ ๋๊ฐ’์œผ๋กœ ์ปจํ…Œ์ด๋„ˆ์˜ ๋งˆ์ง€๋ง‰ ์š”์†Œ์—์„œ ํ•œ๊ฐœ๊ฐ€ ์ง€๋‚œ ๊ฐ’์„ ์‚ฌ์šฉํ•˜๋Š” ์ด์œ 
  • ๋งˆ์ง€๋ง‰ ์š”์†Œ๋ฅผ ๋ฒ”์œ„์˜ ๋์œผ๋กœ ์‚ฌ์šฉํ•จ์œผ๋กœ์จ ๋ฐœ์ƒํ•˜๋Š” ํŠน๋ณ„ํ•œ ์ฒ˜๋ฆฌ๋ฅผ ์—†์• ๋Š” ๊ฒƒ์ด ๊ฐ€๋Šฅ. (์‹ค์ˆ˜๊ฐ€ ์ค„์–ด๋“ฌ)
  • ๋งˆ์ง€๋ง‰ ์š”์†Œ๋ฅผ ๋ฒ”์œ„์˜ ๋์œผ๋กœ ์ •ํ•  ๊ฒฝ์šฐ ๋ฒ”์œ„์•ˆ์— ์ฐพ๋Š” ๊ฒƒ์ด ์—†์„๋•Œ ์ด๋ฅผ ์•Œ๋ ค์ฃผ๋Š” ์ˆ˜๋‹จ์ด ๋ถ€์žฌํ•˜๋‹ค.
  • ๋‹จ์ˆœํžˆ != ์—ฐ์‚ฐ์œผ๋กœ ๋ฒ”์œ„์˜ ์ˆœํšŒ๋ฅผ ๋งˆ์น˜๋Š” ์กฐ๊ฑด์œผ๋กœ ์ด์šฉ์ด ๊ฐ€๋Šฅํ•˜๋‹ค. <>์™€ ๊ฐ™์€ ํฌ๊ธฐ ์—ฐ์‚ฐ์ž๊ฐ€ ๋ถˆํ•„์š”ํ•˜๋‹ค.
  • ๋‘๋ฒˆ์งธ ์ธ์ž๋กœ ํ•˜๋‚˜๊ฐ€ ์ง€๋‚œ ๊ฐ’์„ ๊ฐ–๋„๋กํ•จ์œผ๋กœ์จ ์ž์—ฐ์Šค๋Ÿฝ๊ฒŒ out-of-range์˜ ์ƒํ™ฉ์„ ํŒŒ์•…ํ•˜๋Š” ๊ฒƒ์ด ๊ฐ€๋Šฅํ•˜๋‹ค.
    ~cpp 
     c.end() == c.begin() + c.size()    // this is true
     
  • 1.3. 8.3 Input and output iterators

    ์ž…์ถœ๋ ฅ ๋ฐ˜๋ณต์ž๋Š” ์ปจํ…Œ์ด๋„ˆ์˜ ๋ฐ˜๋ณต์ž์ด์™ธ์˜ ์กด์žฌํ•˜๋Š” ๋ฐ˜๋ณต์ž๋ฅผ ํ‘œํ˜„ํ•˜๊ธฐ ๋•Œ๋ฌธ์— ์ˆœ๋ฐฉํ–ฅ ๋ฐ˜๋ณต์ž์™€ ๊ตฌ๋ณ„์‹œํ‚ด.
    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; ์—์„œ๋„ ํƒ€์ž…์— ๋”ฐ๋ผ์„œ ๋‹ค๋ฅธ ์ผ์„ ํ•œ๋‹ค.

    1.4. 8.4 Using iterators for flexibility

    ~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++
    Valid XHTML 1.0! Valid CSS! powered by MoniWiki
    last modified 2021-02-07 05:22:25
    Processing time 0.0168 sec