[TOC]

# Các CTDL trong thư viện chuẩn STL

## **Vector**
Vector trong c++ là một CTDL **mảng động** (dynamic array), khác với **mảng tĩnh** thông thường (static array). Điểm khác biệt giữa mảng động và mảng tĩnh là mảng động có thể thay đổi kích thước và số lượng phần tử, mảng tĩnh thì không.

#### Iterators:
- begin và end
`v.begin(), v.end()` : begin trả về **iterator** (gần giống con trỏ, đọc ở bài Basic pointer and iterator) ở vị trí đầu tiên và end trả về **iterator** ở sau vị trí cuối cùng
- rbegin và rend
`v.rbegin(), v.rend()` : trả về **reverse iterator** (iterator ngược, rbegin sẽ ở vị trí cuối và tăng dần về rend ở trước vị trí đầu tiền)

#### Khai báo:
- `vector<type> name` : khởi tạo một vector trống
- `vector<type> name(n)` : khởi tạo vector có sẵn n phần tử 0
- `vector<type> name(n, val)` : khởi tạo vector có n phần tử val
- `vector<type> name(first, last)` : khởi tạo vector chứa các phần tử từ trong khoảng iterator [first, last) (từ first tới trước last)

#### Các hàm:

- size
`v.size()` : trả về độ dài của vector
- operator []
`v[i]` : trả về phần tử vị trí i
- front và back
`v.front(), v.back()` : front trả về phần tử đầu tiên (v[0]) và back trả về phần tử cuối cùng (v[v.size()-1])
- empty
`v.empty()` : trả về *true* nếu vector trống (size = 0), *false* nếu ngược lại
- clear
`v.clear()` : xóa mọi phần tử trong vector
- resize
`v.resize(n)` : thay đổi kích thước của vector thành n
- push_back
`v.push_back(val)` : thêm giá trị val vào cuối vector
- pop_back
`v.pop_back()` : xóa giá trị ở cuối vector
- insert
- `v.insert(pos, val)` : chèn val vào vị trí iterator pos
- `v.insert(pos, n, val)` : chèn n giá trị val vào vị trí pos
- `v.insert(pos, first, last)` : chèn các giá trị trong khoảng iterator [first, last) vào vị trí pos
- erase
- `v.erase(pos)` : xóa phần tử ở iterator pos
- `v.erase(first, last)` : xóa các phần từ trong khoảng iterator [first, last)

#### Example:

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

int main() {
    
    int ar[5] = {1, 2, 3, 4, 5};
    vector<int> v0;                            // empty vector
    vector<int> v1 = {10, 9, 8, 7, 6};  
    vector<int> v2(3);                         // 0 0 0
    vector<int> v3(5, 10);                     // 10 10 10 10 10
    vector<int> v4(ar, ar + 3);                // 1 2 3
    vector<int> v5(v2.begin() + 1, v2.end());  // 9 8 7 6

    v0 = v3;                                             	   // 10 10 10 10 10
    v0[1] = 11;                                          	   // 10 11 10 10 10
    v0.push_back(11);                                    	   // 10 11 10 10 10 11
    v0.push_back(12);                                    	   // 10 11 10 10 10 11 12
    v0.pop_back();                                       	   // 10 11 10 10 10 11
    v0.insert(v0.begin(), -1);                           	   // -1 10 11 10 10 10 11
    v0.insert(v0.begin() + 4, 3, 2);                            // -1 10 11 10 2 2 2 10 10 11
    v0.insert(v0.begin() + 1, v1.begin() + 2, v1.begin() + 4);  // -1 8 7 10 11 10 2 2 2 10 10 11
    v0.erase(v0.end() - 1);                                     // -1 8 7 10 11 10 2 2 2 10 10
    v0.erase(v0.begin() + 5, v0.begin() + 8);                   // -1 8 7 10 11 2 10 10
    v0.resize(5);                                               // -1 8 7 10 11

    for(int i = 0; i < v0.size(); ++i)
        cout << v0[i] << ' ';
    cout << endl;
    
    // Một cách khác
    for(vector<int>::iterator it = v0.begin(); it != v0.end(); ++it)
        cout << *it << ' ';
    cout << endl;
    
    // In ngược
    
    for(int i = v0.size() - 1; i >= 0; --i)
        cout << v0[i] << ' ';
    cout << endl;
    
    // Cách khác
    for(vector<int>::reverse_iterator it = v0.rbegin(); it != v0.rend(); ++it)
        cout << *it << ' ';
    cout << endl;
    
    v0.clear();
    cout << v0.empty(); // 1 (true)

    return 0;
}

<br></br>

## **Stack**
Stack là CTDL **LIFO** (last in first out), nghĩa là phần tử được thêm vào cuối cùng sẽ được bị xóa đi đầu tiên. Bạn hãy tưởng tượng nó như một chồng sách, khi thêm một quyển sách ta sẽ đặt lên trên cùng, sau đó muốn lấy một quyển sách nào đó ta phải bỏ lần lượt các cuốn ở trên cùng.

#### Khai báo:
`stack<type> name`

#### Các hàm:
- size
`st.size()` : trả về kích thước của stack
- empty
`st.empty()` : trả về *true* nếu stack trống, *false* ngược lại
- push
`st.push(val)` : thêm val vào trên cùng stack
- pop
`st.pop()` : xóa phần tự trên cùng stack
- top
`st.top()` : trả về phần tử trên cùng stack

#### Example:

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

int main() {
    
    stack<int> st;
    st.push(0);
    for(int i = 1; i <= 5; ++i)
        st.push(i);
    cout << st.size() << endl; // 6
    while(st.empty() == false) {
        cout << st.top() << ' '; // 5 4 3 2 1 0
        st.pop();
    }

    return 0;
}

