Tự học C/C++ | Giới thiệu các thuật toán thư viện chuẩn

Các lập trình viên mới thường dành nhiều thời gian để viết các vòng lặp tùy chỉnh để thực hiện các tác vụ tương đối đơn giản, chẳng hạn như sắp xếp hoặc đếm hoặc tìm kiếm mảng. Các vòng lặp này có thể có vấn đề, cả về mức độ dễ mắc lỗi và về khả năng bảo trì tổng thể, vì các vòng lặp có thể khó hiểu.

Vì tìm kiếm, đếm và sắp xếp là những hoạt động phổ biến phải làm, nên thư viện chuẩn C ++ đi kèm với một loạt các hàm để thực hiện những việc này chỉ trong một vài dòng code. Ngoài ra, các chức năng thư viện tiêu chuẩn này đã được kiểm tra trước, hiệu quả, hoạt động trên nhiều loại vùng chứa khác nhau và nhiều chức năng hỗ trợ song song (khả năng dành nhiều luồng CPU cho cùng một tác vụ để hoàn thành nó nhanh hơn).

Hàm được cung cấp trong thư viện thuật toán thường thuộc một trong ba loại:

• Người kiểm tra – Được sử dụng để xem (nhưng không sửa đổi) dữ liệu trong vùng chứa. Ví dụ bao gồm tìm kiếm và đếm.
• Mutators – Được sử dụng để sửa đổi dữ liệu trong vùng chứa. Ví dụ bao gồm sắp xếp và xáo trộn.
• Người hướng dẫn – Được sử dụng để tạo ra một kết quả dựa trên các giá trị của các thành viên dữ liệu. Ví dụ bao gồm các đối tượng nhân giá trị hoặc các đối tượng xác định các cặp phần tử sẽ được sắp xếp theo thứ tự nào.

Các thuật toán này nằm trong thư viện thuật toán. Trong bài học này, chúng ta sẽ khám phá một số thuật toán phổ biến hơn – nhưng còn nhiều thuật toán khác nữa và chúng ta khuyến khích bạn đọc qua tài liệu tham khảo được liên kết để xem mọi thứ khả dụng!

Lưu ý: Tất cả đều sử dụng trình vòng lặp, vì vậy nếu bạn chưa quen với trình vòng lặp cơ bản, vui lòng xem lại bài  – Giới thiệu về trình vòng lặp.

1. Sử dụng std :: find để tìm một phần tử theo giá trị

std :: find tìm kiếm cho lần xuất hiện đầu tiên của một giá trị trong vùng chứa. std :: find nhận 3 tham số: một trình lặp đến phần tử bắt đầu trong chuỗi, một trình lặp tới phần tử kết thúc trong chuỗi và một giá trị để tìm kiếm. Nó trả về một trình lặp trỏ đến phần tử (nếu nó được tìm thấy) hoặc phần cuối của vùng chứa (nếu phần tử không được tìm thấy).

Ví dụ:

/*
Cafedev.vn - Kênh thông tin IT hàng đầu Việt Nam
@author cafedevn
Contact: cafedevn@gmail.com
Fanpage: https://www.facebook.com/cafedevn
Group: https://www.facebook.com/groups/cafedev.vn/
Instagram: https://instagram.com/cafedevn
Twitter: https://twitter.com/CafedeVn
Linkedin: https://www.linkedin.com/in/cafe-dev-407054199/
Pinterest: https://www.pinterest.com/cafedevvn/
YouTube: https://www.youtube.com/channel/UCE7zpY_SlHGEgo67pHxqIoA/
*/

#include <algorithm>
#include <array>
#include <iostream>
 
int main()
{
  std::array arr{ 13, 90, 99, 5, 40, 80 };
 
  std::cout << "Enter a value to search for and replace with: ";  
  int search{};
  int replace{};
  std::cin >> search >> replace;
 
  // Input validation omitted
 
  // std::find returns an iterator pointing to the found element (or the end of the container)
  // we'll store it in a variable, using type inference to deduce the type of
  // the iterator (since we don't care)
  auto found{ std::find(arr.begin(), arr.end(), search) };
 
  // Algorithms that don't find what they were looking for return the end iterator.
  // We can access it by using the end() member function.
  if (found == arr.end())
  {
    std::cout << "Could not find " << search << '\n';
  }
  else
  {
    // Override the found element.
    *found = replace;
  }
 
  for (int i : arr)
  {
    std::cout << i << ' ';
  }
 
  std::cout << '\n';
 
  return 0;
}

