Lập trình
Chương 6: Lập trình tổng quá
t
8/6/2012
Nội dung
 6.1 Khuân mẫu hàm (Function template)
 6.2 Khuân mẫu lớp
 6.3 Thuật toán tổng quát
Chương 5: Lập trình tổng quát
© 2010 - KimThoa
2
6.1 Khuân mẫu hàm
 Ví dụ hàm tìm giá trị lớn nhất
a. Tìm max hai số nguyên
int max(const int &a, const int &b){
return (a > b)? a: b;
}
b. Tìm max hai số thực
float max(const float &a, const float &b){
return (a > b)? a: b;
}
 Nh
ậ
n xét: Các hàm tìm max của hai số chỉ khác nhau về kiểu dữ li
ệ
u
,

ậ ệ ,
thuật toán giống nhau.
 Tương tự như vậy có rất nhiều hàm chỉ khác nhau về kiểu dữ liệu, không


báo

tham

số

khuôn mẫu
template
<
typename
T>
inline T max(const T &a,const T &b) {
return (a > b)? a : b;
}
Cilẽ t ộthà th kh ô ẫ
 Sử dụng
int max(5,7);
C
omp
il
er s
ẽ

t
ạo m
ột

hà
m

=
0,
int
void main{
complex c1(1.1,2.0);
complex c2(2.0,2,2);
complex c = max(c1,c2);
complex(
double
r0,
int
i=0);
double get_real();
void set_real(double);
doub
l
e
get
im
ag();
};
Lỗi, vì lớp complex trên chưa ₫ịnh
nghĩa phép so sánh > sử dụng trong
hàm khuôn mẫumax
Chương 5: Lập trình tổng quát
© 2010 - KimThoa
5
doub e
get
_

ố

h
o
ặ
c
k
i
ể
u c
ủ
a
ít
n
hất
m
ột

tham số)
—
Hàm cùn
g
tên ₫ể th
ự
c hi
ệ
n cho các thu
ậ
t toán ₫
ặ

kiểu, ví dụ:
l l A l B id (A& B& b){
}
temp
l
ate

<c
l
ass
A
,

c
l
ass
B
>

vo
id
swap
(A&
a,
B& b){
…
}
 Ví dụ:
template
<

double
b = 10 2;
double
b = 10
.
2;
swap(a,b); //swap<int,double>(int,double)
swap(b,a); //swap<double,int>(double,int)
}
Chương 5: Lập trình tổng quát
© 2010 - KimThoa
7
Tóm lược
 Khi sử dụng compiler cần biết mã nguồn thực hiện
khuôn mẫu hàm, do vậy khai báo và ₫ịnh nghĩa
kh ô ẫ hà ê ₫ể ở hd fil
ử d
kh
u
ô
n m
ẫ
u
hà
m n
ê
n
₫ể

ở

sinh

ra

khi

và

chỉ khi khuôn mẫu hàm ₫ược sử dụng với kiểu cụ thể
 Một khuôn mẫu hàm ₫ược sử dụng nhiều lần với các
ể ề ẫ
ki
ể
u khác nhau thì nhi
ề
u hàm khuôn m
ẫ
u ₫ược tạo
ra

Một khuôn mẫuhàm₫ượcsử dụng nhiềulầnvới

Một

khuôn

mẫu

hàm


thư viện thuật toán thông dụng: sao chép, tìm ki
ế
m, s
ắ
p x
ế
p,
lựa chọn,…
 Như
ợ
c ₫iểm
ợ
— Không che giấu ₫ược mã nguồn thực thi, vì compiler phải
biết mã nguồn khi biên dịch
—
Theo dõi tìm kiếmlỗiphứctạp ₫ôi khi lỗinằm ở phầnsử
Theo

dõi
,
tìm

kiếm

lỗi

phức

tạp
,

return z;
}
Complex operator-(const Complex& b) const {
return Complex(real - b.real, imag - b.imag);
}

};
Chương 5: Lập trình tổng quát
© 2010 - KimThoa
10
class DoubleCom
p
lex
{
p{
double real,imag;
public:
Complex(double r = 0, double i =0): real(r),imag(i) {}
double
g
et real
()
const
{
return real
;

}
g
_

n
khá
c n
h
au g
ì?

Giố
ng n
h
au g
ì?
Chương 5: Lập trình tổng quát
© 2010 - KimThoa
11
 Tương tự nhu vậy, trong thực tế có rất nhiều cấu trúc
dữ liệuchỉ khác nhau về kiểudữ liệu còn hoàn toàn
dữ

liệu

chỉ

khác

nhau

về

kiểu

Complex z(real + b.real, imag + b.image);
return z;
}
Complex operator-(const Complex& b) const;

};
Chương 5: Lập trình tổng quát
© 2010 - KimThoa
12
 Định nghĩa hàm thành viên bên ngoài khai báo lớp
template <class T>
Complex<T>::Complex operator-(const Complex<T>& b) const
{
return Complex<T>(real - b.real, imag - b.imag);

Sử d
}

Sử

