C++ STL: Tổng hợp CTDL

C++ STL là một thư viện template cho C++ với những CTDL cũng như giải thuật được xây dựng tổng quát mà vẫn tận dụng được hiệu năng và tốc độ của C. Thư viện STL giúp người dùng thực hiện toàn bộ các công việc như vào ra dữ liệu, quản lý mảng động, xây dựng sẵn những cấu trúc dữ liệu cơ bản và bao gồm cả các giải thuật cơ bản như sắp xếp, tìm min – max, tính tổng, thậm chí là tìm ước chung lớn nhất chẳng hạn. Việc sử dụng STL là rất quan trọng đối với những bạn nào có định hướng tham gia những kỳ thi HSG Tin Học
Để sử dụng thư viện STL, ta chỉ cần khai báo:#include <bits/stdc++.h>

1. STL Map

Map là 1 CTDL của thư viện STL. Mỗi phần tử của CTDL map là sự kết hợp của khóa (key) và ánh xạ của nó (value). Trong map không chứa các khóa mang giá trị giống nhau. 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. Các phần tử trong map được sắp xếp theo trình tự nào đó theo cách so sánh (mặc định là theo trình tự tăng dần).

Khai báo:

map<kiểu_dữ_liệu_1, kiểu_dữ_liệu_2> mp //với kiểu dữ liệu 1 là key, kiểu dữ liệu 2 là value


Cách truy cập phần tử trong map:

\(mp[x]\) (truy cập phần tử có khóa là \(x\)): Nếu khóa đã có trong map thì trả về giá trị của khóa. Ngược lại, nó sẽ thêm khóa đó vào map với giá trị 0. Độ phức tạp: \(O(logN)\). Ta có thể thêm phần tử vào map bằng cú pháp sau: \(mp[x] = v\) (thêm khóa \(x\) với giá trị \(v\) vào map) với độ phức tạp \(O(logN)\).

Ta có thể truy cập vào từng phần tử của map bằng cách dưới đây:

map<int,int> mp;
for (auto x : mp) {
    cout << x.first << ' ' << x.second << '\n';
    // với x.first là khóa và x.second là ánh xạ.
}

Các hàm hay dùng với map:

unordered_map:

unordered_map là 1 map nhưng với các phần tử không được sắp xếp theo khóa. Cách khai báo và các hàm tương tự với map. So sánh độ phức tạp các thao tác của map và unordered_map:

-> Ta nên dùng unordered_map khi không sử dụng đến tính chất sắp xếp của map, ngược lại hãy sử dụng map.

So sánh map và mảng đánh dấu:

Ta có thể sử dụng map như một mảng đánh dấu. Ta có ví dụ nhỏ như sau:

Cho mảng \(a\) gồm \(n\) phần tử. In ra số lần xuất hiện của từng phần tử trong \(a\) theo chỉ số tăng dần.

Input:

• Dòng đầu tiên ghi \(n\) với \(n\) là số phần tử của mảng \(a\) (\(n\)≤\(10^{5}\)).
• Dòng tiếp theo ghi \(n\) số nguyên dương lần lượt là các giá trị từ \(a_{1}\), \(a_{2}\), \(a_{3}\), …, \(a_{n}\).

Output:

• Một dòng duy nhất in ra số lần xuất hiện của từng phần tử trong \(a\) theo chỉ số tăng dần.

Sample Input:

6
1 5 0 2 2 0

Sample Output:

1 1 2 2 2 2

Phân tích:

Ta có 2 cách tiếp cận bài toán:
• Sử dụng mảng đánh dấu: Do ta chỉ có thể khai báo mảng với kích thước khoảng \(10^{7}\) nên ta chỉ có thể dùng mảng đánh dấu khi giới hạn của \(a_{i}\) <= \(10^{7}\).
• Sử dụng map: Do ta có thể khai báo khóa của map là tất cả các kiểu dữ liệu như: int, long long, … nên ta có thể dùng map với giới hạn của \(a_{i}\) lên tới \(10^{18}\).

Code mẫu sử dụng map (code này sử dụng unordered_map vì ta không cần sử dụng tính chất sắp xếp của map) :

#include <bits/stdc++.h>
using namespace std;
const int mx = 1e6 + 5;
const int mod = 1e9 + 7;
int n, a[mx];
signed main() {
    cin >> n;
    unordered_map<int,int> mp;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        mp[a[i]]++;
    }
    for (int i = 1; i <= n; i++) {
        cout << mp[a[i]] << ' ';
    }
    return 0;
}
//honguwu

So sánh giữa sử dụng map và sử dụng mảng:

Ánh xạ dãy số (nén số) bằng map

Ta có thể sử dụng map để ánh xạ dãy số. Ánh xạ dãy số được thực hiện như sau: Giả sử ta nén số một mảng \(a\) có \(n\) phần tử có giá trị thuộc khoảng [\(−10^{9}\),\(10^{9}\)] về mảng nhỏ hơn có giá trị thuộc khoảng [1,\(n\)] mà vẫn đảm bao được quan hệ lớn bé. Ví dụ: \(a\) = {100, 100, 2000, 1500, 900000} → \(b\) = {1,1,3,2,4}.

Code mẫu:

#include<bits/stdc++.h>
using namespace std;

#define pii pair<int, int>

