tritue.edu.vn

Vector: mảng động trong C++

std::vector là một cấu trúc dữ liệu thuộc thư viện chuẩn STL (Standard Template Library), hoạt động như một mảng động có khả năng tự động thay đổi kích thước khi thêm hoặc xóa phần tử.

1. Khai báo và khởi tạo

Cần khai báo thư viện: #include <vector>
Khai báo vector rỗng: vector<int> v;
Khai báo vector có sẵn n phần tử: vector<int> v(n);
Khai báo và gán giá trị ban đầu: vector<int> v = {1, 2, 3};

2. Truy cập phần tử

v[i]: Truy cập phần tử tại chỉ số i (nhanh nhưng không kiểm tra vượt quá giới hạn).
v.at(i): Truy cập phần tử tại chỉ số i, có kiểm tra ngoại lệ nếu vượt quá kích thước.
v.front(): Lấy phần tử đầu tiên của vector.
v.back(): Lấy phần tử cuối cùng của vector.
v.data(): Trả về con trỏ tới vùng nhớ lưu trữ mảng bên trong vector.

3. Thêm và xóa phần tử

v.push_back(val): Thêm phần tử val vào cuối vector (Độ phức tạp \(O(1)\)).
v.emplace_back(val): Thêm phần tử vào cuối vector nhưng tối ưu hiệu năng hơn bằng cách khởi tạo trực tiếp tại chỗ.
v.pop_back(): Xóa phần tử ở cuối vector (Độ phức tạp \(O(1)\)).
v.insert(pos, val): Chèn phần tử val vào vị trí iterator pos (Độ phức tạp \(O(N)\)).
v.erase(pos): Xóa phần tử tại vị trí iterator pos (Độ phức tạp \(O(N)\)).
v.erase(first, last): Xóa một dải phần tử từ iterator first đến trước last.
v.clear(): Xóa toàn bộ phần tử trong vector (kích thước size() trở thành 0).

4. Kích thước và dung lượng (Size & Capacity)

v.size(): Trả về số lượng phần tử hiện tại có trong vector.
v.empty(): Kiểm tra vector có rỗng hay không (trả về true nếu rỗng).
v.resize(n): Thay đổi kích thước vector thành n phần tử.
v.capacity(): Trả về sức chứa hiện tại của bộ nhớ cấp phát cho vector.
v.shrink_to_fit(): Yêu cầu giảm dung lượng bộ nhớ cấp phát bằng với số lượng phần tử hiện tại.

5. Duyệt vector (Iterator)

v.begin(): Trả về iterator trỏ đến phần tử đầu tiên.
v.end(): Trả về iterator trỏ đến vị trí ngay sau phần tử cuối cùng.
Có thể dùng vòng lặp for-each hiện đại: for (int x : v) { ... } hoặc dùng chỉ số for (int i = 0; i < v.size(); i++).

6. Các thuật toán hỗ trợ phổ biến (`<algorithm>`)

sort(v.begin(), v.end()): Sắp xếp các phần tử tăng dần.
reverse(v.begin(), v.end()): Đảo ngược thứ tự các phần tử trong vector.
swap(v1, v2): Hoán đổi nội dung của hai vector v1 và v2.

Code minh họa

Copy

         // ===== <vector>: mảng động =====

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

void in(const vector<int>& v) { for (int x : v) cout << x << " "; cout << "\n"; }

 

int main() {

    // ----------

    vector<int> v = {5, 2, 8};

    v.push_back(1);                           // thêm cuối

    cout << "size=" << v.size() << ", v[0]=" << v[0] << ", back=" << v.back() << "\n";

    v.pop_back();                             // xóa phần tử cuối

    cout << "at(1)=" << v.at(1) << "\n";      // at() kiểm tra biên, [] thì không

    cout << "rong? " << v.empty() << "\n";

 

    // ----------

    v.insert(v.begin() + 1, 99);              // chèn 99 vào vị trí 1

    in(v);

 

    v.erase(v.begin());                       // xóa phần tử đầu

    in(v);

 

    sort(v.begin(), v.end());                 // sắp xếp tăng

    in(v);

 

    auto it = find(v.begin(), v.end(), 8);    // tìm phần tử

    if (it != v.end()) cout << "8 o vi tri " << it - v.begin() << "\n";

 

    vector<int> w(5, 7);                      // 5 phần tử, đều bằng 7

    in(w);

 

    vector<vector<int>> mt(3, vector<int>(4, 0));   // ma trận 3x4

    mt[1][2] = 5;

    cout << "mt[1][2]=" << mt[1][2] << "\n";

 

    // ----------

   

    vector<int> x;

    x.reserve(100);                           // cấp trước bộ nhớ, tránh cấp phát lại

    cout << "size=" << x.size() << ", capacity=" << x.capacity() << "\n";

    for (int i = 1; i <= 10; i++) x.emplace_back(i);   // dựng phần tử tại chỗ

    // Idiom erase-remove: xóa mọi số chẵn

    x.erase(remove_if(x.begin(), x.end(), [](int k) { return k % 2 == 0; }), x.end());

    in(x);

   

    vector<int> d = {3, 1, 3, 2, 1};

    sort(d.begin(), d.end());

 

    d.erase(unique(d.begin(), d.end()), d.end());      // loại phần tử trùng

    in(d);

 

    cout << "lower_bound(2) -> " << *lower_bound(d.begin(), d.end(), 2) << "\n";

    vector<int> chuyen = move(d);             // chuyển quyền sở hữu, không copy

 

    cout << "sau move, d.size()=" << d.size() << "\n";

    x.shrink_to_fit();                        // thu nhỏ capacity cho vừa size

    reverse(x.begin(), x.end());

    for (auto r = x.rbegin(); r != x.rend(); ++r) cout << *r << " ";   // duyệt ngược

    cout << "\n";

    return 0;

}

Link chia sẻ bài viết