Cheatsheet C++

đã đăng vào 31 tháng 3 năm 2025, 11:38 p.m.

Hướng dẫn sử dụng mt19937 và mt19937_64 trong C++

📌 Mục tiêu

  • Giải thích cách sử dụng bộ sinh số ngẫu nhiên chất lượng cao trong C++
  • Phân biệt mt19937 (32-bit) và mt19937_64 (64-bit)
  • Hướng dẫn sinh số ngẫu nhiên, số trong khoảng, số thực, mảng ngẫu nhiên

🧠 Tổng quan

mt19937 và mt19937_64 là gì?
  • Là bộ sinh số ngẫu nhiên dựa trên thuật toán Mersenne Twister.
  • mt19937: sinh số nguyên 32-bit (unsigned int).
  • mt19937_64: sinh số nguyên 64-bit (unsigned long long).
  • Chu kỳ rất dài, phân phối đồng đều, dùng nhiều trong lập trình thi đấu và mô phỏng.

🔧 Code mẫu cơ bản

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

mt19937 rng32(time(0));         // Sinh số ngẫu nhiên 32-bit
mt19937_64 rng64(time(0));      // Sinh số ngẫu nhiên 64-bit

int main() {
    cout << "random 32 (bit): " << rng32() << endl;
    cout << "random 64 (bit): " << rng64() << endl;
}

📘 C++ Hash Map Cheatsheet: map, unordered_map, gp_hash_table

1. std::map

  • Dạng: Cây đỏ-đen (Red-Black Tree)
  • Tự động sắp xếp theo key
  • Độ phức tạp: O(log n) cho các thao tác chèn, tìm kiếm, xóa
#include <bits/stdc++.h>
using namespace std;

unordered_map<int, int> um;

int main() {
    map<int, int> mp;
    mp[1] = 100;
    if (mp.count(1)) {
        cout << mp[1];  // Output: 100
    }
}

✅ Ưu điểm:

  • Sắp xếp theo key
  • Ổn định

❌ Nhược điểm:

  • Chậm hơn unordered_map hoặc gp_hash_table với dữ liệu ngẫu nhiên

2. std::unordered_map

  • Dạng: Hash Table chuẩn
  • Không sắp xếp theo key
  • Độ phức tạp trung bình: O(1) (xấu nhất O(n))

🛠 Tip: Tăng hiệu năng bằng reserve() khi biết trước số phần tử:

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

unordered_map<int, int> um;

int main() {
    um.reserve(1000000);
    um[3] = 3;
    cout << um[3];
}

3. __gnu_pbds::gp_hash_table

  • Cấu trúc dữ liệu thay thế unordered_map với hiệu suất cao hơn
  • Cần include đặc biệt:
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

int main() {
    gp_hash_table<int, int> m;
    m[3] = 1;
    cout << m[3];
}

✅ Ưu điểm:

  • Rất nhanh cho dữ liệu ngẫu nhiên
  • Ít bị đụng độ hash

❌ Nhược điểm:

  • Không tương thích với Clang
  • Không có trong chuẩn STL, chỉ dùng trên GCC (như Codeforces)

4. So sánh hiệu suất

Dữ liệu std::map unordered_map gp_hash_table
Tìm kiếm log(n) Trung bình O(1) Nhanh hơn O(1)
Bộ nhớ Cao Thấp - TB Tối ưu tốt
Dữ liệu ngẫu nhiên Chậm TB - có thể bị tệ Rất tốt
Hỗ trợ Clang ✔️ ✔️ ❌

5. Một số tối ưu khi dùng unordered_map

unordered_map<int, int> um;
um.reserve(1 << 20);              // Dự phòng bộ nhớ
um.max_load_factor(0.25);        // Giảm load factor để tránh đụng độ hash

6. Khi nào dùng cái nào?

Trường hợp Cấu trúc phù hợp
Cần sắp xếp key std::map
Tìm kiếm nhanh, không cần sắp xếp unordered_map
Dữ liệu ngẫu nhiên lớn, cần tốc độ gp_hash_table (nếu dùng GCC)

7. Bài tập áp dụng

📌 Ghi chú

  • Với test ngẫu nhiên lớn, gp_hash_table thường vượt trội về thời gian và bộ nhớ.
  • Nếu không dùng được gp_hash_table, bạn có thể thử tùy biến unordered_map bằng cách tự viết hàm hash.
struct custom_hash {
    size_t operator()(uint64_t x) const {
        return x ^ (x >> 16);
    }
};
unordered_map<uint64_t, int, custom_hash> safe_map;

📘 C++ Cheatsheet: vector 1 chiều & 2 chiều

1. vector 1 chiều

🔹 Khai báo
vector<int> a;                // Vector rỗng
vector<int> b(5);             // Vector 5 phần tử, giá trị mặc định = 0
vector<int> c(5, -1);         // Vector 5 phần tử, mỗi phần tử = -1
🔹 Truy cập phần tử
a[0], a.at(0);               // Truy cập phần tử đầu tiên
a.front();                   // Phần tử đầu
a.back();                    // Phần tử cuối
🔹 Thêm / Xóa phần tử
a.push_back(10);             // Thêm vào cuối
a.pop_back();                // Xóa phần tử cuối
a.insert(a.begin() + 2, 100);// Chèn 100 tại vị trí thứ 2
a.erase(a.begin() + 1);      // Xóa phần tử tại vị trí thứ 1
🔹 Duyệt
for (int x : a) cout << x;
for (int i = 0; i < a.size(); ++i) cout << a[i];
🔹 Resize & Clear
a.resize(10);                // Thay đổi kích thước thành 10 phần tử
a.clear();                   // Xóa toàn bộ phần tử
🔹 Gán
a = vector<int>(5, 7);       // Gán lại vector a thành 5 phần tử = 7
a.assign(3, 100);            // Gán 3 phần tử bằng 100

2. vector 2 chiều

🔹 Khai báo
int n = 3, m = 4;
vector<vector<int>> mat(n, vector<int>(m));          // ma trận n x m, mặc định 0
vector<vector<int>> mat2(n, vector<int>(m, -1));     // ma trận n x m, mỗi phần tử = -1
🔹 Truy cập & Duyệt
mat[i][j];                    // Truy cập phần tử hàng i, cột j

for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j)
        cout << mat[i][j];
🔹 Resize sau khai báo
vector<vector<int>> mat;
mat.resize(n, vector<int>(m, 0));   // Resize thành n x m, tất cả = 0
🔹 Gán lại toàn bộ
mat.assign(n, vector<int>(m, 1));  // Gán lại ma trận n x m toàn bộ = 1

3. Một số mẹo

  • Duyệt nhanh:

    for (auto &row : mat)
  for (auto x : row)
      cout << x << " ";

  • Xoay chiều ma trận:

    vector<vector<int>> rotate90(const vector<vector<int>>& mat) {
  int n = mat.size(), m = mat[0].size();
  vector<vector<int>> res(m, vector<int>(n));
  for (int i = 0; i < n; ++i)
      for (int j = 0; j < m; ++j)
          res[j][n - 1 - i] = mat[i][j];
  return res;
}

🔚 Tổng kết

Tác vụ Cú pháp
Khởi tạo vector<int> v(n, val);
Resize v.resize(new_size);
Gán toàn bộ v.assign(n, val);
Vector 2D vector<vector<int>> mat(n, vector<int>(m));
Xóa v.clear();
Truy cập v[i], mat[i][j]
Duyệt for (int x : v) hoặc for (auto x : row)

Nhận xét

Không có ý kiến tại thời điểm này.