Các thuật toán của STL

Thuộc phần Lập trình hướng đối tượng trong hành trình C++ của Coddy. Bài học 73 trên 104.

Các thuật toán (algorithm) STL là những hàm mẫu (function template) hoạt động trên các phạm vi do bộ lặp (iterator) xác định. Chúng nằm trong các header <algorithm> và <numeric>, đồng thời hoạt động với mọi container có bộ lặp tương thích.

std::sort sắp xếp các phần tử theo thứ tự tăng dần theo mặc định:

#include <algorithm>
#include <vector>

std::vector<int> nums = {5, 2, 8, 1};
std::sort(nums.begin(), nums.end());
// nums: {1, 2, 5, 8}

std::find tìm một giá trị và trả về trình lặp đến kết quả khớp đầu tiên, hoặc end() nếu không tìm thấy:

auto it = std::find(nums.begin(), nums.end(), 5);
if (it != nums.end()) {
    std::cout << "Found at index: " << (it - nums.begin());
}

std::transform áp dụng một phép toán cho từng phần tử và lưu kết quả vào một phạm vi đích:

std::vector<int> doubled(nums.size());
std::transform(nums.begin(), nums.end(), doubled.begin(),
               [](int x) { return x * 2; });
// doubled: {2, 4, 10, 16}

std::accumulate trong <numeric> kết hợp tất cả phần tử thành một giá trị duy nhất:

#include <numeric>

int sum = std::accumulate(nums.begin(), nums.end(), 0);
// sum: 16 (1 + 2 + 5 + 8)

Các thuật toán (algorithm) này nhận phạm vi bộ lặp (iterator) thay vì nhận trực tiếp vùng chứa (container), nhờ đó chúng đủ linh hoạt để hoạt động trên các phạm vi con hoặc nhiều kiểu vùng chứa khác nhau bằng cùng một đoạn code.

Thử thách

Dễ

Hãy xây dựng một trình phân tích điểm, xử lý một tập hợp số bằng các thuật toán STL. Bạn sẽ tạo các hàm tiện ích để minh họa cách sort, find, transform và accumulate phối hợp với nhau để phân tích dữ liệu.

Bạn sẽ sắp xếp code trong hai tệp:

ScoreAnalyzer.h: Định nghĩa các hàm tiện ích dùng thuật toán STL để xử lý các vector số nguyên.
Tạo một hàm có tên sortScores, nhận một std::vector<int>& và sắp xếp vector theo thứ tự tăng dần bằng std::sort.

Tạo một hàm có tên findScore, nhận một const std::vector<int>& và một giá trị mục tiêu kiểu int. Dùng std::find để tìm giá trị mục tiêu. Nếu tìm thấy, trả về chỉ số (khoảng cách tính từ begin). Nếu không tìm thấy, trả về -1.

Tạo một hàm có tên applyBonus, nhận một const std::vector<int>& và một lượng điểm thưởng kiểu int. Dùng std::transform để tạo và trả về một vector mới, trong đó mỗi điểm được cộng thêm điểm thưởng.

Tạo một hàm có tên calculateAverage, nhận một const std::vector<int>& và trả về giá trị trung bình dưới dạng double. Dùng std::accumulate để tính tổng, sau đó chia cho kích thước vector.

Tạo một hàm có tên printVector, nhận một const std::vector<int>& và in ra tất cả phần tử, cách nhau bằng dấu cách, rồi xuống dòng.
main.cpp: Đọc sáu đầu vào, mỗi đầu vào nằm trên một dòng riêng:
1. Điểm thứ nhất (số nguyên)
2. Điểm thứ hai (số nguyên)
3. Điểm thứ ba (số nguyên)
4. Điểm thứ tư (số nguyên)
5. Một điểm cần tìm (số nguyên)
6. Một lượng điểm thưởng cần cộng (số nguyên)
Tạo một vector chứa bốn điểm và minh họa các thuật toán:
1. In Original:, theo sau là nội dung của vector
2. Sắp xếp các điểm rồi in Sorted:, theo sau là vector đã sắp xếp
3. Tìm điểm mục tiêu trong vector đã sắp xếp. Nếu tìm thấy, in Found <value> at index <index>. Nếu không tìm thấy, in <value> not found
4. Cộng điểm thưởng vào các điểm đã sắp xếp rồi in With bonus:, theo sau là vector mới
5. Tính và in giá trị trung bình của các điểm đã sắp xếp ban đầu (trước khi cộng điểm thưởng) dưới dạng Average: <value>, với một chữ số thập phân

Ví dụ, với các đầu vào 75, 90, 60, 85, 85 và 5:

Original: 75 90 60 85 
Sorted: 60 75 85 90 
Found 85 at index 2
With bonus: 65 80 90 95 
Average: 77.5

Với các đầu vào 100, 80, 95, 70, 50 và 10:

Original: 100 80 95 70 
Sorted: 70 80 95 100 
50 not found
With bonus: 80 90 105 110 
Average: 86.2

Nhớ thêm <algorithm> để dùng sort, find và transform</code; thêm <code><numeric> để dùng accumulate. Dùng std::fixed và std::setprecision(1) từ <iomanip> để định dạng giá trị trung bình.

Tự làm thử

#include <iostream>
#include <vector>
#include <iomanip>
#include "ScoreAnalyzer.h"

using namespace std;

int main() {
    // Đọc sáu giá trị đầu vào
    int score1, score2, score3, score4;
    int searchTarget, bonusAmount;
    
    cin >> score1;
    cin >> score2;
    cin >> score3;
    cin >> score4;
    cin >> searchTarget;
    cin >> bonusAmount;
    
    // TODO: Tạo một vector chứa bốn điểm số
    
    // TODO: In "Original:", sau đó in các phần tử của vector
    
    // TODO: Sắp xếp các điểm số rồi in "Sorted:", sau đó in vector đã sắp xếp
    
    // TODO: Tìm điểm số mục tiêu trong vector đã sắp xếp
    // Nếu tìm thấy, in "Found <value> at index <index>"
    // Nếu không tìm thấy, in "<value> not found"
    
    // TODO: Cộng điểm thưởng vào các điểm số đã sắp xếp rồi in "With bonus:", sau đó in vector mới
    
    // TODO: Tính và in điểm trung bình của các điểm số đã sắp xếp (trước khi cộng điểm thưởng)
    // Dùng fixed và setprecision(1) để định dạng
    // In theo mẫu "Average: <value>"
    
    return 0;
}