Các container liên kết (associative containers) trong C++ khác biệt với các container tuyến tính như vector, list ở chỗ chúng lưu trữ dữ liệu dưới dạng cặp khóa-giá trị (key-value). Đặc điểm này giúp tối ưu hiệu suất tra cứu dữ liệu.

Cấu trúc cặp khóa-giá trị

Cặp khóa-giá trị (key-value pair) là cấu trúc cơ bản trong container liên kết. C++ cung cấp class std::pair để quản lý loại dữ liệu này, với thành phần first đại diện cho khóa và second là giá trị tương ứng. Hàm make_pair được sử dụng phổ biến để tạo đối tượng pair từ các giá trị đầu vào.

Container cây nhị phân cân bằng

Bốn container liên kết quan trọng trong STL:

1. set - tập hợp có thứ tự, không chứa phần tử trùng lặp
2. multiset - tương tự set nhưng cho phép phần tử trùng
3. map - từ điển dữ liệu theo khóa, mỗi khóa duy nhất
4. multimap - từ điển cho phép khóa trùng

Mọi container này đều sử dụng cấu trúc cây đỏ-đen (red-black tree) làm nền tảng để đảm bảo dữ liệu luôn được sắp xếp.

Ví dụ với set:

void víDụSet() {
    std::set<int> tậpHợp;
    tậpHợp.insert(30);
    tậpHợp.insert(15);
    
    // Tìm kiếm phần tử
    auto vịTrí = tậpHợp.find(15);
    if(vịTrí != tậpHợp.end()) {
        std::cout << "Phần tử tồn tại: " << *vịTrí << std::endl;
    }
    
    // Xóa phần tử
    tậpHợp.erase(30);
}

Ví dụ với map:

void víDụMap() {
    std::map<std::string, int> bảnĐồ;
    bảnĐồ["apple"] = 10;
    bảnĐồ["banana"] = 5;
    
    // Truy cập theo khóa
    std::cout << "Số lượng táo: " << bảnĐồ["apple"] << std::endl;
    
    // Duyệt bản đồ
    for(const auto& [khóa, giáTrị] : bảnĐồ) {
        std::cout << khóa << ": " << giáTrị << std::endl;
    }
}

Hàm hữu ích:

• lower_bound/upper_bound: Xác định phạm vi phần tử >= hoặc > giá trị
• equal_range: Trả về cặp iterators chỉ phạm vi các phần tử bằng giá trị
• erase: Hỗ trợ xóa theo vị trí, giá trị hoặc khoảng

Đặc điểm kỹ thuật