std::list

#include <list>

template <class T, class Alloc = allocator<T>> class list;

std::list trong C++ là một container tuần tự (sequence container) thực hiện danh sách liên kết đôi (doubly linked list). Điều này có nghĩa là mỗi phần tử trong std::list lưu trữ dữ liệu của chính nó cùng với hai con trỏ, một trỏ đến phần tử trước đó và một trỏ đến phần tử tiếp theo trong danh sách.

Tham số

`T`

Kiểu dữ liệu của các phần tử trong list.

`Alloc`

Kiểu cấp phát bộ nhớ, mặc định là std::allocator<T>. Thường bạn không cần quan tâm đến tham số này.

`forward_list`

Tên của list bạn muốn tạo.

Đặc điểm

Danh sách liên kết đôi: Mỗi phần tử trong std::list chứa con trỏ đến phần tử kế tiếp và phần tử trước đó.
Chèn/xóa hiệu quả: Việc chèn và xóa phần tử ở bất kỳ vị trí nào trong std::list có độ phức tạp O(1) (nếu bạn đã có iterator trỏ đến vị trí đó).
Không hỗ trợ truy cập ngẫu nhiên: std::list không hỗ trợ truy cập ngẫu nhiên các phần tử thông qua toán tử [] hoặc hàm at(). Bạn phải duyệt qua danh sách để đến được phần tử mong muốn (O(n)).
Kích thước linh hoạt: std::list có thể thay đổi kích thước linh hoạt trong quá trình chạy.
Không có capacity(): std::list không có hàm capacity() vì nó không cấp phát bộ nhớ thành khối liên tục.
Sử dụng bộ nhớ nhiều hơn std::vector: Do phải lưu trữ thêm con trỏ cho mỗi phần tử, std::list thường sử dụng nhiều bộ nhớ hơn std::vector (đối với cùng số lượng phần tử). Duyệt danh sách chậm hơn std::vector do các phần tử không nằm liên tục trong bộ nhớ.
Không làm thay đổi iterator (trừ trường hợp xóa): Các thao tác chèn, nối, sắp xếp, đảo ngược, ... không làm thay đổi (invalidate) các iterator đang trỏ đến các phần tử trong std::list (trừ khi bạn xóa chính phần tử mà iterator đang trỏ tới).
Khi nào nên sử dụng std::list:
- Khi bạn cần chèn và xóa phần tử thường xuyên ở bất kỳ vị trí nào trong danh sách.
- Khi bạn không cần truy cập ngẫu nhiên các phần tử.
- Khi việc sử dụng bộ nhớ không phải là vấn đề quá quan trọng.

Ví dụ:

#include <iostream>
#include <list>
#include <string>
#include <algorithm>

