Bài 6.3. Vector và các thao tác hiệu quả

Chào mừng trở lại với series về Cấu trúc dữ liệu và Giải thuật! Sau khi đã làm quen với những khái niệm cơ bản, hôm nay chúng ta sẽ đi sâu vào một trong những cấu trúc dữ liệu phổ biến và mạnh mẽ nhất trong C++ STL (Standard Template Library): std::vector.

Nếu bạn thường xuyên làm việc với C++, chắc hẳn bạn đã gặp hoặc sử dụng vector. Nó được coi là "ngôi sao" hay "ngựa thồ" trong rất nhiều ứng dụng thực tế bởi sự linh hoạt và hiệu quả của mình. Vậy vector là gì và làm sao để sử dụng nó hiệu quả nhất? Hãy cùng tìm hiểu!

Vector Là Gì? Sức Mạnh Của Mảng Động

Hãy tưởng tượng bạn cần lưu trữ một danh sách các số nguyên, nhưng bạn không biết chính xác sẽ có bao nhiêu số. Một mảng tĩnh thông thường (int arr[10];) yêu cầu bạn phải khai báo kích thước cố định từ đầu, điều này gây lãng phí bộ nhớ nếu bạn cần ít hơn hoặc gây tràn bộ đệm nếu bạn cần nhiều hơn.

Đây chính là lúc std::vector tỏa sáng. Vector là một template class cung cấp chức năng của một mảng động. Nó có khả năng tự động thay đổi kích thước khi bạn thêm hoặc bớt phần tử.

Dưới "mũ" của vector, nó sử dụng một khối bộ nhớ liên tục (contiguous memory), giống như mảng tĩnh. Điều này là cực kỳ quan trọng vì nó cho phép vector có những ưu điểm về hiệu suất tương tự như mảng tĩnh, đặc biệt là khả năng truy cập ngẫu nhiên (random access) các phần tử một cách rất nhanh chóng.

Điểm khác biệt lớn nhất so với mảng tĩnh là vector quản lý bộ nhớ cho bạn. Khi vector đầy và bạn thêm một phần tử mới, nó sẽ tự động cấp phát một vùng nhớ lớn hơn (thường là gấp đôi kích thước hiện tại), sao chép các phần tử cũ sang vùng nhớ mới và giải phóng vùng nhớ cũ. Quá trình này gọi là tái cấp phát (reallocation).

Khởi Tạo Vector: Bắt Đầu Hành Trình

Bạn có thể khởi tạo vector theo nhiều cách khác nhau:

Vector rỗng: Tạo một vector không có phần tử nào.

#include <vector>
#include <iostream>

int main() {
    std::vector<int> myVector;
    std::cout << "Kich thuoc ban dau: " << myVector.size() << std::endl;
    return 0;
}

Giải thích: Khai báo một vector có thể chứa các phần tử kiểu int. Ban đầu nó rỗng, size() trả về 0.

Vector với kích thước cố định: Tạo một vector với n phần tử. Các phần tử sẽ được value-initialized (đối với số nguyên là 0, đối với đối tượng là gọi constructor mặc định).

#include <vector>
#include <iostream>

int main() {
    std::vector<int> vectorWithSize(5); // 5 phan tu, gia tri mac dinh la 0
    std::vector<std::string> vectorOfString(3); // 3 phan tu, gia tri mac dinh la "" (chuoi rong)

    std::cout << "Kich thuoc vectorWithSize: " << vectorWithSize.size() << std::endl;
    std::cout << "Phan tu dau tien: " << vectorWithSize[0] << std::endl; // Output: 0
    std::cout << "Kich thuoc vectorOfString: " << vectorOfString.size() << std::endl;
    std::cout << "Phan tu dau tien (string): '" << vectorOfString[0] << "'" << std::endl; // Output: ''

    return 0;
}

Giải thích: Vector được tạo với kích thước ban đầu, và các phần tử được gán giá trị mặc định tương ứng với kiểu dữ liệu.

