Search…

STL - List Trong C++

Trung NguyễnTrung Nguyễn
17/09/20206 min read
Tìm hiểu về STL, viết tắt của cụm từ Standard Template Library, bộ thư viện chuẩn của C++.

STL là gì?

STL là viết tắt của cụm từ Standard Template Library, là bộ thư viện chuẩn của C++,  STL cung cấp các lớp cài đặt sẵn, cho phép thao tác với các kiểu dữ liệu cơ bản cũng như các kiểu dữ liệu tự định nghĩa, việc thành thạo sử dụng thư viện STL sẽ giúp tiếp kiệm thời gian trong lập trình.  

List là gì?

List là một danh sách chứa các đối tượng (các nút (node) – lưu trữ các thông tin dữ liệu và địa chỉ của nút kế tiếp, nút trước đó) liên kết với nhau và cho phép chèn thêm hay xóa bất kì một đối tượng nào trong danh sách. Là một cấu trúc dữ liệu cơ bản để biết thêm tham khảo tại danh sách liên kết đơn.

Cách sử dụng

LƯU Ý : kiểu dữ liệu List là một trong các kiểu dữ liệu mà thư viện STL hỗ trợ, phải include thư viện tương ứng để sử dụng loại dữ liệu mong muốn. Đồng thời phải sử dụng namespace STD để có thể sử dụng code của thư viện này. Để biết thêm về namespace.

Đối với các biến tĩnh cú pháp khai báo như sau:

list<kiểu dữ liệu> TênBiến;

Ví dụ:

list<int> myIntList;

Một số constructor đã được định nghĩa sẵn như:

// default constructor
list<int> myList;

// fill constructor
// myList1 được khởi tạo chứa 4 phần tử có giá trị 50
list<int> myList1(4, 50);

// copy constructor
//tạo một list mới có 4 phần tử và đều có giá trị là 100
list<int> myList(4, 100);
//tạo một list mới với các phần tử và giá trị được chép từ myList vào
list<int> copyMyList(myList);
...

Là một danh sách liên kết bao gồm các thao tác push_back() (thêm phần tử vào vị trí cuối của list) và push_font() (thêm phần tử vào vị trí đầu của list)

//create list with value 10 10 10 10
list<int> myList(4, 10);

//add new Node have value of 5 to the after last Node of the List
myList.push_back(5);

//add new Node have value of 5 to the before first Node of the List
myList.push_front(6);
    
// result 6 10 10 10 10 5

Còn có các hàm xóa một đối tượng trong danh sách pop_back() (xóa vị trí cuối cùng) hay pop_font() (xóa vị trí đầu tiên)

Ví dụ:

//100 100 100 100
list<int> myList (4, 100);

mylist.pop_back();
mylist.pop_front();
// result 100 100

Hoặc xóa một vị trí bất kì trong danh sách(hàm có dạng)

iterator erase (iterator position);

hoặc xóa một vùng trong danh sách

iterator erase (iterator first, iterator last);

Ngoài ra còn có thể xóa một đối tượng có giá trị xác định

void remove (const value_type& val);

Ví dụ:

list<int> myList;
//một vòng lập từ 0 tới 9 và thêm vào cuối cùng của list giá trị tương ứng
for(int i = 0; i < 10; i++)
	myList.push_back(i);

list<int> list1(myList);	// => list1 = [0,1,2,3,4,5,6,7,8,9]

//position ở đây truy cập vị trí đầu tiên của mylist và tăng lên tới vị trí thứ 2
list<int>::iterator position = myList.begin();
position++;

myList.erase(position);		// => mylist = [0,2,3,4,5,6,7,8,9]

// position truy cập phần tử đầu tiên list1
position = list1.begin();

// position1 truy cập phần tử đầu tiên của list1 
list<int>::iterator position1 = list1.begin();
//tăng con trỏ để con trỏ position1 có thể trỏ tới phần tử thứ 4 so với vị trí đầu tiên của list
position1++;
position1++;
position1++;
position1++;

// xóa phần tử từ vị trí đầu tới vị trí thứ 4 so vo với vị trí đầu
list1.erase(position, position1);	// => list1 = {4,5,6,7,8,9}

// Thêm 1 phần tử có giá trị 9 vào cuối list
list1.push_back(9);		// => list1 = {0,4,5,6,7,8,9}
list1.remove(9); // => list1 = {0,4,5,6,7,8}

Truy cập đến vị trí đầu tiên của danh sách thông qua hàm begin() hoặc rend()và truy cập đến phần tử cuối cùng danh sách qua hàm end() hoặc rbegin()

