[Tutorial] Thư viện STL trong C++ : List

Giới thiệu về list:

List trong thư viện STL chính là danh sách liên kết kép: Mỗi phần tử trong list có liên kết đến một phần tử trước nó và một phần tử phía sau nó.

Do đó, list có các ưu điểm đó là chèn và loại bỏ phần tử ở bất cứ vị trí nào trong container với độ phức tạp O(1).

Điểm yếu của list là khả năng truy cập tới phần tử thông qua vị trí với độ phức tạp O(n).

Cách khai báo list:

Để sử dụng list, ta cần khai báo thư viện :

Ví dụ 1: Khai báo list 1  có dữ liệu kiểu int có tên là firstList:

Ví dụ 2: Tạo vector có 4 phần tử int và 4 phần tử này đều có giá trị 100 có tên là secondList:

Ví dụ 3: Khai báo một list kiểu int có tên là thirdList sao chép từ đầu đến cuối secondList:

Lưu ý: begin(), end() là các phương thức cung cấp sẵn của đối tượng list dùng để truy xuất phần tử đấu tiên và cuối cùng của list.

Ví dụ 4: Tạo list kiểu int tiên là fourList và sao chép tất cả phần tử  thirdList

Nhận xét:

Khai báo ở ví dụ 4 có chức năng tương tự như ví dụ 3 nhưng đơn giản hơn.

Các phương thức thành viên:

Capacity:
size() Trả về số lượng phần tử của list
empty() Trả về true(1) nếu list rỗng, ngược lại là false (0)
Element access:
front() Truy xuất phần tử đầu tiên của list
back() Truy xuất phần tử cuối cùng của list
Modifier:
push_back(const x) Thêm phần tử có giá trị x vào cuối list
push_front(const x) Thêm phần tử có giá trị x vào đầu list
pop_back() Loại bỏ phần tử cuối ra khỏi list
pop_front() Loại bỏ phần tử đầu ra khỏi list
insert (iterator positon,const x) Chèn x vào trước vị trí position (x có thể là phần tử hay iterator của một đoạn phần tử).
insert (iterator positon,const x) Chèn phần tử có giá trị x vào trước vị trí position.
insert (iterator positon,int n, const x) Chèn n phần tử có giá trị x vào trước vị trí position.
erase(iterator position) Xóa phần tử ở vị trí position ra khỏi list
swap(list L) Hoán đổi các phần tử của list hiện hành và list L
clear() Xóa list
Operations
splice (iterator positon,list& other) Ghép list other vào vị trí position của list hiện hành, sau khi nối ghép, list other không còn phần tử nào.
splice (iterator positon,list& other, iterator first, iterator last) Ghép các phần tử trong nửa khoảng [first,last) của list other và list hiện hành. Sau khi ghép nối, list other chỉ còn lại các phần tử trong nửa đoạn [ last, L.end() )
splice (iterator positon, list& other, iterator it ): Ghép phần tử có vị trí là it của list other vào vị trí position của list hiện hành. Sau khi ghép nối, list other bị mất đi phần tử ở vị trí it.
remove (const val) Loại bỏ tất cả phần tử có giả trị bằng val trong list.
remove_if (predicate pred) Loại bỏ tất các phần tử trong list nếu
pred return true.Biểu thức predicate pred có thể là một hàm (function) trả về giá trị bool hoặc một class.
sort() Sắp xếp các phần tử của list theo chiều tăng dần.
sort (compare comp) Sắp xếp các phần tử của list tăng dần theo tiêu chí so sánh comp. Biểu thức compare comp có thể là một hàm trả về giá trị bool.
reverse() Đảo ngược lại các phần tử của list.
unique() Loại bỏ các phần tử thích hợp sao cho các phần tử còn lại trong list chỉ xuất hiện đúng duy nhất 1 lần.
unique (BinaryPredicate binary_pred); Loại bỏ các phần tử thích hợp sao cho các phần tử còn lại trong list chỉ xuất hiện đúng duy nhất 1 lần theo tiêu chí nào đó của hàm binary_pred. Biểu thức binary_pred có thể là hàm (function) hoặc lớp (class).Lưu ý: Các phần tử trong list phải được sắp xếp.
merge (list& L)  Ghép list L vào sau vị trí cuối cùng list hiện hành. Sau khi ghép nối, list L không còn phần tử nào.
merge (list& L, Compare comp) Ghép các phần tử của list L vào list hiện hành với vị trí dựa theo biểu thức comp. Biểu thức comp là một hàm trả về giá trị bool.

