Bài 13.1: Cấu trúc dữ liệu Vector trong C++

Khai báo và Khởi tạo Vector

Có nhiều cách để tạo một đối tượng vector. Sự lựa chọn phụ thuộc vào nhu cầu ban đầu của bạn:

Vector rỗng: Tạo một vector không chứa bất kỳ phần tử nào.
```
#include <vector>

int main() {
    vector<int> so;
    vector<string> ten;
    return 0;
}
```
Giải thích: Chúng ta khai báo một vector có tên numbers có thể chứa kiểu dữ liệu int, và một vector names chứa string. Ban đầu, chúng đều trống rỗng.
Vector với kích thước xác định: Tạo vector với một số lượng phần tử nhất định. Các phần tử này sẽ được khởi tạo bằng giá trị mặc định của kiểu dữ liệu (ví dụ: 0 cho số nguyên, chuỗi rỗng cho string).
```
#include <vector>
#include <iostream>

int main() {
    vector<double> d(5);

    cout << "Vector data co " << d.size() << " phan tu." << endl;
    for (double v : d) {
        cout << v << " ";
    }
    cout << endl;

    return 0;
}
```
Output:
```
Vector data co 5 phan tu.
0 0 0 0 0
```
Giải thích: vector<double> data(5); tạo một vector có 5 phần tử, kiểu double. C++ tự động khởi tạo các phần tử này về 0.0. size() là phương thức trả về số lượng phần tử hiện tại của vector.
Vector với kích thước và giá trị khởi tạo ban đầu: Tạo vector với một số lượng phần tử nhất định, tất cả được khởi tạo bằng một giá trị cụ thể do bạn chỉ định.
```
#include <vector>
#include <string>
#include <iostream>

int main() {
    vector<string> ks(3, "Unknown");

    for (const string& t : ks) {
        cout << t << " ";
    }
    cout << endl;

    return 0;
}
```
Output:
```
Unknown Unknown Unknown
```
Giải thích: vector<string> guests(3, "Unknown"); tạo 3 phần tử, mỗi phần tử là một bản sao của chuỗi "Unknown".
Khởi tạo bằng danh sách (Initializer List - C++11 trở lên): Cách hiện đại và tiện lợi để khởi tạo vector với một tập hợp các giá trị cụ thể ngay lúc khai báo.
```
#include <vector>
#include <iostream>

int main() {
    vector<int> ngTo = {2, 3, 5, 7, 11};

    for (int x : ngTo) {
        cout << x << " ";
    }
    cout << endl;

    return 0;
}
```
Output:
```
2 3 5 7 11
```
Giải thích: Cách này trực quan và gọn gàng khi bạn đã có sẵn danh sách các giá trị muốn đưa vào vector ngay từ đầu.
Sao chép từ vector khác: Tạo một vector mới là bản sao của một vector đã tồn tại.
```
#include <vector>
#include <iostream>

int main() {
    vector<int> goc = {1, 2, 3};
    vector<int> banSao = goc;

    goc.push_back(4);

    for (int v : banSao) {
        cout << v << " ";
    }
    cout << endl;

    return 0;
}
```
Output:
```
1 2 3
```
Giải thích: Khi bạn gán một vector cho vector khác (copy = original;), C++ thực hiện sao chép sâu (deep copy). Nghĩa là, một bản sao hoàn toàn mới của các phần tử được tạo ra, và hai vector này độc lập với nhau sau đó.

Truy cập các Phần tử trong Vector

Bạn có thể truy cập các phần tử của vector bằng chỉ số (index), giống như mảng. Chỉ số bắt đầu từ 0.

Có hai cách chính để truy cập:

Sử dụng toán tử []:

#include <vector>
#include <iostream>

int main() {
    vector<int> d = {10, 20, 30, 40, 50};

    cout << "Phan tu dau tien: " << d[0] << endl;
    cout << "Phan tu thu ba: " << d[2] << endl;

    d[1] = 25;
    cout << "Phan tu thu hai sau khi thay doi: " << d[1] << endl;

    return 0;
}

Output:

Phan tu dau tien: 10
Phan tu thu ba: 30
Phan tu thu hai sau khi thay doi: 25

Giải thích: Toán tử [] truy cập phần tử rất nhanh nhưng không kiểm tra chỉ số có hợp lệ không (không kiểm tra biên - bounds checking). Nếu bạn truy cập một chỉ số nằm ngoài phạm vi từ 0 đến size() - 1, chương trình có thể gặp lỗi ngay lập tức hoặc có hành vi không mong muốn.

Sử dụng phương thức .at():

#include <vector>
#include <iostream>
#include <stdexcept>

