Các cấu trúc đặc biệt trong C++ | Công nghệ thông tin | Trường đại học Công Nghệ Sài Gòn

CÁC CẤU TRÚC ĐẶC BIỆT TRONG C++ 1. Cấu trúc set A: 12 -1 2 0 2 6 12 12 - -1, 2, 0, 6
> có 5 số khác nhau 12,
Nếu a[i]<=10^9 int dd[1e9]- >tran mảng
for(int i=1; i<=n; i++) dd[a[i]] = 1;
cnt=0; for(i,1,maxai) if (dd[i]==1) cnt++; 1 set s: - 0 2 6 12 iterator it muốn lấy gt: *it 1.1. Khái niệm
Set để lưu trữ các phần tử không bị trùng lặp, và các phần tử này chính là các khóa.
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.
Có thể viết lại hàm so sánh theo ý mình 1.2. Khai báo: set tên_set; set v; // Khai báo set tăng dần
Hoặc viết class so sánh theo ý mình: struct cmp{
bool operator() (int x, int y){ return x>y;} };
set s; // Khai báo set giảm dần
1.3. Các hàm của set s.size ()
trả về kích thước hiện tại của set. s.empty()
true nếu set rỗng, và ngược lại. s.insert(x) ;
x cùng kiểu với các phần tử s. Chèn phần tử x vào set s. s.erase(x) ;
Xóa phần tử có giá trị là x. s.erase(it);
xóa phần tử tại vị trí it trỏ tới s.clear(); xóa tất cả set. s.swap(v) ; đổi 2 set cho nhau. set s: -1 0 2 6 12 k = s.size();  k =5 t = s.empty();  t = false s.insert(9);  s: -1 0 2 6 12 9 s.insert(12);  s: -1 0 2 6 12 9 s.erase(5);  s: -1 0 2 6 9 12 s.erase(6);
 s: -1 0 2 9 12 {-1 (begin) 0 2 6 9 12} end it = s.find(6); s.erase(it);  s: -1 0 2 12