Vector với kích thước và giá trị khởi tạo: Tạo một vector với n phần tử, tất cả đều có cùng một giá trị ban đầu.

#include <vector>
#include <iostream>

int main() {
    std::vector<double> vectorWithValues(4, 3.14); // 4 phan tu, tat ca la 3.14

    std::cout << "Kich thuoc vectorWithValues: " << vectorWithValues.size() << std::endl;
    std::cout << "Phan tu dau tien: " << vectorWithValues[0] << std::endl; // Output: 3.14
    std::cout << "Phan tu cuoi cung: " << vectorWithValues[3] << std::endl; // Output: 3.14

    return 0;
}

Giải thích: Tạo một vector gồm 4 phần tử, mỗi phần tử đều có giá trị là 3.14.

Truy Cập Các Phần Tử: Nhanh Chóng Như Mảng Tĩnh

Vì vector lưu trữ các phần tử trong bộ nhớ liên tục, việc truy cập một phần tử bất kỳ theo chỉ mục (index) là cực kỳ hiệu quả - chỉ mất thời gian hằng số (O(1)), giống như mảng tĩnh.

Bạn có hai cách chính để truy cập:

Sử dụng toán tử []: Cú pháp giống như mảng truyền thống. Lưu ý: Toán tử [] không kiểm tra chỉ mục có hợp lệ hay không. Nếu bạn truy cập một chỉ mục nằm ngoài phạm vi của vector, chương trình sẽ gây ra lỗi undefined behavior (có thể crash hoặc cho kết quả không mong muốn).
```
std::vector<int> numbers = {10, 20, 30, 40, 50};
std::cout << "Phan tu thu 2 (chi muc 1): " << numbers[1] << std::endl; // Output: 20

// Can than! Chi muc ngoai pham vi (undefined behavior)
// std::cout << numbers[10] << std::endl; // Ngan chan loi
```

Sử dụng phương thức at(): Phương thức này cũng truy cập phần tử theo chỉ mục, nhưng nó có kiểm tra chỉ mục. Nếu chỉ mục không hợp lệ, nó sẽ ném ra một ngoại lệ (std::out_of_range). Cách này an toàn hơn nhưng có thể chậm hơn một chút so với [] do chi phí kiểm tra.

std::vector<int> numbers = {10, 20, 30, 40, 50};
std::cout << "Phan tu thu 4 (chi muc 3) su dung at(): " << numbers.at(3) << std::endl; // Output: 40

try {
    // Thu truy cap chi muc ngoai pham vi
    std::cout << numbers.at(10) << std::endl;
} catch (const std::out_of_range& e) {
    std::cerr << "Loi: " << e.what() << std::endl; // Output: std::out_of_range
}

Khi nào dùng [], khi nào dùng at()? Nếu bạn chắc chắn chỉ mục luôn hợp lệ (ví dụ: khi lặp qua vector bằng vòng lặp dựa trên size()), [] thường được ưu tiên vì hiệu suất. Nếu có khả năng chỉ mục không hợp lệ hoặc bạn muốn có cơ chế xử lý lỗi rõ ràng, hãy dùng at().

Kích Thước và Dung Lượng: Hiểu Rõ Vector Của Bạn

Vector có hai khái niệm liên quan đến kích thước:

size(): Số lượng phần tử thực sự đang có trong vector.
capacity(): Số lượng phần tử tối đa mà vector có thể chứa trước khi nó cần tái cấp phát bộ nhớ.

#include <vector>
#include <iostream>

