Algorithms - Thuật toán STL

📖 Giới thiệu

STL cung cấp một bộ sưu tập phong phú các algorithms có thể áp dụng cho containers thông qua iterators. Các algorithms này được thiết kế generic và hiệu quả.

Ví dụ đơn giản đầu tiên

cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> numbers = {5, 2, 8, 1, 9, 3};
    
    // Sắp xếp
    sort(numbers.begin(), numbers.end());
    
    // Tìm kiếm
    auto it = find(numbers.begin(), numbers.end(), 8);
    if (it != numbers.end()) {
        cout << "Tìm thấy 8 tại vị trí " << (it - numbers.begin()) << endl;
    }
    
    // Hiển thị
    for (int x : numbers) {
        cout << x << " ";
    }
    cout << endl;
    
    return 0;
}

🔧 Các nhóm Algorithm chính

1. Non-modifying algorithms

cpp

find(begin, end, value);           // Tìm kiếm
find_if(begin, end, predicate);    // Tìm với điều kiện
count(begin, end, value);          // Đếm phần tử
count_if(begin, end, predicate);   // Đếm với điều kiện
for_each(begin, end, function);    // Áp dụng function

2. Modifying algorithms

cpp

copy(src_begin, src_end, dest);    // Sao chép
transform(begin, end, dest, func); // Biến đổi
replace(begin, end, old, new);     // Thay thế
remove(begin, end, value);         // Xóa (không thực sự xóa)
unique(begin, end);                // Xóa duplicate liên tiếp

3. Sorting algorithms

cpp

sort(begin, end);                  // Sắp xếp
partial_sort(begin, middle, end);  // Sắp xếp một phần
nth_element(begin, nth, end);      // Tìm element thứ n

4. Binary search (on sorted ranges)

cpp

binary_search(begin, end, value);  // Kiểm tra tồn tại
lower_bound(begin, end, value);    // Vị trí đầu tiên >= value
upper_bound(begin, end, value);    // Vị trí đầu tiên > value

💻 Ví dụ minh họa

Ví dụ 1: Data Analysis Tool

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <iomanip>
using namespace std;

class DataAnalyzer {
private:
    vector<double> data;
    
public:
    void add_data(const vector<double>& new_data) {
        data.insert(data.end(), new_data.begin(), new_data.end());
        cout << "✅ Đã thêm " << new_data.size() << " điểm dữ liệu" << endl;
    }
    
    void print_data() const {
        cout << "\n📊 DỮ LIỆU (" << data.size() << " điểm):" << endl;
        for (int i = 0; i < data.size(); i++) {
            cout << fixed << setprecision(2) << data[i];
            if ((i + 1) % 10 == 0) cout << endl;
            else cout << " ";
        }
        if (data.size() % 10 != 0) cout << endl;
    }
    
    void basic_statistics() const {
        if (data.empty()) {
            cout << "❌ Không có dữ liệu!" << endl;
            return;
        }
        
        cout << "\n📈 THỐNG KÊ CƠ BẢN:" << endl;
        
        // Min/Max
        auto minmax_pair = minmax_element(data.begin(), data.end());
        cout << "Min: " << fixed << setprecision(2) << *minmax_pair.first << endl;
        cout << "Max: " << fixed << setprecision(2) << *minmax_pair.second << endl;
        
        // Sum và Average
        double sum = accumulate(data.begin(), data.end(), 0.0);
        cout << "Tổng: " << sum << endl;
        cout << "Trung bình: " << (sum / data.size()) << endl;
        
        // Median
        vector<double> sorted_data = data;
        sort(sorted_data.begin(), sorted_data.end());
        
        double median;
        if (sorted_data.size() % 2 == 0) {
            median = (sorted_data[sorted_data.size()/2 - 1] + sorted_data[sorted_data.size()/2]) / 2.0;
        } else {
            median = sorted_data[sorted_data.size()/2];
        }
        cout << "Median: " << median << endl;
        
        // Count các giá trị đặc biệt
        int positive_count = count_if(data.begin(), data.end(), [](double x) { return x > 0; });
        int negative_count = count_if(data.begin(), data.end(), [](double x) { return x < 0; });
        int zero_count = count(data.begin(), data.end(), 0.0);
        
        cout << "Số dương: " << positive_count << endl;
        cout << "Số âm: " << negative_count << endl;
        cout << "Số 0: " << zero_count << endl;
    }
    
