Bài giảng Lập trình hướng đối tượng - Thư viện chuẩn C++ Standard Template Library (STL)

rỏ tới các phần tử trong một container các toán tử iterator cho mọi container * truy nhập phần tử được trỏ tới ++ trỏ tới phần tử tiếp theo begin() trả về iterator trỏ tới phần tử đầu tiên end() trả về iterator trỏ tới phần tử đặc biệt chặn cuối container Các loại Iterator Input	(ví dụ: istream_iterator) Đọc các phần tử từ một container, hỗ trợ ++ (chỉ tiến) Output	(ví dụ: ostream_iterator) Ghi các phần tử vào container, hỗ trợ ++ (chỉ tiến) Forward	(ví dụ: hash_set 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 (--,-=) Random access	(Ví dụ: vector iterator) Như bidirectional, nhưng còn có thể nhảy tới phần tử tùy ý Các loại Iterator được hỗ trợ 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 phép toán đối với Iterator 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à + , +=, -, -=, >, >=, 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 random access iterator vector Sequence Container Khai báo 	 std::vector v; type là kiểu dữ liệu của phần tử dữ liệu (int, float, v.v..) Iterator std::vector::iterator iterVar; trường hợp thông thường std::vector::const_iterator iterVar; const_iterator không thể sửa đổi các phần tử std::vector::reverse_iterator iterVar; Duyệt các phần tử theo thứ tự ngược (từ cuối lên đầu) Dùng rbegin để lấy điểm bắt đầu Dùng rend để lấy điểm kết thúc 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 v từ 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 v.clear() Xóa toàn bộ container vector Sequence Container Các hàm thành viên của vector 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 1 // Fig. 21.14: fig21_14.cpp 2 // Demonstrating standard library vector class template. 3 #include 4 5 using std::cout; 6 using std::cin; 7 using std::endl; 8 9 #include // vector class-template definition 10 11 // prototype for function template printVector 12 template 13 void printVector( const std::vector &integers2 ); 14 15 int main() 16 { 17 const int SIZE = 6; 18 int array[ SIZE ] = { 1, 2, 3, 4, 5, 6 }; 19 20 std::vector integers; 21 22 cout ::reverse_iterator reverseIterator; 47 48 for ( reverseIterator = integers.rbegin(); 49 reverseIterator!= integers.rend(); 50 ++reverseIterator ) 51 cout 61 void printVector( const std::vector &integers2 ) 62 { 63 std::vector::const_iterator constIterator; 64 65 for ( constIterator = integers2.begin(); 66 constIterator != integers2.end(); 67 constIterator++ ) 68 cout 5 6 using std::cout; 7 using std::endl; 8 9 #include // vector class-template definition 10 #include // copy algorithm 11 12 int main() 13 { 14 const int SIZE = 6; 15 int array[ SIZE ] = { 1, 2, 3, 4, 5, 6 }; 16 17 std::vector integers( array, array + SIZE ); 18 std::ostream_iterator output( cout, " " ); 19 20 cout subscript   Vector integers after erasing first element: 22 2 10 4 5 6 After erasing all elements, vector integers is empty   Contents of vector integers before clear: 1 2 3 4 5 6 After clear, vector integers is empty Container Adapter Container adapter stack, queue và priority_queue Không phải first class container, cho nên Không hỗ trợ iterator Không cung cấp cấu trúc dữ liệu Lập trình viên có thể chọn cách cài đặt (sử dụng cấu trúc dữ liệu nào) đều cung cấp các hàm thành viên push và pop bên cạch các hàm thành viên khác. stack Adapter stack Header chèn và xóa tại một đầu Cấu trúc Last-in, first-out (LIFO) Có thể chọn cài đặt bằng vector, list, hoặc deque (mặc định) Khai báo 	stack > myStack; 	stack > myOtherStack; 	stack anotherStack; // default deque chọn cài đặt là vector, list hay deque không làm thay đổi hành vi, chỉ ảnh hưởng tới hiệu quả (cài bằng deque và vector là nhanh nhất) 1 // Fig. 21.23: fig21_23.cpp 2 // Standard library adapter stack test program. 3 #include 4 5 using std::cout; 6 using std::endl; 7 8 #include // stack adapter definition 9 #include // vector class-template definition 10 #include // list class-template definition 11 12 // popElements function-template prototype 13 template 14 void popElements( T &stackRef ); 15 16 int main() 17 { 18 // stack with default underlying deque 19 std::stack intDequeStack; 20 21 // stack with underlying vector 22 std::stack > intVectorStack; 23 24 // stack with underlying list 25 std::stack > intListStack; 26 27 // push the values 0-9 onto each stack 28 for ( int i = 0; i 51 void popElements( T &stackRef ) 52 { 53 while ( !stackRef.empty() ) { 54 cout remove, remove_if, remove_copy và remove_copy_if remove remove( iter1, iter2, value); Bỏ mọi phần tử có giá trị value trong khoảng (iter1-iter2) theo cách sau: Chuyển các phần tử có giá trị value xuống cuối không thay đổi kích thước của container hoặc thực sự xóa các phần tử Trả về iterator tới kết thúc “mới” của container các phần tử sau kết thúc mới là không xác định remove_copy remove_copy(iter1, iter2, iter3, value); trong khoảng iter1-iter2, chép các phần tử khác value vào iter3 (output iterator) remove, remove_if, remove_copy và remove_copy_if remove_if giống remove trả về iterator tới phần tử cuối cùng bỏ các phần tử mà hàm trả về true 	remove_if(iter1,iter2, function); các phần tử được truyền cho function, hàm này trả về giá trị bool remove_copy_if giống remove_copy và remove_if 	remove_copy_if(iter1, iter2, iter3, function); Các thuật toán toán học random_shuffle(iter1, iter2) xáo trộn các phần tử trong khoảng một cách ngẫu nhiên count(iter1, iter2, value) trả về số lần xuất hiện của value trong khoảng count_if(iter1, iter2, function) đếm số phần tử làm function trả về true min_element(iter1, iter2) trả về iterator tới phần tử nhỏ nhất max_element(iter1, iter2) trả về iterator tới phần tử lớn nhất Các thuật toán toán học accumulate(iter1, iter2) trả về tổng các phần tử trong khoảng for_each(iter1, iter2, function) Gọi hàm function cho mỗi phần tử trong khoảng không sửa đổi phần tử transform(iter1, iter2, iter3, function) 	 gọi function cho mọi phần tử trong khoảng iter1-iter2, kết quả ghi vào iter3 Các thuật toán tìm kiếm và sắp xếp cơ bản find(iter1, iter2, value) trả về iterator tới lần xuất hiện đầu tiên (trong khoảng) của value find_if(iter1, iter2, function) như find trả về iterator khi function trả về true sort(iter1, iter2) sắp xếp các phần tử theo thứ tự tăng dần binary_search(iter1, iter2, value) tìmgiá trị trong dãy sắp xếp tăng dần, sử dụng thuật toán tìm kiếm nhị phân 1 // Fig. 21.31: fig21_31.cpp 2 // Standard library search and sort algorithms. 3 #include 4 5 using std::cout; 6 using std::endl; 7 8 #include // algorithm definitions 9 #include // vector class-template definition 10 11 bool greater10( int value ); // prototype 12 13 int main() 14 { 15 const int SIZE = 10; 16 int a[ SIZE ] = { 10, 2, 17, 5, 16, 8, 13, 11, 20, 7 }; 17 18 std::vector v( a, a + SIZE ); 19 std::ostream_iterator output( cout, " " ); 20 21 cout ::iterator location; 26 location = std::find( v.begin(), v.end(), 16 ); 27 28 if ( location != v.end() ) 29 cout 10; 81 82 } // end function greater10 Vector v contains: 10 2 17 5 16 8 13 11 20 7   Found 16 at location 4 100 not found   The first value greater than 10 is 17 found at location 2   Vector v after sort: 2 5 7 8 10 11 13 16 17 20   13 was found in v 100 was not found in v Function Object – functor Function object () Các đối tượng có thể gọi như hàm bằng toán tử () 1 // Fig. 21.42: fig21_42.cpp 2 // Demonstrating function objects. 3 #include 4 5 using std::cout; 6 using std::endl; 7 8 #include // vector class-template definition 9 #include // copy algorithm 10 #include // accumulate algorithm 11 #include // binary_function definition 12 13 // binary function adds square of its second argument and 14 // running total in its first argument, then returns sum 15 int sumSquares( int total, int value ) 16 { 17 return total + value * value; 18 19 } // end function sumSquares 20 21 // binary function class template defines overloaded operator() 22 // that adds suare of its second argument and running total in 23 // its first argument, then returns sum 24 template 25 class SumSquaresClass : public std::binary_function { 26 27 public: 28 29 // add square of value to total and return result 30 const T operator()( const T &total, const T &value ) 31 { 32 return total + value * value; 33 34 } // end function operator() 35 36 }; // end class SumSquaresClass 37 fig21_42.cpp(3 of 4) 38 int main() 39 { 40 const int SIZE = 10; 41 int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 42 43 std::vector integers( array, array + SIZE ); 44 45 std::ostream_iterator output( cout, " " ); 46 47 int result = 0; 48 49 cout () ); 64 65 cout : " : 385