STL Vector

Vector trong C++ STL (Standard Template Library) là một container template mạnh mẽ và linh hoạt để lưu trữ và quản lý một tập hợp các phần tử liên tiếp. Nó là một dạng mảng động, tự động mở rộng kích thước khi cần thiết và cung cấp nhiều phương thức hỗ trợ cho việc thao tác dữ liệu.

Ở bài viết này, chúng ta sẽ tìm hiểu một vài hàm thường xuyên được sử dụng trong vector, từ đó giúp tăng tốc độ code và tối ưu được sức mạnh của nó.

Cách khai báo STL Vector

#include <vector>
using namespace std;

vector<int> a1; // vector rỗng với kiểu dữ liệu int
vector<string> s1; // vector rỗng với kiểu dữ liệu string

vector<int> a2(4, 1); // vector gồm 4 phần tử là 1
vector<int> a3 = {1, 2, 3, 4}; // vector gồm 4 phần tử 1, 2, 3, 4


vector<vector<int>> a4; // vector 2 chiều rỗng
vector<vector<int>> a5(3, 4); // vector 2 chiều có kích thước 3x4

vector<vector<int>> a6(3); // tạo ra 3 vector 1 chiều rỗng

vector<vector<int>> a7(3, vector<int>(4, 1)) // tạo ra vector 2 chiều 3x4 với các giá trị là 1

vector<vector<int>> a8 = {
    {1, 2, 3},
    {4, 5, 6}
}; // vector 2 chiều 2x3 với các phần tử được khởi tạo giá trị sẵn

\(size()\)

Hàm size sẽ trả về số phần tử thuộc vector trong \(O(1)\).

vector<int> v = {3, 1, 4, 2, 5};
cout << v.size(); // 5

Tuy nhiên, cần lưu ý rằng hàm \(size()\) trả về một kiểu dữ liệu unsigned nên code như sau sẽ chạy vô tận

vector<int> v;
for (int i = 0; i <= v.size() - 1; i++){
    cout << v[i];
}

// Lưu ý v.size() - 1 sẽ không ra -1.
// Để khắc phục, ta sẽ ép kiểu của v.size()
for (int i = 0; i < (int)v.size() - 1; i++){
    cout << v[i];
}

\(resize()\)

Hàm này sẽ thay đổi kích thước của vector. Cú pháp là \(resize(n, val)\) với \(n\) là kích thước mới của vector, \(val\) là giá trị mặc định của phần tử mới được thêm vào vector nếu kích thước mới lớn hơn kích thước hiện tại của vector.

Lưu ý:

Nếu \(n\) lớn hơn kích thước hiện tại của vector, các phần tử mới sẽ được thêm vào cuối vector và có giá trị mặc định hoặc giá trị được chỉ định val.
Nếu \(n\) nhỏ hơn kích thước hiện tại của vector, các phần tử vượt quá kích thước mới sẽ bị xóa khỏi vector.

vector<int> v;
for (int i = 1; i < 10; i++) v.push_back(i);

v.resize(5);
v.resize(8,100);
v.resize(12);

for (int i = 0;i < v.size(); i++)
    cout << v[i] << " ";

// 1 2 3 4 5 100 100 100 0 0 0 0

Hàm này đặc biệt hữu dụng với những bài yêu cầu phải tạo mảng \(m \times n\) có giới hạn của \(m \times n\) mà không có giới hạn của \(m\) và \(n\).

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

int m, n;
// m * n <= 10^6
// vì m hoặc n có thể lên tới 10^6 
// nên ta không thể tạo mảng 10^6 * 10^6 
// sẵn được
vector<vector<int>> a;

int main(){
    cin >> m >> n;

    // ta sẽ resize lại vector
    a.resize(m, vector<int>(n));
}

\(front(), back()\)

Hàm \(front()\) sẽ trả về giá trị phần tử đầu tiên của vector trong \(O(1)\).
Hàm \(back()\) sẽ trả về giá trị của phần tử cuối cùng của vector cũng trong \(O(1)\).

vector<int> v = {1, 2, 3, 4, 5};
cout << v.front() << " " << v.back();
// 1 5

Lưu ý: Nếu sử dụng hai hàm này với vector rỗng thì sẽ gặp lỗi. Để khắc phục, ta trước tiên sẽ cần kiểm tra xem vector có phần tử nào không bằng hàm \(size()\)

vector<int> v;
if (v.size()) cout << v.front();

\(push_back(), pop_back()\)

Hàm \(push_back\) sẽ thêm phần tử vào cuối vector trong \(O(1)\).
Hàm \(pop_back\) loại bỏ phần tử cuối ở vector trong \(O(1)\).

Tuy nhiên, tương tư với hai hàm \(front\) và \(back\), nếu ta sử dụng trực tiếp hàm \(pop_back\) trực tiếp với vector rỗng thì sẽ gặp lỗi.

vector<int> v;
v.push_back(1); // v = {1}
v.pop_back(); // v = {}

Lưu ý, ta có thể sử dụng hàm \(emplace_back()\) thay thế cho \(push_back()\). Hàm \(emplace_back()\) trong đa số trường hợp sẽ có thời gian chạy tốt hơn so với hàm \(push_back()\). Lí do là vì hàm \(push_back()\) sẽ tạo một bản sao của phần tử sẽ được thêm vào rồi mới cho vào cuối của vector rồi hủy bản sao đó, còn \(emplace_back()\) thì phần tử sẽ được đưa vào vector trực tiếp. Điều này sẽ mang lại nhiều lợi ích khi ta sử dụng vector chứa một kiểu dữ liệu không nguyên thủy.

struct query{
    int type, op, cl, id;
    bool check;
};
vector<query> q;
...
q.emplace_back({1, 1, 5, 1, 0});

\(erase(iterator \; first, iterator \; last)\). Hàm này xóa tất cả các phần tử trong khoảng từ \(iterator \; first\) đến \(iterator \; last – 1\) trong \(O(n)\)
```
vector<int> v = {1, 2, 3, 4, 5};
v.erase(v.begin() + 1);
// v = {1, 3, 4, 5}
```

\(clear()\)

Hàm \(clear()\) đơn giản sẽ xóa tất cả các phần tử của vector. Hàm này hữu dụng khi ta muốn giải phóng tài nguyên của vector và đặc biệt trong những bài có nhiều bộ dữ liệu mà cần sử dụng lại vector để chứa dữ liệu mới.

vector<int> v = {1, 2, 3, 4};
v.clear();
// v = {}

\(empty()\)

Hàm này sẽ trả giá trị \(true\) nếu vector rỗng và ngược lại.

vector<int> v = {};
cout << v.empty() << endl;
// 1

\(swap()\)

Hàm \(swap()\) sẽ hoán đổi dữ liệu giữa hai vector

vector<int> v1 = {1, 2, 3};
vector<int> v2 = {4, 5, 6};

v1.swap(v2);
for (auto v : v1) cout << v << " ";
cout << endl;
for (auto v : v2) cout << v << " ";
cout << endl;
// 4 5 6
// 1 2 3

\(reverse()\)

Hàm \(reverse()\) được sử dụng để đảo thứ tự các phần tử trong một dãy.

vector<int> v = {1, 2, 3, 4, 5};
reverse(v.begin(), v.end());
for (auto x : v) cout << x << " ";
cout << endl;

reverse(v.begin() + 1, v.begin() + 3);
for (auto x : v) cout << x << " ";
cout << endl;
// 5 4 3 2 1 
// 5 3 4 2 1