list<int> l;
l.push_back(1);
l.push_back(2);
l.push_back(3);    
//truy cập tới vị trí cuối của list
cout << *l.rbegin();  // Output: 3

Để xóa hết danh sách, có thể dùng hàm clear()

list<int> l;
l.push_back(1);
l.push_back(2);
l.push_back(3);
l.clear();// => l = {}

Chèn vào một danh sách có thể dùng hàm:

iterator insert (iterator position, const value_type& val);

Tức là chèn giá trị “val” vào danh sách từ vị trí “position” 

Ngoài ra còn có hàm sau:

void insert (iterator position, size_type n, const value_type& val);

Nghĩa là chèn vào danh sách “n” phần tử có giá trị “val” từ vị trí “position

Hoặc chèn một danh sách từ vị trí “first” đến vị trí “last” vào một danh sách từ vị trí “position

void insert (iterator position, InputIterator first, InputIterator last);

Ví dụ:

list<int> myList(4, 10);
//thêm vào myList 5 phần tử có đều có giá trị là 1 bắt đầu từ đầu của myList
myList.insert(myList.begin(), 5, 1);
// => myList = [1,1,1,1,1,10,10,10,10]

list<int> list1(4, 100);// 100 100 100 100
list<int> l;// 1 2 3
l.push_back(1);
l.push_back(2);
l.push_back(3);

//từ l copy các dữ liệu từ đầu cho tới cuối l vào đầu list1
list1.insert(list1.begin(), l.begin(), l.end());
// => list1 = [1,2,3,100,100,100,100]

list<int> list2(4, 10);
list2.push_back(5);
list2.push_front(6);
//thêm vào đầu list2 một phần tử có giá trị là 10
list2.insert(list2.begin(), 10);
// => mylist = [10,6,10,10,10,10,5]

Ngoài ra có thể kiểm tra xem danh sách có rỗng hay không thông qua hàm empty() nếu rỗng trả về true và ngược lại

list<int> mylist;
for (int i = 1; i <= 10; ++i)
	mylist.push_back(i);

int sum = 0;
while (!mylist.empty())
{
	sum += mylist.front();
	mylist.pop_front();
}
// => sum = 55

Hoặc trả về kích thước của danh sách thông qua hàm size()

list<int> myints;
for(int i = 0; i < 10; i++) 
	myints.push_back(i);

cout << "1. size: " << myints.size() << '\n';

Còn có thể sắp xếp danh sách qua hàm sort()

l.push_back(1);
l.push_back(5);
l.push_back(3);
l.push_back(2);
l.push_back(7);
l.sort(); // 1 2 3 5 7

Nhưng hàm merge() sau khi trộn 2 list lại sẽ tự động sort 

std::list<double> first, second;
first.push_back (3.1);
first.push_back (2.2);
first.push_back (2.9);

second.push_back (3.7);
second.push_back (7.1);
second.push_back (1.4);

first.sort();
second.sort();

first.merge(second); // 1.4  2.2  2.9  3.1  3.7  7.1

Từ đầu bài viết đã có sử dụng tới iterator để truy cập vào các phần tử trong list vậy iterator là gì.

list<double> first;

first.push_back (3.1);
first.push_back (2.2);
first.push_back (2.9);

list<double>::iterator value = first.begin() // *value will be 3.1
value++; // *value will be 2.2

Lưu ý iterator thực chất cũng là một con trỏ. Lưu lại địa chỉ của các phần tử Node trong list STL đã đặt tên là iterator và biến nó thành một đối tượng và biến nó thành một đối tượng dùng để duyệt qua một list, vector, ... để có thể làm việc một cách trực quan nhất.

Ưu điểm và nhược điểm của "list"

Việc sử dụng thành thạo các hàm trong “list” nói chung hoặc danh sách “list” nói riêng sẽ giúp ích rất nhiều về vấn đề quản lý, có thể là quản lý một danh sách thông tin nào đó, với các hàm đã được hỗ trợ viết sẵn sẽ giúp dễ dàng cập nhật và sửa chữa. List hỗ trợ vòng lặp 2 chiều, nhưng lại không thể truy cập ngẫu nhiên như các mảng thông thường vì vậy mà việc tìm kiếm một phần tử trong danh sách sẽ rất chậm, lí do từ việc cấu trúc của List được xây dựng tương tự danh sách liên kết đơn.

IO Stream

IO Stream Co., Ltd

developer@iostream.co
383/1 Quang Trung, ward 10, Go Vap district, Ho Chi Minh city
Business license number: 0311563559 issued by the Department of Planning and Investment of Ho Chi Minh City on February 23, 2012

©IO Stream, 2013 - 2024