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

khác về thuật toán
Chương 5: Lập trình tổng quát
© 2010 - KimThoa
3
 Giải pháp: tổng quát hóa các hàm chỉ khác nhau về kiểu ⇒ khuôn mẫu
hàm
 Ví dụ tổng quát hóa hàm max
template
<
class
T>
Tham số khuôn mẫu
template
<
class
T>
T max(const T &a,const T &b){
return (a > b)? a: b;
Sử dụng từ khóa
class hoặc typename
để khai báo tham số
}
 Khuôn mẫu hàm inline
template
<
typename
T>
để

khai


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

th
eo
kh
u
ô
n m
ẫ
u
có dạng int max(const int&, const int&)
Chương 5: Lập trình tổng quát
© 2010 - KimThoa
4
 Ví dụ sử dụng
void main() {
int i1 = 1, i2 = 5;
double d1 = 1.0, d2 = 2.0;
double d = max(d1,d2); // max<double>(double,double)
char c = max('c','a'); // max<char>(char, char)
d = max(i1,d1); // error: ambiguous
c = max('c',i1); // error: ambiguous
d = max<double>(d1,i1); // OK: explicit qualification
c = max<int>('c',i1); // OK: explicit qualification
}
 Áp dụng cho complex?
class complex{
double real, imag;
public:
complex(
double
r

=
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
_

ag();
void set_imag(double);
};
hàm

khuôn

mẫu

max
 Giải pháp cho trường hợp trên là ₫ịnh nghĩa toán tử
so sánh lớn hơn cho lớ
p
com
p
lex.
pp
 Một khuôn mẫu hàm cũng có thể ₫ược nạp chồng bởi
hàm cùng tên hoặc bởi một khuôn mẫu hàm cùng tên
(khá ố l áth ố h ặ k ể ủ ít hất ột
(khá
c s
ố

l
ượng c
á
c
th
am s

ố

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 ₫
ặ

c bi
ệ
t. (Ví
g ự ệ ậ ặ ệ
dụ, hàm max giữa hai chuỗi ký tự có thuật toán thực hiện
khác với tìm max của hai số int hoặc double)
—
Khuôn mẫu hàm cùn
g
tên
g
template <class T> T max(T a, T b, T c) { }
template <class T> T max(T* a, int n) { }
nhưng không ₫ượcnhư thế này:
nhưng

không

₫ược

như

thế

này:
template <class X> X max(X a, X b, X c) { }
Chương 5: Lập trình tổng quát
© 2010 - KimThoa
6
 Tham số khuôn mẫu hàm có thể có hơn một tham số

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
<

class
A class B>
template
<
class
A
,
class B>
void swap( A &a, B &b){
A temp = a;
a = b; //₫úng khi b tương thích với a
b = temp;
//₫úng khi temp tương thích vớib
b = temp;
//₫úng

khi

temp

tương

thích

với

b
}
void main(){
int a = 5;

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
₫ể

ở


h
ea
d
er
fil
e ⇒ s
ử

d
ụng
template sẽ công khai hết phần thực hiện

Mã hàm khuôn mẫuchỉ ₫ượcthựcsự sinh ra khi và
Mã

hàm

khuôn

mẫu

chỉ

₫ược

thực

sự


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


₫ược

sử

dụng

nhiều

lần

với

cùng một kiểu, thì chỉ có một hàm khuôn mẫu ₫ược
tạo
Chương 5: Lập trình tổng quát
© 2010 - KimThoa
8
Ưu/nhược ₫iểm của khuôn mẫu hàm
 Ưu ₫iểm
—Tiết kiệm ₫ược mã nguồn
ế ầ
—
Tính mở: nâng cao tính sử dụng lại, thuật toán vi
ế
t một l
ầ
n
sử dụng vô số lần
— Cho phép xây dựng các thư viên chuẩn rất mạnh như các
ế ắ ế

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
,

₫ôi

khi

lỗi

nằm

ở

phần

sử

dụng nhưng compiler lại báo trong phần ₫ịnh nghĩa khuôn
mẫu hàm
Chương 5: Lập trình tổng quát
© 2010 - KimThoa
9
6.2 Khuôn mẫu lớp
 Nghiên cứu lớp số phức
#include <iostream.h>
class IntComplex{
int real,imag;
public:
Complex(int r = 0, int i =0): real(r),imag(i) {}
int get_real() const { return real; }
int get_imag() const { return imag; }
Complex operator+(const Complex& b) const {
Complex z(real + b.real, imag + b.image);

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
_

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

};
Hilớ ố hứ t ê khá h ì? Giố hì?

H
a
i

lớ
p s
ố
p
hứ
c
t
r
ê

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


dữ

liệu

còn

hoàn

toàn

giống về phép toán, ví dụ như vector, list, complex,…
 Để tiết kiệm mã n
g
uồn thực thi ⇒ tổn
g

q
uát hóa kiểu
g
gq
dữ liệu cho lớp
template <class T>
class Complex{
T real,imag;
public:
Complex(T r = 0, T i =0): real(r),imag(i) {}
T get_real() const { return real; }
T get_imag() const { return imag; }
Complex operator+(const Complex& b) const {

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

13
Tham số khuôn mẫu
 Tham số khuôn mẫu có thể là hằng hoặc kiểu (₫ể làm
tham số mặc ₫ịnh)
template <class T = int, class N = 10>
class Array{
T data[N];
public:
ố

};
Tham s
ố
mặc định
 Sử d
ụ
n
g
void main(){
Array<int,10> a;
ụ g
Giống nhau
Array<int> b;
Array<> c;
}
Chương 5: Lập trình tổng quát
© 2010 - KimThoa
14
Bài tập
 Xây dựng một khuôn mẫu hàm cho phép tìm giá trị

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

void sort(int *p, int n){
for(int i = 0; i < n-1; i++)
for(int j = n-1; j > i; j)
if(p[j] < p[j-1])
swap(p[j], p[j-1]);
}
void swap(int &a, int &b){
int t = a;
a = b;
b = t;
}
Chương 5: Lập trình tổng quát
© 2010 - KimThoa
16
 1. Tổng quát hóa kiểu dữ liệu của các phần tử
template
<
class
T>
template
<
class
T>
void sort(T *p, int n){
for(int i = 0; i < n-1; i++)
for(int j = n-1; j > i; j)
if
(p[j] < p[j
1])
if

(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

> p3[100];
sort(p3,100) //Lỗi, chỉ áp dụng được khi lớp complex định
//nghĩa phép so sánh nhỏ hơn
 Câu hỏi: làm thế nào ₫ể ta có thể sắp xếp lại từ lớn
₫ến nhỏ mà không cần phải viết lại hàm
G ả há h thê th b ế àkh báhà

G
i
ả
i p
há
p: c
h
o
thê
m
th
am
b
i
ế
n v
à
o
kh
ai
bá
o
hà

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:

if
(p
[
j
] >
p
[
j
-1]
)

(p j p j
)
swap(p[j], p[j-1]);
break;
case abs_less:
if(abs(p[j]) < abs(p[j-1])

swap(p[j] p[j
1]);
swap(p[j]
,
p[j
-
1]);
break;
case abs_greater:
if(abs(p[j]) > abs(p[j-1]))

swap(p[j], p[j-1]);

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


₫ược

cách

trên
 Giải pháp: tổng quát hóa phép toán
tem
p
late <class T
,
class Com
p
are>
p
,p
void sort(T *p, int n, Compare comp){
for(int i = 0; i < n-1; i++)
for(int j = n-1; j > i; j)
if
(
com
p(p[j],

p[j
-1
]))
( p(p[j], p[j
]))
swap(p[j], p[j-1]);

}
 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

template <class T>
inline bool less_real(const complex &a, const complex &b){
return (a.get_real() > b.get_real()) //return operator>(a,b)
}
—Sử dụng
co
m
p
l
e
x<
doub
l
e
>
c[
1
00];
cope
doub e
c[ 00];
Sort(c,100,less_real<double>);
Chương 5: Lập trình tổng quát
© 2010 - KimThoa
21
 Kiểu compare là một ₫ối tượng có ₫ịnh nghĩa lại toán
tử gọihàm
tử

gọi


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,

trừ, nhân, chia từng phầntử củahaimảng. Sau ₫óviếtchương
trừ,

nhân,

chia

từng

phần

tử

của

hai

mảng.

Sau

₫ó

viết

chương

trình minh họa cách sử dụng.
 Gợi ý:
—

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 }

T
a
dd(
cons
t
T&
a, cons
t

T&

b){
re
t
urn a+
b
;
}
tem
p
late <class T>
p
struct Add{
int operator()(const T& a, const T& b){ return a+b;}
};
template<class
T>
template<class
T>
void display(const T& a, int n){

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

p
la
y(
result
,
5
);
py( ,);
operation(a,b,result,5,Add<int>());
display(result,5);
}
}
Chương 5: Lập trình tổng quát
© 2010 - KimThoa
25