<br></br>

## **Queue**
Queue là CTDL **FIFO** (first in first out), nghĩa là phần tử được thêm vào đầu tiên sẽ được bị xóa đi đầu tiên. Bạn hãy tưởng tượng nó như một hàng người xếp hàng, khi đó người nào đứng đầu (vào trong hàng trước) sẽ được phục vụ và rời đi trước.

#### Khai báo:
`queue<type> name`

#### Các hàm:
- size
`qu.size()` : trả về kích thước của queue
- empty
`qu.empty()` : trả về *true* nếu queue trống, *false* ngược lại
- push
`qu.push(val)` : thêm val vào sau cùng queue
- pop
`qu.pop()` : xóa phần tự đầu tiên của queue
- front và back
`qu.front(), qu.back()` : trả về phần tử đầu tiên và cuối cùng của queue

#### Example:

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

int main() {
    
    queue<int> qu;
    qu.push(0);
    for(int i = 1; i <= 5; ++i)
        qu.push(i);
    cout << qu.back() << endl; // 5
    cout << qu.size() << endl; // 6
    while(qu.empty() == false) {
        cout << qu.front() << ' '; // 0 1 2 3 4 5
        qu.pop();
    }

    return 0;
}

<br></br>

## **Set và Multiset**
Set đơn giản chỉ là một CTDL chỉ chứa các phần tử riêng biệt. Ngoài ra, các phần tử của set sẽ tự động được sắp xếp (mặc định là tăng dần). Multiset có cách dùng tương tự set nhưng có thể chứa các phần tử giống nhau (vẫn đảm bảo sắp xếp).

#### Iterator:
- begin và end
`s.begin(), s.end()` : trả về iterator ở phần tử đầu set và sau cuối set
- rbegin và rend
`s.rbegin(), s.rend()` : trả về reverse iterator ở phần tử cuối set và trước đầu set

#### Khai báo:
`set<type> name` : khởi tạo một set rỗng

#### Các hàm:
- size
`s.size()` : trả về độ dài của set
- empty
`s.empty()` : trả về *true* nếu set trống, *false* ngược lại
- clear
`s.clear()` : xóa mọi phần tử của set
- insert
`s.insert(val)` : thêm val vào set (tự động đảm bảo thứ tự các phần tử được sắp xếp)
- erase
`s.erase(val)` : xóa val khỏi set
- find
`s.find(val)` : trả về iterator của val trong set, hoặc nếu val không có trong set thì trả về s.end()

Example:

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    set<int> s;
    s.insert(7);
    s.insert(5);
    s.insert(12);
    s.insert(12)
    s.insert(-2);
    s.insert(-2);
    s.insert(3);
    s.erase(5);
	
    if(s.find(3) != s.end()) cout << "Contains 3!" << endl;
    else cout << "No 3!" << endl;

    cout << s.size() << endl;
    for(set<int>::iterator it = s.begin(); it != s.end(); ++it)
        cout << *it << ' ';
    cout << endl;
    s.clear();
    cout << s.empty(); // 1 (true)
	
    multiset<int> ms;
    ms.insert(1);
    ms.insert(1);
    ms.insert(2);
    ms.insert(2);
    ms.erase(1); // nếu erase như này thì sẽ xóa toàn bộ số 1 trong multiset
    ms.erase(ms.find(2)); // nếu muốn chỉ xóa 1 lần xuất hiện của số 2 có thể làm như này

    return 0;
}

<br></br>

## **Map**
Map là CTDL chứa giá trị theo cặp <key, value>. Các cặp <key, value> trong map thực chất là các pair, và được sắp xếp mặc định theo key tăng dần.
:::info
pair chỉ là một kiểu chứa 2 giá trị first và second: `pair<first_type, second_type>`

pair<char, int> p;
p.first = 'f';
p.second = 10;
cout << p.first << ' ' << p.second;

:::

#### Iterator:
- begin và end
`m.begin(), m.end()` : trả về iterator ở phần tử đầu map và sau cuối map
- rbegin và rend
`m.rbegin(), m.rend()` : trả về reverse iterator ở phần tử cuối map và trước đầu map

#### Khai báo:
`map<key_type, value_type> m` : khởi tạo một map trống

#### Các hàm:
- size
`m.size()` : trả về độ dài map
- operator []
`m[val]` : trả về value theo key x (với x thuộc kiểu key_type), nếu m[val] chưa tồn tại thì map sẽ tự tạo
- empty
`m.empty()` : trả về *true* nếu map trống, *false* ngược
lại
- clear
`m.clear()` : xóa mọi phần tử của map
- erase
`m.erase(val)` : xóa cặp <key, value> có key là val
- find
`m.find(val)` : trả về iterator ở vị trí của cặp <key, val> có key là val tìm được, nếu không có trả về end()

#### Example:

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    map<int, int> m;
    m[5] = 10;
    m[-4] = 9;
    m[69] = 420;
    m[5] = 5;
    m[17] = -6;
    m.erase(5);
    cout << m[3] << endl; // vì m[3] chưa có nên map cũng sẽ tự tạo một cặp <key, value> mới có key là 3, và gán giá trị mặc định cho value là 0
	
    if(m.find(69) != m.end()) cout << "Contains 69!" << endl;
    else cout << "No 69!" << endl;

    cout << m.size() << endl;
    for(map<int, int>::iterator it = m.begin(); it != m.end(); ++it)
        cout << it->first << ' ' << it->second << endl;
    m.clear();
    cout << m.empty(); // 1 (true)

    return 0;
}