push_front vào vector: quả bom O(n) núp trên đường nóng

std::vector là cấu trúc mặc định của gần như tất cả chúng ta khi cần 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ệ, tệ đến mức tôi vẫn ngạc nhiên mỗi lần đo lại: thêm ở đầu (push_front).

Lý do đơn giản đến khó chịu. Muốn chèn vào vị trí 0, mọi phần tử đang có phải dịch sang phải một ô để chừa chỗ — nên mỗi lần thêm ở đầu là O(n). Khi bạn thật sự cần một deque (double-ended queue — hàng đợi hai đầu), chèn và xóa được ở cả hai đầu trong O(1), có hai cách làm quen thuộc: 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 câu "thêm ở đầu thì vector cũng được" là một cái bẫy O(n) đội lốt lời khuyên vô hại.

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 ở chính cái làm nó nhanh: bố cục liền mạch. Cùng một đặc điểm giúp nó duyệt như bay lại khiến nó chật vật 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 được chuyện dịch:

• Mảng vòng (ring buffer): một mảng cấp trước cộng hai chỉ số head và tail chạy vòng (lấy mod dung lượng). push_front chỉ lùi head, push_back chỉ tiến tail — 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 khối A đi — với tôi đây là bằng chứng O(n) rõ ràng nhất trong cả sê-ri này. Khi N gấp đôi từ 50k lên 100k, thời gian mỗi lần push_front của vector cũng gấp đôi theo, 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 tôi thấy nên nói thẳng cho công bằng: 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ố.

Khối B là 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.

Khối C là chỗ tôi muốn 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 và hay lấy làm lý do để né.

(Môi trường đo: container gcc:13 trên host ARM AArch64, g++ -O2, mỗi số lấy MIN sau warmup, chia cho số thao tác. Con số tuyệt đối đổi theo máy; cái cần nhìn là dáng per-op theo N và tỉ lệ giữa ba cấu trúc.)

Hai niềm tin đối nghịch, cùng sai

Tôi vào đo với đúng thói quen cũ của mình: "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 mà". Con số bác thẳng: 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 biến thành O(n²) lúc nào không hay. 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 ngay trên đường nóng.

Nhưng có một niềm tin ngược lại cũng sai không kém: "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 cho lành". Đ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ì nghe "phức tạp" là bỏ lỡ đúng công cụ sinh ra cho hàng đợi hai đầu mọc được. Cả hai định kiến, một cái quá tin vector, một cái quá ngại deque, đều tan khi bạn nhìn per-op theo N.

Về đến code hằng ngày

Điều đầu tiên tôi rút ra: 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 hay mạng — tất cả đề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, không một dòng cảnh báo. 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.

Điều thứ hai là cách chọn giữa hai cấu trúc deque, và tôi hay hỏi mình đúng hai câu: "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, thậm chí vector cộng đảo chiều tùy ngữ cảnh.

Và điều cuối, cũng là tinh thần đo lường mà cả sê-ri này xoay quanh: chữ "cũng được" hay che giấu độ phức tạp thật. Đo per-op theo N mới thấy O(n) hiện hình — thêm ở đầu vector O(n) (per-op gấp đôi theo N: 1552 → 3375 ns), ring buffer và std::deque O(1) (~1–3 ns, ring nhanh hơn vector ~1136x ở N=100k); churn hàng đợi ring 0,50 ns vẫn dưới deque 1,77 ns dù cả hai O(1); duyệt thì vector ≈ ring (0,225 vs 0,227), deque chậm ~19% (0,268) vì khối gián tiếp. Cách một cấu trúc đặt phần tử của nó quyết định thao tác nào rẻ và thao tác nào là O(n) núp sẵn chờ bạn đi qua.

Chỗ này dân viết Java hay Go sẽ thấy quen ngay. Trong Java, ArrayDeque chính là một ring buffer đóng gói sẵn — addFirst/addLast O(1) — và tài liệu của nó nói thẳng là nhanh hơn LinkedList khi làm hàng đợi hoặc ngăn xếp, đúng vì lý do liền mạch ở trên; còn dùng ArrayList.add(0, x) thì bạn đang trả đúng cái giá O(n) của vector::push_front. Go thì không có deque trong thư viện chuẩn, nên ai cần hàng đợi hai đầu hiệu năng cao thường tự cuộn một ring buffer trên slice với hai chỉ số head/tail — y hệt bài đo này. Và khi lên tới tầng hệ thống, ring buffer là kiến trúc kinh điển cho mọi hàng đợi cố định ở đường nóng: vòng đệm log, buffer gói mạng trong kernel, hàng chờ sự kiện — chọn nó không phải vì nghe sang, mà vì O(1) bền vững và không cấp phát lại giữa chừng.

Muốn tự thấy thì không mất bao lâu. 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. Sau đó 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, ring nhỉnh hơn vì không quản khối. Cuối cùng, duyệt tuần tự cả ba: vector và ring gần bằng nhau, deque chậm hơn chút vì nhảy khối. Vài phút đó 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ế đúng cho hai đầu biến nó thành O(1) mà gần như không mất gì khi duyệt.