4.4. Những Thuật Toán Quyền Năng - Lập Trình Tân Binh

Bây giờ, sau khi đã nếm thử mật ngọt mà các biến đếm mang lại cho chúng ta khi duyệt lớp chứa, tôi cho rằng rất nhiều người sẽ trở nên háo hức muốn biết STL có thể cung cấp gì nữa cho chúng ta. Trong bài học này, tôi xin phép được thảo luận về các giải thuật của STL, các hàm cho phép chúng ta thực hiện thay đổi trên các lớp chứa. Mong là sẽ không khiến các bạn thất vọng.

Kể từ bài học trước, chúng ta đã rất nhiều lần nhắc đến việc thay đổi lớp chứa. Thế nhưng cụ thể thì thế nào là thay đổi ? Rất đơn giản, đó là những thao tác như sắp xếp lại danh sách, xóa bó đối tượng trùng lặp, đảo ngược đầu cuối hay thay thế đối tượng này bằng đối tượng khác, vv…

Có 1 vài thuật toán khá đơn giản và chúng ta thường không thấy được lợi ích của việc tạo ra các hàm viết sẵn. Thực ra ưu điểm của chúng chính là việc chúng ta có thể sử dụng chúng mà không cần suy nghĩ gì nhiều. Thêm nữa, chúng cũng đã được tối ưu hóa về mặt hiệu suất cho công việc mà chúng ta yêu cầu. Vậy nên lời khuyên là hãy dùng những thuật toán viết sẵn đó bất cứ khi nào có thể.

! Để hiểu rõ hơn bài học này, trước tiên các bạn cần nắm vững về biến đếm và đối tượng hàm đã được nhắc tới trong bài trước do chúng ta sẽ sử dụng rất nhiều đến chúng.

Ví dụ đơn giản

Trước khi bắt đầu, tôi cần báo trước là chúng ta sẽ, như mọi khi, không thảo luận về toàn bộ các thuật toán mà STL cung cấp. Lý do rất đơn giản, có đến khoảng sáu chục thuật toán trong STL nhưng không phải tất cả chúng đều hữu dụng. Vậy nên mục đích của bài học này chỉ là giúp các bạn nắm vững nguyên lý chung của chúng và rồi tự xoay sở nếu cần sử dụng đến các thuật toán khác không được nhắc đến.

Việc cần làm đầu tiên đương nhiên là thêm tệp tiêu đề mà chúng ta muốn sử dụng vào mã nguồn. Trong trường hợp của chúng ta thì đó là gói algorithm. Từ giờ phút này trở đi, chúng ta sẽ sử dụng đến nó rất nhiều.

Khởi động nhẹ nhàng

Trong bài học trước, chúng ta đã tạo ra đối tượng hàm CungCapGiaTri dùng để áp dụng lên tất cả các phần tử của vector. Để làm thế, chúng ta đã sử dụng đến vòng lặp để duyệt tất cả các đối tượng bị chứa trong mảng từ vị trí begin() tới end().

Thuật toán đơn giản nhất là generate() và nó làm công việc hoàn toàn tương tự nhưng với hiệu suất cao hơn. Nó gọi sử dụng 1 đối tượng hàm lên tất cả các đối tượng nằm trong lớp chứa. Nhờ thuật toán này mà đoạn mã dùng để lấp đầy giá trị cho mảng trở nên ngắn gọn hơn nhiều.

#include <algorithm> #include <vector> using namespace std; //Dinh nghia CungCapGiaTri int main() { vector<int> mang(100,0); //Mang gom 100 so 0 CungCapGiaTri f(0); generate(mang.begin(), mang.end(), f); //Ap dung f len tat ca cac doi tuong nam giua begin() và end() return 0; }