int main() {
    std::vector<int> v;

    std::cout << "Ban dau:" << std::endl;
    std::cout << "  Size: " << v.size() << std::endl; // Output: 0
    std::cout << "  Capacity: " << v.capacity() << std::endl; // Output: 0 (hoac mot so nho)

    v.push_back(10);
    v.push_back(20);
    v.push_back(30);

    std::cout << "\nSau khi them 3 phan tu:" << std::endl;
    std::cout << "  Size: " << v.size() << std::endl; // Output: 3
    std::cout << "  Capacity: " << v.capacity() << std::endl; // Co the la 4, 8, ... tuy thuoc implement

    v.push_back(40); // Co the gay tai cap phat

    std::cout << "\nSau khi them phan tu thu 4:" << std::endl;
    std::cout << "  Size: " << v.size() << std::endl; // Output: 4
    std::cout << "  Capacity: " << v.capacity() << std::endl; // Co the la 4, 8, ... (da tang neu can)

    return 0;
}

Giải thích: capacity() luôn lớn hơn hoặc bằng size(). Khi size() bằng capacity() và bạn cố gắng thêm phần tử, vector phải cấp phát bộ nhớ mới, lớn hơn, và di chuyển tất cả các phần tử hiện có sang đó.

Ngoài ra, bạn có thể kiểm tra vector có rỗng hay không bằng empty() (trả về true nếu size() là 0).

std::vector<int> emptyVector;
std::vector<int> nonEmptyVector = {1, 2};

std::cout << "emptyVector co rong khong? " << (emptyVector.empty() ? "Co" : "Khong") << std::endl;
std::cout << "nonEmptyVector co rong khong? " << (nonEmptyVector.empty() ? "Co" : "Khong") << std::endl;

Thêm Phần Tử: Chìa Khóa Của Mảng Động

Vector cung cấp hai phương thức chính để thêm phần tử:

push_back(value): Thêm phần tử vào cuối vector. Đây là thao tác phổ biến nhất và thường là hiệu quả nhất để thêm phần tử vào vector.
- Hiệu quả: Trung bình, thao tác này có độ phức tạp thời gian hằng số (amortized O(1)). Điều này có nghĩa là mặc dù thỉnh thoảng nó có thể mất thời gian O(n) khi cần tái cấp phát (sao chép n phần tử), nhưng chi phí đó được phân tán đều trên nhiều thao tác thêm, làm cho chi phí trung bình trên mỗi lần thêm rất nhỏ. ```cpp #include <vector> #include <iostream>
int main() {
```
std::vector<int> data;
data.push_back(10);
data.push_back(20);
data.push_back(30);

// In vector
for (int val : data) {
    std::cout << val << " "; // Output: 10 20 30
}
std::cout << std::endl;

return 0;
```
} ```
insert(iterator, value) / insert(iterator, count, value) / insert(iterator, first, last): Chèn một hoặc nhiều phần tử vào một vị trí bất kỳ trong vector (được chỉ định bởi iterator).
- Hiệu quả: Thao tác này có độ phức tạp thời gian tuyến tính (O(n)). Bởi vì vector sử dụng bộ nhớ liên tục, khi bạn chèn phần tử vào giữa hoặc đầu, tất cả các phần tử sau vị trí chèn phải được dời chỗ để tạo không gian cho phần tử mới. Việc dời chỗ này tốn thời gian tỷ lệ thuận với số lượng phần tử cần dời. ```cpp #include <vector> #include <iostream> #include <algorithm> // Can cho std::copy
int main() {
```
std::vector<int> data = {10, 30, 40};

// Chen 20 vao vi tri thu 2 (sau 10)
data.insert(data.begin() + 1, 20);
// Vector bay gio la: {10, 20, 30, 40}

// Chen 0 vao dau vector
data.insert(data.begin(), 0);
// Vector bay gio la: {0, 10, 20, 30, 40}

// Chen 5 phan tu co gia tri 100 vao cuoi vector
data.insert(data.end(), 5, 100);
// Vector bay gio la: {0, 10, 20, 30, 40, 100, 100, 100, 100, 100}

// In vector
for (int val : data) {
    std::cout << val << " ";
}
std::cout << std::endl;

return 0;
```
} `` *Giải thích:*data.begin() + 1trả về iterator trỏ đến phần tử thứ hai. Việc chèn ở đầu (dùngdata.begin()) hoặc ở giữa vector đòi hỏi việc dịch chuyển các phần tử sau đó, làm cho thao tác này kém hiệu quả hơnpush_back`.