int main() {
  // 1. Khởi tạo list rỗng
  std::list<int> list1;

  // 2. Khởi tạo list với số lượng phần tử ban đầu và giá trị mặc định
  std::list<float> list2(5, 3.14f); // 5 phần tử, giá trị 3.14

  // 3. Khởi tạo list từ một initializer list
  std::list<std::string> list3 = {"hello", "world", "!"};

  // 4. Khởi tạo list từ một list khác (copy constructor)
  std::list<int> list4 = {1, 2, 3, 4, 5};
  std::list<int> list5(list4);

  // 5. Chèn phần tử vào đầu list
  list1.push_front(10);
  list1.push_front(5);

  // 6. Chèn phần tử vào cuối list
  list1.push_back(20);
  list1.push_back(30);

  // 7. Truy cập phần tử đầu tiên và cuối cùng
  std::cout << "list1.front(): " << list1.front() << '\n'; // Output: 5
  std::cout << "list1.back(): " << list1.back() << '\n';   // Output: 30

  // 8. Xóa phần tử đầu tiên
  list1.pop_front();

  // 9. Xóa phần tử cuối cùng
  list1.pop_back();

  // 10. Chèn phần tử vào vị trí bất kỳ
  auto it = list1.begin();
  std::advance(it, 1); // Di chuyển iterator đến vị trí thứ hai
  list1.insert(it, 15); // Chèn 15 vào trước phần tử thứ hai

  // 11. Xóa phần tử tại vị trí bất kỳ
  it = list1.begin();
  std::advance(it, 1); // Di chuyển iterator đến vị trí thứ hai
  list1.erase(it); // Xóa phần tử thứ hai

  // 12. Duyệt list
  std::cout << "list1:";
  for (int x : list1) {
    std::cout << ' ' << x;
  }
  std::cout << '\n'; // Output: list1: 10 20

  // 13. Kiểm tra list rỗng
  if (list1.empty()) {
    std::cout << "list1 is empty\n";
  } else {
    std::cout << "list1 is not empty\n"; // Output: list1 is not empty
  }

  // 14. Lấy kích thước list
  std::cout << "list1.size(): " << list1.size() << '\n'; // Output: list1.size(): 2

  // 15. Xóa tất cả phần tử
  list1.clear();

  // 16. Sắp xếp
  list4.sort();

  // 17. Đảo ngược
  list4.reverse();

  // 18. Xóa phần tử có giá trị cụ thể
  list4.remove(3);

  // 19. Xóa phần tử thỏa mãn điều kiện
  list4.remove_if([](int n){ return n > 2; });

  // 20. Xóa các phần tử trùng lặp liền kề
  list4.unique();

  // 21. Hợp nhất hai list đã sắp xếp
  std::list<int> list6 = {2,4,6};
  std::list<int> list7 = {1,3,5};
  list6.merge(list7); // list7 phải rỗng sau khi merge
  
  // 22. Xóa phần tử tại vị trí sau iterator đc chỉ định
  it = list6.begin();
  list6.erase_after(it); // xoa phan tu sau phan tu dau tien

  // 23. Chèn phần tử tại vị trí sau iterator đc chỉ định
  list6.insert_after(it, 10);

  // 24. Xây dựng phần tử ngay tại chỗ (tránh copy)
  list3.emplace_front("Hi");
  list3.emplace_back("there");
  it = list3.begin();
  std::advance(it, 1);
  list3.emplace(it, "!"); // list3: Hi ! hello world there

  // 25. Chuyển 1 hoặc nhiều phần tử từ list này sang list khác
  std::list<int> list8 = {1,2,3};
  std::list<int> list9 = {4,5};
  list8.splice(list8.end(), list9); // list8: 1 2 3 4 5, list9: rỗng
  list8.splice(list8.end(), list9, list9.begin()); // list8: 1 2 3 4 5, list9: rỗng (ko có phần tử đầu)
  list9.push_front(6);
  list9.push_front(7);
  list9.push_front(8); // list9: 8 7 6
  list8.splice(list8.end(), list9, ++++list9.begin(), list9.end()); // list8: 1 2 3 4 5 6, list9: 8 7
  

  return 0;
}

Các cách phổ biến khai báo và khởi tạo một std::list

Khai báo một std::list rỗng:

std::list<int> list1; // list rỗng, kiểu int
std::list<std::string> list2; // list rỗng, kiểu std::string

Khai báo và khởi tạo với số lượng phần tử ban đầu và giá trị mặc định:

std::list<float> list3(5, 3.14f); // 5 phần tử, giá trị 3.14f
std::list<int> list4(10, 0); // 10 phần tử, giá trị 0

Khai báo và khởi tạo với `initializer_list` (từ C++11):

std::list<int> list5 = {1, 2, 3, 4, 5};
std::list<std::string> list6 = {"apple", "banana", "orange"};

Khai báo và khởi tạo bằng cách sử dụng iterator range (sao chép từ container khác):

std::vector<int> vec = {10, 20, 30};
std::list<int> list7(vec.begin(), vec.end()); // Sao chép từ vector

std::array<int, 4> arr = {5,6,7,8};
std::list<int> list8(arr.begin(), arr.end()); // Sao chép từ array

Khai báo và khởi tạo bằng cách sử dụng copy constructor:

std::list<int> list9 = {1, 3, 5};
std::list<int> list10(list9); // Sao chép từ list9

Khai báo và khởi tạo bằng cách sử dụng move constructor (từ C++11):