int main() {
    vector<int> d = {10, 20, 30};

    try {
        cout << "Phan tu dau tien: " << d.at(0) << endl;
        cout << "Phan tu thu hai: " << d.at(1) << endl;

        cout << "Phan tu thu 10: " << d.at(10) << endl;

    } catch (const out_of_range& e) {
        cerr << "Loi truy cap phan tu: " << e.what() << endl;
    }

    return 0;
}

Output:

Phan tu dau tien: 10
Phan tu thu hai: 20
Loi truy cap phan tu: vector::_M_range_check: __n (which is 10) >= this->size() (which is 3)

Giải thích: Phương thức .at() cũng truy cập phần tử bằng chỉ số, nhưng nó thực hiện kiểm tra biên. Nếu chỉ số không hợp lệ, nó sẽ ném ra một ngoại lệ (exception) kiểu out_of_range. Điều này giúp bạn phát hiện lỗi sớm hơn trong quá trình phát triển. Mặc dù có chậm hơn một chút so với [] do việc kiểm tra, .at() lại an toàn hơn nhiều.

Ngoài ra, bạn có thể truy cập phần tử đầu và cuối một cách nhanh chóng:

#include <vector>
#include <iostream>

int main() {
    vector<int> d = {10, 20, 30};

    if (!d.empty()) {
        cout << "Phan tu dau tien (dung front()): " << d.front() << endl;
        cout << "Phan tu cuoi cung (dung back()): " << d.back() << endl;
    }

    return 0;
}

Output:

Phan tu dau tien (dung front()): 10
Phan tu cuoi cung (dung back()): 30

Giải thích: front() trả về tham chiếu đến phần tử đầu tiên, back() trả về tham chiếu đến phần tử cuối cùng. Lưu ý rằng bạn phải đảm bảo vector không rỗng trước khi gọi front() hoặc back().

Thêm và Xóa Phần tử

Đây là lúc vector thể hiện sức mạnh của một mảng động!

Thêm vào cuối (push_back()): Phương thức này thêm một phần tử vào cuối vector. Đây là thao tác phổ biến nhất và thường rất hiệu quả.
```
#include <vector>
#include <iostream>

int main() {
    vector<int> so;

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

    for (int v : so) {
        cout << v << " ";
    }
    cout << endl;

    cout << "Kich thuoc vector: " << so.size() << endl;

    return 0;
}
```
Output:
```
10 20 30
Kich thuoc vector: 3
```
Giải thích: push_back() tự động xử lý việc cấp phát thêm bộ nhớ nếu vector đầy. Quá trình này có thể tốn kém một chút nếu cần phải di chuyển tất cả các phần tử sang một vùng nhớ mới lớn hơn, nhưng vector được thiết kế để việc này xảy ra không quá thường xuyên.

Xóa phần tử cuối (pop_back()): Loại bỏ phần tử cuối cùng khỏi vector. Thao tác này cũng rất hiệu quả.

#include <vector>
#include <iostream>

int main() {
    vector<int> so = {10, 20, 30, 40};

    so.pop_back();
    so.pop_back();

    for (int v : so) {
        cout << v << " ";
    }
    cout << endl;

    cout << "Kich thuoc vector: " << so.size() << endl;

    return 0;
}

Output:

10 20
Kich thuoc vector: 2

Giải thích: pop_back() chỉ đơn giản là giảm kích thước logic của vector đi 1 và "quên" đi phần tử cuối cùng. Nó không trả về giá trị của phần tử bị xóa.

Chèn phần tử (insert()): Chèn một hoặc nhiều phần tử vào một vị trí bất kỳ trong vector. Vị trí được chỉ định bằng một iterator.

#include <vector>
#include <iostream>

int main() {
    vector<int> so = {1, 2, 5, 6};

    so.insert(so.begin() + 1, 99);
    so.insert(so.end(), 3, 0);

    vector<int> soThem = {100, 101};
    so.insert(so.begin() + 2, soThem.begin(), soThem.end());

    for (int v : so) {
        cout << v << " ";
    }
    cout << endl;

    return 0;
}

Output:

1 99 100 101 2 5 6 0 0 0

Giải thích: insert() là một thao tác đắt tiền (expensive), đặc biệt khi chèn vào đầu hoặc giữa vector, vì tất cả các phần tử đứng sau vị trí chèn phải được dời chỗ (shifted) để tạo không gian.

