forward_list trong C++ là gì | Laptrinhcanban.com

HOME › lập trình c++ cơ bản dành cho người mới học lập trình>>21. forward_list trong c++

forward_list trong C++ là gì


Cùng tìm hiểu về kiểu forward_list trong C++. Bạn sẽ biết khái niệm forward_list trong c++ là gì, cách khai báo forward_list trong C++, cách khởi tạo forward_list trong C++, cách truy cập phần tử của forward_list, cũng như sự khác biệt giữa list và forward_list trong C++ sau bài học này.

forward_list trong c++ là gì

forward_list trong C++ là một danh sách liên kết đơn được sử dụng làm tiêu chuẩn để xử lý các đối tượng chứa nhiều phần tử trong C++.

Danh sách liên kết một chiều ở đây có nghĩa là từng Node trong danh sách sẽ chứa con trỏ chỉ đến vị trí của Node đứng sau nó, nên việc xác định vị trí của một Node trong danh sách sẽ trở nên dễ dàng hơn với độ phức tạp của thuật toán sẽ là O(1) mà thôi.

Khác với list trong C++ thì forward_list do không chứa con trỏ chỉ đến vị trí của Node đứng trước nó, nên sẽ giúp tiết kiệm bộ nhớ để lưu trữ hơn.

Lại nữa, không hiểu vì lý do gì mà trong forward_list lại không tồn tại hàm thành viên size() như list, nên để lấy kích thước của forward_list thì chúng ta phải dùng tới template function là std::distance().

So với vector, array hay deque thì forward_list và list có tốc độ thêm xóa phần tử ngẫu nhiên nhanh hơn , nhưng bù lại thì tốc độ truy cập ngẫu nhiên cũng vì thế mà chậm hơn.

LoạiTruy cập ngẫu nhiênThêm xóa ngẫu nhiên
vector, array, dequeO(1)O(N)
orward_list, listO(N)O(1)

Cấu trúc dữ liệu của forward_list trong C++

Cấu trúc dữ liệu của forward_list trong C++ như hình sau:

Cấu trúc dữ liệu của forward_list trong C++

Khác với vector với các phần tử được lưu trong một mảng động thì phần tử trong list và forward_list lại được lưu trong các phân vùng bộ nhớ độc lập được gọi là Node. Và những node này được liên kết tuần tự với nhau thông qua con trỏ của chúng.

Với list, mỗi node sẽ lưu trữ các con trỏ của cả các node trước và sau node hiện tại, trong khi với forward_list, chỉ có con trỏ chỉ tới node sau node hiện tại được lưu giữ mà thôi.

Vì thế, forward_list còn được gọi là danh sách liên kết đơn trong C++.

std::forward_list trong C++

std::forward_list trong C++ là một thư viện chuẩn được sử dụng làm tiêu chuẩn để xử lý danh sách liên kết đơn trong C++.

std::forward_list được cài sẵn trong header file forward_list và để sử dụng được chức năng này, chúng ta cần thêm dòng 「#include <forward_list> 」 vào đầu chương trình.

#include <forward_list>   
int main()
{
    std::forward_list<int> lst1; 
    std::forward_list<double> lst2;  
}

Lại nữa, namespace của std::forward_list là std, do đó bằng cách khai báo sử dụng namespace này vào đầu chương trình mà chúng ta có thể viết gọn std::forward_list trong chương trình như sau:

#include <forward_list>   
using namespace std;
int main()
{
   forward_list<int> lst1;
   forward_list<double> lst2;
}

Khai báo forward_list trong C++

Khai báo 1 forward_list trong C++

Để khai báo forward_list trong C++, chúng ta viết dòng std::forward_list, sau đó viết kiểu dữ liệu giữa cặp dấu <>, và cuối cùng là tên biến như sau:

std::forward_list<type> f_lst;

Trong đó f_lst là tên biến forward_list và type là kiểu dữ liệu. Chúng ta có thể dùng bất cứ kiểu dữ liệu nào có trong C++ để khai báo type, ví dụ như char, int, double, hay cấu trúc hoặc class tự tạo chẳng hạn.

Trong trường hợp đã khai báo namespace std vào đầu chương trình, chúng ta cũng có thể lược bỏ dòng std:: và dùng cú pháp khai báo forward_list như sau:

using namespace std;
forward_list<type> f_lst;

Thông thường chúng ta hay khai báo namespace std vào đầu chương trình để sử dụng tới các chức năng thông dụng khác như nhập xuất chẳng hạn, nên trong 2 phương pháp khai báo forward_list ở trên thì phương pháp thứ 2 thường được sử dụng nhiều hơn.

Lưu ý forward_list được khai báo với cú pháp này sẽ có 0 phần tử bên trong nó. Sau khi khai báo forward_list kiểu này, chúng ta có thể sử dụng các hàm thành viên để có thể thêm phần tử vào nó sau này.

Ví dụ cụ thể:

#include <iostream>
#include <forward_list>   
using namespace std;