std::list<int> list11 = {2, 4, 6};
std::list<int> list12(std::move(list11)); // Di chuyển từ list11 (list11 sẽ rỗng sau đó)

Sử dụng `assign()` để gán giá trị sau khi khai báo:

std::list<int> list13;
list13.assign(4, 100); // Gán 4 phần tử có giá trị 100
list13.assign({1, 2, 3}); // Gán các giá trị từ initializer list

std::vector<int> vec2 = {5,4,3,2,1};
list13.assign(vec2.begin()+1, vec2.end()); // list13: 4 3 2 1

lưu ý

Khi sử dụng initializer_list để khởi tạo hoặc gán, bạn cần đảm bảo rằng kiểu dữ liệu của các phần tử trong initializer_list có thể chuyển đổi được sang kiểu phần tử của std::list.
Khi sử dụng iterator range để khởi tạo hoặc gán, bạn cần đảm bảo rằng phạm vi iterator là hợp lệ và các phần tử trong phạm vi có kiểu dữ liệu phù hợp.
Copy constructor và copy assignment operator tạo ra các bản sao độc lập của std::list nguồn.
Move constructor và move assignment operator (từ C++11) di chuyển tài nguyên từ std::list nguồn sang std::list đích, làm cho std::list nguồn trở thành rỗng, hiệu quả hơn so với sao chép.

Các kiểu dữ liệu đặc biệt của std::list

lưu ý

Ngoài các kiểu dữ liệu cơ bản như int, float, double, ..., std::list có thể chứa hầu như bất kỳ kiểu dữ liệu nào trong C++, miễn là kiểu dữ liệu đó thỏa mãn một số yêu cầu nhất định.

Con trỏ:

int*, float*, double*
char* (C-style strings)
Con trỏ đến các đối tượng của lớp tự định nghĩa
Con trỏ hàm

void*

std::list<int*> list_of_pointers;
int x = 10;
list_of_pointers.push_back(&x);

std::list<void*> list_of_void_pointers; // Không khuyến khích, trừ khi bạn biết mình đang làm gì

Các kiểu dữ liệu chuẩn (Standard Library Types):

std::string

std::list<std::string> list_of_strings;
list_of_strings.push_back("hello");

Containers: Bao gồm std::vector, std::list (chính nó), std::deque, std::array, std::set, std::map, std::forward_list, ...

std::list<std::vector<int>> list_of_vectors;
std::list<std::list<int>> list_of_lists;
std::list<std::map<int, std::string>> list_of_maps;

std::pair và std::tuple:

std::list<std::pair<int, std::string>> list_of_pairs;
std::list<std::tuple<int, float, char>> list_of_tuples;

Các kiểu khác: std::complex, std::bitset,...

Kiểu dữ liệu do người dùng định nghĩa (Classes and Structs):

Bạn có thể tạo std::list chứa các đối tượng của bất kỳ lớp (class) hoặc cấu trúc (struct) nào do bạn định nghĩa, miễn là chúng thỏa mãn các yêu cầu về CopyConstructible và Destructible (xem giải thích chi tiết ở phần Yêu cầu đối với kiểu dữ liệu bên dưới).
```
class MyClass {
public:
  int data;
  MyClass(int d) : data(d) {}
};

struct Point {
  int x;
  int y;
};

int main() {
  std::list<MyClass> list_of_objects;
  list_of_objects.push_back(MyClass(10));

  std::list<Point> list_of_points;
  list_of_points.push_back({1, 2});

  return 0;
}
```

Smart Pointers (từ C++11):

std::unique_ptr
std::shared_ptr

std::weak_ptr

std::list<std::unique_ptr<int>> list_of_unique_ptrs;
list_of_unique_ptrs.push_back(std::make_unique<int>(10));

std::list<std::shared_ptr<MyClass>> list_of_shared_ptrs;
list_of_shared_ptrs.push_back(std::make_shared<MyClass>(20));

Yêu cầu đối với kiểu dữ liệu trong std::list:

Để một kiểu dữ liệu T có thể được sử dụng làm kiểu phần tử trong std::list, nó phải thỏa mãn các yêu cầu sau:

CopyConstructible: Kiểu dữ liệu phải có khả năng tạo ra một bản sao của chính nó (thông qua copy constructor). Điều này cần thiết cho các thao tác như push_back(), insert(), assign() (copy assignment),...
Destructible: Kiểu dữ liệu phải có khả năng hủy (thông qua destructor). Điều này cần thiết để giải phóng bộ nhớ khi các phần tử bị xóa khỏi std::list.
MoveConstructible (từ C++11): Mặc dù không bắt buộc, nhưng nếu kiểu dữ liệu có move constructor, std::list có thể sử dụng nó để tối ưu hiệu suất trong các thao tác như push_back(), insert(), emplace_back(), emplace(), resize(), sort(), merge(), splice(), remove(), remove_if(), unique(), reverse(), assign() (move assignment).
MoveAssignable (từ C++11): Để tối ưu trong các thao tác sort(), merge(), splice(), remove(), remove_if(), unique(), reverse(), assign() (move assignment).
EqualityComparable (nếu sử dụng remove() hoặc unique()): Nếu bạn muốn sử dụng hàm remove() để xóa các phần tử có giá trị cụ thể, hoặc unique() (phiên bản không có binary predicate) để xóa các phần tử trùng lặp liên tiếp, kiểu dữ liệu phải hỗ trợ toán tử ==.
LessThanComparable (nếu sử dụng sort() hoặc merge()): Nếu bạn muốn sử dụng hàm sort() để sắp xếp các phần tử, hoặc merge() (phiên bản không có comparison function) để hợp nhất hai danh sách đã sắp xếp, kiểu dữ liệu phải hỗ trợ toán tử <.

lưu ý

Hầu hết các kiểu dữ liệu cơ bản và kiểu dữ liệu chuẩn trong C++ đều thỏa mãn các yêu cầu trên.
Đối với các kiểu dữ liệu do người dùng định nghĩa, bạn cần đảm bảo rằng chúng có đầy đủ các constructor, destructor và toán tử cần thiết (nếu sử dụng các hàm liên quan).
Nếu kiểu dữ liệu của bạn không thể đáp ứng các yêu cầu trên, bạn có thể phải sử dụng con trỏ (thông thường là smart pointers) để quản lý đối tượng một cách thủ công.

Các hàm thành viên


=	Gán nội dung của một std::list khác hoặc một danh sách khởi tạo cho std::list hiện tại.

Trình lặp (Iterators)


begin	Trả về một iterator trỏ đến phần tử đầu tiên trong list
end	Trả về một iterator trỏ đến vị trí sau phần tử cuối cùng trong std::list
rbegin	Trả về một reverse_iterator trỏ đến phần tử cuối cùng của std::list
rend	Trả về một reverse_iterator trỏ đến phần tử trước phần tử đầu tiên của std::list (theo thứ tự thông thường)
cbegin	Trả về một const_iterator trỏ đến phần tử đầu tiên của std::list
cend	Trả về một const_iterator trỏ đến vị trí sau phần tử cuối cùng trong std::list
crbegin	Trả về một const_reverse_iterator trỏ đến phần tử cuối cùng của std::list
crend	Trả về một const_reverse_iterator trỏ đến phần tử trước phần tử đầu tiên của std::list

Dung lượng (Capacity)


empty	Kiểm tra xem std::list có rỗng hay không, tức là không chứa bất kỳ phần tử nào
size	Trả về số lượng phần tử hiện có trong std::list
max_size	Trả về số lượng phần tử tối đa mà std::list có thể chứa

Truy cập phần tử


front	Trả về tham chiếu đến phần tử đầu tiên trong std::list
back	Trả về tham chiếu đến phần tử cuối cùng trong std::list

Thay đổi nội dung (Modifiers)


