STL for newbies: CONTAINERS (Thư viện lưu trữ) - part 3

Containers adpators
-  Một container là một đối tượng cụ thể lưu trữ một tập các đối tượng khác (các phần tử 
của nó). Nó được thực hiện như các lớp mẫu ( class templates). 
-  Container quản lý không gian lưu trữ cho các phần tử của nó và cung cấp các hàm 
thành viên (member function) để truy cập tới chúng, hoặc trực tiếp hoặc thông qua 
các biến lặp (iterator – giống như con trỏ). 
-  Container xây dựng các cấu trúc thuờng sử dụng trong lập trình như: mảng động - 
dynamic arrays (vector), hàng đợi – queues (queue), hàng đợi ưu tiên – heaps (priority 
queue), danh sách kiên kết – linked list (list), cây – trees (set), mảng ánh xạ - 
associative arrays (map),... 
-  Nhiều container chứa một số hàm thành viên giống nhau. Quyết định sử dụng loại 
container nào cho nhu cầu cụ thể nói chung không chỉ phụ thuộc vào các hàm được 
cung cấp mà còn phải dựa vào hiệu quả của các hàm thành viên của nó (độ phức tạp 
(từ giờ mình sẽ viết tắt là ĐPT) của các hàm). Điều này đặc biệt đúng với container 
dãy (sequence containers), mà trong đó có sự khác nhau về độ phức tạp đối với các 
thao tác chèn/xóa phần tử hay truy cập vào phần tử. 
Stack (Ngăn xếp): 
-  Stack là một loại container adaptor, được thiết kế để hoạt động theo kiểu LIFO (Last - 
in first - out) (vào sau ra trước), tức là một kiểu danh sách mà việc bổ sung và loại bỏ 
một phần tử được thực hiển ở cuối danh sách. Vị trí cuối cùng của stack gọi là đỉnh 
(top) của ngăn xếp. 



Khai báo: #include <stack>
Các hàm thành viên: 
-  size : trả về kích thước hiện tại của stack. ĐPT O(1). 
-  empty : true stack nếu rỗng, và ngược lại. ĐPT O(1). 
-  push : đẩy phần tử vào stack. ĐPT O(1). 
-  pop : loại bỏ phẩn tử ở đỉnh của stack. ĐPT O(1). 
-  top : truy cập tới phần tử ở đỉnh stack. ĐPT O(1). 
Chương trình demo: 
#include <iostream> 
#include <stack> 
using namespace std; 
stack <int> s; 
int i; 
main() { 
for (i=1;i<=5;i++) s.push(i); // s={1,2,3,4,5}
s.push(100);  // s={1,2,3,4,5,100} 
cout << s.top() << endl;  // In ra 100 
s.pop();  // s={1,2,3,4,5} 
cout << s.empty() << endl;  // In ra 0 
cout << s.size() << endl;  // In ra 5 
system("pause"); 
} 
Queue (Hàng đợi): 
-  Queue là một loại container adaptor, được thiết kế để hoạt động theo kiểu FIFO (First 
- in first - out) (vào trước ra trước), tức là một kiểu danh sách mà việc bổ sung được 
thực hiển ở cuối danh sách và loại bỏ ở đầu danh sách. 
-  Trong queue, có hai vị trí quan trọng là vị trí đầu danh sách (front), nơi phần tử được 
lấy ra, và vị trí cuối danh sách (back), nơi phần tử cuối cùng được thêm vào. 
Khai báo: #include <queue>
Các hàm thành viên: 
-  size : trả về kích thước hiện tại của queue. ĐPT O(1). 
-  empty : true nếu queue rỗng, và ngược lại. ĐPT O(1). 
-  push : đẩy vào cuối queue. ĐPT O(1). 
-  pop: loại bỏ phần tử (ở đầu). ĐPT O(1). 
-  front : trả về phần tử ở đầu. ĐPT O(1). 
-  back: trả về phần tử ở cuối. ĐPT O(1). 
Chương trình demo: 
#include <iostream> 
#include <queue> 
using namespace std; 
queue <int> q; 
int i; 
main() { 
for (i=1;i<=5;i++) q.push(i); // q={1,2,3,4,5} 
q.push(100);  // q={1,2,3,4,5,100} 
cout << q.front() << endl;  // In ra 1 
q.pop();  // q={2,3,4,5,100} 
cout << q.back() << endl;  // In ra 100 
cout << q.empty() << endl;  // In ra 0 
cout << q.size() << endl;  // In ra 5 
system("pause"); 
} 
Priority Queue (Hàng đợi ưu tiên): 
-  Priority queue là một loại container adaptor, được thiết kế đặc biệt để phần tử ở đầu 
luôn luôn lớn nhất (theo một quy ước về độ ưu tiên nào đó) so với các phần tử khác. 
-  Nó giống như một heap, mà ở đây là heap max, tức là phần tử có độ ưu tiên lớn nhất 
có thể được lấy ra và các phần tử khác được chèn vào bất kì. 
-  Phép toán so sánh mặc định khi sử dụng priority queue là phép toán less (Xem thêm ở 
thư viện functional) 
-  Để sử dụng priority queue một cách hiệu quả, các bạn nên học cách viết hàm so sánh 
để sử dụng cho linh hoạt cho từng bài toán. 
-  Khai báo: #include <queue>
/*Dạng 1 (sử dụng phép toán mặc định là less)*/ 
priority_queue <int> pq; 
/* Dạng 2 (sử dụng phép toán khác) */ 
priority_queue <int,vector<int>,greater<int> > q; //phép toán greater 
Phép toán khác cũng có thể do người dùng tự định nghĩa. Ví dụ: 
Cách khai báo ở dạng 1 tương đương với: 
/* Dạng sử dụng class so sánh tự định nghĩa */
struct cmp{ 
bool operator() (int a,int b) {return a<b;} 
}; 
main() { 
 …   priority_queue <int,vector<int>,cmp > q;  } 