Xóa phần tử (erase()): Xóa một phần tử hoặc một phạm vi các phần tử khỏi vector. Vị trí/phạm vi được chỉ định bằng iterator.
```
#include <vector>
#include <iostream>

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

    so.erase(so.begin());
    so.erase(so.begin() + 2);
    so.erase(so.begin() + 1, so.begin() + 3);

    for (int v : so) {
        cout << v << " ";
    }
    cout << endl;

    return 0;
}
```
Output:
```
20 60
```
Giải thích: Tương tự như insert(), erase() cũng là một thao tác đắt tiền khi xóa ở đầu hoặc giữa, vì các phần tử đứng sau vị trí bị xóa phải được dời chỗ để lấp đầy khoảng trống. erase() trả về iterator trỏ đến phần tử ngay sau phần tử (hoặc phạm vi) vừa bị xóa.

Xóa tất cả các phần tử (clear()): Xóa sạch tất cả phần tử, vector trở về trạng thái rỗng.

#include <vector>
#include <iostream>

int main() {
    vector<int> so = {1, 2, 3};

    cout << "Kich thuoc truoc khi clear: " << so.size() << endl;
    so.clear();

    cout << "Kich thuoc sau khi clear: " << so.size() << endl;
    cout << "Vector co rong khong? " << (so.empty() ? "Co" : "Khong") << endl;

    return 0;
}

Output:

Kich thuoc truoc khi clear: 3
Kich thuoc sau khi clear: 0
Vector co rong khong? Co

Giải thích: clear() đặt kích thước của vector về 0. Tuy nhiên, nó có thể không giải phóng ngay lập tức bộ nhớ đã được cấp phát cho vector.

Kích thước (`size()`) và Khả năng chứa (`capacity()`)

Đây là hai khái niệm quan trọng để hiểu cách vector quản lý bộ nhớ:

size(): Trả về số lượng phần tử thực tế đang có trong vector.
capacity(): Trả về tổng số phần tử mà vector có thể chứa hiện tại mà không cần cấp phát lại bộ nhớ.

Thông thường, capacity() luôn lớn hơn hoặc bằng size(). Khi bạn thêm phần tử bằng push_back() và size() đạt đến capacity(), vector sẽ tự động cấp phát một vùng nhớ mới lớn hơn (thường là gấp đôi kích thước hiện tại), sao chép tất cả các phần tử cũ sang vùng nhớ mới, và giải phóng vùng nhớ cũ. Đây chính là quá trình tái cấp phát (reallocation).

#include <vector>
#include <iostream>

int main() {
    vector<int> so;

    cout << "Ban dau: size = " << so.size() << ", capacity = " << so.capacity() << endl;

    so.push_back(1);
    cout << "Sau push_back(1): size = " << so.size() << ", capacity = " << so.capacity() << endl;

    so.push_back(2);
    cout << "Sau push_back(2): size = " << so.size() << ", capacity = " << so.capacity() << endl;

    so.push_back(3);
    cout << "Sau push_back(3): size = " << so.size() << ", capacity = " << so.capacity() << endl;

    for (int i = 4; i <= 10; ++i) {
        so.push_back(i);
        cout << "Sau push_back(" << i << "): size = " << so.size() << ", capacity = " << so.capacity() << endl;
    }

    so.pop_back();
    cout << "Sau pop_back(): size = " << so.size() << ", capacity = " << so.capacity() << endl;

    return 0;
}

Output:

Ban dau: size = 0, capacity = 0
Sau push_back(1): size = 1, capacity = 1
Sau push_back(2): size = 2, capacity = 2
Sau push_back(3): size = 3, capacity = 4
Sau push_back(4): size = 4, capacity = 4
Sau push_back(5): size = 5, capacity = 8
Sau push_back(6): size = 6, capacity = 8
Sau push_back(7): size = 7, capacity = 8
Sau push_back(8): size = 8, capacity = 8
Sau push_back(9): size = 9, capacity = 16
Sau push_back(10): size = 10, capacity = 16
Sau pop_back(): size = 9, capacity = 16

Giải thích: Chạy ví dụ này sẽ cho bạn thấy cách capacity tăng theo từng bước (không phải tăng 1 đơn vị mỗi lần push_back) để giảm thiểu số lần tái cấp phát. size luôn theo sát số phần tử thực tế.

.reserve(): Bạn có thể sử dụng .reserve(n) để yêu cầu vector cấp phát đủ bộ nhớ cho ít nhất n phần tử ngay từ đầu. Điều này giúp tránh các lần tái cấp phát tốn kém nếu bạn biết trước (hoặc ước lượng) số lượng phần tử tối thiểu sẽ thêm vào.

#include <vector>
#include <iostream>