int main()
{
    forward_list<double> name; //Khai báo forward_list name kiểu double
    forward_list<int> age;     //Khai báo forward_list age kiểu int
}

Ngoài ra cách viết sử dụng cặp dấu <> như trên được viết theo cú pháp khi sử dụng chức năng template của C++ mà chúng ta sẽ cùng học trong các chuyên đề sau.

Khai báo forward_list trong C++ bao gồm chỉ định số phần tử

Mặc dù kiểu forward_list trong C++ là loại mảng động có khả năng tự thay đổi kích thước, tuy nhiên trong trường hợp không chỉ định rõ kích thước của nó, thì việc xử lý nó trong chương trình sẽ tiêu tốn thời gian nhiều hơn so với khi biết kích thước cụ thể của nó.

Bởi vậy nếu đã biết kích thước trước của một forward_list, chúng ta nên chỉ định độ dài (số phần tử) khi khai báo nó, với cú pháp sau đây:

std::forward_list<type> f_lst(length);

Trong đó length chính là độ dài(số phần tử() của forward_list cần tạo.

Với cách khai báo forward_list này thì các phần tử trong forward_list sẽ được gán giá trị mặc định tùy thuộc vào kiểu dữ liệu sử dụng.

Ví dụ, nếu dùng kiểu số như int, double thì các phần tử sẽ có giá trị mặc định bằng 0 như sau:

/*Khai báo forward_list f_lst kiểu số*/
std::forward_list<int> lst1(3);    //{0, 0, 0}
std::forward_list<double> lst2(3); //{0, 0, 0}

Tuy nhiên nếu dùng kiểu chữ như char, string thì các phần tử sẽ có giá trị mặc định bằng Null được biểu diễn bởi trống khi in ra màn hình như sau:

/*Khai báo forward_list f_lst kiểu chữ*/
std::forward_list<char> lst1(3)   //{, , }
std::forward_list<string> lst2(3) //{, , }

Khai báo đồng thời nhiều forward_list trong C++

Trong trường hợp cần khai báo đồng thời nhiều forward_list trong C++, chúng ta viết các tên các biến cách nhau bởi dấu phẩy vào đằng sau std::forward_list với cú pháp sau đây:

using namespace std;
forward_list<type> name1, name2, name3, ... ;

Ví dụ cụ thể:

#include <iostream>
#include <forward_list>   
using namespace std;

int main()
{
    forward_list<string> name, job, sex;
    forward_list<int> age;
}

Khởi tạo forward_list trong C++

Khởi tạo forward_list trong C++ với các phần tử riêng biệt

Ngoài cách khai báo rồi gán giá trị cho forward_list thì chúng ta cũng có thể khởi tạo forward_list và gán luôn giá trị ban đầu cho biến forward_list đó.

Chúng ta khởi tạo forward_list trong C++ cách sử dụng cặp dấu ngoặc {} với cú pháp sau đây:

std::forward_list<type> f_lst {value1, value2, value3, ...};

Trong đó

  • type là kiểu dữ liệu
  • f_lst là tên biến forward_list
  • value là các giá trị của forward_list

Ví dụ:

std::forward_list<string> user{"Kiyoshi", "male", "Tokyo"};
//{"Kiyoshi", "male", "Tokyo"}

Khởi tạo forward_list trong C++ với các phần tử giống nhau

Chúng ta cũng có thể khởi tạo forward_list với các phần tử có giá trị giống nhau, với cú pháp sau đây:

std::forward_list<type> f_lst(length, value);

Trong đó length là số phần tử(độ dài), và value là giá trị sử dụng để khai báo đồng loạt các phần tử của forward_list cần tạo.

Ví dụ:

//Khởi tạo forward_list f_lst kiểu int gồm 5 phần tử có giá trị bằng 8
std::forward_list<int> f_lst(5, 8); //{8, 8, 8, 8, 8}

Khai báo forward_list 2 chiều trong C++

Giống như mảng thì chúng ta cũng có thể sử dụng forward_list đa chiều trong C++, và loại forward_list đa chiều hay được sử dụng đó chính là forward_list 2 chiều trong C++.

Để khai báo forward_list 2 chiều trong C++ cũng như các loại forward_list đa chiều khác, chúng ta sử dụng tới cú pháp sau đây:

using namespace std;
forward_list<forward_list<type> > f_lst {l1, l2, l3, ...};

Trong đó:

  • f_lst là tên biến forward_list 2 chiều
  • l là các forward_list 1 chiều được sử dụng như phần tử của forward_list 2 chiều

Lưu ý, chúng ta cần phải viết thêm dấu cách giữa cặp dấu > > khi khai báo forward_list 2 chiều. Lý do là để phân biệt với toán tử >> được sử dụng để dịch chuyển bit trong C++.

Ví dụ cụ thể:

#include <iostream>
#include <forward_list>   
using namespace std;

int main()
{
    /*Khai báo forward_list 2 chiều*/
    forward_list<forward_list<string> > all_user{ 
        {"Kiyoshi", "male", "Hanoi"}, 
        {"Honda", "male", "Tokyo"}, 
        {"Ajinomoto", "female", "Osaka"}};
    return 0;
}

Chúng ta cũng có thể khởi tạo các forward_list 1 chiều trước rồi dùng chúng để khai báo forward_list 2 chiều như sau:

#include <iostream>
#include <forward_list>   
using namespace std;

int main()
{
    /*Khởi tạo các forward_list 1 chiều làm phần tử trong forward_list 2 chiều*/
    forward_list<string> user1{"Kiyoshi", "male", "Hanoi"};
    forward_list<string> user2{"Honda", "male", "Tokyo"};
    forward_list<string> user3{"Ajinomoto", "female", "Osaka"};

    /*Khai báo forward_list 2 chiều*/
    forward_list<forward_list<string> > all_user{ user1, user2, user3};
    return 0;
}

Truy cập phần tử trong forward_list C++

Khác với vector hay mảng, chúng ta không thể truy cập ngẫu nhiên vào phần tử bất kỳ trong một forward_list. Do đó chúng ta cũng không thể sử dụng index của các phần tử để truy cập vào nó theo cách thông thường được.

Ví dụ nếu dùng index để truy cập vào vị trí ngẫu nhiên trong forward_list thì lỗi sẽ trả về như sau:

forward_list<string> user{"Kiyoshi", "male", "Tokyo"};

cout << user[1];

//main.cpp:9:13: error: no match for ‘operator[]’

Thay vào đó, chúng ta cần phải tiến hành truy cập tuần tự vào các phần tử của forward_list, thông qua vòng lặp hoặc là trình lặp mà Kiyoshi đã giới thiệu trong bài Duyệt forward_list trong C++.

Ví dụ, chúng ta có thể truy cập vào phần tử của forward_list 1 chiều thông qua vòng lặp dựa trên phạm vi như sau:

#include <iostream>
#include <forward_list>   
using namespace std;

int main()
{
    forward_list<string> user{"Kiyoshi", "male", "Tokyo"};
    
    for (string x: user) {
        cout << x << endl;
    }
    return 0;
}

Kết quả:

Kiyoshi
male
Tokyo

Tượng tự khi chúng ta cần truy cập vào phần tử trong forward_list 2 chiều trong C++:

#include <iostream>
#include <forward_list>   
using namespace std;

int main()
{
    /*Khởi tạo các forward_list 1 chiều làm phần tử trong forward_list 2 chiều*/
    forward_list<string> user1{"Kiyoshi", "male", "Hanoi"};
    forward_list<string> user2{"Honda", "male", "Tokyo"};
    forward_list<string> user3{"Ajinomoto", "female", "Osaka"};

    /*Khai báo forward_list 2 chiều*/
    forward_list<forward_list<string> > all_user{ user1, user2, user3};


    for (auto x: all_user) {
        for (auto y: x) {
            cout << y << endl;
        }
    }

    return 0;
}

Và kết quả:

Honda
male
Tokyo
Ajinomoto
female
Osaka

List vs forward_list trong C++

Như đã phân tích ở trên thì sự khác biệt lớn nhất giữa list và forward_list trong C++ đó chính là list là danh sách liên kết hai chiều, còn forward_list là danh sách liên kết đơn mà thôi.

Điều đó có nghĩa các node trong list chứa thông tin con trỏ của cả các node trước và sau nó, trong khi đối với forward_list thì chỉ chứa thông tin con trỏ sau nó mà thôi.

Điều đó cũng có nghĩa là phân vùng bộ nhớ sử dụng cho forward_list sẽ ít hơn list, kéo theo việc sử dụng bộ nhớ sẽ hiệu quả hơn.

Do vậy, ngoài các trường hợp cần chú ý tới vùng bộ nhớ dùng để lưu giữ thì thông thường chúng ta sử dụng list để xử lý các danh sách trong C++.

Tổng kết

Trên đây Kiyoshi đã hướng dẫn bạn về forward_list trong C++ rồi. Để nắm rõ nội dung bài học hơn, bạn hãy thực hành viết lại các ví dụ của ngày hôm nay nhé.

Và hãy cùng tìm hiểu những kiến thức sâu hơn về C++ trong các bài học tiếp theo.

URL Link

https://laptrinhcanban.com/cpp/lap-trinh-cpp-co-ban/forward-list-trong-cpp/forward_list-trong-cpp-la-gi/

Hãy chia sẻ và cùng lan tỏa kiến thức lập trình Nhật Bản tại Việt Nam!

HOME  › lập trình c++ cơ bản dành cho người mới học lập trình>>21. forward_list trong c++

Profile
きよしです！笑

Tác giả : Kiyoshi (Chis Thanh)

Kiyoshi là một cựu du học sinh tại Nhật Bản. Sau khi tốt nghiệp đại học Toyama năm 2017, Kiyoshi hiện đang làm BrSE tại Tokyo, Nhật Bản.