std::forward_list

#include <forward_list>

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

std::forward_list trong C++ (được giới thiệu từ C++11) là một container tuần tự (sequence container) cung cấp danh sách liên kết đơn (singly linked list). Nó cho phép chèn và xóa phần tử hiệu quả ở bất kỳ vị trí nào trong danh sách, nhưng chỉ cho phép duyệt theo một hướng (về phía trước).

Tham số

`T`

Kiểu dữ liệu của các phần tử trong forward_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 forward_list bạn muốn tạo.

Đặc điểm

Danh sách liên kết đơn: Mỗi phần tử trong std::forward_list chỉ trỏ đến phần tử tiếp theo, không có con trỏ đến phần tử phía trước.
Chèn/xóa hiệu quả: Việc chèn và xóa phần tử tại bất kỳ vị trí nào trong std::forward_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::forward_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 từ đầu để đến được phần tử mong muốn.
Chỉ duyệt theo một hướng: Bạn chỉ có thể duyệt std::forward_list theo một hướng từ đầu đến cuối, không thể duyệt ngược lại.
Kích thước không cố định: std::forward_list có thể thay đổi kích thước linh hoạt trong quá trình chạy.
Không có capacity(): std::forward_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.
size() không hiệu quả: std::forward_list không lưu trữ kích thước hiện tại, do đó việc lấy kích thước (ví dụ: bằng std::distance(list.begin(), list.end())) là một thao tác chậm, cần phải duyệt qua toàn bộ danh sách (O(n)).
Tiết kiệm bộ nhớ hơn std::list: Do chỉ sử dụng con trỏ đơn, std::forward_list sử dụng ít bộ nhớ hơn so với std::list (danh sách liên kết đôi).
Khi nào nên sử dụng std::forward_list:
- Khi bạn cần chèn và xóa phần tử thường xuyên, đặc biệt là ở giữa danh sách.
- Khi bạn không cần truy cập ngẫu nhiên các phần tử.
- Khi bạn muốn tiết kiệm bộ nhớ hơn so với std::list.
- Khi bạn chỉ cần duyệt danh sách theo một hướng.

Ví dụ:

#include <iostream>
#include <forward_list>
#include <string>
#include <algorithm>

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

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

  // 3. Chèn phần tử vào đầu forward_list
  list1.push_front(10);
  list1.push_front(20);
  list1.push_front(30);

  // 4. Truy cập phần tử đầu tiên
  std::cout << "list1.front(): " << list1.front() << '\n'; // Output: 30

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

  // 6. Chèn phần tử vào sau một vị trí
  auto it = list1.begin(); // it trỏ đến phần tử đầu tiên (20)
  list1.insert_after(it, 15); // Chèn 15 vào sau 20

  // 7. Xóa phần tử sau một vị trí
  it = list1.begin(); // it trỏ đến phần tử đầu tiên (20)
  list1.erase_after(it); // Xóa phần tử sau 20 (15)

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

  // 9. Kiểm tra forward_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
  }

  // 10. Lấy kích thước forward_list (phải duyệt qua toàn bộ danh sách)
  // std::distance(list1.begin(), list1.end())  // Nên dùng cách này
  // hoặc
  int count = 0;
  for (auto i = list1.begin(); i != list1.end(); ++i)
  {
      count++;
  }
  std::cout << "list1.size(): " << count << '\n'; // Output: list1.size(): 2

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

  // 12. Sắp xếp
  list2.sort();

  // 13. Đảo ngược
  list2.reverse();
  
  // 14. Xóa các phần tử trùng lặp liền kề
  std::forward_list<int> list3 = {1, 2, 2, 2, 3, 3, 2, 1, 1};
  list3.unique();

  // 15. Trộn 2 forward_list đã sắp xếp
  std::forward_list<int> list4 = {2, 4, 6};
  std::forward_list<int> list5 = {1, 3, 5};
  list4.merge(list5);

  // 16. Xóa các phần tử thỏa mãn điều kiện
  list4.remove_if([](int n){ return n > 4; }); // Xóa các số lớn hơn 4
  
  // 17. Xóa một giá trị cụ thể
  list4.remove(2); // Xóa các số có giá trị bằng 2

  return 0;
}

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

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

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

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

std::forward_list<int> list3 = {1, 2, 3, 4, 5};
std::forward_list<std::string> list4 = {"apple", "banana", "orange"};

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

std::forward_list<int> list5(5, 10); // 5 phần tử, giá trị là 10
std::forward_list<float> list6(3, 3.14f); // 3 phần tử, giá trị là 3.14f

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::forward_list<int> list7(vec.begin(), vec.end()); // Sao chép từ vector

std::array<int, 4> arr = {5,6,7,8};
std::forward_list<int> list9(arr.begin(), arr.begin()+2); // Sao chép 2 phần tử từ array

Khai báo và khởi tạo bằng cách sử dụng copy constructor (ít dùng với forward_list):

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

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

std::forward_list<int> list10;
list10.assign(3, 5);  // Gán 3 phần tử có giá trị là 5
list10.assign({1,2,3}); // Gán các giá trị từ initializer list
std::vector<int> vec2 = {9,8,7,6};
list10.assign(vec2.begin()+1, vec2.end()-1); // Gán các giá trị vec2

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