Chạy ví dụ khi phần tử được tìm thấy

Enter a value to search for and replace with: 5 234
13 90 99 234 40 80

Chạy ví dụ khi không tìm thấy phần tử

Enter a value to search for and replace with: 0 234
Could not find 0
13 90 99 5 40 80

Sử dụng std :: find_if để tìm một phần tử phù hợp với một số điều kiện

Đôi khi chúng ta muốn xem liệu có một giá trị trong vùng chứa phù hợp với một số điều kiện (ví dụ: một chuỗi chứa một chuỗi con cụ thể) hơn là một giá trị chính xác hay không. Trong những trường hợp như vậy, std :: find_if là hoàn hảo. Hàm std :: find_if hoạt động tương tự như std :: find, nhưng thay vì truyền vào một giá trị để tìm kiếm, chúng ta truyền vào một đối tượng có thể gọi, chẳng hạn như một con trỏ hàm (hoặc lambda, chúng ta sẽ đề cập sau) kiểm tra xem có tìm thấy kết quả phù hợp không. std :: find_if sẽ gọi hàm này cho mọi phần tử cho đến khi tìm thấy một phần tử phù hợp (hoặc không còn phần tử nào nữa trong vùng chứa để kiểm tra).

Dưới đây là một ví dụ mà chúng ta sử dụng std :: find_if để kiểm tra xem có phần tử nào chứa chuỗi con “nut” không:

#include <algorithm>
#include <array>
#include <iostream>
#include <string_view>
 
// Our function will return true if the element matches
bool containsNut(std::string_view str)
{
  // std::string_view::find returns std::string_view::npos if it doesn't find
  // the substring. Otherwise it returns the index where the substring occurs
  // in str.
  return (str.find("nut") != std::string_view::npos);
}
 
int main()
{
  std::array<std::string_view, 4> arr{ "apple", "banana", "walnut", "lemon" };
 
  // Scan our array to see if any elements contain the "nut" substring
  auto found{ std::find_if(arr.begin(), arr.end(), containsNut) };
 
  if (found == arr.end())
  {
    std::cout << "No nuts\n";
  }
  else
  {
    std::cout << "Found " << *found << '\n';
  }
 
  return 0;
}

Kết quả

Found walnut

Nếu bạn viết ví dụ trên bằng tay, bạn cần ít nhất ba vòng lặp (một để lặp qua mảng và hai để khớp với chuỗi con). Các hàm thư viện chuẩn cho phép chúng ta làm điều tương tự chỉ trong một vài dòng code!

2. Sử dụng std :: count và std :: count_if để đếm số lần xuất hiện

std :: count và std :: count_if tìm kiếm tất cả các lần xuất hiện của một phần tử hoặc một phần tử thỏa coden một điều kiện.

Trong ví dụ sau, chúng ta sẽ đếm có bao nhiêu phần tử chứa chuỗi con “nut”:

/*
Cafedev.vn - Kênh thông tin IT hàng đầu Việt Nam
@author cafedevn
Contact: cafedevn@gmail.com
Fanpage: https://www.facebook.com/cafedevn
Group: https://www.facebook.com/groups/cafedev.vn/
Instagram: https://instagram.com/cafedevn
Twitter: https://twitter.com/CafedeVn
Linkedin: https://www.linkedin.com/in/cafe-dev-407054199/
Pinterest: https://www.pinterest.com/cafedevvn/
YouTube: https://www.youtube.com/channel/UCE7zpY_SlHGEgo67pHxqIoA/
*/

#include <algorithm>
#include <array>
#include <iostream>
#include <string_view>
 
bool containsNut(std::string_view str)
{
  return (str.find("nut") != std::string_view::npos);
}
 
int main()
{
  std::array<std::string_view, 5> arr{ "apple", "banana", "walnut", "lemon", "peanut" };
 
  auto nuts{ std::count_if(arr.begin(), arr.end(), containsNut) };
 
  std::cout << "Counted " << nuts << " nut(s)\n";
 
  return 0;
}

Kết quả

Counted 2 nut(s)

3. Sử dụng std :: sort để tùy chỉnh sắp xếp 

