Bài giảng Kĩ thuật lập trình - Chương 9: Khuôn mẫu hàm và khuôn mẫu lớp

Nội dung text: Bài giảng Kĩ thuật lập trình - Chương 9: Khuôn mẫu hàm và khuôn mẫu lớp

1. Kỹ thuật lập trình Phần III: Lập trình tổng quát Chương 9: 010101010101010110000101010101010101011000010101010101010101100001 StateController010101010010101010010101010101001010101001010101010100101010100101 start() 101001100011001001001010100110001100100100101010011000110010010010 Khuôn mẫu hàmstop()và110010110010001000001011001011001000100000101100101100100010000010khuôn mẫulớp 010101010101010110000101010101010101011000010101010101010101100001 010101010010101010010101010101001010101001010101010100101010100101 101001100011001001001010100110001100100100101010011000110010010010y = A*x + B*u; 110010110010001000001011001011001000100000101100101100100010000010x = C*x + d*u; LQGController010101010101010110000101010101010101011000010101010101010101100001 start() 010101010010101010010101010101001010101001010101010100101010100101 stop() 101001100011001001001010100110001100100100101010011000110010010010 110010110010001000001011001011001000100000101100101100100010000010 12/25/2007
2. Nộidung chương 9 9.1 Khuôn mẫuhàm -Vaitròcủa khuôn mẫuhàm - Định nghĩa khuôn mẫuhàm -Sử dụng khuôn mẫuhàm 9.2 Khuôn mẫulớp - Định nghĩa khuôn mẫulớp -Dẫnxuất khuôn mẫulớp -Vídụ khuôn mẫulớp Vector Chương 9: Khuôn mẫu hàm và khuôn mẫulớp 2
3. 9.1 Khuôn mẫuhàm(function template) ƒ Vấn ₫ề: Nhiều hàm chỉ khác nhau về kiểu dữ liệu tham số áp dụng, không khác nhau về thuật toán ƒ Ví dụ: int max(int a, int b) { return (a > b)? a : b; } double max(double a, double b) { return (a > b)? a : b; } ƒ Các ví dụ khác: các hàm swap, sort, find, select, ƒ Bản chất của vấn ₫ề? Nằm ở ngôn ngữ lập trình còn thấp, chưa gần với tư duy của con người! ƒ Giải pháp: Tổng quát hóa các hàm chỉ khác nhau về kiểu dữ liệu áp dụng thành khuôn mẫu hàm. Chương 9: Khuôn mẫu hàm và khuôn mẫulớp 3
4. Định nghĩakhuônmẫuhàm ƒ Ví dụ tổng quát hóa hàm max ₫ể có thể áp dụng cho nhiềukiểu dữ liệu khác nhau: template T max(T a, T b) { return (a > b)? a : b; } ƒ Ví dụ tổng quát hóa hàm swap: template Sử dụng từ khóa typename void (X& a, X& b) { hoặc class ₫ể khai báo tham X temp = a; số khuôn mẫu a = b; b = temp; } ƒ Mộtkhuônmẫuhàminline: template inline T max(T a, T b) { return (a > b)? a : b;} Chương 9: Khuôn mẫu hàm và khuôn mẫulớp 4
5. Khai báo và sử dụng khuôn mẫuhàm ƒ Ví dụ sử dụng khuôn mẫuhàmmax Khuôn mẫuhàm template T max(T a, T b); template void swap(T&, T&); void main() { Hàm khuôn mẫu int N1 = 5, N2 = 7; double D1 = 5.0, D2 = 7.0; int N = max(N1,N2); // max (int,int) char c = max('c','a'); // max (char, char) double D = max(D1,D2); // max (double, double) swap(N1,N2); // swap (int&,int&) swap(D1,D2); // swap (double&,double&) D = max(D1,A1); // error: ambiguous N = max('c',A1); // error: ambiguous D = max (D1,A1);// OK: explicit qualification N = max ('c',A); // OK: explicit qualification } Chương 9: Khuôn mẫu hàm và khuôn mẫulớp 5
6. Khả năng áp dụng khuôn mẫuhàm ƒ Khả năng áp dụng một khuôn mẫuhàmlàvôtận, nhưng không phảiápdụng ₫ượcchotấtcả các ₫ốisố khuôn mẫu Ví dụ: Điềukiệnràngbuộc ₫ốivớikiểudữ liệucóthể áp dụng trong khuôn mẫu hàm max là phải có phép so sánh lớnhơn(>): template inline T max(T a, T b) { return (a > b)? a : b;} => Đốivớicáckiểudữ liệumới, muốnápdụng ₫ượcthìcầnphải nạpchồng toán tử so sánh > ƒ Tuy nhiên, khả năng áp dụng ₫ượcchưachắc ₫ãcóý nghĩa ƒ Ví dụ: Xác ₫ịnh chuỗikýtự₫ứng sau trong hai chuỗichotrước theo vầnABC char city1[] = "Ha Noi", city2[] = "Hai Phong"; char* city = max(city1,city2); // ??? // max (char*,char*) Chương 9: Khuôn mẫu hàm và khuôn mẫulớp 6
7. Nạpchồng khuôn mẫuhàm ƒ Mộtkhuônmẫuhàmcóthể₫ượcnạpchồng bằng hàm cùng tên char* max(char* a, char* b) { if (strcmp(a,b)) } void f() { char c = max('H','K'); // max (char,char) char city1[] = "Ha Noi", city2[] = "Hai Phong"; char* city = max(city1,city2); // max(char*,char*) } ƒ hoặcbằng mộtkhuônmẫu hàm cùng tên (khác số lượng các tham số hoặckiểucủaítnhấtmộtthamsố), ví dụ: template T max(T a, T b, T c) { } template T max(T* a, int n) { } nhưng không ₫ượcnhư thế này: template X max(X a, X b) { } Chương 9: Khuôn mẫu hàm và khuôn mẫulớp 7
8. Tham số khuôn mẫu ƒ Tham số khuôn mẫuhàmcóthể là mộtkiểucơ bảnhoặcmột kiểudẫnxuất, nhưng không thể là mộtbiếnhoặcmộthằng số: template max(T a, T b) { } // OK template max(int* a) { } // error ƒ Mộtkhuônmẫuhàmcóthể có hơnmộtthamsố kiểu: template void swap(A& a, B& b) { A t = a; a = b; // valid as long as B is compatible to A b = t; // valid as long as A is compatible to B } void f() { double a = 2.0; int b = 3; swap(a,b); // swap (double&,int&) swap(b,a); // swap<int,double)(int&, double&) } Chương 9: Khuôn mẫu hàm và khuôn mẫulớp 8
9. ƒ Thông thường, tham số khuôn mẫuxuấthiệnítnhấtmộtlầnlà kiểuhoặckiểudẫnxuấttrựctiếpcủa các tham biến: template void f1(X a, int b) { } template void f2(X* b) { } template void f3(Y& a, X b) { } ƒ Theo chuẩn ANSI/ISO C++, tham số khuôn mẫu không bắtbuộc phảixuấthiệntrongdanhsáchthambiến, nhưng cầnlưuý khi sử dụng. Ví dụ #include template X* array_alloc(int nelem) { return (X*) malloc(nelem*sizeof(X)); } void main() { double* p1 = array_alloc(5); // error! double* p2 = array_alloc (5); // OK! free(p2); } Chương 9: Khuôn mẫu hàm và khuôn mẫulớp 9
10. Khuôn mẫu hàm và hàm khuôn mẫu ƒ Khuôn mẫuhàmchỉ₫ưaracáchthứcthựchiệnvàsử dụng một thuậttoánnào₫ómộtcáchtổng quát ƒ Trong khi biên dịch khuôn mẫu hàm, compiler chỉ kiểmtravề cú pháp, không dịch sang mã ₫ích ƒ Mã hàm khuôn mẫu ₫ượccompiler tạora(dựa trên khuôn mẫu hàm) khi và chỉ khi khuôn mẫuhàm₫ượcsử dụng vớikiểucụ thể ƒ Nếumộtkhuônmẫuhàm₫ượcsử dụng nhiềulầnvớicáckiểu khác nhau, nhiều hàm khuôn mẫusẽ₫ượctạoratương ứng ƒ Nếumộtkhuônmẫuhàm₫ượcsử dụng nhiềulầnvớicáckiểu tương ứng giống nhau, compiler chỉ tạoramột hàm khuôn mẫu. Chương 9: Khuôn mẫu hàm và khuôn mẫulớp 10
11. Ưu ₫iểmcủakhuônmẫuhàm ƒ Tiếtkiệm ₫ượcmãnguồn=> dễ bao quát, dễ kiểmsoátlỗi, nâng cao hiệuquả lậptrình ƒ Đảmbảo ₫ượctínhchặtchẽ về kiểmtrakiểumạnh trong ngôn ngữ lậptrình(hơnhẳnsử dụng macro trong C) ƒ Tính mở, nâng cao giá trị sử dụng lạicủaphầnmềm: thuậttoán viếtmộtlần, sử dụng vô số lần ƒ Đảmbảohiệusuấttương ₫ương như viếttáchthànhtừng hàm riêng biệt ƒ Cho phép xây dựng các thư việnchuẩnrấtmạnh (các thuậttoán thông dụng như sao chép, tìm kiếm, sắpxếp, lựachọn, ) Chương 9: Khuôn mẫu hàm và khuôn mẫulớp 11
12. Nhược ₫iểmcủakhuônmẫuhàm ƒ Nếumuốn ₫ảmbảotínhmở hoàn toàn thì ngườisử dụng khuôn mẫuhàmcũng phảicómãnguồnthựcthi —Mãnguồnthựcthicần ₫ược ₫ặt trong header file —Khóbảovệ chấtxám ƒ Việctheodõi, tìmlỗibiêndịch nhiềukhigặp khó khăn —Lỗi nhiềukhinằm ở mã sử dụng, nhưng lại ₫ược báo trong mã ₫ịnh nghĩa khuôn mẫuhàm —Vídụ: Compiler không báo lỗi ở dòng lệnh sau ₫ây, mà báo lỗi ở phần ₫ịnh nghĩahàmmax, tại phép toán so sánh lớnhơn không ₫ược ₫ịnh nghĩachokiểu Complex: Complex a, b; Complex c = max(a,b); ƒ Định nghĩavàsử dụng không ₫úng cách có thể dẫntớigiatăng lớnvề mã ₫ích, bởisố lượng hàm khuôn mẫucóthể₫ượctạora quá nhiều không cầnthiết. Chương 9: Khuôn mẫu hàm và khuôn mẫulớp 12
13. Ví dụ: khuôn mẫuhàmcopy template void copy(const S * s, D* d, int n) { while (n ) *d++ = *s++; } void main() { int a[] = {1,2,3,4,5,6,7}; double b[10]; float c[5]; copy(a,b,7); // copy (a,b,7) copy(b,c,5); // copy (b,c,5); } Chương 9: Khuôn mẫu hàm và khuôn mẫulớp 13
14. 9.2 Khuôn mẫulớp (class template) ƒ Nhiều cấu trúc dữ liệu như Point, Complex, Vector, List, Map, trước kia vẫn phải ₫ược ₫ịnh nghĩa riêng cho từng kiểu dữ liệu phần tử cụ thể, ví dụ DoubleComplex, FloatComplex, DoubleVector, IntVector, ComplexVector, DateList, MessageList, ƒ Cách thực hiện mỗi cấu trúc thực ra giống nhau, nói chung không phụ thuộc vào kiểu phần tử cụ thể class IntPoint { int x,y; public: IntPoint(int x0, int y0) : x(x0), y(y0) {} }; class DoublePoint { double x,y; public: DoublePoint(double x0, double y0) : x(x0), y(y0) {} }; Chương 9: Khuôn mẫu hàm và khuôn mẫulớp 14
15. Định nghĩakhuônmẫulớp // Point.h template class Point { Tham số khuôn mẫu: T x, y; Kiểuhoặchằng số public: Point(): x(0), y(0) {} Point(T x0, T y0) : x(x0), y(y0) {} Point(const Point&); Mỗi hàm thành void move(T dx, T dy) { x += dx; y+= dy; } viên củamột bool inRect(Point p1, Point p2); khuôn mẫulớplà // một khuôn mẫu }; hàm template Point ::Point(const Point & b) : x(b.x), y(b.y) {} template bool Point ::inRect(Point p1, Point p2) { return (x >= p1.x && x = p2.x && x = p1.y && y = p2.y && x <= p1.y); } Chương 9: Khuôn mẫu hàm và khuôn mẫulớp 15
16. Sử dụng khuôn mẫulớp: Lớpkhuônmẫu #include "Point.h" void main() { Point A1(5,5),A2(10,10); Point A3(A1); while (A3.inRect(A1,A2)) A3.move(2,3); typedef Point FPoint; FPoint B1(5.0,5.0), B2(10.0,10.0); FPoint B3(B1); while (B3.inRect(B1,B2)) B3.move(2,3); // Point C1(B1); // error if (A3.inRect(B1,B2)) // error ; // } Chương 9: Khuôn mẫu hàm và khuôn mẫulớp 16
17. Những kiểunàocóthể áp dụng? ƒ Khả năng áp dụng củakiểulàvôtận, tuy nhiên không có nghĩa là áp dụng ₫ượcchotấtcả các kiểu ƒ Mộtkiểumuốnápdụng ₫ượcphảihỗ trợ các phép toán ₫ượcsử dụng trong mã thực thi khuôn mẫulớp. ƒ Ví dụ khuôn mẫulớpPoint yêucầukiểutọa ₫ộ phảiápdụng ₫ược các phép toán sau ₫ây: — Chuyển ₫ổitừ số nguyên (trong hàm tạomặc ₫ịnh) — Sao chép (trong hàm tạothứ hai và hàm tạobảnsao) —Toántử += (trong hàm move) — Các phép so sánh >=, <= (trong hàm inRect) ƒ Việckiểmtrakiểu ₫ượctiếnhànhkhisử dụng hàm thành viên củalớpkhuônmẫu, nếucólỗithìsẽ₫ược báo tại mã nguồn thực thi khuôn mẫulớp Chương 9: Khuôn mẫu hàm và khuôn mẫulớp 17
18. Tham số khuôn mẫu: kiểuhoặchằng số template class Array { T data[N]; public: Tham số mặc ₫ịnh Array(const T& x = T(0)); int size() const { return N; } T operator[](int i) const { return data[i]; } T& operator[](int i) { return data[i]; } // }; template Array ::Array(const T& x) { for (int i=0; i a; Array b; // same as above Array<> c; // same as above // } Chương 9: Khuôn mẫu hàm và khuôn mẫulớp 18
19. Dẫnxuấttừ khuôn mẫulớp template class IOBuffer : public Array { public: IOBuffer(T x) : Array (x) {} // }; class DigitalIO : public IOBuffer { public: DigitalIO(bool x) : IOBuffer (x) {} // }; class AnalogIO : public IOBuffer { typedef IOBuffer BaseClass; public: AnalogIO(unsigned short x) : BaseClass(x) {} // }; void main() { IOBuffer delayBuf(0); DigitalIO di(false); AnalogIO ao(0); // } Chương 9: Khuôn mẫu hàm và khuôn mẫulớp 19
20. Ví dụ khuôn mẫulớpVector template class Vector { int nelem; T* data; public: Vector() : nelem(0), data(0) {} Vector(int n, T d); Vector(int n, T *array); Vector(const Vector &); ~Vector(); int size() const { return nelem; } T operator[](int i) const { return data[i]; } T& operator[](int i) { return data[i]; } private: void create(int n) { data = new T[nelem=n]; } void destroy() { if (data != 0) delete [] data; } }; Chương 9: Khuôn mẫu hàm và khuôn mẫulớp 20
21. template Vector ::Vector(int n, T d) { create(n); while (n > 0) data[n] = d; } template Vector ::Vector(int n, T* p) { create(n); while (n > 0) data[n] = p[n]; } template Vector ::~Vector() { destroy(); } template Vector ::Vector(const Vector & a) { create(a.nelem); for (int i=0; i < nelem; ++i) data[i] = a.data[i]; } Chương 9: Khuôn mẫu hàm và khuôn mẫulớp 21
22. #include "Point.h" #include "Vector.h" void main() Vector v(5,1.0); double d = v[0]; v[1] = d + 2.0; Vector v2(v); // int b[] = {1,2,3,4,5}; Vector a(5,b); int n = a[0]; a[1] = n + 2; Vector a2(a); // typedef Vector > Points; Points lines(5,Point (0.0,0.0)); lines[0] = Point (5.0,5.0); // } Chương 9: Khuôn mẫu hàm và khuôn mẫulớp 22
23. Bài tậpvề nhà ƒ Xây dựng một khuôn mẫuhàmxác₫ịnh vị trí (₫ịachỉ) củaphần tử có giá trị lớnnhấtxuấthiện ₫ầutiêntrongmột dãy số. Viết chương trình minh họasử dụng cho hai kiểusố liệucụ thể. ƒ Từ bài tậpxâydựng lớpMessageList, tổng quát hóa thành một khuôn mẫulớpcótênlàList với các phép toán (hàm thành viên) cầnthiết Chương 9: Khuôn mẫu hàm và khuôn mẫulớp 23