Lời khuyên về hiệu quả: Luôn ưu tiên sử dụng push_back() khi có thể. Chỉ sử dụng insert() khi bạn thực sự cần chèn phần tử vào giữa hoặc đầu vector và chấp nhận chi phí hiệu năng O(n).

Xóa Phần Tử: Cẩn Thận Với Chi Phí

Tương tự như thêm, vector cũng có các phương thức xóa với hiệu quả khác nhau:

pop_back(): Xóa phần tử ở cuối vector.
- Hiệu quả: Thao tác này có độ phức tạp thời gian hằng số (O(1)). Đơn giản chỉ là giảm kích thước logic của vector, không cần dịch chuyển phần tử nào. ```cpp #include <vector> #include <iostream>
int main() {
```
std::vector<int> data = {10, 20, 30, 40};

data.pop_back(); // Xoa 40
// Vector bay gio la: {10, 20, 30}

data.pop_back(); // Xoa 30
// Vector bay gio la: {10, 20}

// In vector
for (int val : data) {
    std::cout << val << " ";
}
std::cout << std::endl;

return 0;
```
} ```
erase(iterator) / erase(first, last): Xóa một phần tử hoặc một phạm vi các phần tử được chỉ định bởi iterator.
- Hiệu quả: Thao tác này có độ phức tạp thời gian tuyến tính (O(n)). Khi bạn xóa một phần tử ở giữa hoặc đầu, tất cả các phần tử sau vị trí bị xóa phải được dời chỗ về phía trước để lấp đầy khoảng trống. Việc dời chỗ này tốn thời gian tỷ lệ thuận với số lượng phần tử cần dời. ```cpp #include <vector> #include <iostream> #include <algorithm> // Can cho std::find hoac loop
int main() {
```
std::vector<int> data = {0, 10, 20, 30, 40, 100, 100, 100, 100, 100};

// Xoa phan tu tai chi muc 2 (gia tri 20)
data.erase(data.begin() + 2);
// Vector bay gio la: {0, 10, 30, 40, 100, 100, 100, 100, 100}

// Xoa 3 phan tu cuoi cung (cac gia tri 100)
data.erase(data.end() - 3, data.end());
// Vector bay gio la: {0, 10, 30, 40, 100, 100}

// In vector
for (int val : data) {
    std::cout << val << " ";
}
std::cout << std::endl;

return 0;
```
} `` *Giải thích:* Tương tự nhưinsert,eraseở đầu hoặc giữa vector gây ra chi phí dịch chuyển, làm cho nó kém hiệu quả hơnpop_back`.

clear(): Xóa tất cả các phần tử khỏi vector. Vector trở nên rỗng (size = 0), nhưng capacity có thể vẫn giữ nguyên (tùy thuộc vào implement, nhưng thường không giảm ngay lập tức).
```
std::vector<int> data = {1, 2, 3, 4, 5};
data.clear();
std::cout << "Kich thuoc sau khi clear: " << data.size() << std::endl; // Output: 0
```

Lời khuyên về hiệu quả: Luôn ưu tiên sử dụng pop_back() khi có thể. Chỉ sử dụng erase() khi bạn cần xóa phần tử từ giữa hoặc đầu và chấp nhận chi phí hiệu năng O(n).