Trước đây chúng ta đã sử dụng std :: sort để sắp xếp một mảng theo thứ tự tăng dần, nhưng std :: sort có thể làm được nhiều hơn thế. Có một phiên bản của std :: sort lấy một hàm làm tham số thứ ba cho phép chúng tôi sắp xếp theo cách chúng tôi muốn. Hàm nhận hai tham số để so sánh và trả về true nếu đối số đầu tiên phải được sắp xếp trước đối số thứ hai. Theo mặc định, std :: sort sắp xếp các phần tử theo thứ tự tăng dần.

Hãy sử dụng std :: sort để sắp xếp một mảng theo thứ tự ngược lại bằng cách sử dụng hàm so sánh tùy chỉnh có tên là lớn hơn:

#include <algorithm>
#include <array>
#include <iostream>
 
bool greater(int a, int b)
{
  // Order @a before @b if @a is greater than @b.
  return (a > b);
}
 
int main()
{
  std::array arr{ 13, 90, 99, 5, 40, 80 };
 
  // Pass greater to std::sort
  std::sort(arr.begin(), arr.end(), greater);
 
  for (int i : arr)
  {
    std::cout << i << ' ';
  }
 
  std::cout << '\n';
 
  return 0;
}

Kết quả

99 90 80 40 13 5

Một lần nữa, thay vì viết các hàm vòng lặp tùy chỉnh của riêng mình, chúng ta có thể sắp xếp mảng của mình theo cách chúng ta muốn chỉ trong một vài dòng code!

Hàm lớn hơn của chúng tôi cần 2 đối số, nhưng chúng ta không chuyển nó bất kỳ, vậy chúng đến từ đâu? Khi chúng ta sử dụng một hàm không có dấu ngoặc đơn (), nó chỉ là một con trỏ hàm chứ không phải một lệnh gọi. Bạn có thể nhớ điều này khi chúng ta cố gắng in một hàm không có dấu ngoặc đơn và std :: cout in “1”. std :: sort sử dụng con trỏ này và gọi hàm lớn hơn thực tế với 2 phần tử bất kỳ của mảng. Chúng ta không biết phần tử nào lớn hơn sẽ được gọi với vì nó không được xác định thuật toán sắp xếp std :: sort đang sử dụng ẩn.

4. Sử dụng std :: for_each để thực hiện điều gì đó với tất cả các phần tử của vùng chứa

std :: for_each lấy một danh sách làm đầu vào và áp dụng một hàm tùy chỉnh cho mọi phần tử. Điều này rất hữu ích khi chúng ta muốn thực hiện cùng một thao tác với mọi phần tử trong danh sách.

Dưới đây là một ví dụ mà chúng tôi sử dụng std :: for_each để nhân đôi tất cả các số trong một mảng:

/*
Cafedev.vn - Kênh thông tin IT hàng đầu Việt Nam
@author cafedevn
Contact: cafedevn@gmail.com
Fanpage: https://www.facebook.com/cafedevn
Group: https://www.facebook.com/groups/cafedev.vn/
Instagram: https://instagram.com/cafedevn
Twitter: https://twitter.com/CafedeVn
Linkedin: https://www.linkedin.com/in/cafe-dev-407054199/
Pinterest: https://www.pinterest.com/cafedevvn/
YouTube: https://www.youtube.com/channel/UCE7zpY_SlHGEgo67pHxqIoA/
*/

#include <algorithm>
#include <array>
#include <iostream>
 
void doubleNumber(int &i)
{
  i *= 2;
}
 
int main()
{
  std::array arr{ 1, 2, 3, 4 };
 
  std::for_each(arr.begin(), arr.end(), doubleNumber);
 
  for (int i : arr)
  {
    std::cout << i << ' ';
  }
 
  std::cout << '\n';
 
  return 0;
}

Kết quả:

2 4 6 8

Điều này thường có vẻ là thuật toán không cần thiết nhất đối với các developer mới, vì code tương đương với vòng lặp dựa trên phạm vi ngắn hơn và dễ dàng hơn. Nhưng có những lợi ích đối với std :: for_each. Hãy so sánh std :: for_each với vòng lặp for dựa trên phạm vi.

std::ranges::for_each(arr, doubleNumber); // Since C++20, we don't have to use begin() and end().
// std::for_each(arr.begin(), arr.end(), doubleNumber); // Before C++20
 
