Bài giảng Kỹ thuật lập trình - Chapter 11: Lập trình khái quát - Đào Trung Kiên

EE3490: Kỹ thuật lập trình – HK1 2017/2018 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội Chapter 11: Lập trình khái quát (Generic programming) 1 EE3490: Kỹ thuật lập trình – HK1 2017/2018 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội Khuôn mẫu hàm (Function templates) 2 EE3490: Kỹ thuật lập trình – HK1 2017/2018 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội General  Đôi khi ta muốn viết một lần nhưng có thể tạo ra các hàm với tham số thuộc nhiều kiểu khác nhau, thay vì phải viết chồng nhiều hàm tương tự nhau  int max(int a, int b) { return a>b ? a:b; } double max(double a, double b) { return a>b ? a:b; } float max(float a, float b) { return a>b ? a:b; }  lập trình ở mức độ khái quát cao hơn: coi kiểu của biến cũng là tham số (type parameterization)  Khuôn mẫu hàm (function template): là khái niệm giúp định nghĩa những hàm mà chưa xác định kiểu của các tham số  Có thể hiểu là viết gộp chung các hàm chồng giống nhau về mặt thuật toán  Kiểu của các tham số là tham số của khuôn mẫu 3 EE3490: Kỹ thuật lập trình – HK1 2017/2018 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội Định nghĩa hàm khái quát  Ví dụ 1:  template void swap(T& a, T& b) { T c = a; a = b; b = c; }  T được giả định là kiểu của các tham số a, b và biến c  T sẽ được xác định khi gọi hàm  T là tham số của khuôn mẫu, trong khi a, b là tham số của hàm  Ví dụ 2:  template void push(Containter& s, Object o) {...}  Có thể dùng từ khoá “class” thay vì “typename”  template void swap(T& a, T& b) {...} 4 EE3490: Kỹ thuật lập trình – HK1 2017/2018 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội Gọi hàm khái quát  Gọi với kiểu tường minh:  max(a, b); max(x, y); swap(s1, s2); swap(p1, p2); push(l, st);  Gọi với kiểu ngầm định:  int a, b; double x, y; max(a, b); //  max(a, b); max(x, y); //  max(x, y); max(a, x); //  lỗi 5 EE3490: Kỹ thuật lập trình – HK1 2017/2018 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội Chồng hàm khái quát  Các khuôn mẫu hàm cũng có thể được định nghĩa chồng  template T max(T a, T b) { ... } template T max(T a, T b, T c) { ... } template T max(T* arr, int n) { ... }  Gọi hàm chồng  max(10, 20); max('c', 'f'); max(1.5, 2.1, 3.14); max("1un34k", 6); 6 EE3490: Kỹ thuật lập trình – HK1 2017/2018 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội Cá biệt hoá hàm khái quát  Có thể định nghĩa các phiên bản cho trường hợp riêng của một hàm khái quát  template T max(T a, T b) { return a>b ? a:b; } template const char* max(const char* s1, const char* s2) { return strcmp(s1, s2) == 1 ? s1:s2; }  Cá biệt hoá không hoàn toàn  template void push(Containter& s, Object o) {...} template void push(Stack& s, Object o) { ... } 7 EE3490: Kỹ thuật lập trình – HK1 2017/2018 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội Không chỉ khái quát hoá kiểu của tham số  Khái quát hoá kiểu trả về  template Product makeProd(Worker& w) { w.work(); return w.getResult(); }  Khái quát hoá kiểu của biến cục bộ  template void forEach(const List& l) { Iterator i = l.first(); for (; i!=l.last(); i = i.next()) doSmth(i.get()); } 8 EE3490: Kỹ thuật lập trình – HK1 2017/2018 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội Tham số của khuôn mẫu không chỉ là kiểu...  Có thể là các giá trị sử dụng giá trị đó như hằng  template Object* makeArray() { return new Object[N]; } string* p1 = makeArray(); SinhVien* p2 = makeArray();  Cả giá trị và kiểu cùng là tham số  template T range(T t) { return t<min ? min : (t>max ? max : t); } y = range(x); b = range(a); 9 EE3490: Kỹ thuật lập trình – HK1 2017/2018 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội Lưu ý khi dùng các hàm khái quát  Phần thực thi của các khuôn mẫu hàm chỉ thực sự được biên dịch khi có thông tin về kiểu  nếu viết khuôn mẫu hàm trong thư viện thì cả nguyên mẫu và phần thực thi của hàm đều viết trong file .h (có thể viết riêng phần thực thi ra một file khác rồi include vào file .h)  Khi sử dụng tham số thuộc kiểu gì thì trình biên dịch mới sinh ra hàm tương ứng với kiểu tham số đó  int a = 10, b = 20; swap(a, b); //  sinh ra: void swap(int&, int&) {...} swap(x, y); //  void swap(float&, float&) {...}  Có thể khi dùng ở trường hợp cụ thể mới phát sinh lỗi cú pháp  template T divide(T a, T b) { return a/b; } double z = divide(1.5, 0.5); // OK const char* c = divide("ssss", "dddd"); // lỗi 10 EE3490: Kỹ thuật lập trình – HK1 2017/2018 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội Khuôn mẫu lớp (Class templates) 11 EE3490: Kỹ thuật lập trình – HK1 2017/2018 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội Khái niệm  Tương tự với hàm, các lớp cũng có thể được khái quát hoá  khuôn mẫu lớp  Lớp được khai báo sử dụng những kiểu chưa xác định và được tham số hoá  template class Array { private: int N; Object* p; public: void setAt(int i, Object o) {...} Object& operator[](int i) {...} ... }; 12 EE3490: Kỹ thuật lập trình – HK1 2017/2018 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội Phương thức bên ngoài khuôn mẫu lớp 13 template class Array { private: int N; Object* p; public: Array(int N); ~Array(); void setAt(int i, Object o); int length() const; Object& operator[](int i); }; template Array::Array(int N) { this->N = N; p = new Object[N]; } template Array::~Array() { delete[] p; } template void Array:: setAt(int i, Object o) { p[i] = o; } template int Array::length() const { return N; } template Object& Array:: operator[](int i) { return p[i]; }  Các phương thức ở ngoài được khai báo tương tự như các khuôn mẫu hàm EE3490: Kỹ thuật lập trình – HK1 2017/2018 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội Sử dụng đối tượng của lớp khái quát  Ví dụ:  Array a(10); for (int i=0; i<10; i++) a.setAt(i, i*2); typedef Array StrArray; StrArray s(2); s[0] = string("abcd"); s[1] = string("12345");  Kết hợp khuôn mẫu lớp và hàm  template void printArray(Array &a) { for (int i=0; i<a.length(); i++) cout << a[i]; } printArray(a); printArray(s); 14 EE3490: Kỹ thuật lập trình – HK1 2017/2018 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội Hàm bạn và lớp bạn  Bạn riêng của từng lớp tương ứng  template class Array { ... friend void sort(Array& a); friend class Serializer; };  Bạn chung của tất cả các lớp  template class A { ... friend void func1(); template friend int func2(); friend class B; }; 15 EE3490: Kỹ thuật lập trình – HK1 2017/2018 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội Cá biệt hoá lớp khái quát  template class Map { ... Data find(Key k); }; // cá biệt hoá hoàn toàn template class Map { ... int find(int k); }; // cá biệt hoá không hoàn toàn template class Map { ... Data find(int k); }; 16 EE3490: Kỹ thuật lập trình – HK1 2017/2018 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội Giá trị mặc định của tham số khuôn mẫu  Các tham số của khuôn mẫu lớp có thể có giá trị mặc định  template class Pool { ... }; Pool p1; //  Pool p1; Pool p2; //  Pool p2; Pool p3;  Chú ý: chỉ khuôn mẫu lớp mới có giá trị mặc định của tham số, khuôn mẫu hàm không có(*) 17 * Tuy nhiên, đã được bổ sung trong C++11 EE3490: Kỹ thuật lập trình – HK1 2017/2018 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội Biến static của lớp khái quát  Mỗi lớp được sinh ra từ khuôn mẫu có biến static riêng  template class smartptr { ... static smartptr nullptr; }; template static smartptr smartptr::nullptr; smartptr p1 = smartptr::nullptr; smartptr p2 = smartptr::nullptr;  Tương tự với các phương thức static 18 EE3490: Kỹ thuật lập trình – HK1 2017/2018 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội Các lớp khái quát liên quan  template class Iterator; template class List { ... Iterator begin() { ... } Iterator end() { ... } }; template class Iterator { ... T& getData() { ... } Iterator next() { ... } }; List l; ... Iterator i; for (i = l.begin(); i != l.end(); i = i.next()) cout << i.getData() << endl; 19 EE3490: Kỹ thuật lập trình – HK1 2017/2018 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội Bài tập 1. Viết hàm nhập dữ liệu cho mảng có kiểu bất kỳ 2. Viết hàm sắp xếp một mảng bất kỳ theo 2 cách: (C) sử dụng một hàm so sánh làm cơ sở cho thứ tự sắp xếp, (C++) dùng template void sortC(void* a, int n, int size, int (*compare)(void*, void*)); template void sortCpp(T* a, int n); 3. Viết lớp Stack cho phép chứa dữ liệu kiểu bất kỳ mà không cần dùng con trỏ void* 4. Sửa lại lớp DSLK cho phép chứa dữ liệu kiểu bất kỳ 5. Sửa lại lớp Iterator cho DSLK ở trên 6. Sửa lớp Vector cho phép làm việc với cả dữ liệu float và double 7. Sửa lớp String cho phép làm việc với cả chuỗi ASCII (char) và Unicode (wchar_t) 20