    void transform_data() {
        cout << "\n🔄 BIẾN ĐỔI DỮ LIỆU:" << endl;
        
        // Lưu bản gốc
        vector<double> original = data;
        
        // 1. Absolute values
        vector<double> abs_data = data;
        transform(abs_data.begin(), abs_data.end(), abs_data.begin(), 
                 [](double x) { return abs(x); });
        
        cout << "1. Giá trị tuyệt đối:" << endl;
        cout << "   Trước: ";
        for (int i = 0; i < min(5, (int)data.size()); i++) {
            cout << fixed << setprecision(1) << data[i] << " ";
        }
        cout << endl;
        cout << "   Sau:   ";
        for (int i = 0; i < min(5, (int)abs_data.size()); i++) {
            cout << fixed << setprecision(1) << abs_data[i] << " ";
        }
        cout << endl;
        
        // 2. Square
        vector<double> squared_data = data;
        transform(squared_data.begin(), squared_data.end(), squared_data.begin(),
                 [](double x) { return x * x; });
        
        // 3. Normalization (0-1 range)
        auto minmax = minmax_element(data.begin(), data.end());
        double range = *minmax.second - *minmax.first;
        
        vector<double> normalized_data = data;
        if (range > 0) {
            transform(normalized_data.begin(), normalized_data.end(), normalized_data.begin(),
                     [minmax, range](double x) { return (x - *minmax.first) / range; });
        }
        
        cout << "2. Chuẩn hóa 0-1: ";
        for (int i = 0; i < min(5, (int)normalized_data.size()); i++) {
            cout << fixed << setprecision(2) << normalized_data[i] << " ";
        }
        cout << endl;
    }
    
    void search_operations() {
        if (data.empty()) return;
        
        cout << "\n🔍 THAO TÁC TÌM KIẾM:" << endl;
        
        // Sắp xếp cho binary search
        vector<double> sorted_data = data;
        sort(sorted_data.begin(), sorted_data.end());
        
        // Tìm giá trị cụ thể
        double target = sorted_data[sorted_data.size() / 2]; // Lấy median làm target
        
        // Linear search
        auto linear_result = find(data.begin(), data.end(), target);
        cout << "Linear search cho " << target << ": " 
             << (linear_result != data.end() ? "Tìm thấy" : "Không tìm thấy") << endl;
        
        // Binary search
        bool binary_result = binary_search(sorted_data.begin(), sorted_data.end(), target);
        cout << "Binary search cho " << target << ": " 
             << (binary_result ? "Tìm thấy" : "Không tìm thấy") << endl;
        
        // Range queries
        double lower_val = target - 1.0;
        double upper_val = target + 1.0;
        
        auto lower_it = lower_bound(sorted_data.begin(), sorted_data.end(), lower_val);
        auto upper_it = upper_bound(sorted_data.begin(), sorted_data.end(), upper_val);
        
        int count_in_range = upper_it - lower_it;
        cout << "Số phần tử trong khoảng [" << lower_val << ", " << upper_val << "]: " 
             << count_in_range << endl;
        
        // Find if condition
        auto first_negative = find_if(sorted_data.begin(), sorted_data.end(),
                                     [](double x) { return x < 0; });
        if (first_negative != sorted_data.end()) {
            cout << "Số âm đầu tiên: " << *first_negative << endl;
        }
    }
    
    void sorting_demos() {
        if (data.empty()) return;
        
        cout << "\n🔢 DEMO SẮP XẾP:" << endl;
        
        // 1. Sort tăng dần
        vector<double> asc_data = data;
        sort(asc_data.begin(), asc_data.end());
        cout << "Tăng dần (5 đầu): ";
        for (int i = 0; i < min(5, (int)asc_data.size()); i++) {
            cout << fixed << setprecision(1) << asc_data[i] << " ";
        }
        cout << endl;
        
        // 2. Sort giảm dần
        vector<double> desc_data = data;
        sort(desc_data.begin(), desc_data.end(), greater<double>());
        cout << "Giảm dần (5 đầu): ";
        for (int i = 0; i < min(5, (int)desc_data.size()); i++) {
            cout << fixed << setprecision(1) << desc_data[i] << " ";
        }
        cout << endl;
        
        // 3. Partial sort - chỉ sort 5 phần tử đầu
        vector<double> partial_data = data;
        partial_sort(partial_data.begin(), partial_data.begin() + min(5, (int)partial_data.size()), 
                    partial_data.end());
        cout << "Partial sort (5 nhỏ nhất): ";
        for (int i = 0; i < min(5, (int)partial_data.size()); i++) {
            cout << fixed << setprecision(1) << partial_data[i] << " ";
        }
        cout << endl;
        
        // 4. nth_element - tìm element thứ n
        if (data.size() > 3) {
            vector<double> nth_data = data;
            nth_element(nth_data.begin(), nth_data.begin() + 3, nth_data.end());
            cout << "Element thứ 4 nhỏ nhất: " << nth_data[3] << endl;
        }
    }
    