assign	Gán các phần tử mới cho std::list, thay thế nội dung hiện tại của nó
emplace_front	Xây dựng (construct) một phần tử mới trực tiếp tại đầu std::list
push_front	Thêm một phần tử mới vào đầu std::list
pop_front	Xóa phần tử đầu tiên của std::list
emplace_back	Xây dựng (construct) một phần tử mới trực tiếp tại cuối std::list
push_back	Thêm một phần tử mới vào cuối std::list
pop_back	Xóa phần tử cuối cùng của std::list
emplace	Xây dựng (construct) một phần tử mới trực tiếp tại một vị trí được chỉ định trong std::list
insert	Chèn một hoặc nhiều phần tử mới vào một vị trí cụ thể trong std::list
erase	Xóa một hoặc nhiều phần tử khỏi std::list tại một vị trí cụ thể hoặc trong một phạm vi
swap	Hoán đổi nội dung của hai std::list với nhau
resize	Thay đổi kích thước của std::list
clear	Xóa tất cả các phần tử khỏi std::list

Thao tác (Operations)


splice	Chuyển (transfer) các phần tử từ một std::list khác sang std::list hiện tại, tại một vị trí xác định
remove	Xóa tất cả các phần tử có giá trị bằng với một giá trị cho trước khỏi std::list
remove_if	Xóa tất cả các phần tử thỏa mãn một điều kiện cụ thể khỏi std::list
unique	Xóa các phần tử trùng lặp liên tiếp khỏi std::list
merge	Hợp nhất (merge) hai std::list đã được sắp xếp thành một std::list duy nhất
sort	Sắp xếp các phần tử trong std::list theo thứ tự tăng dần hoặc theo một tiêu chí so sánh tùy chỉnh
reverse	Đảo ngược thứ tự các phần tử trong std::list

Cấp phát (Allocator)


get_allocator	Trả về một bản sao của bộ cấp phát (allocator) được liên kết với std::list


Toán tử quan hệ	Các toán tử quan hệ trong std::list

Tham số​

T​

Alloc​

forward_list​

Đặc điểm​

Ví dụ:​

Các cách phổ biến khai báo và khởi tạo một std::list​

Khai báo một std::list rỗng:​

Khai báo và khởi tạo với số lượng phần tử ban đầu và giá trị mặc định:​

Khai báo và khởi tạo với initializer_list (từ C++11):​

Khai báo và khởi tạo bằng cách sử dụng iterator range (sao chép từ container khác):​

Khai báo và khởi tạo bằng cách sử dụng copy constructor:​

Khai báo và khởi tạo bằng cách sử dụng move constructor (từ C++11):​

Sử dụng assign() để gán giá trị sau khi khai báo:​

Các kiểu dữ liệu đặc biệt của std::list​

Con trỏ:​

Các kiểu dữ liệu chuẩn (Standard Library Types):​

Kiểu dữ liệu do người dùng định nghĩa (Classes and Structs):​

Smart Pointers (từ C++11):​

Yêu cầu đối với kiểu dữ liệu trong std::list:​

Các hàm thành viên​

Trình lặp (Iterators)​

Dung lượng (Capacity)​

Truy cập phần tử​

Thay đổi nội dung (Modifiers)​

Thao tác (Operations)​

Cấp phát (Allocator)​

Tham số

`T`

`Alloc`

`forward_list`

Đặc điểm

Ví dụ:

Các cách phổ biến khai báo và khởi tạo một std::list

Khai báo một std::list rỗng:

Khai báo và khởi tạo với số lượng phần tử ban đầu và giá trị mặc định:

Khai báo và khởi tạo với `initializer_list` (từ C++11):

Khai báo và khởi tạo bằng cách sử dụng iterator range (sao chép từ container khác):

Khai báo và khởi tạo bằng cách sử dụng copy constructor:

Khai báo và khởi tạo bằng cách sử dụng move constructor (từ C++11):

Sử dụng `assign()` để gán giá trị sau khi khai báo:

Các kiểu dữ liệu đặc biệt của std::list

Con trỏ:

Các kiểu dữ liệu chuẩn (Standard Library Types):

Kiểu dữ liệu do người dùng định nghĩa (Classes and Structs):

Smart Pointers (từ C++11):

Yêu cầu đối với kiểu dữ liệu trong std::list:

Các hàm thành viên

Trình lặp (Iterators)

Dung lượng (Capacity)

Truy cập phần tử

Thay đổi nội dung (Modifiers)

Thao tác (Operations)

Cấp phát (Allocator)