int main() {
    vector<int> so;
    cout << "Ban dau: size = " << so.size() << ", capacity = " << so.capacity() << endl;

    so.reserve(100);
    cout << "Sau reserve(100): size = " << so.size() << ", capacity = " << so.capacity() << endl;

    for (int i = 1; i <= 10; ++i) {
        so.push_back(i);
        cout << "Sau push_back(" << i << "): size = " << so.size() << ", capacity = " << so.capacity() << endl;
    }

    return 0;
}

Output:

Ban dau: size = 0, capacity = 0
Sau reserve(100): size = 0, capacity = 100
Sau push_back(1): size = 1, capacity = 100
Sau push_back(2): size = 2, capacity = 100
Sau push_back(3): size = 3, capacity = 100
Sau push_back(4): size = 4, capacity = 100
Sau push_back(5): size = 5, capacity = 100
Sau push_back(6): size = 6, capacity = 100
Sau push_back(7): size = 7, capacity = 100
Sau push_back(8): size = 8, capacity = 100
Sau push_back(9): size = 9, capacity = 100
Sau push_back(10): size = 10, capacity = 100

Giải thích: reserve() chỉ ảnh hưởng đến capacity, nó không thay đổi size() và không thêm bất kỳ phần tử nào vào vector.

.resize(): Thay đổi số lượng phần tử thực tế của vector (size).
- Nếu kích thước mới lớn hơn kích thước hiện tại, các phần tử mới sẽ được thêm vào cuối và khởi tạo bằng giá trị mặc định (hoặc giá trị bạn cung cấp). Vector có thể cần cấp phát lại bộ nhớ.
- Nếu kích thước mới nhỏ hơn, các phần tử ở cuối sẽ bị xóa bỏ. capacity có thể không thay đổi. ```cpp #include <vector> #include <iostream>
int main() {
```
vector<int> so = {10, 20, 30};
cout << "Ban dau: size = " << so.size() << ", capacity = " << so.capacity() << endl;

so.resize(5);
cout << "Sau resize(5): size = " << so.size() << ", capacity = " << so.capacity() << endl;
for (int v : so) cout << v << " "; cout << endl;

so.resize(7, 100);
cout << "Sau resize(7, 100): size = " << so.size() << ", capacity = " << so.capacity() << endl;
for (int v : so) cout << v << " "; cout << endl;

so.resize(2);
cout << "Sau resize(2): size = " << so.size() << ", capacity = " << so.capacity() << endl;
for (int v : so) cout << v << " "; cout << endl;

return 0;
```
}
```
Output:
```
Ban dau: size = 3, capacity = 3 Sau resize(5): size = 5, capacity = 6 10 20 30 0 0 Sau resize(7, 100): size = 7, capacity = 7 10 20 30 0 0 100 100 Sau resize(2): size = 2, capacity = 7 10 20 `` *Giải thích:*resize()thay đổisize. Nếu bạn muốn vector có đúng N phần tử, hãy dùngresize(N). Nếu bạn chỉ muốn đảm bảo có đủ chỗ cho N phần tử mà không thay đổi số lượng hiện tại, hãy dùngreserve(N)`.

Vòng lặp với Vector

Bạn có thể duyệt qua các phần tử của vector bằng nhiều cách:

Sử dụng chỉ số (Index): Phù hợp khi bạn cần truy cập phần tử theo vị trí.

#include <vector>
#include <iostream>

int main() {
    vector<int> d = {10, 20, 30, 40, 50};

    for (size_t i = 0; i < d.size(); ++i) {
        cout << d[i] << " ";
    }
    cout << endl;

    return 0;
}

Output:

10 20 30 40 50

Giải thích: size_t là kiểu dữ liệu không dấu, thường dùng cho kích thước và chỉ số của các container trong C++ để tránh các vấn đề về số âm.

Sử dụng Iterator: Iterator là một khái niệm tổng quát trong STL, giống như con trỏ, dùng để trỏ đến các phần tử trong một container. Vector cung cấp begin() (iterator đến phần tử đầu tiên) và end() (iterator đến vị trí sau phần tử cuối cùng).

#include <vector>
#include <iostream>