Mã nguồn trở nên sáng sủa và dễ hiểu hơn nhiều. Chỉ cần biết chút tiếng Anh tiếng Em là các bạn có thể hiểu được « generate » nghĩa là « phát sinh ». Vậy nên câu lệnh của chúng ta có thể được hiểu ngay là dùng đối tượng hàm f để tạo ra giá trị cho đối tượng nằm giữa begin() và end(). Khó mà có thể đơn giản hơn được nữa.

? Nhưng tại sao lại cần sử dụng biến đếm ? Vì sao generate() không đơn giản là nhận vào 1 tham số kiểu mảng vector cho tham số đầu tiên ?

Câu hỏi xuất sắc ! Nó chứng tỏ là các bạn vẫn đang theo kịp vấn đề mà chúng ta đang thảo luận. Đúng là nếu có thể viết lệnh kiểu như generate(mang, f) thì chúng ta có thể tránh được cả đống phiền toái khi sử dụng biến đếm. Vậy lí do gì mà chúng ta lại phải phức tạp vấn đề lên.

Trong thực tế, ý tưởng đó không tuyệt vời như chúng ta tưởng. Hãy tưởng tượng nếu chúng ta chỉ muốn áp dụng đối tượng hàm lên 10 đối tượng bị chứa đầu tiên chứ không phải toàn bộ mảng. Phương án vừa được đưa ra sẽ không còn khả thi nữa. Lúc đó, lợi ích của việc sử dụng biến đếm lại trở nên rõ ràng hơn nhiều khi cho phép chúng ta giới hạn trong 1 phần của tập hợp chứ không phải toàn bộ. Để thực hiện yêu cầu trên, chúng ta có thể làm như sau :