lưu ý

Ngoài các kiểu dữ liệu cơ bản như int, float, double, ..., std::forward_list có thể chứa bất kỳ kiểu dữ liệu nào thỏa mãn các yêu cầu sau:

Có thể sao chép (Copyable): Kiểu dữ liệu phải có copy constructor hoặc move constructor để std::forward_list có thể tạo bản sao của các phần tử khi cần thiết (ví dụ: khi insert_after() với tham số giá trị const value_type&).
Có thể hủy (Destructible): Kiểu dữ liệu phải có destructor để std::forward_list có thể giải phóng bộ nhớ khi các phần tử bị xóa.
Có thể so sánh bằng (nếu sử dụng các hàm như sort(), unique(), merge(), remove()): Nếu bạn muốn sử dụng các hàm như sort(), unique(), merge(), remove(), kiểu dữ liệu cần phải hỗ trợ các toán tử so sánh (<, >, ==, !=, <=, >=) hoặc bạn cần cung cấp hàm so sánh tùy chỉnh.

Con trỏ: int*, char*, MyClass*,...

Mặc dù std::forward_list có thể chứa con trỏ, bạn cần phải tự quản lý việc cấp phát và giải phóng bộ nhớ cho các đối tượng được trỏ đến để tránh rò rỉ bộ nhớ.
Các kiểu dữ liệu chuẩn:
- std::string
- std::vector
- std::deque
- std::array
- std::list
- ...

Các kiểu dữ liệu do người dùng định nghĩa (Classes và Structs):

class MyClass {
public:
     int data;
     std::string name;
     MyClass(int d, const std::string& n) : data(d), name(n) {}

     // Cần thiết cho các hàm như sort(), unique(),...
     bool operator<(const MyClass& other) const {
         return data < other.data;
     }
};

struct Point {
     int x;
     int y;
};

int main() {
     std::forward_list<MyClass> list1;
     list1.emplace_front(10, "Object 1");
     list1.emplace_front(20, "Object 2");

     std::forward_list<Point> list2;
     list2.emplace_front(Point{1,2});
     list2.push_front(Point{3,4});

     return 0;
}

Các container std::forward_list lồng nhau:

std::forward_list<std::forward_list<int>> nestedList;
nestedList.push_front({1,2,3});
nestedList.emplace_front(std::initializer_list<int>{4,5,6,7});

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


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

Trình lặp (Iterators)


before_begin	Trả về một iterator trỏ đến vị trí trước phần tử đầu tiên trong forward_list
begin	Trả về một iterator trỏ đến phần tử đầu tiên trong forward_list
end	Trả về một iterator trỏ đến vị trí sau phần tử cuối cùng trong forward_list
cbefore_begin	Trả về một const_iterator trỏ đến vị trí trước phần tử đầu tiên trong forward_list
cbegin	Trả về một const_iterator trỏ đến phần tử đầu tiên trong forward_list
cend	Trả về một const_iterator trỏ đến vị trí sau phần tử cuối cùng trong forward_list

Dung lượng (Capacity)


empty	Kiểm tra xem forward_list có rỗng hay không
max_size	Trả về số lượng phần tử tối đa mà forward_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 forward_list

Thay đổi nội dung (Modifiers)


assign	Gán các phần tử mới cho forward_list, thay thế nội dung hiện tại của nó
emplace_front	Xây dựng một phần tử mới trực tiếp tại đầu forward_list
push_front	Thêm một phần tử mới vào đầu forward_list
pop_front	Xóa phần tử đầu tiên của forward_list
emplace_after	Xây dựng một phần tử mới trực tiếp vào vị trí sau một iterator cho trước trong forward_list
insert_after	Chèn một hoặc nhiều phần tử mới vào sau một vị trí iterator cho trước trong forward_list
erase_after	Xóa một hoặc nhiều phần tử khỏi forward_list tại vị trí sau một iterator cho trước
swap	Hoán đổi nội dung của hai forward_list với nhau
resize	Thay đổi kích thước của forward_list
clear	Xóa tất cả các phần tử khỏi forward_list, làm cho forward_list trở thành rỗng

Thao tác (Operations)


splice_after	Chuyển (transfer) các phần tử từ một forward_list khác hoặc từ một phạm vi trong forward_list khác sang forward_list hiện tại
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 forward_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 forward_list
unique	Xóa các phần tử trùng lặp liên tiếp khỏi forward_list
merge	Hợp nhất (merge) hai forward_list đã được sắp xếp thành một forward_list duy nhất
sort	Sắp xếp các phần tử trong forward_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 forward_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 forward_list


Toán tử quan hệ	Các toán tử quan hệ trong forward_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::forward_list​

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

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

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

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 (ít dùng với forward_list):​

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::forward_list​

Con trỏ: int*, char*, MyClass*,...​

Các kiểu dữ liệu chuẩn:​

Các kiểu dữ liệu do người dùng định nghĩa (Classes và Structs):​

Các container std::forward_list lồng nhau:​

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)​