Capacity:

size()

Trả về số lượng phần tử của list.

Ví dụ: Tạo một list  có kích thước là 10 và in ra số lượng phần tử của list này.

empty()

Trả về true(1) nếu list rỗng, ngược lại là false (0)

Ví dụ: Kiểm tra list có rỗng không và  in ra thông báo tương ứng.

Element access:

front()

Truy xuất phần tử đầu tiên của list. Truy xuất ở đây bao gồm in hoặc chỉnh sửa giá trị.

Ví dụ: Tạo list có 5 phần tử có giá trị lần lượt là a,b,c,d,e. Thay đổi phẩn tử đầu tiền thành ‘A’ và in ra kết quả.

back()

Truy xuất phần tử cuối cùng của list. Truy xuất ở đây bao gồm in hoặc chỉnh sửa giá trị.

Ví dụ: Tạo list có 5 phần tử có giá trị lần lượt là  A,B,C,D,E. Thay đổi phẩn tử cuối cùng thành ‘e’ và in ra kết quả.

Modifier:

push_back(const x)

Thêm phần tử có giá trị x vào cuối list.

Phương thức push_back(x) thường dùng để khởi tạo list một cách “động”, có nghĩa là kích thước list chưa xác định trước.

queue-push_back

Ví dụ:

Viết chương trình cho người dùng nhập vào kích thước list và nhập vào giá trị các phần tử. Lưu trữ các phần tử theo đúng thứ tự đã nhập. In ra các phần tử trong list.

Lưu ý: để in tất các phần tử trong list, ta dùng vòng lặp for với biến là iterator. Ta không thể dùng toán tử dấu ngoặc vuông “[ ]” như vector. Ví dụ, sử dụng truy xuất list như bên dưới là sai:

push_front(const x):

Thêm phần tử có giá trị x vào đầu list.

deque - push_font

Ví dụ: Khởi tạo list có các phần tử là kí tự lần lượt theo thứ tự là ‘B’,’C’,’D’,’E’. Thêm phần tử ‘A’ vào đầu danh sách. In các phần tử theo đúng thứ tự lưu trữ.

 

pop_back()

Loại bỏ phần tử cuối cùng ra khỏi list.

 

deque-pop_back

Ví dụ: Viết chương trình cho người dùng nhập vào kích thước list và nhập vào giá trị các phần tử. Sau đó, loại bỏ đi một nửa các phần tử ở cuối list.  In ra các phần tử trong list.

pop_front()

Loại bỏ phần tử đầu tiên ra khỏi list.

deque-pop_front

Ví dụ: Tạo danh sách có 5 phần tử lần lượt theo thứ tự là ‘a’,’b’,’c’,’d’,’e’. Loại bỏ phần tử đâu tiên ra khỏi list và in ra màn hình các phần tử còn lại.

insert

insert có thể dùng với 3 cách sau:

insert (iterator positon,const x): Chèn phần tử có giá trị x vào trước vị trí position.

insert (iterator positon,int n, const x): Chèn n phần tử có giá trị x vào trước vị trí position.

insert (iterator positon,iterator a, itertator b): Chèn vào trước vị trí position của list hiện hành tất cả các phần tử trong nửa khoảng [a,b) của một list khác.

Ví dụ 1: Tạo list có 5 phần tử đều có giá trị là 100. Chèn phần tử có giá trị 200 vào vị trí đầu tiên của list.

Lưu ý: Ta phải dùng lệnh it++ để tăng biến iterator it lên 1 đơn vị rồi sau đó mới dùng lệnh: myList.insert(it,200) để  chèn vào vị trí thứ 2. Ta không thể dùng lệnh myList.insert(it+1,200)  như đối với vector vì list không thể truy cập phần tử qua toán tử dấu ngoặc vuông “[]”.

Ví dụ 2: Tạo list có 5 phần tử đều có giá trị là 100. Chèn 2 phần tử có giá trị 200 vào vị trí thứ 3  của list.

 

Chú ý: Ta dùng lệnh advance(it,2) để tăng it lên 2 đơn vị.

