Giao diện
📦 std::vector — Dynamic Array
std::vector là container phổ biến nhất trong C++. Nó là dynamic array — tự động grow/shrink và quản lý memory cho bạn. Tạo Vector
cpp
#include <vector>
#include <iostream>
int main() {
// Empty vector
std::vector<int> v1;
// Vector với initial size (5 phần tử, mặc định = 0)
std::vector<int> v2(5);
// Vector với size và value
std::vector<int> v3(5, 10); // [10, 10, 10, 10, 10]
// Initializer list (C++11)
std::vector<int> v4 = {1, 2, 3, 4, 5};
std::vector<int> v5{1, 2, 3, 4, 5}; // Same
// Copy constructor
std::vector<int> v6(v4);
// From array/iterators
int arr[] = {1, 2, 3};
std::vector<int> v7(std::begin(arr), std::end(arr));
return 0;
}Basic Operations
Thêm phần tử
cpp
std::vector<int> v;
v.push_back(10); // Thêm cuối: [10]
v.push_back(20); // [10, 20]
v.push_back(30); // [10, 20, 30]
v.emplace_back(40); // C++11: Construct in-place (efficient!)
// [10, 20, 30, 40]
// Insert ở vị trí cụ thể
v.insert(v.begin() + 1, 15); // [10, 15, 20, 30, 40]Xóa phần tử
cpp
std::vector<int> v = {1, 2, 3, 4, 5};
v.pop_back(); // Xóa cuối: [1, 2, 3, 4]
v.erase(v.begin()); // Xóa đầu: [2, 3, 4]
v.erase(v.begin() + 1); // Xóa index 1: [2, 4]
v.clear(); // Xóa tất cả: []Truy cập phần tử
cpp
std::vector<int> v = {10, 20, 30, 40, 50};
// Operator [] — KHÔNG check bounds
int a = v[2]; // 30
// at() — CÓ check bounds (throw exception nếu out of range)
int b = v.at(2); // 30
// int c = v.at(10); // ❌ Throws std::out_of_range
// Front và Back
int first = v.front(); // 10
int last = v.back(); // 50
// Pointer tới data (cho C interop)
int* ptr = v.data();Size vs Capacity — CRITICAL!
┌─────────────────────────────────────────────────────────────────┐
│ SIZE vs CAPACITY │
├─────────────────────────────────────────────────────────────────┤
│ │
│ vector với size=5, capacity=8: │
│ │
│ ┌────┬────┬────┬────┬────┬────┬────┬────┐ │
│ │ 10 │ 20 │ 30 │ 40 │ 50 │ │ │ │ │
│ └────┴────┴────┴────┴────┴────┴────┴────┘ │
│ ◄────── size = 5 ──────►◄── reserved ──► │
│ ◄────────── capacity = 8 ────────────────► │
│ │
│ • size(): Số phần tử thực sự có │
│ • capacity(): Memory đã allocate (có thể > size) │
│ │
└─────────────────────────────────────────────────────────────────┘cpp
#include <vector>
#include <iostream>
int main() {
std::vector<int> v;
std::cout << "Empty: size=" << v.size()
<< ", capacity=" << v.capacity() << std::endl;
// size=0, capacity=0
v.push_back(1);
std::cout << "After 1: size=" << v.size()
<< ", capacity=" << v.capacity() << std::endl;
// size=1, capacity=1
v.push_back(2);
std::cout << "After 2: size=" << v.size()
<< ", capacity=" << v.capacity() << std::endl;
// size=2, capacity=2
v.push_back(3);
std::cout << "After 3: size=" << v.size()
<< ", capacity=" << v.capacity() << std::endl;
// size=3, capacity=4 ← DOUBLED!
return 0;
}Cách Vector Grows
Khi size == capacity và cần thêm phần tử:
- Allocate new memory (thường gấp đôi capacity)
- Copy/Move tất cả phần tử sang vùng mới
- Delete old memory
⚠️ Reallocation Invalidates Pointers/Iterators!
cpp
std::vector<int> v = {1, 2, 3};
int* ptr = &v[0];
v.push_back(4); // Có thể trigger reallocation!
*ptr = 100; // ❌ UNDEFINED BEHAVIOR nếu reallocated!reserve() — Pre-allocate
cpp
std::vector<int> v;
v.reserve(1000); // Allocate capacity=1000 ngay
// Giờ push_back 1000 lần không gây reallocation
for (int i = 0; i < 1000; ++i) {
v.push_back(i); // Efficient — no reallocation
}📌 Best Practice
Nếu biết trước số lượng phần tử, dùng reserve() để tránh multiple reallocations.
shrink_to_fit() — Release excess
cpp
std::vector<int> v(1000); // size=1000, capacity=1000
v.clear(); // size=0, capacity vẫn=1000!
v.shrink_to_fit(); // Request giảm capacity về match sizeIterating
cpp
std::vector<int> v = {1, 2, 3, 4, 5};
// 1️⃣ Range-based for (PREFERRED)
for (const auto& elem : v) {
std::cout << elem << " ";
}
// 2️⃣ Index-based
for (size_t i = 0; i < v.size(); ++i) {
std::cout << v[i] << " ";
}
// 3️⃣ Iterator-based
for (auto it = v.begin(); it != v.end(); ++it) {
std::cout << *it << " ";
}
// 4️⃣ Reverse
for (auto it = v.rbegin(); it != v.rend(); ++it) {
std::cout << *it << " ";
}2D Vector
cpp
#include <vector>
int main() {
// 3x4 matrix filled with 0
std::vector<std::vector<int>> matrix(3, std::vector<int>(4, 0));
matrix[1][2] = 42;
// Iterate
for (const auto& row : matrix) {
for (int val : row) {
std::cout << val << " ";
}
std::cout << std::endl;
}
return 0;
}Common Algorithms với Vector
cpp
#include <vector>
#include <algorithm>
#include <numeric>
int main() {
std::vector<int> v = {5, 2, 8, 1, 9, 3};
// Sort
std::sort(v.begin(), v.end()); // [1, 2, 3, 5, 8, 9]
// Reverse sort
std::sort(v.begin(), v.end(), std::greater<int>()); // [9, 8, 5, 3, 2, 1]
// Find
auto it = std::find(v.begin(), v.end(), 5);
if (it != v.end()) {
std::cout << "Found at index " << (it - v.begin()) << std::endl;
}
// Min/Max
auto minIt = std::min_element(v.begin(), v.end());
auto maxIt = std::max_element(v.begin(), v.end());
// Sum
int sum = std::accumulate(v.begin(), v.end(), 0);
// Count
int count = std::count(v.begin(), v.end(), 5);
// Remove-erase idiom
v.erase(std::remove(v.begin(), v.end(), 3), v.end());
return 0;
}Performance Summary
| Operation | Time Complexity | Note |
|---|---|---|
push_back() | O(1) amortized | Occasional O(n) reallocation |
pop_back() | O(1) | |
operator[], at() | O(1) | Random access |
insert() at middle | O(n) | Shift elements |
erase() at middle | O(n) | Shift elements |
find() | O(n) | Linear search |
size(), empty() | O(1) |
📚 Tổng kết
| Concept | Key Takeaway |
|---|---|
std::vector | Default container — dùng khi không chắc |
size() vs capacity() | size = actual, capacity = allocated |
reserve() | Pre-allocate để tránh reallocation |
emplace_back() | Efficient hơn push_back cho objects |
| Reallocation | Invalidates pointers và iterators |
| Range-based for | Preferred iteration style |
➡️ Tiếp theo
Tiếp theo: std::string — Text manipulation.