Try   HackMD

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;
}



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;
}



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;
}



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;
}



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.

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;
}
Last changed by 
 
Đỗ Đăng Khoa
0
1
82

Read more

Nguyên tố, ước nguyên tố

Ta có thể thấy rằng mọi hợp số n đều có ít nhất 2 ước i và j (i \le j, i, j \neq 1, n) sao cho i \cdot j = n. Vậy chỉ cần kiểm tra tất cả các i, và vì i lớn nhất có thể là \sqrt n nên ta chỉ cần kiểm tra các số trong khoảng \left[2; \sqrt n\right].

May 21, 2025
mod

[TOC]([ok] (https://cp-algorithms.com/algebra/module-inverse.html))

Jun 1, 2024
Lời giải môn tin kì thi tuyển sinh 10 PTNK 2024

Cho một bảng hình chữ nhật N \cdot M

May 27, 2024
Lũy thừa nhị phân

Thuật toán tính a^b bình thường nếu chỉ chạy b lần rồi nhân a vào kết quả sẽ có độ phức tạp O(b), không hiệu quả với b lớn. Đối với thuật toán lũy thừa nhị phân dùng chia để trị chỉ mất độ phức tạp O(\log b), cực kì hiệu quả.

Mar 7, 2024
Read more from Đỗ Đăng Khoa
Published on HackMD