C++vector | list | |
|---|---|---|
| Bộ nhớ | contiguous (cache-friendly) | linked nodes (non-contiguous) |
| Random access | O(1) | O(n) |
| Insert/delete cuối | O(1) amortized | O(1) |
| Insert/delete giữa | O(n) (shift) | O(1) tại vị trí iterator |
| Memory overhead | thấp | cao (2 pointer/node) |
Trong thực tế, vector gần như luôn thắng nhờ cache locality — ngay cả khi insert/delete nhiều ở giữa, cache miss của list thường đắt hơn O(n) shift của vector trên dữ liệu nhỏ/trung bình.
Dùng list khi: cần giữ iterator hợp lệ sau khi insert/delete, splice nhiều đoạn lớn (std::list::splice là O(1)).
Dùng vector cho mặc định — chỉ chuyển sang list sau khi đo đạc thực tế.