List trong C++ STL là container lưu trữ dữ liệu theo thứ tự tuần tự và cấp phát bộ nhớ không liên tục. List được triển khai dưới dạng danh sách liên kết đôi (doubly linked list), cho phép chèn/xóa từ cả hai đầu và duyệt xuôi/ngược.
Ưu điểm so với vector
List nhanh hơn trong chèn/xóa phần tử nếu iterator đã trỏ đúng vị trí.
Nhược điểm
Không truy cập ngẫu nhiên (random access) được như vector. Để lấy phần tử thứ 4 phải duyệt từ đầu hoặc cuối.
Các hàm thành viên chính
| Hàm | Mô tả |
|---|---|
push_front(x) | Thêm x vào đầu list. |
push_back(x) | Thêm x vào cuối list. |
insert(pos, n, x) | Chèn n bản sao x trước vị trí pos. Trả về iterator đầu tiên mới chèn. |
pop_front() | Xóa phần tử đầu. |
front() | Trả về tham chiếu phần tử đầu. |
pop_back() | Xóa phần tử cuối. |
back() | Trả về tham chiếu phần tử cuối. |
size() | Số phần tử. |
resize(n, val) | Thay đổi kích thước thành n, phần tử mới mang giá trị val. |
max_size() | Số phần tử tối đa có thể chứa. |
clear() | Xóa tất cả phần tử. |
remove(x) | Xóa tất cả phần tử bằng x. |
remove_if(pred) | Xóa phần tử thỏa mãn predicate. |
erase(pos) / erase(first, last) | Xóa 1 phần tử hoặc dãy. Trả về iterator sau phần tử cuối cùng xóa. |
empty() | Kiểm tra rỗng. |
begin(), end(), rbegin(), rend() | Iterator đầu/cuối (thuận/nghịch). |
cbegin(), cend(), crbegin(), crend() | Const iterator. |
reverse() | Đảo ngược list. |
unique() | Xóa các phần tử trùng lặp liên tiếp. |
emplace(pos, args) | Tạo và chèn phần tử tại pos. |
emplace_front(args) | Tạo và chèn vào đầu. |
emplace_back(args) | Tạo và chèn vào cuối. |
operator= | Gán list khác. |
swap(other) | Hoán đổi nội dung với list khác. |
merge(other) | Trộn 2 list đã sắp xếp. |