for (auto& i : arr)
{
  doubleNumber(i);
}

Với std :: for_each, ý định của chúng tôi rất rõ ràng. Gọi doubleNumber với mỗi phần tử của arr. Trong vòng lặp for dựa trên phạm vi, chúng ta phải thêm một biến mới, i. Điều này dẫn đến một số sai lầm mà một lập trình viên có thể mắc phải khi họ mệt mỏi hoặc không chú ý. Đối với một, có thể có một chuyển đổi ngầm nếu chúng tôi không sử dụng tự động. Chúng ta có thể quên ký hiệu và và doubleNumber sẽ không ảnh hưởng đến mảng. Chúng ta có thể vô tình chuyển một biến khác với i thành doubleNumber. Những sai lầm này không thể xảy ra với std :: for_each.

Ngoài ra, std :: for_each có thể bỏ qua các phần tử ở đầu hoặc cuối của một vùng chứa, ví dụ: bỏ qua phần tử đầu tiên của arr, std :: next có thể được sử dụng để bắt đầu phần tử tiếp theo.

std::for_each(std::next(arr.begin()), arr.end(), doubleNumber);
// Now arr is [1, 4, 6, 8]. The first element wasn't doubled.

Điều này là không thể với vòng lặp dựa trên phạm vi.

Giống như nhiều thuật toán, std :: for_each có thể được song song hóa để đạt được tốc độ xử lý nhanh hơn, làm cho nó phù hợp hơn với các dự án lớn và dữ liệu lớn hơn là vòng lặp dựa trên phạm vi.

5. Thứ tự thực hiện

Lưu ý rằng hầu hết các thuật toán trong thư viện thuật toán không đảm bảo một thứ tự thực thi cụ thể. Đối với các thuật toán như vậy, hãy cẩn thận để đảm bảo bất kỳ hàm nào bạn chuyển vào không giả sử một thứ tự cụ thể, vì thứ tự của lệnh gọi có thể không giống nhau trên mọi trình biên dịch.

Các thuật toán sau đảm bảo thực thi tuần tự: std :: for_each, std :: copy, std :: copy_backward, std :: move và std :: move_backward.

Bạn nên

Trừ khi được chỉ định khác, đừng giả sử rằng các thuật toán thư viện chuẩn sẽ thực thi theo một trình tự cụ thể. std :: for_each, std :: copy, std :: copy_backward, std :: move và std :: move_backward có đảm bảo tuần tự.

6. Phạm vi trong C ++ 20

Việc phải chuyển arr.begin () và arr.end () một cách rõ ràng cho mọi thuật toán là một chút khó chịu. Nhưng đừng sợ – C ++ 20 thêm các dải ô, cho phép chúng ta chỉ cần chuyển arr. Điều này sẽ làm cho code của chúng tôi thậm chí còn ngắn hơn và dễ đọc hơn.

7. Phần kết luận

Thư viện thuật toán có rất nhiều chức năng hữu ích có thể làm cho code của bạn đơn giản hơn và mạnh mẽ hơn. Chúng ta chỉ đề cập đến một tập hợp con nhỏ trong bài học này, nhưng vì hầu hết các hàm này hoạt động rất giống nhau, một khi bạn biết cách hoạt động của một vài hàm, bạn có thể sử dụng hầu hết chúng.

Bạn nên

Ủng hộ việc sử dụng các hàm từ thư viện thuật toán hơn là viết hàm của riêng bạn để làm điều tương tự

Cài ứng dụng cafedev để dễ dàng cập nhật tin và học lập trình mọi lúc mọi nơi tại đây.

Nguồn và Tài liệu tiếng anh tham khảo:

• cplusplus
• w3schools
• Geeksforgeeks
• learncpp

Tài liệu từ cafedev:

• Full series tự học C++ từ cơ bản tới nâng cao tại đây nha.
• Ebook về C++ tại đây.
• Các series tự học lập trình MIỄN PHÍ khác
• Nơi liên hệ hợp tác hoặc quảng cáo cùng Cafedevn tại đây.

Nếu bạn thấy hay và hữu ích, bạn có thể tham gia các kênh sau của cafedev để nhận được nhiều hơn nữa:

• Group Facebook
• Fanpage
• Youtube
• Instagram
• Twitter
• Linkedin
• Pinterest
• Trang chủ

Chào thân ái và quyết thắng!