d
ụng
void main{
Complex<int> c1(1,1), c2(2,3);
Complex<int> c3 = c1+c2;
Complex<double> c4(1.0,2.0), c5(3.0,5.0);
Complex<double> c6 = c4 + c5;
};
Chương 5: Lập trình tổng quát
© 2010 - KimThoa

lớn nhất/hoặc nhỏ nhất trong một mảng
 Tổng quát hóa kiểu dữ liệu cho lớp array, thực hiện
các hàm thành viên cần thiết ₫ể có thể
—
Khai báo và khởitạo giá trị ban ₫ầu
Khai

báo

và

khởi

tạo

giá

trị

ban

₫ầu
—Hủy bộ nhớ khi không còn sử dụng
—Thực hiện các phép toán +,-, +=, -=,…
Chương 5: Lập trình tổng quát
© 2010 - KimThoa
15
6.3 Thuật toán tổng quát
 Ví dụ: hãy viết hàm sắp xếp các phần tử của một
mảng theo thứ tự từ nhỏ ₫ến lớn

(p[j] < p[j
-
1])
swap(p[j], p[j-1]);
}
void swap(T &a, T &b){
T
t = a;
T
t = a;
a = b;
b = t;
}
 Thuật toán trên áp dụng cho nhiều kiểu dữ liệu có
₫ịnh nghĩa phép so sánh nhỏ hơn
Int
p[100];
Int
p[100];
sort(p,100); //OK
char p2[100];
sort(p2,100); //OK
complex<
double
> p3[100];
Chương 5: Lập trình tổng quát
© 2010 - KimThoa
17
complex<
double

m
enum comparetype {less, greater, abs_less, abs_greater};
template <class T>
void
sort(
T
*
p,
int
n,comparetype c){
void
sort(
T
p,
int
n,comparetype c){
for(int i = 0; i < n-1; i++)
for(int j = n-1; j > i; j)
switch(c){
case less:
if
(p[j] < p[j
1])
if
(p[j] < p[j
-
1])
swap(p[j], p[j-1]);
break;
case greater:

Chương 5: Lập trình tổng quát
© 2010 - KimThoa
18
break;
}
}
 Nhược ₫iểm:
—
Hi
ệ
u
q
uả khôn
g
cao
ệ q g
—Tốc ₫ộ chậm
— Không có tính năng mở: ví dụ nếu muốn só sánh số phức
theo phầnthực thì không dùng ₫ượccáchtrên
theo

phần

thực

thì

không

dùng

}
 Kiểu Compare có thể là
—Một hàm
—Một ₫ối tượng thuộc lớp có ₫ịnh nghĩa lại toán tử gọi hàm
Chương 5: Lập trình tổng quát
© 2010 - KimThoa
19
 Kiểu Compare là một hàm
template <class T>
inline bool less(const T &a, const T &b){
return a < b; //return operator<(a,b)
}
template <class T>
inline bool greater(const T &a, const T &b){
return a > b; //return operator>(a,b)
}
}
int
v[100];
—Sử dụng
int
v[100];
double d[100];
sort(v,100,less<int>);
sort(d,100,greater<double>)
Một hàm
Chương 5: Lập trình tổng quát
© 2010 - KimThoa
20
— So sánh số phức


hàm
template <class T>
struct Less {
bool operator()(const T &a, const T &b){
return a<b;
}
};
template <class T>
struct Greater {
bool operator()(const T &a, const T &b){
return a>b;
—
Sử dụng
}
};
Sử

dụng
int v[100];
double d[100];
sort(v,100,Less<int>());
Một ₫ối tượng
Chương 5: Lập trình tổng quát
© 2010 - KimThoa
22
sort(d,100,Greater<double>())
Bài tập
 Áp dụng tổng quát hóa kiểu dữ liệu và tổng quát hóa phép toán
₫ể xây dựng các hàm càn thiết thực hiện các phép toán cộng,

Hàm thực hiện phép toán
template <class T, class OP>
void operation(T *p1, T *p2, T *result,int n, OP op){ }
—
Định nghĩa phép toán theo dạng hàm
template <class T>
T add(const T &a, const T &b){ }

—Hoặc ₫ịnh nghĩa phép toán theo dạng ₫ối tượng
template <class T>
struct Add{ };
Chương 5: Lập trình tổng quát
© 2010 - KimThoa
23

Chương trình
template<class T, class OP>
void operation(T* p1, T* p2,T* result,int n, OP op){
for(int i = 0;i<n;i++){
result[i]
=
op(p1[i],p2[i]);
result[i]

op(p1[i],p2[i]);
}
}
template<class T>
T dd( t
T& t T& b){ t b }

cout<<"\n";
for(int i = 0;i<n;i++)
Chương 5: Lập trình tổng quát
© 2010 - KimThoa
24
cout<<"\t"<<a[i];
}
Chương trình
void main(){
int a[5] = {1,2,3,4,5};
i tb[5] {1112131415}
i
n
t

b[5]
=
{11
,
12
,
13
,
14
,
15}
;
int result[5];
operation(a,b,result,5,add<int>);
dis