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

Sequence containers 
-  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ử. 



Iterator: 
Tất cả các container ở 2 loại: Sequence container và Associative container đều hỗ trợ các 
iterator như sau (ví dụ với vector, những loại khác có chức năng cũng vậy). 
/*khai báo iterator “it”*/
vector <int> :: iterator it; 
/* trỏ đến vị trí phần tử đầu tiên của vector */ 
it=vector.begin(); 
/*trỏ đến vị trí kết thúc (không phải phần tử cuối cùng nhé) của vector) */ 
it=vector.end(); 
/* khai báo iterator ngược “rit” */ 
vector <int> :: reverse_iterator rit; rit = vector.rbegin(); 
/* trỏ đến vị trí kết thúc của vector theo chiều ngược (không phải phần tử 
đầu tiên nhé*/
rit = vector.rend(); 
Tất cả các hàm iterator này đều có độ phức tạp O(1). 
Vector (Mảng động): 
Khai báo vector: 
#include <vector> 
... 
/* Vector 1 chiều */ 
/* tạo vector rỗng kiểu dữ liệu int */ 
vector <int> first; 
//tạo vector với 4 phần tử là 100 
vector <int> second (4,100); 
// lấy từ đầu đến cuối vector second 
vector <int> third (second.begin(),second.end()) 
//copy từ vector third 
vector <int> four (third) 
/*Vector 2 chiều*/ 
/* Tạo vector 2 chiều rỗng */ 
vector < vector <int> > v; 
/* khai báo vector 5×10 */
vector < vector <int> > v (5, 10) ; 
/* khai báo 5 vector 1 chiều rỗng */
vector < vector <int> > v (5) ; 
//khai báo vector 5*10 với các phần tử khởi tạo giá trị là 1 
vector < vector <int> > v (5, vector <int> (10,1) ) ; 
Các bạn chú ý 2 dấu “ngoặc” không được viết liền nhau. 
Ví dụ như sau là sai: 
/*Khai báo vector 2 chiều SAI*/ 
vector <vector <int>> v; 
Các hàm thành viên: 
Capacity:
-  size : trả về số lượng phần tử của vector. ĐPT O(1). 
-  empty : trả về true(1) nếu vector rỗng, ngược lại là false(0). ĐPT 
O(1). 
Truy cập tới phần tử:
- operator [] : trả về giá trị phần tử thứ []. ĐPT O(1). 
-  at : tương tự như trên. ĐPT O(1). 
-  front: trả về giá trị phần tử đầu tiên. ĐPT O(1). 
-  back: trả về giá trị phần tử cuối cùng. ĐPT O(1). 
Chỉnh sửa: 
-  push_back : thêm vào ở cuối vector. ĐPT O(1). 
-  pop_back : loại bỏ phần tử ở cuối vector. ĐPT O(1). 
-  insert (iterator,x): chèn “x” vào trước vị trí “iterator” ( x có thể 
là phần tử hay iterator của 1 đoạn phần tử…). ĐPT O(n). 
-  erase : xóa phần tử ở vị trí iterator. ĐPT O(n). 
-  swap : đổi 2 vector cho nhau (ví dụ: first.swap(second);). ĐPT O(1). 
-  clear: xóa vector. ĐPT O(n). 
Nhận xét: 
-  Sử dụng vector sẽ tốt khi: 
o  Truy cập đến phần tử riêng lẻ thông qua vị trí của nó O(1) 
o  Chèn hay xóa ở vị trí cuối cùng O(1). 
-  Vector làm việc giống như một “mảng động”. 
Ví dụ 1: Ví dụ này chủ yếu để làm quen sử dụng các hàm chứ không có đề bài cụ thể. 
#include <iostream> 
#include <vector> 
using namespace std; 
vector <int> v; //Khai báo vector
vector <int>::iterator it; //Khai báo iterator 
vector <int>::reverse_iterator rit; //Khai báo iterator ngược
int i; 
main() { 
for (i=1;i<=5;i++) v.push_back(i); // v={1,2,3,4,5}
cout << v.front() << endl;  // In ra 1
cout << v.back() << endl;  // In ra 5
cout << v.size() << endl;  // In ra 5
v.push_back(9);  // v={1,2,3,4,5,9}
cout << v.size() << endl;  // In ra 6
v.clear();  // v={}
cout << v.empty() << endl;  // In ra 1 (vector rỗng) 
for (i=1;i<=5;i++) v.push_back(i); // v={1,2,3,4,5}
v.pop_back();  // v={1,2,3,4}
cout << v.size() << endl;  // In ra 4
v.erase(v.begin()+1);  // Xóa ptử thứ 1 v={1,3,4}
v.erase(v.begin(),v.begin()+2);  // v={4}
v.insert(v.begin(),100);  // v={100,4} 
v.insert(v.end(),5);  // v={100,4,5}
/*Duyệt theo chỉ số phần tử*/
for (i=0;i<v.size();i++) cout << v[i] << " "; // 100 4 5
cout << endl; 
/*Chú ý: Không nên viết 
for (i=0;i<=v.size()-1;i++) ... 
Vì nếu vector v rỗng thì sẽ dẫn đến sai khi duyệt !!! 
*/ 
/*Duyệt theo iterator*/
for (it=v.begin();it!=v.end();it++) 
cout << *it << " " ; 
//In ra giá trị ma iterator đang trỏ tới "100 4 5"
cout << endl; 
/*Duyệt iterator ngược*/
for (rit=v.rbegin();rit!=v.rend();rit++) 
cout << *rit << " "; // 5 4 100
cout << endl; 
system("pause"); 
} 
Ví dụ 2: Cho đồ thị vô hướng G có n đỉnh (các đỉnh đánh số từ 1 đến n) và m cạnh và không 
có khuyên (đường đi từ 1 đỉnh tới chính đỉnh đó). 
Cài đặt đồ thị bằng danh sách kề và in ra các cạnh kề đối với mỗi cạnh của đồ thị. 
Dữ liệu vào: 
-  Dòng đầu chứa n và m cách nhau bởi dấu cách 
-  M dòng sau, mỗi dòng chứa u và v cho biết có đường đi từ u tới v. Không có cặp đỉnh 
u,v nào chỉ cùng 1 đường đi. 
Dữ liệu ra: 
-  M dòng: Dòng thứ i chứa các đỉnh kề cạnh i theo thứ tự tăng dần và cách nhau bởi 
dấu cách. 
Giới hạn: 1 <= n,m <= 10000 
Ví dụ: 
INPUT  OUTPUT
6 7
1 2 
1 3 
1 5 
2 3 
2 6 
3 5 
6 1 
2 3 5 6
1 3 6 
1 2 5 
1 3 
1 2 
Chương trình mẫu: 
#include <iostream> 
#include <vector> 
using namespace std; 
vector < vector <int> > a (10001);  
//Khai báo vector 2 chiều với 10001 vector 1 chiều rỗng
int m,n,i,j,u,v; 
main() { 
/*Input data*/
cin >> n >> m; 
for (i=1;i<=m;i++) { 
cin >> u >> v; 
a[u].push_back(v); 
a[v].push_back(u); 
} 
/*Sort cạnh kề*/ 
for (i=1;i<=m;i++) 
sort(a[i].begin(),a[i].end()); 
/*Print Result*/ 
for (i=1;i<=m;i++) { 
for (j=0;j<a[i].size();j++) cout << a[i][j] << " "; 
cout << endl; 
} 
system("pause"); 
} 
Deque (Hàng đợi hai đầu): 
-  Deque (thuờng được phát âm giống như “deck”) là từ viết tắt của double-ended 
queue (hàng đợi hai đầu). 
-  Deque có các ưu điểm như: 
o  Các phần tử có thể truy cập thông cua chỉ số vị trí của nó. O(1) 
o  Chèn hoặc xóa phần tử ở cuối hoặc đầu của dãy. O(1) 
Khai báo:  #include <deque>
Capacity:
-  size : trả về số lượng phần tử của deque. ĐPT O(1). 
-  empty : trả về true(1) nếu deque rỗng, ngược lại là false(0). ĐPT 
O(1). 
Truy cập phần tử:
- operator [] : trả về giá trị phần tử thứ []. ĐPT O(1). 
-  at : tương tự như trên. ĐPT O(1). 
-  front: trả về giá trị phần tử đầu tiên. ĐPT O(1). 
-  back: trả về giá trị phần tử cuối cùng. ĐPT O(1). 
Chỉnh sửa: 
-  push_back : thêm phần tử vào ở cuối deque. ĐPT O(1). 
-  push_front : thêm phần tử vào đầu deque. ĐPT O(1). 
-  pop_back : loại bỏ phần tử ở cuối deque. ĐPT O(1). 
-  pop_front : loại bỏ phần tử ở đầu deque. ĐPT O(1). 
-  insert (iterator,x): chèn “x” vào trước vị trí “iterator” ( x có thể 
là phần tử hay iterator của 1 đoạn phần tử…). ĐPT O(n). 
-  erase : xóa phần tử ở vị trí iterator. ĐPT O(n). 
-  swap : đổi 2 deque cho nhau (ví dụ: first.swap(second);). ĐPT O(n). 
clear: xóa vector. ĐPT O(1).
List (Danh sách liên kết): 
-  List được thực hiện như danh sách nối kép (doubly-linked list). Mỗi phần tử trong 
danh sách nối kép có liên kết đến một phần tử trước đó và một phần tử sau nó. 
-  Do đó, list có các ưu điểm như sau: 
o  Chèn và loại bỏ phần tử ở bất cứ vị trí nào trong container. O(1). 
-  Điểm yếu của list là khả năng truy cập tới phần tử thông qua vị trí. O(n). 
-  Khai báo: #include <list> 
Các hàm thành viên: 
Capacity:
-  size : trả về số lượng phần tử của list. ĐPT O(1). 
-  empty : trả về true(1) nếu list rỗng, ngược lại là false(0). ĐPT 
O(1). 
Truy cập phần tử: 
-  front: trả về giá trị phần tử đầu tiên. ĐPT O(1). 
-  back: trả về giá trị phần tử cuối cùng. ĐPT O(1). 
Chỉnh sửa: 
-  push_back : thêm phần tử vào ở cuối list. ĐPT O(1). 
-  push_front : thêm phần tử vào đầu list. ĐPT O(1). 
-  pop_back : loại bỏ phần tử ở cuối list. ĐPT O(1). 
-  pop_front : loại bỏ phần tử ở đầu list. ĐPT O(1). 
-  insert (iterator,x): chèn “x” vào trước vị trí “iterator” ( x có thể 
là phần tử hay iterator của 1 đoạn phần tử…). ĐPT là số phần tử thêm 
vào. 
-  erase : xóa phần tử ở vị trí iterator. ĐPT là số phần tử bị xóa đi. 
-  swap : đổi 2 list cho nhau (ví dụ: first.swap(second);). ĐPT O(1). 
-  clear: xóa list. ĐPT O(n).
Operations: 
-  splice : di chuyển phần tử từ list này sang list khác. ĐPT O(n). 
-  remove (const) : loại bỏ tất cả phần tử trong list bằng const. ĐPT 
O(n). 
-  remove_if (function) : loại bỏ tất các phần tử trong list nếu hàm 
function return true . ĐPT O(n). 
-  unique : loại bỏ các phần tử bị trùng lặp hoặc thỏa mãn hàm nào đó. 
ĐPT O(n). Lưu ý: Các phần tử trong list phải được sắp xếp.
-  sort : sắp xếp các phần tử của list. O(NlogN)
-  reverse : đảo ngược lại các phần tử của list. O(n).
Xem tiếp: part 3