Standard Template Library Algorithms (STL algorithm)

####Chào các bạn đang theo dõi khóa học lập trình trực tuyến ngôn ngữ C++.

Trong bài học này, chúng ta cùng tìm hiểu thành phần cuối cùng trong STL, đó là STL algorithm.

###STL Algorithm

STL Algorithm cung cấp cho chúng ta một số thuật toán cơ bản để thao tác với các container class. Những thuật toán thường được sử dụng như search, sort, insert, reoder, remove, copy… tất cả đều được sử dụng để thao tác trên các container.

Lưu ý: Các thuật toán này được cài đặt như những hàm có phạm vi global sử dụng các Iterator. Điều này có nghĩa các thuật toán này chỉ cần cài đặt một lần và nó được sử dụng cho các container chứa một tập hợp các iterator.

Khi chúng ta sử dụng các thuật toán này, có thể chúng sẽ giúp chương trình của chúng ta hoạt động nhanh hơn, nhưng cũng có thể có trường hợp làm cho chương trình không hoạt động, lặp vô hạn hoặc có hiệu suất thấp.

Để sử dụng STL algorithm, các bạn chỉ cần include thư viện algorithm vào file chương trình là được.

####Search

#####std::min_element and std::max_element

min_element và max_element được sử dụng để tìm ra phần tử có giá trị nhỏ nhất hoặc lớn nhất trong một STL container. Chức năng của 2 hàm này khá dễ hiểu, nên các bạn có thể xem ví dụ cụ thể bên dưới:

#include <iostream>
#include <algorithm>
#include <vector>

int main()
{
	std::vector<__int32> container;
	
	for (int i = 0; i < 10; i++)
		container.push_back(i + 1);

	std::vector<__int32>::iterator iterMax = std::max_element(container.begin(), container.end());
	std::vector<__int32>::iterator iterMin = std::min_element(container.begin(), container.end());

	std::cout << "Max = " << *iterMax << std::endl;
	std::cout << "Min = " << *iterMin << std::endl;

	return 0;
}

Hai hàm này đều nhận vào 2 đối số là 2 Iterator đại diện cho đoạn container mà bạn muốn tìm kiếm và trả về một Iterator trỏ đến vị trí có phần tử lớn nhất hoặc nhỏ nhất. Ví dụ các bạn muốn chỉ search một nữa sau của container:

std::vector<__int32>::iterator iterMax = std::max_element(container.begin() + container.size() / 2, container.end());

#####std::find

Hàm này được sử dụng để tìm kiếm một giá trị đưa ra có tồn tại trong container hay không, nếu có thì trả về một Iterator trỏ đến vị trí xuất hiện phần tử đó, ngược lại thì trả về Iterator trỏ đến end() của container. Ví dụ:

#include <iostream>
#include <algorithm>
#include <vector>

int main()
{
	std::vector<__int32> container;
	
	for (int i = 0; i < 10; i++)
		container.push_back(i + 1);

	std::vector<__int32>::iterator iter = std::find(container.begin(), container.end(), 11);
	if (iter == container.end())
	{
		std::cout << "Can not find your given value!" << std::endl;
	}
	else
	{
		std::cout << "Found at index: " << iter - container.begin() << std::endl;
	}

	return 0;
}

#####std::find_if

Hàm này được định nghĩa như sau:

template <class InputIterator, class UnaryPredicate>
InputIterator find_if (InputIterator first, InputIterator last, UnaryPredicate pred);

Hàm này nhận vào 2 đối số đầu tiên là 2 Iterator chỉ vị trí đầu và cuối (giới hạn đoạn container) mà các bạn muốn tìm kiếm. Khác với hàm std::find, hàm này không tìm kiếm sự xuất hiện của một giá trị cụ thể, mà các bạn cần cung cấp cho hàm một điều kiện nào đó, điều kiện này được biểu diễn thông qua một hàm có dạng:

bool isSatisfyYourCondition(container_type value);

Tham số thứ 3 của hàm std::find_if là một con trỏ hàm có dạng:

bool (*ptr)(container_type);

Do đó, chúng ta có thể truyền đối số thứ 3 cho hàm std::find_if là tên của hàm isSatisfyYourCondition mình đã khai báo ở trên (chỉ là ví dụ minh họa).

Với mỗi lần duyệt qua một phần tử trong đoạn container từ first đến last, mỗi phần tử sẽ được kiểm tra bên trong hàm được gán cho tham số thứ 3 của std::find_if. Nếu phần tử được kiểm tra thõa mãn điều kiện bạn đặt ra (hàm isSatisfyYourCondition trả về true), một Iterator trỏ đến phần tử vừa kiểm tra sẽ được trả về. Iterator last mà bạn truyền vào sẽ được trả về nếu không có phần tử nào thõa mãn điều kiện.

Mình lấy một ví dụ như sau:

#include <iostream>
#include <algorithm>
#include <vector>

bool isFive(__int32 value)
{
	return value == 5;
}

int main()
{
	std::vector<__int32> container;
	
	for (int i = 0; i < 10; i++)
		container.push_back(i + 1);

	std::vector<__int32>::iterator iter = std::find_if(container.begin(), container.end(), isFive);
	
	if (iter != container.end())
	{
		std::cout << "Found at index: " << iter - container.begin() << std::endl;
	}
	else
	{
		std::cout << "Can not found this value!" << std::endl;
	}

	return 0;
}

Hàm isFive sẽ chịu trách nhiệm kiểm tra giá trị của một phần tử trong container có bằng 5 hay không. Do mình kiểm tra từ đầu đến cuối container, nên chắc chắn sẽ hàm std::find_if sẽ tìm được phần tử phù hợp.

Các bạn thử thay đổi lại một chút như sau:

std::vector<__int32>::iterator iter = std::find_if(container.begin(), container.end() - 8, isFive);
	
if (iter != container.end())
{
	std::cout << "Found at index: " << iter - container.begin() << std::endl;
}
else
{
	std::cout << "Can not found this value!" << std::endl;
}

và xem thử kết quả có gì khác biệt.

####Sort

Sắp xếp cũng là một trong những thuật toán thường xuyên được áp dụng trong thực tế.

#####std::sort

Có 2 định nghĩa được overload cho hàm std::sort, một phiên bản được sử dụng để sắp xếp đoạn container từ Iterator first đến Iterator last theo thứ tự giá trị tăng dần từ bé đến lớn. Ví dụ:

#include <iostream>
#include <ctime>
#include <cstdlib>
#include <algorithm>
#include <vector>

int main()
{
	std::vector<__int32> container;
	
	srand(time(NULL));
	for (int i = 0; i < 10; i++)
		container.push_back(rand() % 100);

	for (int i = 0; i < container.size(); i++)
		std::cout << container.at(i) << " ";
	std::cout << std::endl;

	std::sort(container.begin(), container.end());

	for (int i = 0; i < container.size(); i++)
		std::cout << container.at(i) << " ";
	std::cout << std::endl;

	return 0;
}

Một phiên bản khác của std::sort là hàm có 3 tham số, trong đó, tham số thứ 3 là một con trỏ hàm có dạng:

bool (*ptr)(container_type, container_type);

Hàm được trỏ đến bởi tham số này sẽ định nghĩa mối quan hệ giữa 2 phần tử được đem ra so sánh (để sắp xếp). Các bạn có thể tham khảo thêm tại đường dẫn bên dưới:

std::sort

###Tổng kết

Qua bài học này, các bạn đã cùng mình tìm hiểu một số STL algorithm phổ biến được định nghĩa bên trong thư viện algorithm. Để xem chi tiết về các algorithm khác của STL, các bạn có thể tham khảo tại đây: http://www.cplusplus.com/reference/algorithm/

Hẹn gặp lại các bạn trong bài học tiếp theo trong khóa học lập trình C++ hướng thực hành.

Mọi ý kiến đóng góp hoặc thắc mắc có thể đặt câu hỏi trực tiếp tại diễn đàn

www.daynhauhoc.com