›
›

Bài giảng Kỹ thuật lập trình - Chương 11: Thư viện chuẩn C++

pdf 28 trang cucquyet12 3510
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Kỹ thuật lập trình - Chương 11: Thư viện chuẩn C++", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_ky_thuat_lap_trinh_chuong_11_thu_vien_chuan_c.pdf

Nội dung text: Bài giảng Kỹ thuật lập trình - Chương 11: Thư viện chuẩn C++

  1. ng 1 ươ 01010101010101011000010101010101010101100001 Chương 11: ThưStateControllerviệnchu01010101001010101001010101010100101010100101ẩnC++ start() 10100110001100100100101010011000110010010010 Ch stop() 11001011001000100000101100101100100010000010 01010101010101011000010101010101010101100001 01010101001010101001010101010100101010100101 N Ơ 10100110001100100100101010011000110010010010y = A*x + B*u; 11001011001000100000101100101100100010000010x = C*x + d*u; LQGController01010101010101011000010101010101010101100001 start() 01010101001010101001010101010100101010100101 stop() 10100110001100100100101010011000110010010010 11001011001000100000101100101100100010000010 11/9/2005 2004, HOÀNG MINH S ©
  2. Nộidung chương 11 11.1 Cấutrúcthư việnchuẩnC++ 11.2 Standard Template Library Giới thiệu chung Các cấu trúc dữ liệu chuẩn Thuật toán tổng quát Các bộ truy lặp và ₫ối tượng hàm N Ơ Ch2004, HOÀNG MINH S ương 11: Thư việnchuẩnC++ 2 © 2005 - HMS ©
  3. 11.1 Cấutrúcthư việnchuẩnC++ ANSI/ISO C++ Công trình của Standard Template Library Alexander Stepanov (STL) Standard Các thư việnC++ Strings Streams Extensions N Standard C Ơ Các thư việnC Library Tấtcả thư việnchuẩnC++ nằmtrongphạmvi tênstd Ch2004, HOÀNG MINH S ương 11: Thư việnchuẩnC++ 3 © 2005 - HMS ©
  4. Standard C Library Tiệníchgiúpgỡ rối Các thao tác vớikiểukýtự hẹp Các thao tác vớikiểukýtự rộng Mã lỗicủacáchàmtrongthư việnchuẩnC Các tính chấtcủakiểusố thựcdấuphảy ₫ộng Hỗ trợ lậptrìnhvớitậpkýtự theo ISO 646 Các tính chấtcủakiểudữ liệusố nguyên Hỗ trợ lậptrìnhvớicácyêucầubản ₫ịa N Ơ Các hàm toán thông dụng Hỗ trợ các lệnh nhảy"xa" Ch2004, HOÀNG MINH S ương 11: Thư việnchuẩnC++ 4 © 2005 - HMS ©
  5. Standard C Library (tiếp) Hỗ trợ kiểmtracáctrường hợpngoạilệ Phụcvụ truy nhậpcácthamsố gọihàm Định nghĩamộtsố macro và kiểu thông dụng Phụcvụ nhập/xuấtdữ liệu thông dụng Các hàm thông dụng Các hàm thao tác vớichuỗikýtự Các hàm và cấutructhời gian và ngày tháng Các hàm thao tác vớichuỗikýtự rộng N Ơ Ch2004, HOÀNG MINH S ương 11: Thư việnchuẩnC++ 5 © 2005 - HMS ©
  6. Standard Extensions Khuôn mẫulớpchoquản lý dãy bit Khuôn mẫulớpchocáckiểusố phức Lớpcơ sở hỗ trợ lậptrìnhvớingoạilệ Khai báo các hàm toán tử new và delete Định nghĩamộtsố lớpngoạilệ thông dụng Hỗ trợ khai thác thông tin kiểu ₫ộng Mở rộng hỗ trợ lậptrìnhbản ₫ịa Các khuôn mẫulớpvàlớpmảng giá trị N Ơ Ch2004, HOÀNG MINH S ương 11: Thư việnchuẩnC++ 6 © 2005 - HMS ©
  7. Strings ƒ Header file: —Khuônmẫulớp: basic_string —Lớp string: typedef basic_string string —Lớpwstring: typedef basic_string wstring ƒ Cho phép lậptrìnhvớicácchuỗikýtự mộtcáchrất thuậntiện —Khôngcầnquantâmtớiquảnlýbộ nhớ₫ộng —Cóthể sao chép, gán giống như các kiểudữ liệucơ bản —Cóthể truy nhậpkýtự qua chỉ số toán tử [] giống như chuỗi ký tự thô N Ơ —Cóthể áp dụng các phép toán +, ==, !=, > , <, —Cóthể truy nhậpchuỗicon, tìmkiếm, thay thế ký tự, —Cóthể áp dụng các thuậttoántổng quát (string, wstring cũng ₫ược coi là các container, có các hàm begin(), end() ) Ch2004, HOÀNG MINH S ương 11: Thư việnchuẩnC++ 7 © 2005 - HMS ©
  8. Sử dụng string ƒ Khai báo biến string string s1( "Hello" ); string s2( 8, 'x' ); // 8 'x' characters string month = "March"; // Implicitly calls constructor ƒ Các hàm truy nhậpthuộctính n=s1.size(); // Number of characters in string n=s1.length(); // Same as size() n=s1.capacity(); // Number of elements that can be // stored without reallocation n=s1.max_size(); // Maximum possible string size if (s1.empty()) // Returns true if empty N Ơ s1.resize(newlength); // Resizes string to newlength Ch2004, HOÀNG MINH S ương 11: Thư việnchuẩnC++ 8 © 2005 - HMS ©
  9. ƒ Phép gán s2 = s1; // Makes a separate copy s2.assign(s1); // Same as s2 = s1; myString.assign(s, start, N); // Copies N characters from s // beginning at index start s2[0] = s3[2]; // Individual characters ƒ Ghép chuỗikýtự s3.append( "pet" ); s3 += "pet"; // Both add "pet" to end of s3 s3.append( s1, start, N ); // Appends N characters from s1, // beginning at index start ƒ So sánh chuỗikýtự (theo vầnABC) ==, !=, , = ƒ Truy nhậpchuỗicon N s = s1.substr( start, N ); Ơ ƒ Hoán ₫ổihaichuỗikýtự: s1.swap(s2); Ch2004, HOÀNG MINH S ương 11: Thư việnchuẩnC++ 9 © 2005 - HMS ©
  10. ƒ Các hàm tìm kiếm: trả về chỉ số nếutìmthấyvàstring::npos nếu không tìm thấy i=s1.find(s2); i=s1.rfind(s2); // Searches right-to-left i=s1.find_first_of(s2); // Returns first occurrence of any // character in s2 i=s1.find_first_of("abcd"); // Returns index of first 'a', // 'b', 'c' or 'd' i=s1.find_last_of(s2); // Finds last occurrence of any char in s2 i=s1.find_first_not_of(s2); // Finds first character NOT in s2 i=s1.find_last_not_of(s2); // Finds last character NOT in s2 ƒ Các hàm xóa và thay thế s1.erase(start); // Erase from start to end of string s1.replace(begin,N,s2); // begin: index in s1 to start replacing // N: number of characters to replace N Ơ // s2: replacement string Ch2004, HOÀNG MINH S ương 11: Thư việnchuẩnC++ 10 © 2005 - HMS ©
  11. Streams ƒ Header files: , , , ƒ Đượcxâydựng lại hoàn toàn —Trêncơ sở khuôn mẫulớp —Về cơ bảnlàtương thích vớicácthư việntrước ₫ây —Linhhoạtvàhiệusuấtcaohơnso vớicácthư việntrước ₫ây —Hỗ trợ kỹ thuậtlậptrìnhtổng quát basic_ios basic_istream basic_ostream N Ơ basic_ifstream basic_iostream basic_ofstream basic_fstream Ch2004, HOÀNG MINH S ương 11: Thư việnchuẩnC++ 11 © 2005 - HMS ©
  12. 11.2 Standard Template Library (STL) ƒ STL ₫ược Alexander Stepanov lần ₫ầu tiên xây dựng, khi từ Nga sang Mỹ làm việc cho Hewlet Packard ƒ STL sử dụng kỹ thuậtlậptrìnhtổng quát và cung cấp: —Cáccấutrúcdữ liệuchuẩn (Containers) —Cácbộ truy lặp(Iterators) —Cácthuậttoántổng quát (Algorithms) ƒ Ý tưởng chính: —VớiN kiểudữ liệu, M cấutrúcdữ liệu, và K thuậttoán, lẽ ra cầnxâydựng N*M cấutrúccụ thể và N *M *K hàm cụ thể — STL (with C++ templates): M cấu trúc + K thuậttoán N Ơ Ch2004, HOÀNG MINH S ương 11: Thư việnchuẩnC++ 12 © 2005 - HMS ©
  13. Ví dụ 1 ƒ Đọcdãysố nguyên từ mộttệp tin “numbers.txt”, tính toán và hiểnthị các giá trị —Nhỏ nhất, lớnnhất — Đứng giữa —Trungbìnhcộng — Trung bình nhân (y1 * y2 * yn)^(1/n) ƒ Bình thường ta cần bao nhiêu dòng lệnh ₫ể thực hiện? —Cấpphátbộ nhớ₫ộng (lớnbaonhiêu?) N —Vònglặp ₫ọccácgiátrị từ tệptin Ơ —Cácvònglặptínhtoán — Ch2004, HOÀNG MINH S ương 11: Thư việnchuẩnC++ 13 © 2005 - HMS ©
  14. Giảiphápsử dụng STL vector v; copy(istream_iterator (ifstream("numbers.txt")), istream_iterator (), back_inserter(v)); sort(v.begin(), v.end()); cout ()),1.0/v.size()) << endl; Ch2004, HOÀNG MINH S ương 11: Thư việnchuẩnC++ 14 © 2005 - HMS ©
  15. Ví dụ 2 ƒ Viếtmộtchương trình in ra các từ và tầnsuấtxuất hiện trong mộttệptin, sắpxếptheothứ tự ABC vector v; map m; copy(istream_iterator (ifstream("words.txt")), istream_iterator (), back_inserter(v)); for (vector ::iterator vi = v.begin(); vi != v.end(); ++vi) ++m[*vi]; N Ơ for (map ::iterator mi = m.begin(); mi != m.end(); ++mi) cout first second << endl; Ch2004, HOÀNG MINH S ương 11: Thư việnchuẩnC++ 15 © 2005 - HMS ©
  16. STL containers ƒ Các cấu trúc dãy (sequence containers) —vector — list (móc nốihaichiều) —deque ƒ Các cấutrúcsắp xếp liên hệ (associative containers) — map, multimap, — set, multiset ƒ Các cấu trúc dẫn xuất (container adapters) — queue, priority_queue, —stack N Ơ Ch2004, HOÀNG MINH S ương 11: Thư việnchuẩnC++ 16 © 2005 - HMS ©
  17. Các hàm thành viên chung ƒ Hàm thành viên cho tất cả các cấu trúc —Hàm tạo mặc ₫ịnh, hàm tạo bản sao —Hàm hủy – empty – max_size, size – = >= == != – swap ƒ Hàm thành viên chỉ cho các cấu trúc dãy – begin, end – rbegin, rend , N – erase clear Ơ Ch2004, HOÀNG MINH S ương 11: Thư việnchuẩnC++ 17 © 2005 - HMS ©
  18. vector ƒ #include ƒ Mộtmảng ₫ộng thựcsự: truy nhậptùyý, co dãn₫ược ƒ Khai báo ₫ơngiản: vector v(10); ƒ Hàm tạo: – vector () – vector (size_t num_elements) – vector (size_t num, T init) ƒ Thuộctính: – v.empty() N Ơ – v.size() – v.capacity() – v.begin() – V.end() Ch2004, HOÀNG MINH S ương 11: Thư việnchuẩnC++ 18 © 2005 - HMS ©
  19. ƒ Bổ sung phầntử – v.push_back(42); – v.insert(iter before, T val) – v.insert(iter before, iter start, iter end) ƒ Truy nhậpphầntử – v.at(i) // reference, range checked! – v[i] // reference, not range checked – v.front() // reference to first element – v.back() // reference to last element z v.back() = 4; // legal if size > 0 ƒ Loạibỏ phầntử – v.pop_back() // removes last element – v.clear() // removes everything N Ơ – v.erase(iterator i) – v.erase(iter start, iter end) Ch2004, HOÀNG MINH S ương 11: Thư việnchuẩnC++ 19 © 2005 - HMS ©
  20. Ví dụ sử dụng vector vector v; for (int i = 0; i ::iterator p = v.begin(); p != v.end(); ++p) N cout << *p; // ABCDEFGHI Ơ Ch2004, HOÀNG MINH S ương 11: Thư việnchuẩnC++ 20 © 2005 - HMS ©
  21. list ƒ Danh sách móc nốihaichiều ƒ Chỉ truy nhậptuầntự ƒ Hàm tạo – list () – list (size_t num_elements) – list (size_t num, T init) ƒ Tính chất – l.empty() – l.size() – l.begin() N – l.end() Ơ Ch2004, HOÀNG MINH S ương 11: Thư việnchuẩnC++ 21 © 2005 - HMS ©
  22. ƒ Bổ sung phầntử – l.push_back(43); – l.push_front(31); – l.insert(iter b, iter s, iter s) / ƒ Truy nhậpphầntử – l.front() // T & – l.back() // T & ƒ Loạibỏ phầntử – l.pop_back() – l.pop_front() – l.erase(iterator i) – l.erase(iter start, iter end) N Ơ Ch2004, HOÀNG MINH S ương 11: Thư việnchuẩnC++ 22 © 2005 - HMS ©
  23. Ví dụ sử dụng list list l; for (int i = 0; i ::iterator i = l.begin(); i != l.end(); ++i) cout << *i; // DCBAABCD N Ơ Ch2004, HOÀNG MINH S ương 11: Thư việnchuẩnC++ 23 © 2005 - HMS ©
  24. Ví dụ sử dụng map #pragma warning(disable: 4786) #include #include #include using namespace std; void main() { map telbook; telbook["Bush"] = 1234567; telbook["Putin"] = 7654321; telbook["Chirac"]= 1231231; // string name; while (cin >> name) { if(telbook.find(name) != telbook.end()) N Ơ cout << "The phone number for " << name << " is " << telbook[name] << '\n'; else cout << "No such name exists\n"; } } Ch2004, HOÀNG MINH S ương 11: Thư việnchuẩnC++ 24 © 2005 - HMS ©
  25. Thuật toán tổng quát ƒ Các thuật toán thông dụng nhất, bao gồm: —Các thuật toán quản lý dữ liệu: copy, count, find, binary_search, sort, merge, replace, —Các thuật toán tập hợp: set_union, set_difference, set_intersect, —Các thuật toán số học: transform, accumulate, generate, for_each ƒ Các thuật toán yêu cầu ₫ầu vào là các bộ truy lặp (iterators), kết quả ₫ầu ra nhiều khi cũng là bộ truy lặp N ƒƠ Mỗi thuật toán có thể áp dụng cho nhiều cấu trúc dữ liệu khác nhau, nhưng không phải tất cả Ch2004, HOÀNG MINH S ương 11: Thư việnchuẩnC++ 25 © 2005 - HMS ©
  26. Khuôn mẫu ₫ối tượng hàm STL function objects Ý nghĩa plus Cộng minus Trừ multiplies Nhân divides Chia modulus Phần dư negate Đảo dấu equal_to Bằng nhau greater Lớn hơn greater_equal Lớn hơn hoặc bằng less Nhỏ hơn less_equal Nhỏ hơn hoặc bằng N Ơ not_equal_to relational logical_and AND logical_not NOT logical_or OR Ch2004, HOÀNG MINH S ương 11: Thư việnchuẩnC++ 26 © 2005 - HMS ©
  27. Các loại iterators ƒ Truy lặp ngẫu nhiên (Random Access Iterators): có thể áp dụng *, ++, , [], !=, ==, >, =, <= ƒ Truy lặp hai chiều (Binary Iterators): có thể áp dụng *, ++, , !=, == ƒ Truy lặp tiến (Forward Iterators): có thể áp dụng *, ++, !=, == ƒ Truy lặp lùi (Backward Iterators): có thể áp dụng *, , !=, == ƒ Nhập (Input Iterators): Đọc/nhập dữ liệu, dịch một chiều (tiến) ƒ Xuất (Output Iterators): Ghi/xuất dữ liệu, dịch một chiều (tiến) N Ơ Ch2004, HOÀNG MINH S ương 11: Thư việnchuẩnC++ 27 © 2005 - HMS ©
  28. Bài tậpvề nhà ƒ Hoàn thiện bài tập chương 10 ƒ Ôn tập các phần ₫ã học ƒ Chuẩn bị sẵn các câu hỏi thảo luận N Ơ Ch2004, HOÀNG MINH S ương 11: Thư việnchuẩnC++ 28 © 2005 - HMS ©