int main() {
    vector<int> d = {10, 20, 30};

    for (vector<int>::iterator it = d.begin(); it != d.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;

    for (auto it = d.begin(); it != d.end(); ++it) {
         cout << *it << " ";
    }
    cout << endl;

    return 0;
}

Output:

10 20 30
10 20 30

Giải thích: Vòng lặp chạy từ begin() cho đến khi iterator bằng end(). *it dereference iterator để lấy giá trị của phần tử.

Vòng lặp dựa trên phạm vi (Range-based for loop - C++11 trở lên): Cách duyệt vector đơn giản và hiện đại nhất khi bạn chỉ cần truy cập từng phần tử mà không cần chỉ số hay iterator tường minh.
```
#include <vector>
#include <iostream>

int main() {
    vector<int> d = {10, 20, 30};

    for (int e : d) {
        cout << e << " ";
    }
    cout << endl;

    for (int& e : d) {
        e *= 2;
    }

     for (int e : d) {
        cout << e << " ";
    }
    cout << endl;

    return 0;
}
```
Output:
```
10 20 30
20 40 60
```
Giải thích: for (int element : data) có nghĩa là "với mỗi element trong data, thực hiện các lệnh bên trong". Nếu bạn chỉ muốn đọc giá trị, dùng int element. Nếu bạn muốn thay đổi giá trị của phần tử gốc trong vector, hãy dùng int& element (tham chiếu).

Vector các Kiểu Dữ liệu Khác nhau

Vector không chỉ chứa các kiểu dữ liệu cơ bản như int, double, char. Nó có thể chứa bất kỳ kiểu dữ liệu nào, bao gồm cả các đối tượng của lớp bạn tự định nghĩa, con trỏ, hoặc thậm chí là các vector khác (vector lồng nhau).

#include <vector>
#include <string>
#include <iostream>

struct Point {
    int x, y;
};

int main() {
    vector<string> tin = {"Hello", "World", "C++"};
    for (const string& t : tin) {
        cout << t << " ";
    }
    cout << endl;

    vector<Point> diem;
    diem.push_back({1, 2});
    diem.push_back({5, 10});

    cout << "Diem dau tien: (" << diem[0].x << ", " << diem[0].y << ")" << endl;

    vector<vector<int>> maTran = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };

    cout << "Phan tu tai [1][2]: " << maTran[1][2] << endl;

    for (const auto& dong : maTran) {
        for (int g : dong) {
            cout << g << " ";
        }
        cout << endl;
    }

    return 0;
}

Output:

Hello World C++
Diem dau tien: (1, 2)
Phan tu tai [1][2]: 6
1 2 3
4 5 6
7 8 9

Giải thích: Vector cực kỳ linh hoạt. Bạn có thể tạo vector chứa các kiểu phức tạp tùy ý. Vector lồng nhau thường được dùng để biểu diễn ma trận hoặc dữ liệu 2D.

Lợi ích của Vector

Kích thước động: Tự động điều chỉnh kích thước khi cần thiết, rất tiện lợi.
Truy cập ngẫu nhiên hiệu quả: Nhờ tính liên tục của bộ nhớ, việc truy cập bất kỳ phần tử nào bằng chỉ số [] hoặc .at() có độ phức tạp là O(1) - hằng số thời gian.
Duyệt hiệu quả: Duyệt qua các phần tử bằng vòng lặp rất nhanh vì chúng nằm liên tục trong bộ nhớ, tận dụng tối đa cache của CPU (tính cache locality).
Tích hợp với STL Algorithms: Vector hoạt động mượt mà với các thuật toán tiêu chuẩn của STL (như sắp xếp sort, tìm kiếm find, vv.).

Khi nào cần cân nhắc?

Mặc dù vector rất mạnh, nhưng có những trường hợp thao tác có thể tốn kém:

insert() và erase() ở giữa hoặc đầu: Các thao tác này yêu cầu dời chỗ các phần tử sau vị trí chèn/xóa, có độ phức tạp O(n) (tuyến tính với số lượng phần tử cần dời).
Tái cấp phát: Nếu vector thường xuyên phải cấp phát lại bộ nhớ (do push_back liên tục vượt quá capacity mà không dùng reserve), việc này có thể gây chậm chương trình do phải cấp phát mới, sao chép dữ liệu và giải phóng cũ.

Nếu ứng dụng của bạn thường xuyên thực hiện chèn/xóa ở đầu hoặc giữa, hoặc cần thêm/bớt phần tử rất thường xuyên ở nhiều vị trí, các cấu trúc dữ liệu khác như list hoặc deque có thể là lựa chọn tốt hơn. Tuy nhiên, với hầu hết các trường hợp, vector là điểm khởi đầu tuyệt vời và đủ hiệu quả.

Vector là một công cụ không thể thiếu trong bộ công cụ của lập trình viên C++. Nắm vững cách sử dụng nó sẽ giúp bạn giải quyết được rất nhiều bài toán một cách hiệu quả và linh hoạt.

Hy vọng bài viết này đã cung cấp cho bạn cái nhìn sâu sắc về vector và cách sử dụng nó. Hãy thử nghiệm với các ví dụ code để củng cố kiến thức nhé!

Comments

There are no comments at the moment.