Associative 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ử.
Set (Tập hợp):
- Set là một loại associative containers để lưu trữ các phần tử không bị trùng lặp
(unique elements), và các phần tử này chính là các khóa (keys).
- Khi duyệt set theo iterator từ begin đến end, các phần tử của set sẽ tăng dần theo phép
toán so sánh.
- Mặc định của set là sử dụng phép toán less, bạn cũng có thể viết lại hàm so sánh theo
ý mình.
- Set được thực hiện giống như cây tìm kiếm nhị phân (Binary search tree).
Khai báo:
#include <set>
set <int> s;
set <int, greater<int> > s;
Hoặc viết class so sánh theo ý mình:
struct cmp{
bool operator() (int a,int b) {return a<b;}
};
set <int,cmp > myset ;
Capacity:
- size : trả về kích thước hiện tại của set. ĐPT O(1)
- empty : true nếu set rỗng, và ngược lại. ĐPT O(1).
Modifiers:
- insert : Chèn phần tử vào set. ĐPT O(logN).
- erase : có 2 kiểu xóa: xóa theo iterator, hoặc là xóa theo khóa. ĐPT
O(logN).
- clear : xóa tất cả set. ĐPT O(n).
- swap : đổi 2 set cho nhau. ĐPT O(n).
Operations:
- find : trả về itarator trỏ đến phần tử cần tìm kiếm. Nếu không tìm
thấy itarator trỏ về “end” của set. ĐPT O(logN).
- lower_bound : trả về iterator đến vị trí phần tử bé nhất mà không bé
hơn (lớn hơn hoặc bằng) khóa (dĩ nhiên là theo phép so sánh), nếu
không tìm thấy trả về vị trí “end” của set. ĐPT O(logN).
- upper_bound: trả về iterator đến vị trí phần tử bé nhất mà lớn hơn
khóa, nếu không tìm thấy trả về vị trí “end” của set.. ĐPT O(logN).
- count : trả về số lần xuất hiện của khóa trong container. Nhưng trong
set, các phần tử chỉ xuất hiện một lần, nên hàm này có ý nghĩa là sẽ
return 1 nếu khóa có trong container, và 0 nếu không có. ĐPT O(logN).
Chương trình Demo 1:
#include <iostream>
#include <set>
using namespace std;
main() {
set <int> s;
set <int> ::iterator it;
s.insert(9); // s={9}
s.insert(5); // s={5,9}
cout << *s.begin() << endl; //In ra 5
s.insert(1); // s={1,5,9}
cout << *s.begin() << endl; // In ra 1
it=s.find(5);
if (it==s.end()) cout << "Khong co trong container" << endl;
else cout << "Co trong container" << endl;
s.erase(it); // s={1,9}
s.erase(1); // s={9}
s.insert(3); // s={3,9}
s.insert(4); // s={3,4,9}
it=s.lower_bound(4);
if (it==s.end()) cout << "Khong co phan tu nao trong set khong be hon 4" << endl;
else cout << "Phan tu be nhat khong be hon 4 la " << *it << endl; // In ra 4
it=s.lower_bound(10);
if (it==s.end()) cout << "Khong co phan tu nao trong set khong be hon 10" << endl;
else cout << "Phan tu be nhat khong be hon 10 la " << *it << endl; // Khong co ptu nao
it=s.upper_bound(4);
if (it==s.end()) cout << "Khong co phan tu nao trong set lon hon 4" << endl;
else cout << "Phan tu be nhat lon hon 4 la " << *it << endl; // In ra 9
/* Duyet set */
for (it=s.begin();it!=s.end();it++) {
cout << *it << " ";
}
// In ra 3 4 9
cout << endl;
system("pause");
}
Lưu ý:Nếu bạn muốn sử dụng hàm lower_bound hay upper_bound để tìm phần tử lớn nhất
“bé hơn hoặc bằng” hoặc “bé hơn” bạn có thể thay đổi cách so sánh của set để tìm kiếm. Mời
bạn xem chương trình sau để rõ hơn:
#include <iostream>
#include <set>
#include <vector>
using namespace std;
main() {
set <int, greater <int> > s;
set <int, greater <int> > :: iterator it; // Phép toán so sánh là greater
s.insert(1); // s={1}
s.insert(2); // s={2,1}
s.insert(4); // s={4,2,1}
s.insert(9); // s={9,4,2,1}
/* Tim phần tử lớn nhất bé hơn hoặc bằng 5 */
it=s.lower_bound(5);
cout << *it << endl; // In ra 4
/* Tim phần tử lớn nhất bé hơn 4 */
it=s.upper_bound(4);
cout << *it << endl; // In ra 2
system("pause");
}
Mutiset (Tập hợp):
- Multiset giống như Set nhưng có thể chứa các khóa có giá trị giống nhau.
- Khai báo : giống như set.
- Các hàm thành viên:
Capacity:
- size : trả về kích thước hiện tại của multiset. ĐPT O(1)
- empty : true nếu multiset rỗng, và ngược lại. ĐPT O(1).
Chỉnh sửa:
- insert : Chèn phần tử vào set. ĐPT O(logN).
- erase :
o xóa theo iterator ĐPT O(logN)
o xóa theo khóa: xóa tất cả các phần tử bằng khóa trong multiset
ĐPT: O(logN) + số phần tử bị xóa.
- clear : xóa tất cả set. ĐPT O(n).
- swap : đổi 2 set cho nhau. ĐPT O(n).
Operations:
- find : trả về itarator trỏ đến phần tử cần tìm kiếm. Nếu không tìm
thấy itarator trỏ về “end” của set. ĐPT O(logN). Dù trong multiset có
nhiều phần tử bằng khóa thì nó cũng chỉ iterator đến một phần tử.
- lower_bound : trả về iterator đến vị trí phần tử bé nhất mà không bé
hơn (lớn hơn hoặc bằng) khóa (dĩ nhiên là theo phép so sánh), nếu
không tìm thấy trả về vị trí “end” của set. ĐPT O(logN).
- upper_bound: trả về iterator đến vị trí phần tử bé nhất mà lớn hơn
khóa, nếu không tìm thấy trả về vị trí “end” của set.. ĐPT O(logN).
- count : trả về số lần xuất hiện của khóa trong multiset. ĐPT O(logN)
+ số phần tử tìm được.
Chương trình Demo:
#include <iostream>
#include <set>
using namespace std;
main() {
multiset <int> s;
multiset <int> :: iterator it;
int i;
for (i=1;i<=5;i++) s.insert(i*10); // s={10,20,30,40,50}
s.insert(30); // s={10,20,30,30,40,50}
cout << s.count(30) << endl; // In ra 2
cout << s.count(20) << endl; // In ra 1
s.erase(30); // s={10,20,40,50}
/* Duyet set */
for (it=s.begin();it!=s.end();it++) {
cout << *it << " ";
}
// In ra 10 20 40 50
cout << endl;
system("pause");
}
Map (Ánh xạ):
- Map là một loại associative container. Mỗi phần tử của map là sự kết hợp của khóa
(key value) và ánh xạ của nó (mapped value). Cũng giống như set, trong map không
chứa các khóa mang giá trị giống nhau.
- Trong map, các khóa được sử dụng để xác định giá trị các phần tử. Kiểu của khóa và
ánh xạ có thể khác nhau.
- Và cũng giống như set, các phần tử trong map được sắp xếp theo một trình tự nào đó
theo cách so sánh.
- Map được cài đặt bằng red-black tree (cây đỏ đen) – một loại cây tìm kiếm nhị phân
tự cân bằng. Mỗi phần tử của map lại được cài đặt theo kiểu pair (xem thêm ở thư
viện utility).
Khai báo:
#include <map>
...
map <kiểu_dữ_liệu_1,kiểu_dữ_liệu_2>
// kiểu dữ liệu 1 là khóa, kiểu dữ liệu 2 là giá trị của khóa.
Sử dụng class so sánh:
Dạng 1:
struct cmp{
bool operator() (char a,char b) {return a<b;}
};
.....
map <char,int,cmp> m;
- Truy cập đến giá trị của các phần tử trong map khi sử dụng iterator:
Ví dụ ta đang có một iterator là it khai báo cho map thì:
(*it).first; // Lấy giá trị của khóa, kiểu_dữ_liệu_1
(*it).second; // Lấy giá trị của giá trị của khóa, kiểu_dữ_liệu_2
(*it) // Lấy giá trị của phần tử mà iterator đang trỏ đến, kiểu pair
it->first; // giống như (*it).first
it->second; // giống như (*it).second
Capacity:
- size : trả về kích thước hiện tại của map. ĐPT O(1)
- empty : true nếu map rỗng, và ngược lại. ĐPT O(1).
Truy cập tới phần tử:
- operator [khóa]: Nếu khóa đã có trong map, thì hàm này sẽ trả về giá
trị mà khóa ánh xạ đến. Ngược lại, nếu khóa chưa có trong map, thì
khi gọi [] nó sẽ thêm vào map khóa đó. ĐPT O(logN)
Chỉnh sửa
- insert : Chèn phần tử vào map. Chú ý: phần tử chèn vào phải ở kiểu
“pair”. ĐPT O(logN).
- erase :
o xóa theo iterator ĐPT O(logN)
o xóa theo khóa: xóa khóa trong map. ĐPT: O(logN).
- clear : xóa tất cả set. ĐPT O(n).
- swap : đổi 2 set cho nhau. ĐPT O(n).
Operations:
- find : trả về itarator trỏ đến phần tử cần tìm kiếm. Nếu không tìm
thấy iterator trỏ về “end” của map. ĐPT O(logN).
- lower_bound : trả về iterator đến vị trí phần tử bé nhất mà không bé
hơn (lớn hơn hoặc bằng) khóa (dĩ nhiên là theo phép so sánh), nếu
không tìm thấy trả về vị trí “end” của map. ĐPT O(logN).
- upper_bound: trả về iterator đến vị trí phần tử bé nhất mà lớn hơn
khóa, nếu không tìm thấy trả về vị trí “end” của map. ĐPT O(logN).
- count : trả về số lần xuất hiện của khóa trong multiset. ĐPT O(logN)
Chương trình demo:
#include <iostream>
#include <map>
#include <vector>
using namespace std;
main() {
map <char,int> m;
map <char,int> :: iterator it;
m['a']=1; // m={{'a',1}}
m.insert(make_pair('b',2)); // m={{'a',1};{'b',2}}
m.insert(pair<char,int>('c',3) ); // m={{'a',1};{'b',2};{'c',3}}
cout << m['b'] << endl; // In ra 2
m['b']++; // m={{'a',1};{'b',3};{'c',3}}
it=m.find('c'); // it point to key 'c'
cout << it->first << endl; // In ra 'c'
cout << it->second << endl; // In ra 3
m['e']=100; //m={{'a',1};{'b',3};{'c',3};{'e',100}}
it=m.lower_bound('d'); // it point to 'e'
cout << it->first << endl; // In ra 'e'
cout << it->second << endl; // In ra 100
system("pause");
}
Multi Map (Ánh xạ):
Giống như map nhưng có thể chứa các phần tử có khóa giống nhau, do đó nó khác map ở chỗ
không có opearator[].
Xem tiếp: part 5
Không có nhận xét nào:
Đăng nhận xét