int main() { vector<int> mang(100,0); // Mang gom 100 so 0 CungCapGiaTri f(0); generate(mang.begin(), mang.begin()+10, f); //Ap dung f cho 10 doi tuong dau tien generate(mang.end()-5, mang.end(), f); //Va 5 doi tuong sau cung return 0; }

Dễ dàng quá, phải không ?

Trong thực tế, đây là 1 đặc điểm quan trọng của các giải thuật của STL, chính là luôn được áp dụng trên 1 dải đối tượng nằm giữa 2 biến đếm.

Ứng dụng trên các lớp chứa khác

Lợi ích khác của việc sử dụng các biến đếm, đó là chúng tồn tại cho tất cả các loại lớp chứa. Điều này giúp cho chúng ta có thể áp dụng các giải thuật lên hầu hết tất cả các lớp chứa 1 cách dễ dàng. Đương nhiên chúng ta vẫn còn những hạn chế nhất định khi áp dụng tùy thuộc vào kiểu biến đếm là truy cập ngẫu nhiên hay dịch chuyển 2 chiều hay gì khác.

Ví dụ, chúng ta hoàn toàn có thể áp dụng đối tượng hàm lên list<int> mà không có gì khác biệt.

int main() { list<int> mang; //Danh sach so nguyen //Khoi tao cac thanh phan trong danh sach CungCapGiaTri f(0); generate(mang.begin(), mang.end(), f); //Ap dung f len tat ca doi tuong trong danh sach return 0; }

Cú pháp hoàn toàn giống nhau ! Chỉ cần 1 lần hiểu nguyên lý hoạt động thì chúng ta thoải mái áp dụng các thao tác phức tạp lên đủ loại lớp chứa khác nhau.

! Đương nhiên là chúng ta cũng cần phải có sự tương thích nhất định giữa đối tượng hàm muốn áp dụng và kiểu lớp chứa. Không thể nào lại áp dụng đối tượng hàm xử lý string lên 1 deque chứa các số thực được. Mọi thứ cần đảm bảo hợp lý nếu không chúng ta rất dễ nhận được các thông báo lỗi khá khó hiểu từ phía STL. Vậy nên, hãy sử dụng chúng 1 cách thận trọng.

Đếm, tìm kiếm, sắp xếp

Khởi động xong rồi. Giờ thì chúng ta sẽ cùng nhau chinh phục các thuật toán trong tệp tiêu đề algorithm. Hãy bắt đầu bằng các hàm đếm.

Đếm các đối tượng

Việc đếm số lượng đối tượng là thao tác rất dễ thực hiện. STL lại lần nữa thể hiện xuất sắc và cung cấp cho chúng ta công cụ giúp đoạn mã trở nên rõ ràng hơn và hiệu suất cao hơn trong 1 vài trường hợp.

Để đếm số đối tượng bị chứa có giá trị bằng giá trị cho trước, chúng ta sẽ cần sử dụng thuật toán count(). Ai biết 1 chút tiếng Anh là thậm chí có thể đoán ngay được từ trước ấy chứ. Ví dụ dưới đây là câu lệnh đếm số lượng phần tử bị chứa có giá trị bằng 2.

int soLuong = count(tapHop.begin(), tapHop.end(), 2);

Và đương nhiên là tapHop có thể là lớp chứa thuộc bất kỳ loại nào, ít nhất thì với thuật toán này là thế.

Trước khi đi sâu hơn, chúng ta hãy thử tổng kết những kiến thức về đối tượng hàm, generate() với cả count() trong 1 bài tập nhỏ nhé. Hãy nghĩ thử xem làm sao chúng ta tạo ra 1 chương trình khởi tạo mảng gồm 100 số nguyên có giá trị bất kỳ nằm giữa 0 với 9 rồi đếm số lượng số 5 được sinh ra ngẫu nhiên trong số đó. Nhớ là chỉ cần dùng STL thôi nhé!

Thách thức bé tẹo này không làm khó được các bạn chứ ? Dưới đây là 1 đoạn mã đáp án để tham khảo nếu cần :

#include <iostream> #include <cstdlib> //De su dung rand() #include <ctime> //De su dung time() #include <vector> #include <algorithm> using namespace std; class KhoiTao { public: int operator()() const { return rand() % 10; //Tra ve so bat ky giua 0 va 9 } }; int main() { srand(time(0)); vector<int> mang(100,-1); //Mang dong gom 100 o generate(mang.begin(), mang.end(), KhoiTao()); //Khoi tao ngau nhien cac gia tri int const soLuongSo5 = count(mang.begin(), mang.end(), 5); //Dem so luong so 5 cout << "Có tổng cộng " << soLuongSo5 << " số 5 được sinh ra." << endl; return 0; }

Theo ý kiến cá nhân thì tôi thấy đoạn mã này khá rõ ràng. Chúng ta hiểu ngay được chuyện gì đang xảy ra bên trong đó. Các vòng lặp cồng kềnh được che giấu đằng sau các thuật toán STL sẵn có.

Sự trở lại của các phép thử

Nếu các bạn nghĩ rằng có thể dễ dàng thực hiện điều mong muốn mà không sử dụng đến loại đối tượng hàm đặc biệt này thì nhầm to rồi. Trong bài học trước, tôi từng nói với các bạn là các phép thử được sử dụng để kiểm tra 1 tính chất của 1 đối tượng nào đó. Vậy nên chúng ta sẽ hoàn toàn có thể sử dụng nó để đếm số lượng đối tượng đạt được 1 yêu cầu nào đó. Và chúng ta cũng có 1 thuật toán riêng để thực hiện điều này, đó là count_if(). Tương tự như count() nhưng lần này, chúng ta cần thêm 1 tham số là 1 phép thử predicat.

Trong bài học trước, chẳng phải chúng ta đã viết 1 phép thử để kiểm tra xem chứ chữ « a » trong chuỗi ký tự không còn gì. Hãy tận dụng thử nó nhé !

#include <algorithm> #include <string> #include <vector> using namespace std; class PhepThu { public: bool operator()(string const& chuoiKyTu) const { for(int i(0); i<chuoiKyTu.size(); ++i) { if((chuoiKyTu[i] == 'a') { //Kiem tra tung ky tu return true; //Tra ve dung khi tim thay chu 'a' } } return false; //Neu di toi cuoi tuc la khong tim thay chu 'a' } }; int main() { vector<string> mang; //… Dien mang tu du lieu trong tep int const soLuong = count_if(mang.begin(), mang.end(), PhepThu()); //… Va su dung ket qua duoc luu trong 'soLuong' return 0; }

Nguyên lý hoạt động thật mãnh mẽ ! Phép thử PhepThu được áp dụng lên tất cả các đối tượng của mảng và chúng ta chỉ việc đếm số lần kết quả trả về là đúng nhờ count_if() và chúng ta sẽ biết số lượng chuỗi có ký tự « a » trong đó.

Tìm kiếm

Việc tìm kiếm trong tập hợp cũng chẳng khó khăn hơn là bao. Chúng ta sử dụng thuật toán find() và find_if() hoàn toàn tương tự như các thuật toán về đếm lúc trước. Điểm khác biệt là kết quả trả về của chúng là 1 biến đếm trỏ lên đối tượng cần tìm hoặc end() nếu không tìm thấy đối tượng nào.

Để tìm kiếm chữ « a » trong danh sách ký tự deque<char> :

#include <deque> #include <algorithm> #include <iostream> using namespace std; int main() { deque<char>mangChuCai; //Dien gia tri cho tung o chu cai deque<char>::iterator viTri = find(mangChuCai.begin(),mangChuCai.end(), 'a'); if(mangChuCai == mangChuCai.end()) { cout << "Không tìm thấy chữ 'a' ! " << endl; } else { cout << "Đã tìm thấy chữ 'a' ! " << endl; } return 0; }

Tôi sẽ không ghi ra đây phiên bản sử dụng phép thử nhưng tôi hoàn toàn tin tưởng việc các bạn có thể xoay sở và tự mình hiểu được cách sử dụng.

Nhân nói về việc tìm kiếm, các bạn cũng nên biết rằng chúng ta có sẵn 2 phương thức min_element() và max_element() cho phép chúng ta tìm ra đối tượng nhỏ nhất và lớn nhất trong tập hợp.

Sắp xếp !

Chúng ta thường xuyên phải thực hiện sắp xếp các đối tượng bị chứa và thú thực thì công việc này cũng không phải là nhẹ nhàng gì. Đây thuộc về 1 trong những vấn đề được ưu tiên hàng đầu trong số các vấn đề của nghiên cứu thuật toán nâng cao. Nói chung, tôi không cho rằng việc viết ra 1 hàm sắp xếp tối ưu là khả dĩ với tất cả mọi người.

1 lần nữa, STL cứu rỗi chúng ta khi đưa ra 1 hàm giải pháp cho vấn đề này và chúng ta hoàn toàn có thể đảm bảo về chất lượng mã cũng như hiệu suất của nó. Tên của hàm này là sort(), dịch ra tiếng Việt thì đơn giản là sắp xếp.

Sau đây, hãy sắp xếp mảng được khởi tạo ngẫu nhiên. Chúng ta cung cấp 2 biến đếm làm tham số để chỉ ra khoảng đối tượng muốn sắp xếp.

int main() { srand(time(0)); vector<int> mang(100,-1); //Mang gom 100 o generate(mang.begin(),mang.end(), CungCapGiaTri()); //Khoi tao ngau nhien gia tri cac o sort(mang.begin(),mang.end()); //Sap xep mang for(vector<int>::iterator it = mang.begin(); it != mang.end(); it++) { cout << *it << endl; //Hien thi mang sau khi sap xep } return 0; }

Phép thần đã nằm gọn trong tay chúng ta.

! Hàm sort() chỉ có thể sử dụng với các loại lớp chứa sử dụng biến đếm truy cập ngẫu nhiên, tức là vector và deque. Ngoài ra việc sắp xếp map cũng không mang nhiều ý nghĩa do chúng mặc định là đã được sắp xếp theo thứ tự khi hình thành.

Mặc định thì hàm sort() sử dụng phép toán < để so sánh các đối tượng bị chứa trước khi sắp xếp chúng. Tuy nhiên, chúng ta cũng có lựa chọn khác khi cung cấp 1 đối tượng hàm thực hiện so sánh làm tham số thứ 3 cho hàm này. Chúng ta đã từng gặp loại đối tượng hàm này trong bài trước khi chúng ta muốn thay đổi xử lý mặc định của nhóm kết hợp. Nguyên lý hoạt động ở đây cũng tương tự như vậy : Nếu muốn sắp xếp theo cách của riêng bạn, hãy sử dụng phép so sánh của riêng bạn.

Ví dụ để sắp xếp các chuỗi theo độ dài của chúng, chúng ta có thể dùng lại đối tượng hàm lúc trước :

class SoSanhChieuDai { public: bool operator()(const string& a, const string& b) { return a.length() < b.length(); } }; int main() { vector<string> mang; //… Dien gia tri bang cach doc 1 tep du lieu. sort(mang.begin(),mang.end(), SoSanhChieuDai()); //Mang da duoc sap xep theo chieu dai doi tuong return 0; }

Đơn giản, hiệu quả và vô cùng mạnh mẽ ! Chúng ta còn có thể đòi hỏi gì hơn nữa chứ ?

Và thêm nhiều thuật toán khác…

Đường đang đẹp tội gì không đi tiếp. Còn xa chúng ta mới đảo qua hết các thuật toán tồn tại trong STL.

Trong ví dụ về sự sắp xếp, tôi đã hiển thị nội dung tập hợp được sắp xếp thông qua vòng lặp. Chúng ta có thể dùng thuật toán khác giúp đoạn mã chúng ta trở nên lịch lãm hơn. Cụ thể, việc hiển thị 1 đối tượng chẳng phải cũng giống như là truyền nó như tham số cho hàm chuyên hiển thị các thứ sao. Lúc này thì 1 hàm như thế hẳn là không còn làm khó được các bạn nữa.

class HienThi { public: void operator()(int a) const { cout << a << endl; } };

Chúng ta chỉ còn việc áp dụng hàm này cho tất cả các đối tượng trong danh sách. Thuật toán cho phép chúng ta làm việc này là for_each().

int main() { srand(time(0)); vector<int> mang(100, -1); generate(mang.begin(), mang.end(), CungCapGiaTri()); //Khoi tao ngau nhien cac gia tri sort(mang.begin(), mang.end()); for_each(mang.begin(), mang.end(), CungCapGiaTrij()); //Va hien thi chung return 0; }

Đoạn mã lại tiếp tục rút ngắn 1 cách thần kỳ. Chúng ta thậm chỉ còn có thể làm tốt hơn nữa nếu sử dụng các luồng. Nhưng đấy là câu chuyện của 1 ngày đẹp trời khác.

Nhờ thuật toán này, chúng ta có thể làm vô số việc. Việc đầu tiên nảy ra trong đầu tôi là dùng để tính tổng các đối tượng bị chứa. Bằng cách nào các bạn biết không ? Chẳng phải là chỉ cần 1 thuộc tính của đối tượng hàm để lưu trữ kết quả là đủ sao. Rồi chúng ta sẽ áp dụng nó lên tất cả đối tượng trong tập hợp.

class TinhTong { public: TinhTong() : m_tong(0) {} void operator()(int n) { m_tong += n; } int ketQua() const { return m_tong; } private: int m_tong; };

Phép toán () đơn giản là cộng thêm giá trị của đối tượng đang xét vào m_tong. Sau khi thực hiện thuật toán, chúng ta lấy ra kết quả nhờ phương thức ketQua() của đối tượng hàm. Tuy nhiên, chúng ta cần cẩn thận khi sử dụng for_each() dó nó chỉ làm việc với tham trị chứ không phải tham chiếu của đối tượng hàm. Điều đó nghĩa là đối tượng mà thuộc tính m_tong thay đổi chỉ là bản sao chứ không phải đối tượng hàm mà chúng ta tạo ra trong main(). Thật mày là những người tạo ra STL đã nghĩ đến điều đó và cho for_each() trả về giá trị của đối tượng hàm mà nó đã sử dụng sau khi xử lý xong. Vậy nên chúng ta có thể sử dụng đối tượng trả về này để lấy ra kết quả mà chúng ta cần.

int main() { srand(time(0)); vector<int> mang(100, -1); generate(mang.begin(), mang.end(), CungCapGiaTri()); // Khoi tao ngau nhien cac gia tri TinhTong tong; //Tinh tong cac doi tuong va lay ra ket qua tong = for_each(mang.begin(), mang.end(), tong); cout << "Tổng của các giá trị được khởi tạo ngẫu nhiên là : " << tong.ketQua() << endl; return 0; }

Nếu các bạn vẫn muốn luyện tập thêm thì tôi có ý tưởng này. Chúng ta có thể viết hàm tính trung bình cộng của 1 mảng chứa điểm số chẳng hạn. Chúng ta đã từng xử lý vấn đề này trước đây trong giáo trình nhưng lần này có khác biệt, đó là cần phải vui vẻ với đối tượng hàm và for_each() của STL.

Xử lý đồng thời 2 tập hợp

Chúng ta sẽ kết thúc bài học này với thuật toán cuối cùng cho phép chúng ta xử lý đồng thời 2 tập hợp. Hãy tưởng tượng chúng ta muốn tính tổng của các đối tượng trong 2 tập hợp và lưu kết quả vào 1 tập hợp thứ 3. Để làm điều này, chúng ta sẽ cần 1 đối tượng hàm thực hiện phép cộng. Chúng ta chẳng phải từng thảo luận 1 hàm như thế trong tệp tiêu đề functional rồi còn gì. Về phần còn lại, chúng ta sẽ phải đồng thời duyệt 2 mảng và ghi kết quả vào mảng thứ 3. Điều này được thực hiện nhờ transform(). Nó nhận vào tổng cộng 5 tham số : 2 biến đếm chỉ ra khoảng đối tượng cần xử lý trong mảng thứ 1, biến đếm trỏ vào đầu của mảng thứ 2, biến đếm trỏ vào đầu mảng lưu kết quả, và cuối cùng là đối tượng hàm thực hiện phép cộng.

#include <vector> #include <algorithm> #include <functional> using namespace std; int main() { vector<double> a(50, 0.); //3 mang, moi mang chu 50 so thuc vector<double> b(50, 0.); vector<double> c(50, 0.); //... Dien cac mang 'a' et 'b' transform(a.begin(), a.end(), b.begin(), c.begin(), plus<double>()); //Vay la cac o trong mang 'c' se chua 'a' va 'b' return 0; }

! Đương nhiên yêu cầu ở đây là mảng b và c phải đủ lớn. Nếu chúng có kích thước nhỏ hơn 50, vốn là kích thước của a thì đoạn mã thực thi sẽ gặp vấn đề vì thuật toán đang cố điền giá trị vào các ô nhớ không tồn tại.

Chúng ta dừng lại ở đây thôi. Tôi đã điểm qua tất cả các thuật toán thông dụng nhất và tôi tin chắc là các bạn đều đã nắm được nguyên lý hoạt động rồi. Rồi từ đây, cuộc đời lập trình viên của các bạn có thể sẽ đổi khác đi. Hoặc không ?

Tóm tắt bài học :

• Các thuật toán của STL cho phép thực hiện các xử lý trên các dữ liệu.
• Chúng ta sử dụng chúng bằng cách chỉ ra khoảng đối tượng giữa 2 biến đếm mà chúng ta muốn xử lý.
• 1 vài thuật toán sử dụng đến các đối tượng hàm, ví dụ để tìm các đối tượng mang 1 đặc điểm cụ thể hoặc để áp dụng 1 xử lý lên tất cả các đối tượng bị chứa.