void advance (iterator& it, int n) là phương thức con của đối tượng iterator và chỉ dùng phương thức này thao tác được với iterator. Ta không thể dùng lệnh it+=2 hoặc it=it+2.

Ví dụ 3: Tạo list thứ nhất có 5 phần tử đều có giá trị là 100. Tạo list thứ hai có 3 phần tử đều có giá trị là 200. Chèn tất cả các phần tử của list thứ hai vào vị trí thứ 2 của list thứ nhất.

Lưu ý: Ngoài việc chèn list này vào list khác, ta có thể chèn một mảng các phần tử vào list.

erase

Phương thức erase có 2 cách dùng:

erase (iterator position): Xóa phần tử ở vị trị position

erase (iterator first, iterator last): Xóa tất cả các phần tử trong nửa khoảng [frist,last), có nghĩa là từ phẩn tử thứ first đến phần tử thứ (last-1).

Ví dụ 1: Tạo một list có 10 phần tử có giá trị từ 1 đến 10. Xóa phần tử thứ 6 và in ra các phần tử còn lại.

Ví dụ 2: Tạo một list có 10 phần tử có giá trị từ 1 đến 10. Xóa  3 phần tử ở đầu list.

swap(list L)

Hoán đổi list L với list hiện hành.

Ví dụ: Cho hai list, list thứ nhất có 5 phần tử đều là số 1, list thứ hai có 5 phần tử đều là số 2. Hoán đổi hai list trên và in ra các phần tử của mỗi list.

clear()

Xóa hoàn toàn một list.

Ví dụ: Tạo một list có 5 phần tử đều có giá trị là 5. In kích thước của list trước và sau khi dùng phương thức clear()

Lưu ý: Khác với vector, phương thức clear() của list sẽ xóa đi hoàn toàn danh sách.

Operations:

splice

splice (iterator positon,list& other): ghép list other vào vị trí position của list hiện hành, sau khi nối ghép, list other không còn phần tử nào.

splice (iterator positon,list& other, iterator first, iterator last): ghép các phần tử trong nửa khoảng [first,last) của list other và list hiện hành. Sau khi ghép nối, list other chỉ còn lại các phần tử trong nửa đoạn [ last, L.end() )

splice (iterator positon, list& other, iterator it ): ghép phần tử có vị trí là it của list other vào vị trí position của list hiện hành. Sau khi ghép nối, list other bị mất đi phần tử ở vị trí it.

Ví dụ 1: Tạo danh sách thứ nhất có 5 phần tử đều có giá trị là 100. Tạo danh sách thứ hai có 3 phần tử đều có giá trị là 200. Ghép danh sách thứ 2 vào đầu danh sách thứ nhất.

Ví dụ 2: Tạo danh sách thứ nhất có 5 phần tử đều có giá trị là 100. Tạo danh sách thứ hai có 5 phần tử đều có giá trị là 200. Ghép 2 phần tử đầu củadanh sách thứ 2 vào đầu danh sách thứ nhất.

Ví dụ 3: Tạo list thứ nhất có các phần tử là a,b,c,d,e. Tạo list thứ hai có các phần tử là A,B,C,D,E. Chuyển phần tử C của list thứ hai vào vị trí cuối cùng của list thứ nhất.

remove (const val)

Loại bỏ tất cả phần tử có giả trị bằng val trong list.

Ví dụ: Tạo một danh sách có các phần tử lần lượt là 10,15,15,20,30,40. Loại bỏ phần tử có giá trị bằng 15 ra khỏi danh sách.

remove_if (predicate pred)

Loại bỏ tất các phần tử trong list nếu pred trả về giá trị  true. Predicate có thể là một hàm (function) hoặc một class.

Ví dụ 1: Tạo một list có các phần tử lần lượt là 1, 10, 2, 20, 3, 30, 4, 40. Loại bỏ các phần tử có 1 kí tự ra khỏi list.

Ví dụ 2: Tạo một list có các phần tử lần lượt là 1, 2, 3, 4, 5, 6, 7, 8, 9. Loại bỏ các phần tử lẻ ra khỏi list.

Lưu ý: khi sử dụng predicate như là một class, thì khi truyền tham số cho hàm remove_if ta phải thêm dấu ngoặc đơn () như trong lệnh : mylist.remove_if (is_odd());

