set::begin() và set::end() trong C++ STL

std::set là container liên kết (thường là red-black tree) lưu trữ phần tử duy nhất, đã sắp xếp. begin() và end() trả về bidirectional iterator duyệt theo thứ tự tăng dần.

Đặc điểm

• begin(): iterator đến phần tử nhỏ nhất (first).
• end(): iterator past-the-end (sau phần tử lớn nhất).
• Phạm vi [begin(), end()) bao gồm tất cả phần tử theo thứ tự sort.
• Iterator là const – không thể sửa đổi giá trị qua iterator (key immutable).
• Có cbegin(), cend() (C++11), rbegin(), rend() (duyệt ngược).

Ví dụ

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s = {7, 6, 1, 4, 2, 9, 10}; // tự sắp xếp, unique

    cout << "Elements in order: ";
    for (auto it = s.begin(); it != s.end(); ++it)
        cout << *it << ' ';
    cout << endl;

    // Range-based for (C++11) tự dùng begin/end
    cout << "Range-based: ";
    for (int x : s) cout << x << ' ';
    cout << endl;

    // Duyệt ngược
    cout << "Reverse: ";
    for (auto it = s.rbegin(); it != s.rend(); ++it)
        cout << *it << ' ';
    cout << endl;

    return 0;
}

Kết quả

Elements in order: 1 2 4 6 7 9 10
Range-based: 1 2 4 6 7 9 10
Reverse: 10 9 7 6 4 2 1

Độ phức tạp

• begin(), end(): O(1).
• Duyệt toàn bộ: O(n).
• Tìm kiếm find(), lower_bound(): O(log n).

Lưu ý

• Không thể *it = new_value – key là const. Muốn sửa: erase + insert.
• set không hỗ trợ operator[] hay at().
• C++17: set::extract(), merge() chuyển node giữa set không copy.