Các hàm thành viên: 
-  size : trả về kích thước hiện tại của priority queue. ĐPT O(1) 
-  empty : true nếu priority queue rỗng, và ngược lại. ĐPT O(1). 
-  push : đẩy vào priority queue. ĐPT O(logN). 
-  pop: loại bỏ phần tử ở đỉnh priority queue. ĐPT O(logN). 
-  top : trả về phần tử ở đỉnh priority queue. ĐPT O(1). 
Chương trình Demo 1: 
#include <iostream> 
#include <queue> 
#include <vector> 
using namespace std; 
main() { 
priority_queue <int> p; // p={}
p.push(1);  // p={1} 
p.push(5);  // p={1,5}
cout << p.top() << endl; // In ra 5 
p.pop();  // p={1} 
cout << p.top() << endl; // In ra 1
p.push(9);  // p={1,9} 
cout << p.top() << endl; // In ra 9 
system("pause"); 
} 
Chương trình Demo 2: 
#include <iostream> 
#include <queue> 
#include <vector> 
using namespace std; 
main() { 
priority_queue < int , vector <int> , greater <int> > p; // p={} 
p.push(1);  // p={1} 
p.push(5);  // p={1,5} 
cout << p.top() << endl; // In ra 1 
p.pop();  // p={5} 
cout << p.top() << endl; // In ra 5 
p.push(9);  // p={5,9} 
cout << p.top() << endl; // In ra 5 
system("pause"); 
} 
Chương trình Demo 3: 
#include <iostream> 
#include <queue> 
#include <vector> 
using namespace std; 
struct cmp{ 
bool operator() (int a,int b) {return a<b;} 
}; 
main() { 
priority_queue < int , vector <int> , cmp > p; // p={}
p.push(1); // p={1} 
p.push(5);  // p={1,5} 
cout << p.top() << endl; // In ra 1 
p.pop();  // p={5} 
cout << p.top() << endl; // In ra 5 
p.push(9);  // p={5,9}
cout << p.top() << endl; // In ra 5 
system("pause"); 
} 
Xem tiếp: part 4