std::vector là cấu trúc mặc định của hầu hết chúng ta cho một danh sách: thêm ở cuối (push_back) khấu hao O(1), truy cập ngẫu nhiên O(1), duyệt cực nhanh nhờ liền mạch trong bộ nhớ. Nhưng có một thao tác mà vector làm rất tệ: thêm ở đầu (push_front). Vì mọi phần tử phải dịch sang phải một ô để chừa chỗ, mỗi lần thêm ở đầu là O(n). Khi bạn cần một deque (double-ended queue — hàng đợi hai đầu), chèn/xóa được ở cả hai đầu trong O(1), có hai cách làm: mảng vòng (ring buffer) và khối phân đoạn (như std::deque). Tôi đo cả ba trong container gcc:13, và con số cho thấy "thêm ở đầu thì vector cũng được" là một cái bẫy O(n).
Dịch cả mảng O(n) so với lùi một chỉ số O(1)
Vấn đề của vector nằm ở bố cục liền mạch — chính cái làm nó nhanh khi duyệt lại làm nó chậm khi thêm ở đầu:
vector::push_front(thực ra làinsert(begin(), x)): để chèn vào vị trí 0, mọi phần tử hiện có phải dịch sang phải một ô. Đó là O(n) mỗi lần, và xây một danh sách n phần tử bằng cách thêm ở đầu là O(n²).
Hai cách làm deque tránh chuyện dịch:
- Mảng vòng (ring buffer): một mảng cấp trước cộng hai chỉ số
headvàtailchạy vòng (lấy mod dung lượng).push_frontchỉ lùihead,push_backchỉ tiếntail— O(1), không dịch gì. Dữ liệu vẫn liền mạch (trừ đúng một chỗ nối khi vòng qua) nên duyệt vẫn nhanh như mảng. Hạn chế: dung lượng cố định (muốn lớn hơn thì phải mọc lại như vector). - Khối phân đoạn (
std::deque): nhiều khối cố định, nối với nhau bằng một mảng con trỏ khối. Thêm ở hai đầu = cấp một khối mới ở đầu hoặc cuối — O(1), không dịch, và mọc vô hạn. Cái giá: duyệt phải đi qua nhiều khối rời, mỗi khối một lần gián tiếp con trỏ, nên kém mảng liền mạch một chút.
Đo: vector O(n), ring và deque O(1)
Tôi đo push_front theo hai kích thước N (để lộ dáng O(n) so với O(1)), một vòng churn hàng đợi bền vững, và duyệt tuần tự:
int, g++ -O2:
A. push_front (thêm ở ĐẦU):
N=50.000 : vector 1551,5 ns/op | ring 2,94 ns | deque 0,96 ns
N=100.000 : vector 3374,6 ns/op | ring 2,97 ns | deque 0,66 ns
-> N gấp đôi thì vector gấp đôi mỗi op (O(n)); ring & deque KHÔNG đổi (O(1))
-> ở N=100k, ring nhanh hơn vector ~1136 lần
B. CHURN hàng đợi (push_back + pop_front, 20 triệu lượt, cửa sổ 1000):
ring buffer : 0,50 ns/lượt (O(1) bền vững)
std::deque : 1,77 ns/lượt (O(1), nhưng quản khối nên chậm hơn)
C. DUYỆT tuần tự (10 triệu phần tử):
vector : 0,225 ns/phần tử (liền mạch)
ring : 0,227 ns/phần tử (liền mạch, một lần wrap)
deque : 0,268 ns/phần tử (nhiều khối, con trỏ gián tiếp)
Nhìn A — đây là bằng chứng O(n) rõ nhất trong cả sê-ri: khi N gấp đôi từ 50k lên 100k, thời gian mỗi push_front của vector cũng gấp đôi, từ 1551 lên 3375 ns. Đó chính là dấu hiệu O(n) — chi phí một thao tác phụ thuộc số phần tử đã có. Trong khi đó ring buffer giữ nguyên ~2,95 ns và deque ~0,7 ns bất kể N. Ở N=100k, ring nhanh hơn vector ~1136 lần, và khoảng cách càng giãn khi N lớn hơn. Một chi tiết trung thực: deque push_front (0,66 ns) ở đây còn nhanh hơn ring của tôi (2,95 ns), vì ring phải làm phép % dung_lượng mỗi lần còn deque chỉ ghi vào khối đầu — cả hai đều O(1), chỉ khác hằng số.
Nhìn B — churn hàng đợi bền vững: ring buffer 0,50 ns/lượt, deque 1,77 ns/lượt. Cả hai đều O(1) (thời gian không tăng dù chạy 20 triệu lượt), nhưng ring buffer tự cài nhanh hơn ~3,5 lần vì nó chỉ đụng một mảng cấp sẵn, còn std::deque phải quản lý các khối. Đây là lý do ring buffer là lựa chọn cho hàng đợi kích thước cố định ở đường nóng.
Nhìn C — chỗ báo trung thực về cái giá của deque: duyệt tuần tự, vector và ring ngang nhau (0,225 vs 0,227 ns) vì cả hai liền mạch; deque chậm hơn ~19% (0,268 ns) vì phải nhảy qua nhiều khối, mỗi khối một lần gián tiếp con trỏ. Chênh lệch có thật nhưng nhỏ — không phải "deque chậm hơn vector nhiều" như người ta hay tưởng.
Một lần tôi đo hớ: "thêm ở đầu thì vector cũng được" và "deque chậm hơn vector vì phức tạp"
Tôi vào đo với thói quen: "cần thêm phần tử ở đầu à? Dùng vector rồi insert(begin(), x), hoặc push_back rồi đảo ngược — vector là được". Đo phá tan: vector::push_front phải dịch cả mảng nên là O(n) — thời gian mỗi lần gấp đôi khi N gấp đôi (1551 → 3375 ns), và xây một hàng đợi bằng cách thêm ở đầu thành O(n²). Một ring buffer chỉ lùi một chỉ số, O(1) (~3 ns), nhanh hơn vector 1136 lần ở N=100k. "Thêm ở đầu thì vector cũng được" là một quả bom O(n) núp sẵn trên đường nóng.
Còn một niềm tin ngược cũng sai: "deque phức tạp hơn vector (nhiều khối, con trỏ) nên chắc chậm hơn, tránh đi". Đo cho thấy std::deque push_front/push_back đều O(1) (0,66 ns), nhanh hơn nhiều vector cho thao tác hai đầu; và duyệt tuần tự chỉ chậm hơn vector ~19% (0,268 vs 0,225 ns) — một cái giá nhỏ, không phải thảm họa. Né deque vì "phức tạp" là bỏ lỡ đúng công cụ cho hàng đợi hai đầu mọc được.
Bài học đo lường: deque (hàng đợi hai đầu) chèn/xóa O(1) ở CẢ HAI đầu — vector push_front phải DỊCH cả mảng O(n) (per-op gấp đôi khi N gấp đôi: 1552 → 3375 ns), còn ring buffer (mảng cấp trước + head/tail chạy vòng) chỉ lùi/tiến một chỉ số O(1) (~3 ns) = ~1136x ở N=100k; std::deque (khối phân đoạn) cũng O(1) hai đầu (0,66 ns), mọc vô hạn, duyệt chỉ chậm ~19% vs vector. Ring buffer churn 0,50 ns < deque 1,77 ns (cả hai O(1)). Nếu tôi tin "vector cũng được" tôi đặt một O(n²) trên đường nóng; nếu tôi tin "deque chậm vì phức tạp" tôi né đúng cấu trúc cho việc này.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: cần thêm/bớt ở đầu (hay cả hai đầu) thì đừng dùng vector — dùng ring buffer hoặc std::deque. Hàng đợi (queue), sliding window, undo/redo, hàng chờ công việc, buffer âm thanh/mạng — đều cần thao tác hai đầu. vector::push_front/erase(begin()) là O(n) mỗi lần và biến vòng lặp thành O(n²) một cách âm thầm. Nếu kích thước có trần biết trước, ring buffer là nhanh nhất; nếu cần mọc tùy ý, std::deque cho O(1) hai đầu mà vẫn mọc được.
Hệ quả thứ hai: chọn giữa ring buffer và deque theo "cố định hay mọc" và "duyệt nhiều hay không". Ring buffer: dung lượng cố định, nhanh nhất, dữ liệu liền mạch nên duyệt bằng vector — hợp cho buffer kích thước biết trước. std::deque: mọc vô hạn, hai đầu O(1), nhưng duyệt chậm hơn ~19% và các phần tử không nằm trong một khối liền (đừng lấy &deque[0] làm con trỏ mảng như với vector). Nếu bạn duyệt tuần tự rất nhiều và cần liền mạch, cân nhắc ring buffer hoặc thậm chí vector + đảo chiều tùy ngữ cảnh.
Hệ quả thứ ba là tinh thần đo lường: "cũng được" che giấu độ phức tạp — đo per-op theo N mới thấy O(n) hiện hình. Con số mang theo: thêm ở đầu: vector O(n) (per-op gấp đôi theo N: 1552 → 3375 ns), ring buffer & std::deque O(1) (~1–3 ns, ring nhanh hơn vector ~1136x ở N=100k); churn hàng đợi ring 0,50 ns < deque 1,77 ns (cả hai O(1)); duyệt: vector ≈ ring (0,225 vs 0,227), deque chậm ~19% (0,268) vì khối gián tiếp. Ring buffer cho kích thước cố định, deque cho mọc được; đừng push_front vào vector. Cách một cấu trúc đặt phần tử quyết định thao tác nào rẻ và thao tác nào là O(n) núp sẵn.
Thử ba mươi giây
Cài một ring buffer đơn giản: một mảng cấp trước, hai chỉ số head và cnt, push_front làm head = (head + cap - 1) % cap rồi ghi, push_back ghi vào (head + cnt) % cap. Rồi bấm giờ ba cách thêm N phần tử ở đầu: vector::insert(begin()), ring buffer, và std::deque::push_front. Làm với N=50.000 rồi N=100.000 và xem thời gian mỗi lần thêm của vector gấp đôi khi N gấp đôi — đó là O(n) hiện hình — trong khi ring và deque giữ nguyên. Rồi churn một hàng đợi (thêm cuối, bỏ đầu) hàng chục triệu lần: ring và deque đều giữ tốc độ ổn định (O(1)), ring nhỉnh hơn vì không quản khối. Cuối cùng, duyệt tuần tự cả ba và so: vector và ring gần bằng nhau (liền mạch), deque chậm hơn chút vì nhảy khối. Ba mươi giây đó cho bạn thấy điều mà "thêm ở đầu thì vector cũng được" giấu đi: một thao tác nghe vô hại có thể là O(n) mỗi lần, và một cấu trúc thiết kế cho hai đầu biến nó thành O(1) mà gần như không mất gì khi duyệt.
