🔧 STL Algorithms — Tổng quan

C++ STL cung cấp hơn 100 algorithms sẵn có. Thay vì viết loops thủ công, bạn dùng các hàm đã được tối ưu và test kỹ.

---

Philosophy: Algorithms + Iterators + Containers

┌─────────────────────────────────────────────────────────────────┐
│                    STL ARCHITECTURE                             │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│   CONTAINERS                ITERATORS              ALGORITHMS  │
│   ──────────               ──────────             ───────────  │
│   vector                      ↓                    sort        │
│   list          ────►    begin/end    ────►        find        │
│   map                         ↓                    transform   │
│   set                  (abstraction)               accumulate  │
│                                                    copy        │
│                                                    ...         │
│                                                                 │
│  Algorithms KHÔNG biết container cụ thể!                       │
│  Chúng chỉ làm việc với iterators.                             │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

---

Headers

#include <algorithm>  // sort, find, transform, copy, ...
#include <numeric>    // accumulate, iota, partial_sum, ...
#include <functional> // std::greater, std::less, std::function

---

Algorithm Categories

1. Non-Modifying Sequence Operations

Algorithm	Description
std::find	Tìm phần tử đầu tiên khớp
std::find_if	Tìm phần tử thỏa điều kiện
std::count	Đếm occurrences
std::count_if	Đếm theo điều kiện
std::all_of	Kiểm tra tất cả thỏa predicate
std::any_of	Kiểm tra có ít nhất 1 thỏa
std::none_of	Kiểm tra không có ai thỏa
std::for_each	Thực thi function cho mỗi element

2. Modifying Sequence Operations

Algorithm	Description
std::copy	Copy elements
std::transform	Transform và output
std::fill	Fill với 1 giá trị
std::generate	Generate với function
std::replace	Replace giá trị
std::remove	Remove (cần erase sau)
std::unique	Remove consecutive duplicates
std::reverse	Đảo ngược
std::rotate	Xoay elements

3. Sorting Operations

Algorithm	Description
std::sort	Sort range
std::stable_sort	Sort giữ relative order
std::partial_sort	Sort first N
std::nth_element	Partition at nth
std::is_sorted	Check if sorted

4. Binary Search (on sorted ranges)

Algorithm	Description
std::binary_search	Check if exists
std::lower_bound	First not less than
std::upper_bound	First greater than
std::equal_range	Both bounds

5. Numeric Operations (<numeric>)

Algorithm	Description
std::accumulate	Sum/reduce
std::inner_product	Dot product
std::partial_sum	Prefix sums
std::adjacent_difference	Differences
std::iota	Fill with incrementing values

---

Quick Examples

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

int main() {
    std::vector<int> v = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    
    // Sort
    std::sort(v.begin(), v.end());
    // [1, 2, 3, 4, 5, 6, 7, 8, 9]
    
    // Find
    auto it = std::find(v.begin(), v.end(), 5);
    if (it != v.end()) {
        std::cout << "Found at index: " << (it - v.begin()) << std::endl;
    }
    
    // Sum
    int sum = std::accumulate(v.begin(), v.end(), 0);
    std::cout << "Sum: " << sum << std::endl;  // 45
    
    // Count
    int count = std::count_if(v.begin(), v.end(), 
                              [](int x) { return x > 5; });
    std::cout << "Count > 5: " << count << std::endl;  // 4
    
    // Transform (double each)
    std::transform(v.begin(), v.end(), v.begin(),
                   [](int x) { return x * 2; });
    
    return 0;
}

---

Part 2 Structure

Topic	Description
Lambda Expressions	Extensive lambda tutorial
Sorting & Comparators	Custom sort rules
Searching	find, binary_search
Transform & Reduce	Functional operations
Code Golf	STL power demonstrations

---

➡️ Tiếp theo

Tiếp theo: Lambda Expressions — Học cách viết inline functions.

🧠 Quiz

Câu 1: Đoạn code sau in ra gì?

std::vector<int> v = {1, 2, 3, 4, 5};
int result = std::accumulate(v.begin(), v.end(), 10);
std::cout << result;

• [ ] A) 15
• [x] B) 25
• [ ] C) 10
• [ ] D) 0

💡 Giải thích: std::accumulate(begin, end, init) tính tổng bắt đầu từ giá trị init. Ở đây init = 10, tổng các phần tử = 1+2+3+4+5 = 15, kết quả = 10 + 15 = 25. Tham số thứ 3 là giá trị khởi tạo, không phải bị bỏ qua.

Câu 2: std::find trả về gì khi không tìm thấy phần tử?

std::vector<int> v = {1, 2, 3};
auto it = std::find(v.begin(), v.end(), 99);

• [ ] A) nullptr
• [ ] B) Iterator trỏ tới phần tử cuối
• [x] C) v.end() — past-the-end iterator
• [ ] D) Throw exception std::out_of_range

💡 Giải thích: Khi không tìm thấy, std::find trả về iterator bằng tham số last (ở đây là v.end()). Đây là convention chuẩn của STL — luôn kiểm tra if (it != v.end()) trước khi dereference. Không bao giờ throw exception.

Câu 3: std::transform dùng để làm gì?

std::vector<int> v = {1, 2, 3};
std::vector<int> out(3);
std::transform(v.begin(), v.end(), out.begin(), [](int x) { return x * x; });

• [x] A) Áp dụng function lên mỗi phần tử và lưu kết quả vào output range
• [ ] B) Lọc các phần tử thỏa điều kiện
• [ ] C) Sắp xếp vector theo custom comparator
• [ ] D) Tính tổng các phần tử sau khi biến đổi

💡 Giải thích: std::transform áp dụng một function/lambda lên mỗi phần tử trong input range và ghi kết quả vào output range. Ở đây, out sẽ chứa {1, 4, 9}. Nó giống map() trong functional programming. Lưu ý output range phải đủ lớn để chứa kết quả.