const int N = 1e6 + 5;

int a[N], b[N], c[N];
map<int, int> mp;

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        mp[a[i]]++;
    }
    int cnt = 0;
    for (auto it : mp) {
        cnt++;
        b[cnt] = it.first;
    }
    for (int i = 1; i <= n; i++) {
        int x = lower_bound(b + 1, b + 1 + cnt, a[i]) - b;
        c[i] = x;
    }
}
// mảng c chứa dãy số sau khi được ánh xạ.

2. STL Set

Set là 1 CTDL của thư viện STL. CTDL set 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). Các phần tử của set sẽ tăng dần theo phép toán so sánh (mặc định là tăng dần). Bạn cũng có thể viết lại hàm so sánh theo ý của mình.

Khai báo:

• Dạng 1 (sử dụng phép toán mặc định): set<kiểu_dữ_liệu> s; (sắp xếp tăng dần)
• Dạng 2 (sử dụng phép toán khác): set<kiểu_dữ_liệu, greater<kiểu_dữ_liệu>> s //phép toán greater; (sắp xếp giảm dần).

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 2 tương đương với:

struct cmp{
 bool operator() (int a,int b) {return a>b;}
};
set <int,cmp> s ;

Ta có thể truy cập vào từng phần tử của set bằng cách dưới đây:

set<int> s;
for (auto x : s) {
    cout << x << ' ';
}

Ta cũng có thể truy cập phần tử đầu tiên và cuối cùng của set bằng cách:

cout << *s.begin(); // phần tử đầu tiên
cout << *s.rbegin(); // phần tử cuối cùng

Các hàm hay dùng với set:

Cách dùng lower_bound và upper_bound để tìm phần tử đầu tiên lớn hơn hoặc bằng \(x\) và lớn hơn \(x\) trong set:

cout << *s.lower_bound(x); // tìm phần tử đầu tiên lớn hơn hoặc bằng x
cout << *s.upper_bound(x); // tìm phần tử đầu tiên lớn hơn x

Khai báo iterator trong set:

set<int> :: iterator it;


Multiset:

Multiset giống như set nhưng có thể chứa các giá trị giống nhau. Cách khai báo và các hàm tương tự như set.

3. STL Priority Queue

Priority Queue là 1 CTDL của thư viện STL. CTDL priority queue đượ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 đó), 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 (phần tử lớn nhất được lấy ra đầu tiên). Để 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

• Dạng 1 (sử dụng phép toán mặc định là less): priority_queue<kiểu_dữ_liệu> pq; (ưu tiên đưa phần tử lớn nhất ra)
• Dạng 2 (sử dụng phép toán khác): priority_queue<kiểu_dữ _liệu, vector<kiểu_dữ _liệu>, greater<kiểu_dữ _liệu>> q; //phép toán greater
  (ưu tiên đưa phần tử bé nhất ra)

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 2 tương đương với:

struct cmp{
 bool operator() (int a,int b) {return a>b;}
};
main() {
 …
 priority_queue <int, vector<int>, cmp > q;
}

Các hàm hay sử dụng với priority queue:

4. STL Stack

Stack là 1 CTDL của thư viện STL. CTDL stack đượ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:

stack<kiểu_dữ_liệu> st;

Các hàm hay sử dụng với stack:

5. STL Queue

Queue là 1 CTDL của thư viện STL. CTDL queue đượ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:

queue<kiểu_dữ_liệu> q;

Các hàm hay sử dụng với queue:

6. Luyện tập

Đây là một số bài tập luyện tập trong sách Competitive Programming Basic của Code Dream, đăng ký mua ngay để được luyện tập nhiều dạng bài về thuật toán khác, chấm bài online tại http://oj.codedream.edu.vn

ÁP DỤNG GIẢI BÀI TOÁN TRUEBRAC:

Phân tích bài toán:

Nhận xét:

Do dãy ngoặc đúng có số dấu ngoặc mở và ngoặc đóng bằng nhau; giữa một cặp dấu ngoặc tương ứng là một dãy ngoặc đúng nên ta có thể làm như sau:

• Duyệt xâu cần kiểm tra.
• Khi gặp dấu ngoặc mở thì đẩy vào stack; còn khi gặp dấu ngoặc đóng thì kiểm tra nếu đỉnh stack có dấu ngoặc mở tương ứng với nó thì đẩy dấu ngoặc mở đó ra khỏi stack, ngược lại xâu không phải dãy ngoặc đúng.
• Sau khi duyệt hết xâu nếu stack rỗng thì xâu là dãy ngoặc đúng và ngược lại.

Code mẫu:

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define int int64_t
#define pii pair<int, int>
const int mx = 1e6 + 5;
const int mod = 1e9 + 7;
void sub() {
    string s;
    cin >> s;
    stack<int> st;
    for (int i = 0; i < s.size(); i++) {
        if (s[i]=='(' || s[i]=='[' || s[i]=='{' ) st.push(s[i]);
        else {
            if (!st.empty() && ((s[i]==')' && st.top()=='(') || (s[i]==']' && st.top()=='[') || (s[i]=='}' && st.top()=='{'))) st.pop();
            else {
                cout << "NO";
                return;
            }
        }
    }
    if (st.empty()) cout << "YES";
    else cout << "NO";
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    sub();
    return 0;
}
//honguwu