Mảng và vector
Giả sử bạn phải lưu điểm thi của một lớp bốn mươi học sinh. Nếu khai báo bốn mươi
biến rời diem1, diem2, ... thì vừa mỏi tay vừa không cách nào viết một vòng lặp
gọn để cộng dồn hay tìm điểm cao nhất. Bài toán nào có nhiều giá trị cùng loại
đều gặp cảnh này: danh sách tên, danh sách giá tiền, dãy số đọc từ bàn phím. Cách làm
đúng là gom tất cả vào một danh sách duy nhất, rồi thao tác qua chỉ số.
C++ cho ta hai công cụ. Mảng tĩnh (int a[100];) là dãy ô nhớ liền nhau, kích
thước cố định ngay khi khai báo. vector là danh sách co giãn được: bạn thêm
bớt phần tử tùy ý, không cần đoán trước số lượng. Bài này đi từ mảng tĩnh, thứ giúp
bạn hiểu bản chất bộ nhớ, rồi tới vector, thứ bạn sẽ dùng hằng ngày.
Mảng tĩnh: dãy ô nhớ liền nhau
Khai báo int a[5]; xin cấp năm ô nhớ số nguyên nằm sát nhau. Mỗi ô có một chỉ số
(index) đánh từ 0, nên năm ô là a[0], a[1], a[2], a[3], a[4]. Không có
a[5]: chỉ số cuối luôn là kích thước trừ một. Đây là nguồn nhầm lẫn kinh điển của
người mới, vì ta quen đếm từ một.
Vì sao lại đánh số từ 0? Câu trả lời nằm ở bộ nhớ. Trình biên dịch cấp cho a một khối liền
mạch, mỗi int thường chiếm bốn byte. Gọi địa chỉ của byte đầu là B. Khi gặp a[i], chương
trình không tìm kiếm gì cả, nó chỉ tính B + i * 4 rồi đọc thẳng chỗ đó. Vậy chỉ số không phải
"phần tử thứ mấy" theo cách đếm của con người, nó là số ô phải nhảy kể từ đầu khối: phần tử đầu
nằm ngay tại B, nhảy không ô nào, nên là a[0]. Hiểu vậy rồi thì "chỉ số cuối bằng kích thước trừ
một" không còn là quy tắc phải học thuộc, nó là hệ quả tự nhiên. Công thức đó cũng cho thấy thời gian
lấy a[0] và lấy a[4999] là như nhau, và đó là lý do mảng có mặt trong mọi ngôn ngữ.
#include <iostream>
using namespace std;
int main() {
int a[5] = {10, 20, 30, 40, 50}; // 5 ô, chỉ số 0..4
cout << a[0] << "\n"; // 10, phần tử đầu
cout << a[4] << "\n"; // 50, phần tử cuối
a[2] = 99; // gán như biến thường -> a = {10,20,99,40,50}
cout << a[2] << "\n"; // 99
}
Duyệt mảng bằng vòng lặp. Sức mạnh của mảng lộ ra khi ghép với for. Ta cho biến
đếm i chạy từ 0 tới n - 1, mỗi vòng chạm một ô. Mẫu này lặp lại suốt sự nghiệp
lập trình của bạn.
#include <iostream>
using namespace std;
int main() {
int a[5] = {10, 20, 30, 40, 50};
int tong = 0, lonNhat = a[0];
for (int i = 0; i < 5; i++) { // i: 0,1,2,3,4
tong += a[i]; // cộng dồn từng ô
if (a[i] > lonNhat) lonNhat = a[i];
}
cout << tong << " " << lonNhat; // 150 50
}
Hãy chạy đoạn trên bằng đầu. Chú ý ta khởi tạo lonNhat bằng a[0] chứ không bằng 0: nếu mảng
toàn số âm thì mốc 0 không bao giờ bị đánh bại và kết quả sẽ sai. Vòng i = 0: tong thành 10,
lonNhat giữ nguyên. Vòng i = 1: tong thành 30, lonNhat thành 20. Cứ thế tới vòng i = 4:
tong thành 150, lonNhat thành 50. Lúc này i tăng lên 5, điều kiện i < 5 sai, vòng lặp
dừng đúng lúc, chưa hề chạm tới a[5]. Cái khuôn này (một biến tích lũy khởi tạo trước vòng lặp, một
vòng for chạy từ 0 tới n - 1) lặp lại trong hầu hết bài toán trên dãy.
Nhược điểm của mảng tĩnh là kích thước đóng cứng, mà lại phải là hằng số biết ngay lúc biên dịch, nên
bạn không thể đọc n từ bàn phím rồi viết int a[n]; một cách chuẩn mực. Cách chống chế quen thuộc
là khai báo dư thật nhiều rồi chỉ dùng n ô đầu, nhưng cách đó vừa lãng phí vừa vẫn sập nếu dữ liệu
vượt con số bạn đoán. Đây chính là lý do vector ra đời.
Ý tưởng cốt lõi
vector<int> a = {10, 20, 30};, danh sách số nguyên, truy cập bằng chỉ sốa[0],a[1]...a.push_back(40)thêm phần tử vào cuối;a.size()cho số phần tử.for (int x : a)duyệt từng phần tử củaa(vòng lặp dạng range).
Mã nguồn
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> a = {10, 20, 30};
a.push_back(40);
int tong = 0;
for (int x : a) tong += x;
cout << tong; // 100
}
Thử ngay: xem mảng và vector chạy từng bước
1int main() {2 vector<int> a = {10, 20, 30};3 a.push_back(40);4 int tong = 0;5 for (int x : a) tong += x;6 cout << tong;7}
vector co giãn: push_back và size
vector khắc phục đúng chỗ mảng tĩnh thua. Bạn khai báo một danh sách rỗng rồi
thêm phần tử khi cần, hệ thống tự lo cấp phát bộ nhớ.
vector<int> v;tạo danh sách rỗng.v.push_back(x)gắnxvào cuối danh sách, danh sách dài thêm một.v.size()trả về số phần tử hiện có.v[i]truy cập phần tử thứi, đánh số từ0như mảng.v.back()là phần tử cuối, viết gọn chov[v.size() - 1].
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> v; // rỗng, size = 0
v.push_back(3); // v = {3}
v.push_back(1); // v = {3, 1}
v.push_back(4); // v = {3, 1, 4}
cout << v.size() << "\n"; // 3
cout << v.back() << "\n"; // 4
v[1] = 9; // v = {3, 9, 4}
for (int i = 0; i < v.size(); i++) cout << v[i] << " ";
}
Có ba cách khai báo vector hay dùng khi đã biết số lượng: vector<int> v(5); tạo năm
phần tử toàn 0, vector<int> v(5, 7); tạo năm phần tử toàn 7, còn vector<int> v = {1, 2, 3}; liệt kê thẳng.
Bên trong vector: dung lượng và phép nhân đôi
vector vẫn dựa trên một khối nhớ liền mạch, vì muốn giữ tính chất quý nhất của mảng: truy cập v[i]
trong thời gian hằng số. Nhưng khối liền mạch không nới ra tại chỗ được, bởi ngay sau đuôi khối rất
có thể đã có dữ liệu của thứ khác. Bí quyết của nó là giữ hai con số:
size()là số phần tử bạn đang thực sự có.capacity()là số chỗ nó đã xin sẵn từ hệ thống, thường lớn hơnsize().
Phần chênh giữa hai con số đó là chỗ trống dự phòng ở cuối khối. Khi push_back mà còn chỗ trống,
việc thêm cực rẻ: ghi vào ô trống kế tiếp rồi tăng size lên một. Nhưng khi size đã bằng
capacity, vector buộc phải xin một khối mới lớn hơn, chuyển toàn bộ phần tử cũ sang, rồi trả khối
cũ về hệ thống. Lần push_back xui xẻo đó đụng tới mọi phần tử đang có, nên nó đắt.
Vậy nên xin khối mới lớn hơn bao nhiêu? Nếu chỉ xin thêm một chỗ mỗi lần, thêm n phần tử phải chép
xấp xỉ n * n / 2 lần, đủ treo máy khi n lớn. Giải pháp thực tế là nhân đôi: mỗi lần đầy thì xin
khối gấp đôi. Khi đó các lần sao chép là 1, 2, 4, 8, ..., tổng luôn nhỏ hơn 2n, chia đều cho n
lần push_back thì mỗi lần chỉ gánh một chi phí hằng số. Đó là ý nghĩa của chi phí khấu hao
(amortized): thỉnh thoảng có một lần rất đắt, nhưng trung bình trên cả dãy thao tác thì giá mỗi lần vẫn
là hằng số. Nếu biết trước sẽ thêm bao nhiêu phần tử, hãy gọi v.reserve(n) ngay từ đầu: nó nâng
capacity mà không đụng size, nên các lần push_back sau đó khỏi phải dời khối.
push_back có thể làm hỏng tham chiếu cũVì push_back có lúc dời cả khối nhớ sang chỗ mới, mọi con trỏ và tham chiếu đang trỏ vào phần
tử của vector đều vô hiệu sau lần cấp phát lại đó.
vector<int> v = {1, 2, 3};
int& r = v[0]; // r bám vào ô đầu của khối hiện tại
v.push_back(4); // vector có thể đã dời sang khối khác
// r bây giờ có thể trỏ vào vùng nhớ chết, đọc hay ghi đều là hành vi không xác định
Quy tắc an toàn: hãy giữ chỉ số thay vì địa chỉ, vì chỉ số vẫn đúng sau khi khối dời chỗ.
Xem chạy từng bước: cấp phát lại làm treo tham chiếu
Trình mô phỏng đầu bài cho thấy push_back nới vector một cách êm ả. Trình dưới đây phóng to đúng khoảnh khắc nguy hiểm: khi size chạm capacity, push_back phải xin một khối nhớ mới và trả khối cũ về hệ thống, khiến một tham chiếu đang bám vào phần tử cũ trở thành treo. Hãy theo dõi khối #B1 bị bỏ lại còn r thì vẫn ôm địa chỉ trong nó.
1#include <iostream>2#include <vector>3using namespace std;45int main() {6 vector<int> v = {1, 2};7 int& r = v[0];8 v.push_back(3);9 r = 99;10 cout << v[0];11}
Chọn mảng tĩnh hay vector
Giờ ta có đủ cơ sở để so sánh thay vì học thuộc lời khuyên suông.
| Tiêu chí | Mảng tĩnh int a[N] | vector<int> v |
|---|---|---|
| Kích thước | cố định, biết lúc biên dịch | đổi được lúc chạy |
| Thêm phần tử | không thêm được | push_back, khấu hao hằng số |
| Biết độ dài | phải tự giữ một biến n | có sẵn v.size() |
| Chi phí ngầm | gần như không có | quản lý dung lượng, đôi khi cấp phát lại |
| Truyền vào hàm | suy biến thành con trỏ, mất độ dài | giữ nguyên độ dài |
| Rủi ro tràn ngăn xếp | có, nếu N lớn | n/a |
Dùng mảng tĩnh khi số lượng cố định, nhỏ, biết chắc ngay khi viết mã: ba tọa độ của một điểm, hai
mươi sáu ô đếm chữ cái. Dùng vector trong mọi trường hợp còn lại. Lời khuyên gọn nhất cho người
mới: mặc định dùng vector, chỉ quay về mảng tĩnh khi có lý do rõ ràng.
Ba cách duyệt và khi nào sửa được phần tử
Mẫu đọc dữ liệu chuẩn: đọc số lượng n, rồi đọc n giá trị vào vector. Sau đó bạn
duyệt theo một trong ba cách.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> v(n);
for (int i = 0; i < n; i++) cin >> v[i]; // đọc n số
for (int i = 0; i < n; i++) cout << v[i] << " "; // cách 1: theo chỉ số
for (int x : v) cout << x << " "; // cách 2: range, chỉ đọc
for (int &x : v) x *= 2; // cách 3: range tham chiếu, sửa được
}
Điểm dễ sai: cách 2 (for (int x : v)) tạo một bản sao của từng phần tử, nên gán
vào x không đụng tới vector gốc. Muốn sửa phần tử ngay trong danh sách, phải
thêm dấu & như cách 3 (for (int &x : v)), khi đó x là bí danh của phần tử thật.
Truyền vector vào hàm
Khi tách phần xử lý dãy số thành một hàm riêng, xuất hiện câu hỏi mà nhiều người viết sai suốt nhiều năm không biết: nên khai báo tham số kiểu gì?
Mặc định C++ truyền tham số theo giá trị, nghĩa là sao chép. Với một int thì chép bốn byte,
chẳng đáng gì. Nhưng với vector<int> chứa một triệu phần tử, mỗi lần gọi hàm là một lần chép bốn
megabyte rồi hủy đi khi hàm kết thúc, dù hàm có thể chỉ đọc để cộng dồn và chẳng cần bản sao nào. Có
ba cách khai báo tham số:
vector<int> v: nhận bản sao, sửa thoải mái mà không đụng bản gốc, nhưng tốn một lần chép.vector<int>& v: nhận tham chiếu, tức chính bản gốc. Không chép gì cả, và sửa được dữ liệu của người gọi.const vector<int>& v: nhận tham chiếu hằng. Không chép gì cả, đồng thời trình biên dịch cấm hàm sửa dữ liệu. Đây là cách dùng cho mọi hàm chỉ đọc.
#include <iostream>
#include <vector>
using namespace std;
long long tinhTong(const vector<int>& v) { // chỉ đọc: không sao chép, không được sửa
long long s = 0;
for (int x : v) s += x;
return s;
}
void nhanDoiTatCa(vector<int>& v) { // cần sửa bản gốc: tham chiếu thường
for (int &x : v) x *= 2;
}
int main() {
vector<int> v = {1, 2, 3};
cout << tinhTong(v) << "\n"; // 6
nhanDoiTatCa(v);
cout << tinhTong(v) << "\n"; // 12, v đã thành {2, 4, 6}
}
const vector<int>& không chỉ là mẹo tăng tốc. Chữ const còn là lời hứa đọc được bằng mắt: ai nhìn
chữ ký hàm cũng biết ngay tinhTong không thể làm hỏng dữ liệu của họ, và nếu bạn lỡ tay viết
v[0] = 5; bên trong, trình biên dịch báo lỗi ngay. Hãy biến điều này thành thói quen: hễ hàm chỉ
đọc một đối tượng lớn, nhận nó bằng tham chiếu hằng.
Ngược lại, quên dấu & ở nhanDoiTatCa thì hàm nhân đôi một bản sao rồi vứt đi, còn v ở main vẫn
y nguyên. Chương trình chạy trơn tru, không báo lỗi, chỉ có kết quả sai. Loại lỗi im lặng này khó tìm
hơn nhiều so với lỗi làm sập chương trình.
Mảng nhiều chiều sơ lược
Dữ liệu dạng bảng như ma trận điểm hay bản đồ ô vuông cần hai chỉ số: hàng và cột.
Với vector, ta dùng vector của vector.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n = 2, m = 3;
vector<vector<int>> g(n, vector<int>(m, 0)); // lưới 2x3 toàn 0
g[0][1] = 5; // hàng 0, cột 1
g[1][2] = 7; // hàng 1, cột 2
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) cout << g[i][j] << " ";
cout << "\n";
}
}
Luôn nhớ thứ tự chỉ số là [hàng][cột]. Mảng tĩnh hai chiều viết int g[100][100];,
nếu lớn thì khai báo ngoài main để tránh tràn ngăn xếp.
Truy cập v[i] với i < 0 hoặc i >= v.size() là hành vi không xác định: chương
trình có thể cho kết quả rác, chạy vẫn ra nhưng sai, hoặc sập bất chợt. Ba cái bẫy hay
gặp:
- Viết
for (int i = 0; i <= n; i++)thay vìi < n, chạm nhầmv[n]không tồn tại. - Quên
v[v.size()]không phải phần tử cuối, phần tử cuối làv[v.size() - 1]. - Dùng
v.size() - 1khivectorrỗng: vìsize()là kiểu không dấu,0 - 1không cho-1mà cho một số cực lớn.
Trong vòng lặp nên lấy int n = v.size(); trước rồi so sánh với n cho an toàn.
Vì sao C++ không kiểm tra biên giúp bạn
Nếu truy cập ngoài biên nguy hiểm đến vậy, sao trình biên dịch không chặn lại? C++ cố tình không làm,
và đây là lựa chọn thiết kế có chủ đích, thường được tóm bằng câu "bạn không phải trả tiền cho thứ
bạn không dùng". Muốn kiểm biên, mỗi lần đọc v[i] máy phải chèn thêm một phép so sánh và một nhánh
rẽ. Nghe thì nhỏ, nhưng trong vòng lặp chạy hàng tỉ lượt của phần mềm đồ họa hay mô phỏng vật lý, phép
so sánh ấy ăn mất một phần đáng kể thời gian chạy, trong khi lập trình viên đã tự biết i luôn hợp lệ.
Hệ quả là khi bạn viết v[7] trên một vector bốn phần tử, chương trình vẫn ngoan ngoãn tính
B + 7 * 4 rồi đọc chỗ đó, chẳng buồn biết chỗ đó thuộc về ai. Có thể nơi ấy là vùng nhớ của biến
khác, bạn đọc ra số rác hoặc ghi đè lên biến đó, khiến bug hiện ra ở chỗ hoàn toàn không liên quan.
Có thể nơi ấy nằm ngoài vùng hệ điều hành cấp cho tiến trình và chương trình sập. Nguy hiểm nhất là khi
nó chạy có vẻ đúng trên máy bạn rồi sập trên máy người khác. Chuẩn C++ gọi mọi khả năng đó là hành vi
không xác định.
May thay, vẫn có cửa an toàn: v.at(i) làm đúng việc của v[i] nhưng có kiểm biên, nếu i vượt quá
thì ném ngoại lệ std::out_of_range thay vì âm thầm phá hoại.
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> v = {10, 20, 30};
cout << v.at(1) << "\n"; // 20, an toàn
// cout << v.at(7); // ném std::out_of_range, dừng ngay và báo rõ
// cout << v[7]; // KHÔNG báo gì, đọc bừa vùng nhớ lạ
}
Khi biên dịch cũng nên bật cảnh báo -Wall -Wextra và dùng bộ kiểm tra bộ nhớ -fsanitize=address,
công cụ này chỉ ra chính xác dòng nào chạm ngoài biên.
Tự kiểm tra
Chỉ số hợp lệ của a sau push_back là từ mấy đến mấy?
Từ 0 đến 3 (4 phần tử: a[0]..a[3]). Truy cập a[4] là vượt biên, hành vi
không xác định, một trong những lỗi phổ biến nhất khi dùng mảng/vector.
Bài tập
Bài 1: Đọc n số vào vector rồi in tổng và giá trị lớn nhất.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> v(n);
for (int i = 0; i < n; i++) cin >> v[i];
if (v.empty()) { cout << "0 0\n"; return 0; } // chặn trước khi chạm v[0]
long long tong = 0;
int mx = v[0]; // lấy phần tử đầu làm mốc
for (int x : v) { tong += x; if (x > mx) mx = x; }
cout << tong << " " << mx << "\n";
}
Chú ý dùng long long cho tong vì cộng nhiều số dễ vượt giới hạn int. Dòng
v.empty() cũng không thừa: nếu người dùng gõ n bằng 0 thì v[0] là truy cập ngoài
biên, đúng cái bẫy mà cả bài này cảnh báo.
Bài 2: Đếm xem trong vector có bao nhiêu số chẵn.
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> v = {3, 8, 5, 12, 7, 4};
int dem = 0;
for (int x : v) if (x % 2 == 0) dem++; // x chẵn khi chia 2 dư 0
cout << dem; // 3
}
Ta chỉ cần một biến đếm và một điều kiện x % 2 == 0.
Bài 3: Đảo ngược thứ tự phần tử trong vector rồi in ra.
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> v = {1, 2, 3, 4, 5};
int n = v.size();
for (int i = 0; i < n / 2; i++) {
int tam = v[i]; // đổi chỗ hai đầu tiến dần vào giữa
v[i] = v[n - 1 - i];
v[n - 1 - i] = tam;
}
for (int x : v) cout << x << " "; // 5 4 3 2 1
}
Chỉ cần chạy nửa mảng và ghép ô i với ô đối xứng n - 1 - i.
Bài 4: Viết hàm nhận vector điểm và trả về điểm trung bình, không sao chép dữ liệu.
#include <iostream>
#include <vector>
using namespace std;
double diemTrungBinh(const vector<double>& diem) { // tham chiếu hằng: không chép, không sửa
if (diem.empty()) return 0.0; // chặn chia cho 0 khi vector rỗng
double tong = 0.0;
for (double d : diem) tong += d;
return tong / diem.size();
}
int main() {
vector<double> diem = {7.5, 8.0, 6.0, 9.5};
cout << diemTrungBinh(diem); // 7.75
}
Tham số là const vector<double>&: hàm chỉ đọc nên không cần bản sao, và const bảo đảm nó không sửa
dữ liệu của người gọi. Dòng diem.empty() không thừa: vector rỗng thì size() bằng 0 và phép chia
cho kết quả vô nghĩa. Biến tong phải là double, vì chia hai số nguyên cho ra thương nguyên.
Bài 5: Đọc n số rồi in ra những số lớn hơn giá trị trung bình.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> v;
v.reserve(n); // xin sẵn chỗ, tránh cấp phát lại nhiều lần
for (int i = 0; i < n; i++) {
int x;
cin >> x;
v.push_back(x);
}
double tong = 0;
for (int x : v) tong += x;
double tb = v.empty() ? 0 : tong / v.size();
for (int x : v) if (x > tb) cout << x << " ";
}
Bài này bắt buộc phải duyệt hai lượt: muốn biết một số có lớn hơn trung bình hay không thì phải
biết trung bình trước, mà muốn biết trung bình thì phải đọc hết dữ liệu. Đó là lý do phải lưu cả dãy
vào vector thay vì xử lý từng số rồi vứt đi.
Câu hỏi tự kiểm
- 1Một vector<int> a có 4 phần tử. Chỉ số hợp lệ và cách lấy phần tử cuối là gì?
- 2Đoạn for (int x : v) x *= 2; tác động thế nào tới v?
- 3Sau int& r = v[0]; rồi v.push_back(4); vì sao r có thể trở nên nguy hiểm?
- 4Truy cập v[7] trên một vector chỉ có 4 phần tử thường xảy ra chuyện gì?
Tóm tắt
Mảng gom nhiều giá trị cùng loại vào một khối ô nhớ liền mạch, truy cập qua chỉ số đánh từ 0.
Chỉ số là số ô phải nhảy kể từ đầu khối chứ không phải thứ tự đếm của con người, nên mọi phần tử đều
đọc nhanh như nhau.
Mảng tĩnh cố định kích thước ngay lúc biên dịch. vector giữ tính liền mạch nhưng co giãn được, nhờ
tách bạch size với capacity và nhân đôi dung lượng mỗi lần đầy, khiến chi phí push_back thành
hằng số theo nghĩa khấu hao. Biết trước số lượng thì gọi reserve. Khi truyền dãy vào hàm, dùng
const vector<T>& cho hàm chỉ đọc để tránh sao chép, dùng vector<T>& khi thật sự cần sửa bản gốc.
Cạm bẫy lớn nhất vẫn là truy cập ngoài biên. C++ cố tình không kiểm biên để đổi lấy tốc độ, nên trách
nhiệm thuộc về bạn: nhớ chỉ số cuối là size() - 1, cẩn thận với size() không dấu khi vector rỗng,
và dùng at() khi gỡ lỗi.
vector<T> là danh sách co giãn: chỉ số bắt đầu từ 0, push_back thêm cuối,
for (auto x : v) duyệt từng phần tử. Luôn nhớ chỉ số cuối là size() - 1.