set :: iterator it ;
it = s.begin(); cout<<*it;  -1 it
it = s.end(); it--; cout<<*it;  12
it = s.lower_bound(2); cout<<*it; 2  s: -1 12
it = s.upper_bound(2); cout<<*it; 12  s: -1 0 2 5 18
1.4. Truy cập phần tử: it s.find(x) iterator trả về
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.
s.lower_bound(x) trả về iterator đến vị trí phần tử bé nhất >= x
nếu không tìm thấy trả về vị trí “end” của set. s.upper_bound(x) iterator trả về
đến vị trí phần tử bé nhất >x,
nếu không tìm thấy trả về vị trí “end” của set. s.count(x)
trả về 1 nếu có x trong set , và 0 nếu không có.
1.5. Xuất các phần tử trong set s: it i it it it it it set ::iterator it;
for(it = v.begin(); it != v.end(); it++) cout<<*it<<" "; 1.6. Ví dụ: N = 8
A: 12 -1 2 0 2 6 12 12 -> có 5 số khác nhau 12, -1, 2, 0, 6 struct bg{ int gt; int id; }; struct cmp{ bool operator() (bg x, bg y){ return x.gt>y.gt;} }; set s; int n, a[10000]; void doc(){ cin>>n;
for(int i=1; i<=n; i++) cin>>a[i]; } void xuly(){ set v;
for(int i=1; i<=n; i++) s.insert({ }), v.insert(a[i]); a[i],i // Xuat s set :: iterator itr; s:
for(itr = s.begin(); itr != s.end(); itr++){ 1 12 s.begin() //bg x = *itr; 6 6 //cout< ; ” ” 3 2
cout<id<< “ “<< <itr->gt 4 0 } 2 -1 cout<s.end() // Xuat v set ::iterator it;
for(it = v.begin(); it != v.end(); it++) cout<<*it<<" ";
cout<// v: -1 0 2 6 12 // Xuat phan tu dau tien"
cout<<*v.begin()<// -1
v.erase(5); // v: -1 0 2 6 12
v.erase(6); // v: -1 0 2 12 it = v.find(6);
if (it != v.end()) cout<<"YES"; else cout<<"NO"; // NO it=v.upper_bound(12);
cout<<*it< 4, vị trí end vì ko có số lớn hơn 12 it=v.lower_bound(11);
cout<<*it< 12, >=11 }
Giả sử v: -1 0 2 6 12 struct cmp{ bool operator() (bg x, bg y){ return x >y;} };
set h(v.begin(), v.end()); // Tạo một set h từ set v  h: 12 6 2 0 -1
2. Cấu trúc multiset
C++ cũng chứa một cấu trúc multiset và unordered_multiset mà làm việc giống như
set và unordered_set nhưng chúng có thể chứa nhiều thể hiện của một phần tử. Ví
dụ, mã sau có 3 thể hiện của số 5 được thêm vào multiset: multiset s; s.insert(5); s.insert(5); s.insert(5); cout < < s.count(5) < < "\n"; // 3
Hàm erase xóa tất cả các thể hiện của một phần tử từ multiset: s.erase(5); cout < < s.count(5) < < "\n"; // 0
Nếu muốn chỉ 1 thể hiện bị xóa thì ta có thể làm như sau: s.erase(s.find(5)); cout < < s.count(5) < < "\n"; // 2 Làm bài tập:
https://www.spoj.com/PTIT/problems/P161PROH/
https://vn.spoj.com/problems/VMSORT/
https://vn.spoj.com/problems/CPPSET/ 3. Cấu trúc map 3.1. Khái niệm
Các lớp vector, list thuộc cấu trúc Sequence Containers (cấu trúc tuần tự), riêng với
lớp map thuộc một cấu trúc khác đó là Associative Containers (cấu trúc liên kết), là kiểu dữ
liệu cho phép quản lý một cặp key/value - khóa và giá trị, nghĩa là muốn xác định được nội
dung value thì phải biết được vị trí key mà map đang quản lý.
Map là một tập hợp của nhiều phần tử như cấu trúc mảng, mỗi phần tử chính là
một cặp bao gồm giá trị bắt đầu gọi là key (tạm dịch là chìa khóa) và giá trị đích value (tạm
dịch là giá trị ẩn). Trong khi key trong mảng thông thường luôn là các số nguyên liên tiếp 0, 1, …, n 1, -
khi n là kích thước của mảng, thì key trong map có thể là bất kỳ kiểu dữ liệu nào
và không nhất thiết phải là các giá trị liên tiếp.
Trong lập trình, khi bạn muốn dùng một định danh nào đó thay thế cho giá trị ẩn thật sự
đằng sau nó, ví dụ dùng từ "một" để thay thế cho số "1", thì bạn nên nghĩ ngay tới việc sử dụng cấu trúc map.
Một điểm đặc biệt nữa là mỗi key trong map là duy nhất và không thể bị trùng lắp, trong
khi giá trị ẩn của key đó thì có thể bị trùng lắp với giá trị ẩn của khác, đây cũng là key điều dễ
hiểu bởi vì nếu chúng ta có hai điểm bắt đầu, chúng ta sẽ phân vân không biết chọn điểm bắt
đầu nào, đó là một trong những tính chất quan trọng của map.
Nếu bạn muốn lưu danh sách các phần tử không bị trùng lắp hoặc đếm số lần xuất hiện của
mỗi từ trong câu thì sao, map là sự lựa chọn hoàn hảo. 3.2. Khai báo: map m; VD: map m; map p(m.begin(), m.end());
// Tạo một map p từ map m.
Trong đó kiểu dữ liệu của key thường là string, kiểu dữ liệu của value thường là giá trị số
Mã sau đây tạo một map khi key là string và value là số nguyên integer: map m; m["monkey"] = 4 ; m["banana"] = 3 ; m["harpsichord"] = 9; cout <
< m["banana"] << "\n"; // 3
Nếu giá trị của key được yêu cầu nhưng map không chứa nó, thì key được tự động
thêm vào map với giá trị mặc định. Ví dụ, trong mã sau, key "aybabtu" với giá trị 0 được thêm vào map. map m; cout <
< m["aybabtu"] << "\n"; // 0
3.3. Các hàm của map m.size ()
trả về kích thước hiện tại của map m.empty()
true nếu map rỗng, và ngược lại. m.insert({x,y}) ; chèn x : khóa; y: gía // neu khoa da trị tương ứng vào m co ko chen m.erase(key) ;
Xóa phần tử có khóa là key ra khỏi m
m.erase(it, m.end()); Xóa các phần tử từ vị trí truy cập iterator it đến cuối m.clear(); xóa tất cả map. m.swap(v) ; đổi 2 map cho nhau.
1.4. Truy cập phần tử: m.find(x)
trả về iterator trỏ đến phần tử cần tìm kiếm. m.count(x)
trả về số lượng khóa x trong map, và 0 nếu không có.
1.5. Xuất các phần tử trong map
Mã in tất cả các key và value của map là: map :: iterator it;
for(it= m.begin(); it!=m.end(); it++)
cout<first<<" "<second<
m[key] = giá_trị; // cập nhật giá trị mới cho key
VD: N = 8; A: 1 2 4 2 2 4 1000000000 2 #include using namespace std; map m; int n,a[100000+5]; void doc(){ cin>>n;
for(int i=1; i<=n; i++) cin>>a[i]; } void xuly(){
for(int i=1; i<=n; i++) m[a[i]]++; 1 1 2 4
map :: iterator it; 4 2 cout< 100000000 1 m.insert({10,2}); // 1 1 2 4
for(it= m.begin(); it!=m.end(); it++) 4 2
cout<first<<" "<second< 10 2 100000000 1 int res=0;
for(it= m.begin(); it!=m.end(); it++)
res = max(res, it->second); cout<
for(it= m.begin(); it!=m.end(); it++)
if (res == it->second) cout<first<<" "; //2 cout< cout< // 1 1 1 4 2 m.erase(2); 10 2
for(it= m.begin(); it!=m.end(); it++) 100000000 1
cout<first<<" "<second< } int main(){
freopen("VDMAP.INP", "r", stdin);
freopen("VDMAP.OUT", "w", stdout);
ios_base :: sync_with_stdio(false);
cin.tie(0); cout.tie(0); doc(); xuly(); return 0; } Làm bài tập:
https://www.spoj.com/PTIT/problems/P161PROH/
https://vn.spoj.com/problems/VMSORT/
https://www.spoj.com/PTIT/problems/P176PROG/ 4. Iterators và ranges
Nhiều hàm trong thư viện C++ chuẩn hoạt động với iterators. Một iterator là một biến mà
trỏ đến một phần tử trong một CTDL. Iterator begin
thường sử dụng 2 con trỏ
và end để định nghĩa một dãy chứa tất tất cả các
phần tử trong CTDL. Con trỏ begin trỏ đến phần tử đầu tiên của CTDL, và con trỏ end trỏ
đến vị trí phía sau phần tử cuối cùng. Được minh họa như sau:
{3,↑s.begin()4,6,8,12,13,14,17}↑s.end()
Chú ý tính bất đối xứng trong iterator: s.begin() trỏ đến một phần tử trong CTDL, trong khi
s.end() trỏ đến bên ngoài CTDL.
Làm việc với ranges
Iterator được sử dụng trong thư viện C++ chuẩn để xác định một dãy các phần tử trong
CTDL. Chúng ta thường muốn xử lý tất cả các phần tử trong một CTDL, vì vậy Iterator begin và end
thường được dùng cho hàm.
Ví dụ, mã sắp xếp một vector sau sử dụng hàm sort, sau đó đảo ngược thứ tự các phần tử sử dụng hàm
, và cuối cùng là xáo trộn thứ tự các phần tử với hàm reverse random_shuffle. sort(v.begin(), v.end()); reverse(v.begin(), v.end());
random_shuffle(v.begin(), v.end());
Những hàm này cũng có thể sử dụng với mảng thông thường. Trong trường hợp này, các
hàm phải xác định các con trỏ trỏ đến một mảng thay vì iterator: sort(a, a+n); reverse(a, a+n); random_shuffle(a, a+n); Set iterator
Iterator thường được sử dụng để truy xuất đến cấu trúc set. Mã sau tạo một iterator it mà
trỏ đến một phần tử nhỏ nhất trong set: set::iterator it = s.begin();
Một cách viết mã ngắn gọn như sau: auto it = s.begin();
Phần tử mà con trỏ iterator trỏ đến có thể được truy suất bằng ký hiệu *. Ví dụ, mã sau in ra
phần tử đầu tiên của set: auto it = s.begin();
cout << *it << "\n";
Iterator có thể được di chuyển bằng toán tử operator ++ (tiến) và -- (lùi), nghĩa là iterator có
thể di chuyển đến phần tử tiếp theo hoặc phần tử trước đó trong set. Mã sau in ra tất cả các
phần tử của set từ đầu đến cuối:
for (auto it = s.begin(); it != s.end(); it++) cout << *it << "\n";
Hàm find(x) trả về một iterator mà trỏ đến một phần tử có giá trị là x. Tuy nhiên, nếu set
không chứa x, thì iterator sẽ là end. auto it = s.find(x); if (it == s.end()){ // x không tìm thấy }
Hàm lower_bound(x) trả về một iterator trỏ đến phần tử nhỏ nhất trong set mà có giá trị
nhỏ hơn x và hàm upper_bound(x) trả về một iterator trỏ đến con trỏ nhỏ nhất trong set
mà có giá trị lớn hơn x. Cả 2 hàm, nếu một phần tử không tồn tại thì trả về giá trị của end.
Những hàm này không được hỗ trợ trong cấu trúc unordered_set là cấu trúc chứa các phần
tử không có thứ tự. Ví dụ, mã sau tìm phần tử gần với x nhất: auto it = s.lower_bound(x); if (it == s.begin()){
cout << *it << "\n"; } else if (it == s.end()){ it--;
cout << *it << "\n"; } else { int a = *it; it--; int b = *it;
if (x-b < a-x) cout << b << "\n";
else cout << a << "\n"; }
Mã trên giả thiết rằng set là không rỗng, và đi qua tất cả các khả năng có thể bằng iterator it.
Đầu tiên, iterator trỏ đến phần tử nhỏ nhất có giá trị nhỏ hơn x. Nếu it bằng begin, thì phần
tử tương ứng là gần với x nhất. Nếu it bằng end, phần tử lớn nhất trong set là gần với x nhất.
Nếu không phải 2 trường hợp trên thì phần tử gần x nhất là phần tử tương ứng hoặc phần tử đứng trước đó.
5. Các cấu trúc khác
Bitset là một mảng mà mỗi phần
tử chỉ có giá trị là 0 hoặc 1.
Ví dụ, mã sau tạo một bitset chứa 10 phần tử: bitset<10> s; s[1] = 1; s[3] = 1; s[4] = 1; s[7] = 1;
cout << s[4] << "\n"; // 1
cout << s[5] << "\n"; // 0
Lợi ích của việc sử dụng bitset là nó yêu cầu ít bộ nhớ hơn so với mảng thông thường, bởi vì
mỗi phần tử trong bitset chỉ sử dụng 1 bít bộ nhớ. Ví dụ, nếu n bits được lưu trữ trong một
mảng int, 32n bits bộ nhớ sẽ được sử dụng, nhưng với bitset tương ứng chỉ yêu cầu n bits bộ
nhớ. Hơn nữa, các giá trị của một bitset có thể thao tác hiệu quả bằng cách sử dụng các toán
tử bit, điều này có thể dùng bitset để tối ưu thuật toán. Mã sau đây chỉ ra một số cách để tạo ra một bitset nói trên:
bitset<10> s(string(0010011010)); // from right to left
cout << s[4] << "\n"; // 1
cout << s[5] << "\n"; // 0
Hàm count trả về số lượng bít 1 trong bitset:
bitset<10> s("0010011010");
cout << s.count() << "\n"; // 4
Mã sau đây minh họa các ví dụ sử dụng các toán tử bit:
bitset<10> a(string("0010011010"));
bitset<10> b(string("1011011000"));
cout << (a&b) << "\n"; // 0010010000
cout << (a|b) << "\n"; // 1011111110
cout << (a^b) << "\n"; // 1011011110