Đề tài STL (Standard Template Library)

 nên thao tác trên các đối tượng khác nhau. Templete có phải là cách duy nhất để thực hiện công việc không? - Người ta cũng có thể sử dụng tính kế thừa trong C++ để tạo ra các tập hợp khác nhau của các đối tượng khác nhau. Khi đó người ta cần dùng kết hợp thừa kế và đa thừa kế. - Tuy nhiên khó khăn khi sử dụng tính kế thừa trong trường hợp này là cần phải xác định trước một lớp nào đó, lập trình viên cũng cần xác định trước các lớp thừa kế được xây dựng như thế nào để biết được lớp mới cần thừ kế những thuộc tính nào. Các khó khăn này làm công việc lập trình nặng nề hơn. --> Kết luận: để xây dựng các tập hợp đối tượng, sử dụng template sẽ thuận tiện hơn rất nhiều so với sử dụng tính kế thừa. STL - string Thư viện chuẩn STL (Standard Template Library) cung cấp kiểu string (xâu ký tự), giúp các bạn tránh khỏi nhiều phiền phức thường gặp ở thư viện . Các chỉ thị #include cần khai báo để sử dụng string : 	#include 	using std::string; 	//using namespace std; STL - string 1. Các toán tử trên String (Operating on strings) Các toán tử +, += dùng để ghép hai chuỗi và cũng để ghép một ký tự với chuỗi. Các phép so sánh theo thứ tự từ điển: = = (bằng nhau), != (khác nhau), > (lớn hơn), >= (lớn hơn hay bằng), > với cin để nhập một chuỗi ký tự đến khi gặp một khoảng trống thì dừng. STL - string Ví dụ: char st[]=“ABCDEF”; string s, s1, s2, s3; s=“XYZ”; s1=" ABC"; s2=" MNP"; s3 = s1+ s2; s3+= s1; cout có bổ sung thêm một số phương thức và thuộc tính, do đó, nó có toàn bộ các tính chất của 1 vector, vd hàm size(), push_back(), toán tử [] … Phương thức	 Mô tả v.size()	Số lượng phần tử. v.empty () 	Trả về 1 nếu chuỗi rỗng, 0 nếu ngược lại. v.max_size()	Trả về số lượng phần tử tối đa đã được cấp phát. v1 == v2 	Trả về 1 nếu hai chuỗi giống nhau. v1 != v2 	Trả về 1 nếu hai chuỗi khác nhau. v.begin()	Trả về iterator đầu tin của chuỗi. v.end()	Trả về iterator lặp cuối cng của chuỗi. v.front() 	Trả về tham chiếu đến phần tử đầu tin của chuỗi. v.back()	Trả về tham chiếu đến phần tử cuối cng của chuỗi. v1.swap(v2) 	Hoán đổi 2 chuỗi với nhau (giống việc hoán đổi giá 	trị của 2 biến). STL - string 2. Tìm kiếm trên string: //Ví dụ hàm find(), rfind(). #include #include #include using namespace std; int main () { 	string str="ConCho chay qua rao"; 	cout #include #include using namespace std; int main () { 	string str="con cho la con cho con. Con meo ko phai la con cho"; 	str.replace(4, 3, "CHO"); // "con CHO la con cho con. Con meo ko 	//phai la con cho"; 	cout #include #include using namespace std; int main () { 	string str="day cung la xau thu"; 	str.erase(0, 3); // " cung la xau thu" 	cout #include #include using namespace std; int main () { 	string str="day la .. xau thu"; 	string istr = "them"; 	str.insert(8, istr); 	cout #include #include using namespace std; int main () { 	string s="ConCho chay qua rao"; 	cout = ) được định nghĩa sẵn. Tuy nhiên, nếu muốn so sánh một phần của một chuỗi thì sẽ cần sử dụng phương thức compare(): int compare ( const string& str ) const; int compare ( const char* s ) const; int compare ( size_t pos1, size_t n1, const string& str ) const; int compare ( size_t pos1, size_t n1, const char* s) const; int compare ( size_t pos1, size_t n1, const string& str, size_t pos2, size_t n2 ) const; int compare ( size_t pos1, size_t n1, const char* s, size_t n2) const; Hàm trả về giá trị 0 nếu 2 chuỗi = nhau, 0 nếu chuỗi 1 > chuỗi 2. STL - string Ví dụ: // comparing apples with apples #include #include using namespace std; int main () { 	string str1 ("green apple"); 	string str2 ("red apple"); 	if (str1.compare(str2) != 0) 	cout >= == != swap Các hàm thành viên của first-class container begin, end rbegin, rend erase, clear vector Sequence Container vector cấu trúc dữ liệu với các vùng nhớ liên tiếp truy nhập các phần tử bằng toán tử [ ] sử dụng khi dữ liệu cần được sắp xếp và truy nhập dễ dàng Cơchế hoạt động khi hết bộ nhớ cấp phát một vùng nhớ liên lục lớn hơn tự sao chép ra vùng nhớ mới trả lại vùng nhớ cũ sử dụng randomaccess iterator Để có thể dùng vector thì bạn phải thêm 1 header #include và phải có using std::vector; Cú pháp của vector cũng rất đơn giản, 	 std::vector v; 	type là kiểu dữ liệu của phần tử dữ liệu (int, float, v.v..) ví dụ : 	vector v ; 	vector v(10); 	vector v(10, 2); Khai báo vector v có kiểu int. Chú ý kiểu của vector được để trong 2 dấu ngoặc nhọn. vector Sequence Container vector Sequence Container Các hàm thành viên của vector v.push_back(value) thêm phần tử vào cuối (sequence container nào cũng có hàm này). v.size() kích thước hiện tại của vector v.capacity() kích thước có thể lưu trữ trước khi phải cấp phát lại khi cấp phát lại sẽ cấp phát kích thước gấp đôi vector v(a, a + SIZE) tạo vector vtừ SIZE phần tử đầu tiên của mảng a vector Sequence Container Các hàm thành viên của vector 	 v.insert(iterator, value ) 	chèn value vào trước vị trí của iterator v.insert(iterator, array , array + SIZE) chèn vào vector SIZE phần tử đầu tiên của mảng array v.erase( iterator ) xóa phần tử khỏi container v.erase( iter1, iter2 ) xóa bỏ các phần tử bắt đầu từ iter1 đến hết phần tử liền trước iter2 Các hàm thành viên của vector v.clear() Xóa toàn bộ container v.front(), v.back() Trả về phần tử đầu tiên và cuối cùng v.[elementNumber] = value; Gán giá trị value cho một phần tử v.at[elementNumber] = value; Như trên, nhưng kèm theo kiểm tra chỉ số hợp lệ có thể ném ngoại lệ out_of_bounds vector Sequence Container Mảng 2 chiều với Vector : vector Sequence Container #include using namespace std; int main() { 	vector > matrix(3, vector(2,0)); 	//chu y viet > > de khong nham voi toan tu >> 	for(int x = 0; x list List có thể khởi tạo bằng constructor mặc định hoặc sao chép từ mảng, từ list khác hay container khác: int a[10]; list list0; list list1(a+2,a+7); list list2( list1.begin()++, --list1.end()); Ví dụ tạo một list, đưa phần tử với và truy xuất phần tử list list1; list1.push_back("Zebra");list1.push_back("Penguin");list1.push_front("Lion"); list::iterator i; for(i=list1.begin();i!=list1.end();++i) 	cout > listOfList; Các phương thức cơ bản của list list c.size() 	Số lượng phần tử của list c. empty () 	Trả về 1 nếu danh sách là trống, 0 nếu ngược lại c.max_size() 	Trả về số lượng phần tử tối đa của list c1 == c2 	Trả về 1 nếu hai danh sách giống nhau c1 != c2 	Trả về 1 nếu hai danh sách khác nhau (nhanh hơn 	!(c1==c2)) c1 iterator) Kết hợp input iterator và output iterator Multi-pass (có thể duyệt chuỗi nhiều lần) Bidirectional 	(Ví dụ: list iterator) Như forward iterator, nhưng có thể lùi (--,-=) Randomaccess 	(Ví dụ: vector iterator) Như bidirectional, nhưng còn có thể nhảy tới phần tử tùy ý Sequence container vector: random access deque: random access list: bidirectional Associative container(hỗ trợ các loại bidirectional) set, multiset,map, multimap Container adapter (không hỗ trợ iterator) stack, queue, priority_queue Các loại Iterator được hỗ trợ Input iterator ++ , =*p , -> , == , != Output iterator ++ , *p= , p = p1 Forward iterator Kết hợp các toán tử của input và output iterator Bidirectional iterator các toán tử cho forward, và -- Random iterator các toán tử cho bidirectional, và + , +=, -, -=, >, >=, #include using namespace std; int main() { int A[] = {3,2,3,1,2,3,5,3}; int n = sizeof(A)/sizeof(*A); list V; for (int i=0; i::iterator vi; cout ::reverse_iterator rvi; cout Algorithm (các thuật toán ) Do thư viện gồm rất nhiều hàm khác nhau, người ta phân thành các nhóm hàm sau: - Nhóm các hàm không thay đổi giá trị của container - Nhóm các hàm thay đổi giá trị của container - Nhóm các hàm sắp xếp - Nhóm các hàm trên danh sách được sắp xếp - Nhóm các hàm trộn - Nhóm các làm trên heap - Nhóm các hàm tìm min/max. Algorithm (các thuật toán ) Nhóm các hàm không thay đổi giá trị của container Các thuật toán tìm kiếm: bao gồm find(), find_if() tìm theo điều kiện, search() dùng để so khớp 1 chuỗi liên tiếp các phần tử cho trước, hàm search_n tìm kiếm với số lần lặp xác định, hàm find_end tìm kết quả cuối cùng, find_first_not_of(), find_last_not_of() … Các thuật toán đếm: - Hàm count dùng để đếm số lượng phần tử trong một chuỗi các phần tử cho trước 	list l;l.push_back("hello");l.push_back("world"); 	cout() ); Hàm is_sorted kiểm tra xem 1 chuỗi đã được sắp xếp hay chưa: int A[] = {1, 4, 2, 8, 5, 7}; const int N = sizeof(A) / sizeof(int); assert(!is_sorted(A, A + N)); sort(A, A + N); assert(is_sorted(A, A + N));  NHÓM CÁC HÀM TRÊN DANH SÁCH ĐƯỢC SẮP XẾP - Tìm cận dưới và cận trên (lower_bound, upper_bound) - Tìm kiếm nhị phân (binary_search) - Trộn 2 danh sách đã được sắp xếp (merge) - Các phép toán trên tập hợp: 	- Xác nhận tập con includes 	- Hợp (set_union)- Giao (set_intersection) 	- Phép loại ( set_difference ) lấy ra các phần tử sai khác 	- Phép trừ tập hợp ( set_symmetric_difference ) CÁC HÀM TRÊN HEAP Bao gồm tạo heap (make_heap), thêm phần tử vào heap (push_heap), xóa phần tử khỏi heap (pop_heap), sắp xếp heap (sort_heap) #include #include #include using namespace std; int main () { 	int myints[] = {10,20,30,5,15}; 	vector v(myints,myints+5); 	vector::iterator it; make_heap (v.begin(),v.end()); cout << "initial max heap : " << v.front() << endl; pop_heap (v.begin(),v.end()); v.pop_back(); cout << "max heap after pop : " << v.front() << endl; v.push_back(99); push_heap (v.begin(),v.end()); cout << "max heap after push: " << v.front() << endl; sort_heap (v.begin(),v.end()); cout << "final sorted range :"; for (unsigned i=0; i<v.size(); i++) 	cout << " " << v[i]; return 0; } CÁC HÀM TÌM MIN & MAX Tìm min & max trong 1 cặp: const int x = min(3, 9), y = max(3, 9); assert(x == 3); assert(y == 9); Tìm min & max trong 1 tập int A[] = {3,4,2,6,3,1,2,3,2,3,4,5,6,4,3,2,1}; int N = sizeof(A) / sizeof(*A); cout << "So nho nhat trong mang: " << *min_element(A, A+N) << endl; cout << "So lon nhat trong mang: " << *max_element(A, A+N) << endl; CÂU HỎI ? The End