Lưu ý quan trọng về Iterator sau khi erase: Khi bạn gọi erase(iterator) hoặc erase(first, last), tất cả các iterator hoặc con trỏ trỏ đến các phần tử tại hoặc sau vị trí bị xóa đều trở nên không còn hiệu lực (invalidated). Phương thức erase trả về một iterator trỏ đến phần tử tiếp theo sau phần tử cuối cùng bị xóa. Nếu bạn xóa trong vòng lặp, phải sử dụng iterator trả về này để tiếp tục vòng lặp một cách an toàn.
```
#include <vector>
#include <iostream>

int main() {
    std::vector<int> numbers = {10, 20, 30, 40, 50, 60};

    // Xoa cac phan tu lon hon 30
    for (auto it = numbers.begin(); it != numbers.end(); ) {
        if (*it > 30) {
            // Xoa phan tu hien tai. 'erase' tra ve iterator den phan tu tiep theo.
            it = numbers.erase(it);
        } else {
            // Khong xoa, tien toi phan tu tiep theo mot cach binh thuong.
            ++it;
        }
    }

    // In vector sau khi xoa
    for (int val : numbers) {
        std::cout << val << " "; // Output: 10 20 30
    }
    std::cout << std::endl;

    return 0;
}
```
Giải thích: Vòng lặp này đúng. Khi một phần tử bị xóa, erase(it) trả về iterator đến phần tử ngay sau phần tử vừa bị xóa (vốn đã dịch chuyển lên). Chúng ta gán kết quả này lại cho it để tiếp tục vòng lặp từ vị trí đúng. Nếu không xóa, chúng ta tăng it như bình thường.

Quản Lý Dung Lượng: Tránh Tái Cấp Phát Không Cần Thiết

Như đã đề cập, tái cấp phát (reallocation) xảy ra khi size() bằng capacity() và bạn thêm phần tử. Quá trình này bao gồm cấp phát bộ nhớ mới, sao chép tất cả phần tử cũ, và giải phóng bộ nhớ cũ. Đây là một thao tác có thể tốn kém (O(n)).

Nếu bạn ước tính được số lượng phần tử tối đa mà vector của bạn có thể chứa hoặc biết rằng bạn sẽ thêm một lượng lớn phần tử, bạn có thể sử dụng phương thức reserve(n) để yêu cầu vector cấp phát trước một dung lượng bộ nhớ đủ lớn (ít nhất là n). Điều này giúp tránh hoặc giảm thiểu số lần tái cấp phát xảy ra trong quá trình thêm phần tử, từ đó cải thiện đáng kể hiệu suất.

#include <vector>
#include <iostream>

int main() {
    std::vector<int> data;

    std::cout << "Ban dau:" << std::endl;
    std::cout << "  Size: " << data.size() << std::endl;
    std::cout << "  Capacity: " << data.capacity() << std::endl;

    // Uoc tinh se them khoang 100 phan tu, yeu cau vector cap phat truoc
    data.reserve(100);

    std::cout << "\nSau khi reserve(100):" << std::endl;
    std::cout << "  Size: " << data.size() << std::endl; // Size van la 0
    std::cout << "  Capacity: " << data.capacity() << std::endl; // >= 100

    // Bay gio them phan tu se rat hieu qua (O(1) tuyet doi) cho den khi vuot qua capacity
    for (int i = 0; i < 50; ++i) {
        data.push_back(i);
    }

    std::cout << "\nSau khi them 50 phan tu:" << std::endl;
    std::cout << "  Size: " << data.size() << std::endl; // Output: 50
    std::cout << "  Capacity: " << data.capacity() << std::endl; // Van la >= 100 (chua tai cap phat)

    // Them them phan tu cho den khi gan day capacity
    for (int i = 50; i < 100; ++i) {
        data.push_back(i);
    }

    std::cout << "\nSau khi them 100 phan tu tong cong:" << std::endl;
    std::cout << "  Size: " << data.size() << std::endl; // Output: 100
    std::cout << "  Capacity: " << data.capacity() << std::endl; // Van la >= 100

    data.push_back(101); // Co the gay tai cap phat neu capacity = 100

    std::cout << "\nSau khi them phan tu thu 101:" << std::endl;
    std::cout << "  Size: " << data.size() << std::endl; // Output: 101
    std::cout << "  Capacity: " << data.capacity() << std::endl; // Co the da tang

    return 0;
}