sort

có hai hình thức sử dụng sort là :

sort(): Sắp xếp các phần tử của list theo chiều tăng dần.

sort (compare comp) : Sắp xếp các phần tử của list tăng dần theo tiêu chí so sánh comp. Biểu thức compare comp có thể là một hàm trả về giá trị bool.

Ví dụ: Tạo list chứ các phần tử từ 1 đến 9. Sắp xếp lại các phần tử theo chiều từ 9 đến 1.

Ví dụ 2: Tạo list chứa các phần tử kiểu string bao gồm “AAAA”,”BBB”,”CC”,”D”. Sắp xếp lại các phần tử trong list theo chiều tăng dần độ dài của chuỗi.

reverse()

Đảo ngược lại các phần tử của list.

Ghi chú: Ta có thể dùng phương thức reverse() phối hợp với phương thức sort() để sắ xếp các phần tử theo chiều giảm dần. Bởi vì mật định hàm sort() là sắp xếp tăng dần do đó sau khi dùng hàm sort(), ta dùng thêm hàm reverse() để lại ngược lại các phần tử.

Ví dụ: Tạo list có các phần tử lần lượt là 0,1,2,3,4,5,9,8,6,5. Sắp xếp lại các phần tử theo chiều giảm dần.

unique

unique(): Loại bỏ các phần tử thích hợp sao cho các phần tử còn lại trong list chỉ xuất hiện đúng duy nhất 1 lần.

unique (BinaryPredicate binary_pred): Loại bỏ các phần tử thích hợp sao cho các phần tử còn lại trong list chỉ xuất hiện đúng duy nhất 1 lần dựa theo tiêu chí của hàm binary_pred. Biểu thức binary_pred có thể là hàm (function) hoặc lớp (class).

Lưu ý: Các phần tử trong list phải được sắp xếp, nếu không sắp xếp thì phương thức unique sẽ cho kết quả sai.

Ví dụ 1: Tạo list bao gồm các phần tử có giá trị lần lượt là 1, 2, 3, 4, 1, 2, 3, 4. Loại bỏ các phần tử sau cho các phần tử chỉ xuất hiện 1 lần.

 

Ví dụ 2: Cho một list bao gồm các 8 số thập phân sau: 1.1, 2.1, 3.1, 4.1, 1.2, 2.2, 3.2, 4.2. Giả sử các số thập phân có phần nguyên giống nhau thì được xem là một số duy nhất. Hãy loại bỏ các phần tử sau cho các phần tử chỉ xuất hiện 1 lần.

merge

Có hai cách sử dụng chính như sau:

merge (list& L): Ghép list L vào sau vị trí cuối cùng list hiện hành. Sau khi ghép nối, list L không còn phần tử nào.

merge (list& L, Compare comp): Ghép các phần tử của list L vào list hiện hành với vị trí dựa theo biểu thức comp. Biểu thức comp là một hàm trả về giá trị bool.

Ví dụ 1: Tạo list thứ nhất có 5 phần tử đều có giá trị 100, list thứ hai có các 3 phần tử đều có giá trị 200. Hãy di chuyển tất cả các phần tử của list thứ hai vào sau list thứ nhất.

 

Ví dụ 2: Tạo list thứ nhất bao gồm 3 phần tử 3.1,  2.2 , 2.9. Tạo list thứ hai bao gồm 4 phần tử 3.7, 7.1, 1.4, 2.1. Hãy trộn các phần tử của list thứ hai vào list thứ nhất dựa theo biểu thức comp như sau:

Hãy in các phần tử trong danh sách thứ nhất sau khi trộn.

Kết quả:

first contains: 3.7 7.1 3.1 2.2 2.9 1.4 2.1

Giải thích:

List 1 List 2
3.1   2.2   2.9 3.7   7.1   1.4   2.1 3.1 >3.7 à false à print 3.7
3.1   2.2   2.9 7.1   1.4   2.1 3.1> 7.1 à false à print 7.1
3.1   2.2   2.9 1.4   2.1 3.1 > 1.4 à true à print 3.1
2.2   2.9 1.4   2.1 2.2 >1.4 à true à print 2.2
2.9 1.4   2.1 2.9>1.4 àtrue à print 2.9
1.4   2.1 print 1.4 , print 2.1

 

Share
Share