    void filtering_operations() {
        if (data.empty()) return;
        
        cout << "\n🔧 THAO TÁC LỌC DỮ LIỆU:" << endl;
        
        // Remove negative values (không thực sự xóa)
        vector<double> filtered_data = data;
        auto new_end = remove_if(filtered_data.begin(), filtered_data.end(),
                                [](double x) { return x < 0; });
        filtered_data.erase(new_end, filtered_data.end());
        
        cout << "Sau khi loại bỏ số âm: " << filtered_data.size() << " phần tử" << endl;
        
        // Copy if - sao chép phần tử thỏa mãn điều kiện
        vector<double> positive_data;
        copy_if(data.begin(), data.end(), back_inserter(positive_data),
               [](double x) { return x > 0; });
        
        cout << "Chỉ số dương: " << positive_data.size() << " phần tử" << endl;
        
        // Unique - xóa duplicate liên tiếp
        vector<double> unique_data = data;
        sort(unique_data.begin(), unique_data.end());
        auto unique_end = unique(unique_data.begin(), unique_data.end());
        unique_data.erase(unique_end, unique_data.end());
        
        cout << "Sau khi xóa duplicate: " << unique_data.size() << " phần tử duy nhất" << endl;
    }
    
    void advanced_operations() {
        if (data.empty()) return;
        
        cout << "\n⚡ THAO TÁC NÂNG CAO:" << endl;
        
        // Partition - chia thành 2 nhóm
        vector<double> partition_data = data;
        auto partition_point = partition(partition_data.begin(), partition_data.end(),
                                       [](double x) { return x >= 0; });
        
        int positive_count = partition_point - partition_data.begin();
        cout << "Partition (>=0 | <0): " << positive_count << " | " 
             << (partition_data.size() - positive_count) << endl;
        
        // All/Any/None of
        bool all_positive = all_of(data.begin(), data.end(), [](double x) { return x > 0; });
        bool any_negative = any_of(data.begin(), data.end(), [](double x) { return x < 0; });
        bool none_zero = none_of(data.begin(), data.end(), [](double x) { return x == 0; });
        
        cout << "Tất cả dương: " << (all_positive ? "Có" : "Không") << endl;
        cout << "Có số âm: " << (any_negative ? "Có" : "Không") << endl;
        cout << "Không có số 0: " << (none_zero ? "Đúng" : "Sai") << endl;
        
        // Generate sequences
        vector<int> sequence(10);
        iota(sequence.begin(), sequence.end(), 1); // 1, 2, 3, ..., 10
        
        cout << "Dãy số tự động: ";
        for (int x : sequence) cout << x << " ";
        cout << endl;
    }
    
    void clear_data() {
        data.clear();
        cout << "🗑️ Đã xóa toàn bộ dữ liệu" << endl;
    }
    
    size_t size() const {
        return data.size();
    }
};

int main() {
    cout << "=== DATA ANALYSIS WITH STL ALGORITHMS ===" << endl;
    
    DataAnalyzer analyzer;
    
    // Thêm dữ liệu mẫu
    vector<double> sample_data = {
        3.5, -2.1, 8.7, -1.4, 6.2, 0.0, 4.8, -3.6, 7.1, 2.9,
        -0.5, 5.3, 1.8, -4.2, 9.1, 0.7, -1.8, 6.4, 3.2, -2.7
    };
    
    analyzer.add_data(sample_data);
    analyzer.print_data();
    
    // Thống kê cơ bản
    analyzer.basic_statistics();
    
    // Biến đổi dữ liệu
    analyzer.transform_data();
    
    // Tìm kiếm
    analyzer.search_operations();
    
    // Sắp xếp
    analyzer.sorting_demos();
    
    // Lọc dữ liệu
    analyzer.filtering_operations();
    
    // Thao tác nâng cao
    analyzer.advanced_operations();
    
    return 0;
}

🏋️ Thực hành

Bài tập 1: Text Processing

Sử dụng STL algorithms để:

Đếm từ, ký tự
Tìm từ dài nhất/ngắn nhất
Loại bỏ duplicate words

Bài tập 2: Grade Analytics

Phân tích điểm với:

Percentile calculations
Grade distribution
Outlier detection

Bài tập 3: Performance Comparison

So sánh hiệu suất các algorithms:

Linear vs binary search
Different sorting algorithms
Custom vs STL implementations

📋 Tóm tắt

STL Algorithms: Generic, iterator-based functions
Categories: Non-modifying, modifying, sorting, searching
Key Concepts: Iterators, predicates, function objects
Benefits: Tested, optimized, readable code

Bài tiếp theo: Iterators - Container navigation patterns.

Algorithms - Thuật toán STL ​

📖 Giới thiệu ​

Ví dụ đơn giản đầu tiên ​

🔧 Các nhóm Algorithm chính ​

1. Non-modifying algorithms ​

2. Modifying algorithms ​

3. Sorting algorithms ​

4. Binary search (on sorted ranges) ​

💻 Ví dụ minh họa ​

Ví dụ 1: Data Analysis Tool ​

🏋️ Thực hành ​

Bài tập 1: Text Processing ​

Bài tập 2: Grade Analytics ​

Bài tập 3: Performance Comparison ​

📋 Tóm tắt ​