Giải thích: reserve() chỉ ảnh hưởng đến capacity(), không thay đổi size(). Bằng cách gọi reserve() trước khi bắt đầu thêm nhiều phần tử bằng push_back(), chúng ta đảm bảo rằng vector có đủ không gian, tránh được các lần tái cấp phát tốn kém. Điều này đặc biệt quan trọng khi bạn thêm hàng ngàn hoặc hàng triệu phần tử.

Phương thức resize(n) thì khác. Nó thay đổi size() của vector thành n.

Nếu n nhỏ hơn size() hiện tại, các phần tử ở cuối sẽ bị xóa.
Nếu n lớn hơn size() hiện tại, vector sẽ được mở rộng đến kích thước n và các phần tử mới sẽ được value-initialized. resize() có thể gây tái cấp phát nếu dung lượng hiện tại không đủ cho kích thước mới. ```cpp std::vector<int> data = {1, 2, 3, 4, 5}; data.resize(3); // data = {1, 2, 3} data.resize(7); // data = {1, 2, 3, 0, 0, 0, 0} (gia tri mac dinh la 0 cho int) data.resize(9, 99); // data = {1, 2, 3, 0, 0, 0, 0, 99, 99} (gia tri moi la 99)

Bài tập ví dụ:

Đếm số nguyên tố

Mô tả

Cho mảng số nguyên A[] gồm N phần tử, hãy đếm các số nguyên tố trong mảng.

Input Format

Dòng đầu tiên là N : số lượng phần tử trong mảng
Dòng thứ 2 gồm N phần tử viết cách nhau một khoảng trống

Constraints

1 ≤ N ≤ 10^6
0 ≤ A[i] ≤ 10^9

Output Format

In ra số lượng số nguyên tố trong dãy theo thứ tự xuất hiện.

Nếu trong mảng không tồn tại số nguyên tố nào thì in ra "NONE"

Sample Input 0

5
1 3 23 5 8

Sample Output 0

Đây là hướng dẫn giải bài "Đếm số nguyên tố" bằng C++ một cách ngắn gọn:

Đọc dữ liệu:
- Đọc số lượng phần tử N.
- Đọc N phần tử của mảng.
Hàm kiểm tra số nguyên tố (isPrime):
- Viết một hàm isPrime(int num) để kiểm tra xem một số num có phải là số nguyên tố hay không.
- Trong hàm này:
  - Xử lý các trường hợp đặc biệt: số nhỏ hơn hoặc bằng 1 không phải số nguyên tố. Số 2 là số nguyên tố. Các số chẵn lớn hơn 2 không phải số nguyên tố.
  - Với các số lẻ lớn hơn 2, kiểm tra xem nó có chia hết cho bất kỳ số lẻ nào từ 3 đến căn bậc hai của nó hay không. Nếu tìm thấy một ước số, nó không phải số nguyên tố.
  - Nếu không tìm thấy ước số nào trong phạm vi trên, nó là số nguyên tố.
Đếm số nguyên tố trong mảng:
- Khởi tạo một biến đếm prime_count = 0.
- Duyệt qua từng phần tử trong mảng đã đọc.
- Với mỗi phần tử, gọi hàm isPrime() để kiểm tra.
- Nếu hàm trả về true (là số nguyên tố), tăng biến prime_count lên 1.
In kết quả:
- Sau khi duyệt hết mảng, kiểm tra giá trị của prime_count.
- Nếu prime_count bằng 0, in ra "NONE".
- Ngược lại, in ra giá trị của prime_count.

Lưu ý: Do A[i] có thể lên đến 10^9, việc kiểm tra số nguyên tố cần sử dụng kiểu dữ liệu phù hợp (ví dụ long long cho biến vòng lặp kiểm tra ước nếu cần, mặc dù int cho số num và sqrt(num) là đủ trong C++ vì căn bậc hai của 10^9 vẫn nằm trong giới hạn của int). Hàm sqrt() thường làm việc với kiểu double hoặc long double, cần cẩn thận khi so sánh kết quả.

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.