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 bạn tiếp kiệm thời gian trong lập trình.
C/C++ Nguyễn Hoàng Minh Trung 2014-09-21 23:15:26

Giới thiệu

Các bạn đã sử dụng qua array (mảng) để chứa dữ liệu trong từng phần tử trong một array và có thể duyệt qua từng phần tử đó để làm việc với các dữ liệu đó. Nhược điểm của array là khi sử dụng các bạn khởi tạo với một số lượng phần tử nhất định, thì giới hạn này sẽ không thể bị phá vỡ bởi quy tắc của kiểu dữ liệu này, kể cả với cấp phát động. List ra đời để hỗ trợ cho các lập trình viên một kiểu dữ liệu mới để quản lý việc các phần tử được thêm mới và xóa khỏi vùng nhớ một các dễ dàng.

Tiền đề bài viết

Trong quá trình học tập tại STDIO tôi đã hiểu được nền tảng của C++ nhưng vì tốc độ phát triển một chương trình và sự tiện lợi, tôi đã sử dụng qua một kiểu dữ liệu mới là "list" để giúp giảm thời gian viết ra một chương trình, game mới.

Đối tượng hướng đến

Đối tượng hướng đến các bạn lập trình viên đang học hỏi về 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 bạn 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 các bạn 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ợ, ta 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, ta 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 ta 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 ta 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 ta 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 ta 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 tôi đã 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 các bạn 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 cho các bạn 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 các bạn 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.