| AcceleratedC++/Chapter7 | AcceleratedC++/Chapter9 |
1. Chapter 8 Writing generic functions ¶
Ch9~Ch12
์ฐธ๊ณ ํ์ด์ง) ParametricPolymorphism
1.1. 8.1 What is a generic function? ¶
ํจ์์ ํธ์ถ์ ํจ์์ ๋งค๊ฐ๋ณ์๋ฅผ 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
typename ์ ์์ง ์ธ์คํด์คํ ๋์ง ์์ ํจ์๋ฅผ ์ปดํ์ผ๋ฌ๊ฐ ์ฝ์ด๋ค์ผ๋ ํ์ ๋งค๊ฐ๋ณ์์ ๊ด๊ณ๋ ํ์ ์ ํ์ ์์ฑํ ๋ ์์ ๋ถ์ฌ์ผ ํ๋ ํค์๋ ์. ex) vector<T> or vector<T>::size_type
์๋ก ๋ค๋ฅธ ํ์
์ ๊ฐ์ฒด์ด๋ผ๋ ํ๋๋ผ๋ ๊ฐ๊ฐ์ ๊ฐ์ฒด๋ฅผ ๊ฐ์ง๊ณ ํํ๋ ํ๋์์์ ๊ณตํต์ ํ๋์์์ ๊ฐ๋๋ค.
Runtime์ด ์๋๋ผ Compile ํ์์ ์ค์ ๋ก ํ์ ์ด ๋ณํํ๋ ๊ฐ์ฒด๋ฅผ ์ ์ ํ ์์ฑํ๋ฉด ์ฌ๋ฐ๋ฅธ ๋์์ ๋ณด์ฅํ๋ค.
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 ์ ๋ค๋ฆญ ํจ์์ ํ์ ¶
์ค์ ์ ๋ค๋ฆญ ํจ์์ ์ฌ์ฉ์์ ๊ฐ์ฅ ๋ฌธ์ ์ ๋๋ ๊ฒ์ ํจ์๋ด๋ถ์ ์ฐ์ฐ์ ๋งค๊ฐ๋ณ์ ํ์
์ด ์ง์์ ํ๋ ๊ฐ์ด๋ค.
max ํจ์์ ๊ตฌํ
| 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)๋ฅผ ์ ์ํ์ฌ ๋ฐ๋ณต์๋ฅผ ๋ถ๋ฅํ๋ค. ์นดํ ๊ณ ๋ฆฌ์ ๋ถ๋ฅ๋ ๋ฐ๋ณต์์ ์์๋ฅผ ์ ๊ทผํ๋ ๋ฐฉ๋ฒ์๋ฐ๋ฅธ ๋ถ๋ฅ์ด๋ฉฐ, ์ด๋ ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉ ์ ํจ์ฑ ์ฌ๋ถ๋ฅผ ๊ฒฐ์ ํ๋๋ฐ ๋์์ด ๋๋ค.
์๋ฅผ ๋ค์๋ฉด find(B, E, D)๊ฐ์ ํจ์์ ๊ฒฝ์ฐ ์์ฃผ ๋จ์ํ ์ ํ์ ์ฐ์ฐ๋ง์ ์ด์ฉํ๊ธฐ ๋๋ฌธ์ ๋๋ถ๋ถ์ ์ปจํ ์ด๋์ ๋ํด์ ์ฌ์ฉ์ด ๊ฐ๋ฅํ๋ค. ๊ทธ๋ฌ๋ sort(B, E)๊ฐ์ ๊ฒฝ์ฐ์๋ ๊ธฐ๋ณธ์ ์ธ ์ฌ์น์ฐ์ฐ๋ค์ ๋ฐ๋ณต์์ ๋ํด์ ์ฌ์ฉํ๊ธฐ ๋๋ฌธ์ ์ด๋ฐ ์ฐ์ฐ์ ์ง์ํ๋ string, vector ๋ง์ด ์๋ฒฝํ๊ฒ ์ง์๋๋ค.
STL์ ์ด๋ฐ ๋ถ๋ฅ๋ฅผ ์ํด์ 5๊ฐ์ ๋ฐ๋ณต์ ์นดํ ๊ณ ๋ฆฌ(iterator category)๋ฅผ ์ ์ํ์ฌ ๋ฐ๋ณต์๋ฅผ ๋ถ๋ฅํ๋ค. ์นดํ ๊ณ ๋ฆฌ์ ๋ถ๋ฅ๋ ๋ฐ๋ณต์์ ์์๋ฅผ ์ ๊ทผํ๋ ๋ฐฉ๋ฒ์๋ฐ๋ฅธ ๋ถ๋ฅ์ด๋ฉฐ, ์ด๋ ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉ ์ ํจ์ฑ ์ฌ๋ถ๋ฅผ ๊ฒฐ์ ํ๋๋ฐ ๋์์ด ๋๋ค.
1.2.2. 8.2.2 ์์ฐจ์ ์ฝ๊ธฐ-์ ์ฉ ์ ๊ทผ ¶
โป ๋ชจ๋ ์์ฐจ๋ฐ๋ณต์์์๋ -- ์ฐ์ฐ์ ํ ์ ์๋ค.
find ๊ตฌํ 1
์๊ธฐ์ ๊ฐ์ ๋ฐ๋ณต์๋ฅผ ์ ๋ ฅ ๋ฐ๋ณต์(input iterator)๋ผ๊ณ ํจ.
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 ๊ตฌํ
class Out ๋ฐ๋ณต์๋ฅผ ์ถ๋ ฅ์ ๋ฐฐํ์ ์ผ๋ก ์ฌ์ฉํ๋ ค๋ฉด ++ ์ฐ์ฐ์ด ๋์ ๋ฌธ ์ฌ์ด์์ 1๋ฒ์ด์์ ๋ฌดํจ๊ฐ ๋๋๋ก ๋ง๋ค์ด ์ฃผ์ด์ผํ๋ค.
์๊ธฐ ์๊ตฌ์ฌํญ์ ๋ง์กฑ์ํค๋ ๊ฒฝ์ฐ์ ๋ฐ๋ณต์๋ฅผ ์ถ๋ ฅ ๋ฐ๋ณต์(Output iterator)๋ผ๊ณ ํจ.
๋ชจ๋ ์ปจํ ์ด๋๋ back_inserter(class T)๋ฅผ ํตํด์ ์ถ๋ ฅ ๋ฐ๋ณต์๋ฅผ ๋ฆฌํด์ํฌ ์ ์๋ค. ์ด ๋ฐ๋ณต์๋ write-once์ ํน์ฑ์ ๊ฐ์ง๋ค.
~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 ๊ตฌํ
์ฌ๊ธฐ์ beg๋ ์ ๋ ฅ ๋ฐ๋ณต์, ์ถ๋ ฅ ๋ฐ๋ณต์ 2๊ฐ์ง์ ํน์ฑ์ ๋ชจ๋ ๋ง์กฑ์์ผ์ผ ํ๋ค.
*, ++(์ ,ํ์), ==, =, ., ->์ ๊ฐ์ ์ฐ์ฐ์ด ๊ฐ๋ฅํ๋ค๋ฉด ์๋ฐฉํฅ ๋ฐ๋ณต์(forward iterator)๋ผ๊ณ ํจ.
~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 ๊ตฌํ
์๋ฐฉํฅ ์ฐ์ฐ์์ ๋ชจ๋ ์ฐ์ฐ์ ์ง์ํ๊ณ --์ฐ์ฐ์ ์ง์ํ๋ค๋ฉด ์ด ๋ฐ๋ณต์๋ ์๋ฐฉํฅ ๋ฐ๋ณต์(bidirection iterator) ๋ผ๊ณ ๋ถ๋ฅธ๋ค. ํ์ค ๋ผ์ด๋ธ๋ฌ๋ฆฌ ์ปจํ ์ด๋ ํด๋์ค๋ค์ ๋ชจ๋ ์๋ฐฉํฅ ๋ฐ๋ณต์๋ฅผ ์ง์ํจ.
~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 ๊ตฌํ
Binary_search๋ฐ์ด๋๋ฆฌ ์์น
์์ ์ ๊ทผ ๋ฐ๋ณต์์ ๊ฒฝ์ฐ ์๋ฐฉํฅ ๋ฐ๋ณต์์ ๋ชจ๋ ํน์ฑ๊ณผ ํจ๊ป ๋ค์๊ณผ ๊ฐ์ ์ฐ์ฐ์ ๋ง์กฑํ๋ค.
์์ ์ ๊ทผ ๋ฐ๋ณต์๋ฅด ์ด์ฉํ๋ ์๊ณ ๋ฆฌ์ฆ์ sort. vector, string ๋ง์ด ์์ ์ ๊ทผ ๋ฐ๋ณต์๋ฅผ ์ง์ํ๋ค. list๋ ๋น ๋ฅธ ๋ฐ์ดํฐ์ ์ฝ์ , ์ญ์ ์ ์ต์ ํ ๋์๊ธฐ ๋๋ฌธ์ ์์ฐจ์ ์ธ ์ ๊ทผ๋ง ๊ฐ๋ฅํจ.
~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;
}
์ฐธ๊ณ ์๋ฃ) ์์ ์ ๊ทผ ๋ฐ๋ณต์์ ๊ฒฝ์ฐ ์๋ฐฉํฅ ๋ฐ๋ณต์์ ๋ชจ๋ ํน์ฑ๊ณผ ํจ๊ป ๋ค์๊ณผ ๊ฐ์ ์ฐ์ฐ์ ๋ง์กฑํ๋ค.
| 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 ์ ๋ฐ๋ณต์๋ฅผ ์ป์์ผ๋ก์จ ์ ์ถ๋ ฅ ์คํธ๋ฆผ์ ์ ์ดํ๋ ๊ฒ์ด ๊ฐ๋ฅํ๋ค.
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++
----
AcceleratedC++










