Thư viện khuôn mẫu chuẩn - STL

Chia sẻ: Nguyễn Thị Phương Phương | Ngày: | Loại File: PDF | Số trang:12

Thêm vào BST

Báo xấu

269
lượt xem 12
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Thư viện chuẩn C++ Standard Template Library (STL) Ngoại trừ lớp string, tất cả các thành phần còn lại của thư viện đều là các khuôn mẫu. Tác giả đầu tiên của STL là Alexander Stepanov, mục đích của ông là xây dựng một cách thể hiện tư tưởng lập trình tổng quát, Các khái niệm trong STL được phát triển độc lập với C++.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Thư viện khuôn mẫu chuẩn - STL

1 3 Thư viện khuôn mẫu chuẩn - STL • Thư viện chuẩn C++ gồm 2 phần: – Lớp string – Thư viện khuôn mẫu chuẩn – STL Thư viện chuẩn C++ • Ngoại trừ lớp string, tất cả các thành phần còn lại của thư viện đều là các khuôn mẫu Standard Template Library (STL) • Tác giả đầu tiên của STL là Alexander Stepanov, mục đích của ông là xây dựng một cách thể hiện tư tưởng lập trình tổng quát • Các khái niệm trong STL được phát triển độc lập với C++ – Do đó, ban đầu, STL không phải là một thư viện C++, mà nó đã được chuyển đổi thành thư viện C++ – Nhiều tư tưởng dẫn đến sự phát triển của STL đã được cài đặt phần nào trong Scheme, Ada, và C © 2003 Prentice Hall, Inc. All rights reserved. © 2003 Prentice Hall, Inc. All rights reserved. 2 4 Tổng quan Thư viện khuôn mẫu chuẩn - STL • Thư viện chuẩn C++ bao gồm 32 header file, trong đó ta đã làm quen với một số file (ít nhất đến một • Một số lời khuyên về STL mức độ nào đó) – STL được thiết kế đẹp và hiệu quả - không có thừa kế hay hàm ảo trong bất kỳ định nghĩa nào – Từ tư tưởng lập trình tổng quát dẫn tới những "khối cơ bản" (building block) mà có thể kết hợp với nhau theo đủ kiểu – Tuy làm quen với STL tốn không ít thời gian nhưng thành quả tiềm tàng về năng xuất rất xứng đáng với thời gian đầu tư – Tóm lại – hãy học và hãy sử dụng! • Bài giảng này chỉ để giới thiệu một phần rất nhỏ của STL © 2003 Prentice Hall, Inc. All rights reserved. © 2003 Prentice Hall, Inc. All rights reserved.
5 7 Giới thiệu Standard Template Library (STL) Các hàm thành viên STL • Ba thành phần chính của STL • Các hàm thành viên mọi container đều có – Các thành phần rất mạnh xây dựng dựa trên – Default constructor, copy constructor, destructor template – empty – max_size, size • Container: các cấu trúc dữ liệu template – = < >= == != • Iterator: giống con trỏ, dùng để truy nhập các phần – swap tử dữ liệu của các container • Algorithm: các thuật toán để thao tác dữ liệu, tìm • Các hàm thành viên của first-class container kiếm, sắp xếp, v.v.. – begin, end – rbegin, rend – erase, clear © 2003 Prentice Hall, Inc. All rights reserved. © 2003 Prentice Hall, Inc. All rights reserved. 6 8 Giới thiệu về các Container Giới thiệu về Iterator • 3 loại container – Sequence container – container chuỗi • Iterator tương tự như con trỏ • các cấu trúc dữ liệu tuyến tính (vector, danh sách liên kết) – trỏ tới các phần tử trong một container • first-class container – các toán tử iterator cho mọi container • vector, deque, list • * truy nhập phần tử được trỏ tới – Associative container – container liên kết • ++ trỏ tới phần tử tiếp theo • các cấu trúc phi tuyến, có thể tìm phần tử nhanh chóng • begin() trả về iterator trỏ tới phần tử đầu tiên • first-class container • end() trả về iterator trỏ tới phần tử đặc biệt chặn cuối • các cặp khóa/giá trị container • set, multiset, map, multimap – Container adapter – các bộ tương thích container • stack, queue, priority_queue © 2003 Prentice Hall, Inc. All rights reserved. © 2003 Prentice Hall, Inc. All rights reserved.
9 11 Các loại Iterator Các phép toán đối với Iterator • Input (ví dụ: istream_iterator) • Input iterator – Đọc các phần tử từ một container, hỗ trợ ++,+= (chỉ tiến) ++ , =*p , -> , == , != • Output (ví dụ: ostream_iterator) • Output iterator ++ , *p= , p = p1 – Ghi các phần tử vào container, hỗ trợ ++,+= (chỉ tiến) • Forward iterator • Forward (ví dụ: hash_set iterator) – Kết hợp các toán tử của input và output iterator – Kết hợp input iterator và output iterator – Multi-pass (có thể duyệt chuỗi nhiều lần) • Bidirectional iterator các toán tử cho forward, và • Bidirectional (Ví dụ: list iterator) -- – Như forward iterator, nhưng có thể lùi (--,-=) • Random iterator • Random access (Ví dụ: vector iterator) các toán tử cho bidirectional, và – Như bidirectional, nhưng còn có thể nhảy tới phần tử tùy ý + , +=, -, -=, >, >=,
13 15 Sequence Container vector Sequence Container • 3 loại sequence container: • Khai báo – vector – dựa theo mảng – std::vector v; – deque – dựa theo mảng • type là kiểu dữ liệu của phần tử dữ liệu (int, float, v.v..) – list – danh sách liên kết hiệu quả cao • 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; • Visits elements in reverse order (end to beginning) • Use rbegin to get starting point • Use rend to get ending point © 2003 Prentice Hall, Inc. All rights reserved. © 2003 Prentice Hall, Inc. All rights reserved. 14 16 vector Sequence Container vector Sequence Container • vector • Các hàm thành viên của vector – – v.push_back(value) – cấu trúc dữ liệu với các vùng nhớ liên tiếp • thêm phần tử vào cuối (sequence container nào cũng có hàm • truy nhập các phần tử bằng toán tử [] này). – sử dụng khi dữ liệu cần được sắp xếp và truy nhập dễ dàng – v.size() • Cơ chế hoạt động khi hết bộ nhớ • kích thước hiện tại của vector – cấp phát một vùng nhớ liên lục lớn hơn – v.capacity() – tự sao chép ra vùng nhớ mới • kích thước có thể lưu trữ trước khi phải cấp phát lại – trả lại vùng nhớ cũ • khi cấp phát lại sẽ cấp phát kích thước gấp đôi • sử dụng random access iterator – vector v(a, a + SIZE) • tạo vector v từ SIZE phần tử đầu tiên của mảng a © 2003 Prentice Hall, Inc. All rights reserved. © 2003 Prentice Hall, Inc. All rights reserved.
17 19 1 // Fig. 21.14: fig21_14.cpp Outline vector Sequence Container 2 3 // Demonstrating standard library vector class template. #include 4 fig21_14.cpp 5 using std::cout; (1 of 3) • Các hàm thành viên của vector 6 7 using std::cin; using std::endl; – v.insert(iterator, value ) 8 9 #include // vector class-template definition • chèn value vào trước vị trí của iterator 10 – v.insert(iterator, array , array + SIZE) 11 // prototype for function template printVector 12 template < class T > • chèn vào vector SIZE phần tử đầu tiên của mảng array 13 void printVector( const std::vector< T > &integers2 ); 14 – v.erase( iterator ) 15 int main() • xóa phần tử khỏi container 16 { 17 const int SIZE = 6; Tạo một vector chứa các giá trị int – v.erase( iter1, iter2 ) 18 int array[ SIZE ] = { 1, 2, 3, 4, 5, 6 }; • xóa bỏ các phần tử bắt đầu từ iter1 đến hết phần tử liền 19 trước iter2 20 std::vector< int > integers; Gọi các hàm thành viên. 21 – v.clear() 22 cout
21 23 46 std::vector< int >::reverse_iterator reverseIterator; 1 // Fig. 21.15: fig21_15.cpp Outline 2 // Testing Standard Library vector class template Outline 47 3 // element-manipulation functions. 48 for ( reverseIterator = integers.rbegin(); 4 #include 49 reverseIterator!= integers.rend(); fig21_14.cpp Duyệt ngược vector bằng fig21_15.cpp 5 50 ++reverseIterator ) (3 of 3) một reverse_iterator. 6 using std::cout; (1 of 3) 51 cout output( cout, " " ); Copy range of iterators to output 61 void printVector( const std::vector< T > &integers2 ) 19 (ostream_iterator). 62 { 20 cout ::const_iterator constIterator; 21 std::copy( integers.begin(), integers.end(), output ); 64 22 65 for ( constIterator = integers2.begin(); 23 cout
25 27 52 // erase remaining elements 53 integers.erase( integers.begin(), integers.end() ); Outline 54 cout
29 31 1 // Fig. 21.23: fig21_23.cpp 49 // pop elements from stack object to which stackRef refers Outline Outline 2 // Standard library adapter stack test program. 50 template< class T > 3 #include 51 void popElements( T &stackRef ) 4 fig21_23.cpp 52 { fig21_23.cpp 5 using std::cout; (1 of 3) 53 while ( !stackRef.empty() ) { (3 of 3) 6 using std::endl; 54 cout intDequeStack; 20 21 // stack with underlying vector 22 std::stack< int, std::vector< int > > intVectorStack; 23 24 // stack with underlying list 25 std::stack< int, std::list< int > > intListStack; © 2003 Prentice Hall, Inc. © 2003 Prentice Hall, Inc. 26 All rights reserved. All rights reserved. 30 32 27 // push the values 0-9 onto each stack Outline 28 29 for ( int i = 0; i < 10; ++i ) { intDequeStack.push( i ); Các thuật toán 30 intVectorStack.push( i ); viên push. sử dụng hàm thành fig21_23.cpp 31 intListStack.push( i ); (2 of 3) 32 • Trước STL 33 } // end for 34 – các thư viện của các hãng khác nhau không tương 35 // display and remove elements from each stack 36 cout
33 35 remove, remove_if, remove_copy và Các thuật toán toán học remove_copy_if • remove • random_shuffle(iter1, iter2) – remove( iter1, iter2, value); – xáo trộn các phần tử trong khoảng một cách ngẫu nhiên – Bỏ mọi phần tử có giá trị value trong khoảng (iter1- • count(iter1, iter2, value) iter2) theo cách sau: – trả về số lần xuất hiện của value trong khoảng • Chuyển các phần tử có giá trị value xuống cuối • count_if(iter1, iter2, function) • không thay đổi kích thước của container hoặc thực sự xóa các – đếm số phần tử làm function trả về true phần tử • min_element(iter1, iter2) – Trả về iterator tới kết thúc “mới” của container – trả về iterator tới phần tử nhỏ nhất – các phần tử sau kết thúc mới là không xác định • max_element(iter1, iter2) • remove_copy – trả về iterator tới phần tử lớn nhất – 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) © 2003 Prentice Hall, Inc. All rights reserved. © 2003 Prentice Hall, Inc. All rights reserved. 34 36 remove, remove_if, remove_copy và Các thuật toán toán học remove_copy_if • remove_if • accumulate(iter1, iter2) – giống remove – trả về tổng các phần tử trong khoảng • trả về iterator tới phần tử cuối cùng • for_each(iter1, iter2, function) • bỏ các phần tử mà hàm trả về true – Gọi hàm function cho mỗi phần tử trong khoảng remove_if(iter1,iter2, function); – không sửa đổi phần tử • các phần tử được truyền cho function, hàm này trả về giá • transform(iter1, iter2, iter3, function) trị bool – gọi function cho mọi phần tử trong khoảng iter1-iter2, kết quả ghi vào iter3 • remove_copy_if – giống remove_copy và remove_if remove_copy_if(iter1, iter2, iter3, function); © 2003 Prentice Hall, Inc. All rights reserved. © 2003 Prentice Hall, Inc. All rights reserved.
37 39 27 Outline Các thuật toán tìm kiếm và sắp xếp cơ bản 28 29 if ( location != v.end() ) cout
41 43 77 // determine whether argument is greater than 10 1 // Fig. 21.42: fig21_42.cpp Outline Outline 78 bool greater10( int value ) 2 // Demonstrating function objects. 79 { 3 #include 80 return value > 10; fig21_31.cpp 4 81 (4 of 4) 5 using std::cout; fig21_42.cpp 82 } // end function greater10 6 using std::endl; (1 of 4) fig21_31.cpp 7 output (1 of 1) 8 #include // vector class-template definition Vector v contains: 10 2 17 5 16 8 13 11 20 7 9 #include // copy algorithm 10 #include // accumulate algorithm Found 16 at location 4 11 #include // binary_function definition 100 not found 12 Tạo một hàm để dùng với accumulate. 13 // binary function adds square of its second argument and The first value greater than 10 is 17 14 // running total in its first argument, then returns sum found at location 2 15 int sumSquares( int total, int value ) 16 { Vector v after sort: 2 5 7 8 10 11 13 16 17 20 17 return total + value * value; 18 13 was found in v 19 } // end function sumSquares 100 was not found in v 20 © 2003 Prentice Hall, Inc. © 2003 Prentice Hall, Inc. All rights reserved. All rights reserved. 42 44 21 // binary function class template defines overloaded operator() Outline Function Object – functor 22 23 // that adds suare of its second argument and running total in // its first argument, then returns sum 24 template< class T > STL function objects Type 25 class SumSquaresClass : public std::binary_function< T, T, T > {fig21_42.cpp • Function object divides< T > arithmetic 26 (2 of 4) 27 public: () equal_to< T > relational 28 Tạo một function object (nó còn có thể đóng gói dữ liệu). greater< T > relational – Các đối tượng có thể gọi 29 // add square of value to total and return result Overload operator(). greater_equal< T > relational 30 const T operator()( const T &total, const T &value ) như hàm bằng toán tử () 31 { less< T > relational 32 return total + value * value; less_equal< T > relational 33 logical_and< T > logical 34 } // end function operator() logical_not< T > logical 35 logical_or< T > logical 36 }; // end class SumSquaresClass minus< T > 37 arithmetic modulus< T > arithmetic negate< T > arithmetic not_equal_to< T > relational plus< T > arithmetic multiplies< T > arithmetic © 2003 Prentice Hall, Inc. © 2003 Prentice Hall, Inc. All rights reserved. All rights reserved.
45 38 int main() Outline 39 { 40 const int SIZE = 10; 41 int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 42 fig21_42.cpp 43 std::vector< int > integers( array, array + SIZE ); (3 of 4) 44 45 std::ostream_iterator< int > output( cout, " " ); 46 47 int result = 0; đầu tiên, accumulate 48 truyền 0 và phần tử thứ nhất 49 cout