Khóa học CTDL và GT

Bài 6.2. Set, Map và các thao tác cơ bản

Chào mừng quay trở lại với chuỗi bài về Cấu trúc dữ liệu và Giải thuật!

Trong thế giới lập trình, việc lưu trữ và quản lý dữ liệu hiệu quả là chìa khóa thành công. Chúng ta đã đi qua các cấu trúc tuyến tính như Array, Vector hay List. Hôm nay, chúng ta sẽ khám phá hai "công cụ" cực kỳ mạnh mẽ và phổ biến khác trong C++ Standard Template Library (STL): Set và Map.

Set và Map giải quyết những bài toán cụ thể mà các cấu trúc tuyến tính gặp khó khăn, đặc biệt là khi cần đảm bảo tính duy nhất hoặc cần truy cập dữ liệu dựa trên một định danh đặc trưng.

Hãy cùng đi sâu vào từng loại!

Set: Tập hợp của những phần tử "Độc nhất"

Set là một cấu trúc dữ liệu lưu trữ một tập hợp các phần tử duy nhất. Điều này có nghĩa là mỗi phần tử chỉ xuất hiện tối đa một lần trong Set. Nếu bạn cố gắng thêm một phần tử đã tồn tại, thao tác đó sẽ bị bỏ qua.

Điểm đặc biệt của std::set trong C++ STL là các phần tử được lưu trữ có thứ tự. Theo mặc định, chúng được sắp xếp tăng dần.

Đặc điểm chính của std::set:

• Duy nhất: Không cho phép các phần tử trùng lặp.
• Có thứ tự: Các phần tử được sắp xếp theo một thứ tự nhất định (mặc định là tăng dần).
• Hiệu quả: Các thao tác cơ bản như thêm (insert), xóa (erase), tìm kiếm (find/count) thường có độ phức tạp thời gian là O(log n), với n là số lượng phần tử trong set. Điều này là do std::set thường được cài đặt dựa trên các cấu trúc cây tìm kiếm cân bằng như Red-Black Tree.

Các thao tác cơ bản với std::set trong C++

Để sử dụng std::set, bạn cần include header <set>.

1. Khai báo và Khởi tạo:

Bạn khai báo một Set bằng cách chỉ định kiểu dữ liệu của các phần tử mà nó sẽ lưu trữ:

#include <set>
#include <iostream>
#include <string>

int main() {
    // Khai báo một set lưu trữ số nguyên
    std::set<int> ages;

    // Khai báo một set lưu trữ chuỗi ký tự
    std::set<std::string> uniqueNames;

    // Khai báo và khởi tạo Set với các giá trị ban đầu (từ initializer list C++11)
    std::set<double> temperatures = { 25.5, 28.0, 25.5, 22.1 }; // Lưu ý: 25.5 sẽ chỉ được thêm 1 lần

    // In các phần tử trong temperatures để kiểm tra
    std::cout << "Temperatures Set: ";
    for (double temp : temperatures) {
        std::cout << temp << " ";
    }
    std::cout << std::endl; // Output sẽ là: 22.1 25.5 28

    return 0;
}

Giải thích: Đoạn code trên minh họa cách khai báo các set với các kiểu dữ liệu khác nhau. Khi khởi tạo temperatures với { 25.5, 28.0, 25.5, 22.1 }, giá trị 25.5 bị trùng lặp nên chỉ có một bản sao được thêm vào set. Khi in ra, các phần tử được sắp xếp theo thứ tự tăng dần (22.1, 25.5, 28).

2. Thêm phần tử (insert):

Sử dụng phương thức insert() để thêm một phần tử vào Set. Nếu phần tử đã tồn tại, Set sẽ không thay đổi.

#include <set>
#include <iostream>

int main() {
    std::set<int> mySet;

    // Thêm các phần tử
    mySet.insert(10);
    mySet.insert(5);
    mySet.insert(20);
    mySet.insert(5); // Thêm lại số 5

    // In các phần tử trong Set
    std::cout << "Elements in mySet: ";
    for (int val : mySet) {
        std::cout << val << " ";
    }
    std::cout << std::endl; // Output: 5 10 20

    // Thêm phần tử và kiểm tra kết quả
    auto result = mySet.insert(30); // result là một pair<iterator, bool>
    if (result.second) {
        std::cout << "Inserted 30 successfully." << std::endl; // second là true nếu thêm thành công
    } else {
        std::cout << "Failed to insert 30 (already exists)." << std::endl; // second là false nếu phần tử đã tồn tại
    }

    result = mySet.insert(10); // Thêm lại số 10
     if (result.second) {
        std::cout << "Inserted 10 successfully." << std::endl;
    } else {
        std::cout << "Failed to insert 10 (already exists)." << std::endl; // Sẽ vào đây
    }


    return 0;
}

Giải thích: Phương thức insert trả về một std::pair. Phần tử .first là một iterator trỏ đến vị trí của phần tử được thêm vào (hoặc phần tử đã tồn tại nếu không thêm được). Phần tử .second là một giá trị boolean, true nếu phần tử được thêm mới, false nếu phần tử đã tồn tại và không có gì thay đổi.

3. Xóa phần tử (erase):

Sử dụng phương thức erase() để xóa một phần tử. Bạn có thể xóa theo giá trị hoặc theo iterator.

#include <set>
#include <iostream>

int main() {
    std::set<int> mySet = {10, 5, 20, 15, 25};

    std::cout << "Set initially: ";
    for (int val : mySet) std::cout << val << " ";
    std::cout << std::endl; // Output: 5 10 15 20 25

    // Xóa phần tử có giá trị 15
    size_t elements_erased = mySet.erase(15); // Trả về số phần tử đã xóa (0 hoặc 1)
    if (elements_erased > 0) {
        std::cout << "Erased 15." << std::endl;
    } else {
        std::cout << "15 not found." << std::endl;
    }

    std::cout << "Set after erasing 15: ";
    for (int val : mySet) std::cout << val << " ";
    std::cout << std::endl; // Output: 5 10 20 25

    // Xóa phần tử không tồn tại (ví dụ: 100)
    elements_erased = mySet.erase(100);
     if (elements_erased > 0) {
        std::cout << "Erased 100." << std::endl;
    } else {
        std::cout << "100 not found." << std::endl; // Sẽ vào đây
    }

    // Xóa phần tử sử dụng iterator (ví dụ: xóa phần tử đầu tiên)
    if (!mySet.empty()) {
        auto it = mySet.begin(); // Lấy iterator đến phần tử đầu tiên (số 5)
        mySet.erase(it);
        std::cout << "Erased first element." << std::endl;
    }

     std::cout << "Set after erasing first element: ";
    for (int val : mySet) std::cout << val << " ";
    std::cout << std::endl; // Output: 10 20 25


    return 0;
}

Giải thích: Phương thức erase(value) trả về số lượng phần tử đã bị xóa (luôn là 0 hoặc 1 với std::set). Phương thức erase(iterator) xóa phần tử tại vị trí iterator đó trỏ tới.

4. Tìm kiếm phần tử (find, count):

• find(value): Trả về một iterator trỏ đến phần tử nếu tìm thấy, hoặc mySet.end() nếu không tìm thấy.
• count(value): Trả về số lần xuất hiện của phần tử (luôn là 0 hoặc 1 với std::set). Thường dùng để kiểm tra sự tồn tại.

#include <set>
#include <iostream>

int main() {
    std::set<int> mySet = {10, 5, 20};

    // Tìm kiếm bằng count
    if (mySet.count(10)) {
        std::cout << "10 is in the set." << std::endl;
    } else {
        std::cout << "10 is not in the set." << std::endl;
    }

     if (mySet.count(15)) {
        std::cout << "15 is in the set." << std::endl;
    } else {
        std::cout << "15 is not in the set." << std::endl; // Sẽ vào đây
    }

    // Tìm kiếm bằng find
    auto it = mySet.find(20);
    if (it != mySet.end()) {
        std::cout << "Found 20 in the set." << std::endl;
    } else {
        std::cout << "Did not find 20." << std::endl;
    }

    it = mySet.find(25);
    if (it != mySet.end()) {
        std::cout << "Found 25 in the set." << std::endl;
    } else {
        std::cout << "Did not find 25." << std::endl; // Sẽ vào đây
    }

    return 0;
}

Giải thích: count(value) là cách đơn giản và hiệu quả nhất để kiểm tra xem một phần tử có tồn tại trong std::set hay không. find(value) hữu ích khi bạn cần lấy iterator đến vị trí của phần tử đó (ví dụ: để xóa nó).

5. Kích thước và trạng thái rỗng (size, empty):

• size(): Trả về số lượng phần tử trong Set.
• empty(): Trả về true nếu Set rỗng, false nếu ngược lại.

#include <set>
#include <iostream>

int main() {
    std::set<int> mySet = {10, 5, 20};

    std::cout << "Size of set: " << mySet.size() << std::endl; // Output: 3

    if (!mySet.empty()) {
        std::cout << "Set is not empty." << std::endl;
    }

    mySet.clear(); // Xóa tất cả phần tử
    std::cout << "Size of set after clearing: " << mySet.size() << std::endl; // Output: 0

    if (mySet.empty()) {
        std::cout << "Set is now empty." << std::endl;
    }

    return 0;
}

Giải thích: Các phương thức này giúp bạn kiểm tra trạng thái và kích thước hiện tại của Set.

Biến thể std::unordered_set

Ngoài std::set (sắp xếp), C++ còn cung cấp std::unordered_set. std::unordered_set lưu trữ các phần tử duy nhất nhưng không đảm bảo thứ tự. Nó thường được cài đặt dựa trên bảng băm (hash table).

Ưu điểm của std::unordered_set là các thao tác trung bình có độ phức tạp thời gian là O(1) (hằng số), nhanh hơn O(log n) của std::set, đặc biệt với dữ liệu lớn. Tuy nhiên, trong trường hợp xấu nhất (ví dụ: tất cả các phần tử có cùng mã băm - hash collision), hiệu suất có thể giảm xuống O(n).

Khi nào dùng std::set và khi nào dùng std::unordered_set?

• Dùng std::set khi bạn cần các phần tử phải được sắp xếp hoặc cần hiệu suất O(log n) được đảm bảo trong mọi trường hợp (worst-case).
• Dùng std::unordered_set khi bạn chỉ cần các phần tử duy nhất và ưu tiên hiệu suất trung bình O(1) hơn thứ tự của các phần tử.

Cách sử dụng std::unordered_set tương tự như std::set, chỉ cần include header <unordered_set>.

#include <unordered_set>
#include <iostream>
#include <string>

int main() {
    // Khai báo một unordered_set
    std::unordered_set<std::string> colors = {"red", "blue", "green", "red"}; // "red" chỉ thêm 1 lần

    std::cout << "Colors in unordered_set (order not guaranteed): ";
    for (const std::string& color : colors) {
        std::cout << color << " ";
    }
    std::cout << std::endl; // Thứ tự in ra có thể khác nhau mỗi lần chạy

    // Các thao tác tương tự:
    colors.insert("yellow"); // O(1) trung bình
    if (colors.count("blue")) { // O(1) trung bình
        std::cout << "Blue is in the set." << std::endl;
    }
    colors.erase("green"); // O(1) trung bình

    std::cout << "Colors after modifications: ";
    for (const std::string& color : colors) {
        std::cout << color << " ";
    }
    std::cout << std::endl;

    return 0;
}

Giải thích: std::unordered_set hoạt động giống std::set về mặt đảm bảo tính duy nhất và các phương thức cơ bản (insert, erase, count, find), nhưng thứ tự của các phần tử khi duyệt qua là không xác định do cách lưu trữ bằng bảng băm.

Map: Ánh xạ Khóa tới Giá trị

Trong khi Set lưu trữ các phần tử duy nhất, Map lại lưu trữ các cặp khóa-giá trị (key-value pairs). Mỗi cặp bao gồm một khóa duy nhất (key) và một giá trị (value) được liên kết với khóa đó. Bạn có thể dùng khóa để tra cứu hoặc truy cập nhanh chóng đến giá trị tương ứng.

Hãy hình dung Map như một cuốn từ điển, nơi mỗi từ (khóa) được ánh xạ tới định nghĩa của nó (giá trị).

Tương tự như Set, C++ cung cấp hai loại Map chính trong STL: std::map và std::unordered_map.

Đặc điểm chính của std::map:

• Khóa duy nhất: Mỗi khóa chỉ xuất hiện tối đa một lần.
• Có thứ tự: Các cặp khóa-giá trị được sắp xếp dựa trên thứ tự của khóa.
• Hiệu quả: Các thao tác cơ bản trên khóa (thêm, xóa, tìm kiếm) thường có độ phức tạp thời gian là O(log n), do std::map cũng được cài đặt dựa trên cây tìm kiếm cân bằng.

Các thao tác cơ bản với std::map trong C++

Để sử dụng std::map, bạn cần include header <map>.

1. Khai báo và Khởi tạo:

Bạn khai báo một Map bằng cách chỉ định kiểu dữ liệu của khóa và kiểu dữ liệu của giá trị: std::map<Kieu_Khoa, Kieu_Gia_Tri>.

#include <map>
#include <iostream>
#include <string>

int main() {
    // Khai báo một map ánh xạ tên học sinh (string) tới điểm số (int)
    std::map<std::string, int> studentScores;

    // Khai báo một map ánh xạ mã sản phẩm (int) tới giá (double)
    std::map<int, double> productPrices;

    // Khai báo và khởi tạo Map với các giá trị ban đầu
    std::map<char, int> letterCounts = { {'a', 1}, {'b', 2}, {'c', 1} }; // Khóa 'a' và 'c' duy nhất

    // In các cặp khóa-giá trị trong letterCounts
    std::cout << "Letter Counts Map: ";
    for (const auto& pair : letterCounts) {
        std::cout << "{" << pair.first << ": " << pair.second << "} ";
    }
    std::cout << std::endl; // Output sẽ được sắp xếp theo khóa: {a: 1} {b: 2} {c: 1}

    return 0;
}

Giải thích: Map lưu trữ các cặp. pair.first là khóa, pair.second là giá trị. std::map tự động sắp xếp các cặp dựa trên khóa.

2. Thêm phần tử:

Có nhiều cách để thêm cặp khóa-giá trị vào Map:

• Sử dụng toán tử []: myMap[key] = value;. Nếu khóa chưa tồn tại, nó sẽ được thêm mới. Nếu khóa đã tồn tại, giá trị cũ sẽ bị ghi đè.
• Sử dụng phương thức insert(): Thêm một std::pair hoặc một std::map::value_type (tương đương với std::pair<const Key, Value>). Phương thức này chỉ thêm cặp mới nếu khóa chưa tồn tại.

#include <map>
#include <iostream>
#include <string>

int main() {
    std::map<std::string, int> studentScores;

    // Cách 1: Sử dụng toán tử []
    studentScores["Alice"] = 95; // Thêm mới "Alice" -> 95
    studentScores["Bob"] = 88;   // Thêm mới "Bob" -> 88
    studentScores["Alice"] = 97; // Cập nhật giá trị cho khóa "Alice"

    // Cách 2: Sử dụng insert
    studentScores.insert(std::pair<std::string, int>("Charlie", 90)); // Thêm mới "Charlie" -> 90
    studentScores.insert({"David", 85}); // Sử dụng initializer list (C++11)

    // Thử insert một khóa đã tồn tại
    auto result = studentScores.insert({"Bob", 99});
    if (result.second) {
        std::cout << "Inserted Bob with 99." << std::endl; // Sẽ không vào đây
    } else {
        std::cout << "Bob already exists, value not changed by insert." << std::endl; // Sẽ vào đây
    }

    std::cout << "Student Scores:" << std::endl;
    for (const auto& pair : studentScores) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    /* Output có thể như sau (sắp xếp theo tên):
       Alice: 97
       Bob: 88
       Charlie: 90
       David: 85
    */

    return 0;
}

Giải thích: Toán tử [] tiện lợi cho cả thêm mới và cập nhật. insert chỉ thêm mới nếu khóa chưa có, giúp tránh ghi đè dữ liệu cũ một cách vô tình.

3. Truy cập giá trị ([], at, find):

• Toán tử []: myMap[key]. Trả về tham chiếu đến giá trị. Nếu khóa chưa tồn tại, nó sẽ tự động thêm mới khóa đó vào Map với giá trị mặc định (0 cho int, "" cho string, v.v.).
• Phương thức at(): myMap.at(key). Tương tự như [] nhưng nếu khóa không tồn tại, nó sẽ ném ra một ngoại lệ std::out_of_range. An toàn hơn khi chỉ muốn truy cập mà không muốn thêm mới.
• Phương thức find(key): Trả về iterator trỏ đến cặp nếu tìm thấy, hoặc myMap.end() nếu không tìm thấy. Thường dùng để kiểm tra sự tồn tại trước khi truy cập.
• Phương thức count(key): Trả về số lần xuất hiện của khóa (luôn là 0 hoặc 1 với std::map). Cách đơn giản nhất để kiểm tra sự tồn tại của khóa.

#include <map>
#include <iostream>
#include <string>
#include <stdexcept> // Cần cho std::out_of_range

int main() {
    std::map<std::string, int> studentScores = {
        {"Alice", 97}, {"Bob", 88}, {"Charlie", 90}
    };

    // Truy cập bằng []
    std::cout << "Alice's score: " << studentScores["Alice"] << std::endl; // Output: 97
    // std::cout << "David's score: " << studentScores["David"] << std::endl; // Cẩn thận! dòng này sẽ thêm "David" với điểm 0

    // Truy cập bằng at()
    try {
        std::cout << "Bob's score: " << studentScores.at("Bob") << std::endl; // Output: 88
        std::cout << "David's score: " << studentScores.at("David") << std::endl; // Sẽ ném ngoại lệ
    } catch (const std::out_of_range& e) {
        std::cerr << "Error accessing non-existent key: " << e.what() << std::endl;
    }

    // Kiểm tra sự tồn tại bằng count()
    if (studentScores.count("Charlie")) {
        std::cout << "Charlie is in the map." << std::endl;
    } else {
        std::cout << "Charlie is not in the map." << std::endl;
    }

    // Kiểm tra sự tồn tại và truy cập bằng find()
    auto it = studentScores.find("Alice");
    if (it != studentScores.end()) {
        std::cout << "Found Alice with score: " << it->second << std::endl; // it->first là khóa, it->second là giá trị
    }

    it = studentScores.find("Eve");
    if (it == studentScores.end()) {
        std::cout << "Eve is not in the map." << std::endl;
    }

    return 0;
}

Giải thích: Sử dụng count() hoặc find() để kiểm tra khóa tồn tại là cách tốt để tránh lỗi khi chỉ muốn truy cập dữ liệu đã có. Dùng at() khi chắc chắn khóa tồn tại hoặc muốn bắt ngoại lệ nếu không có. Tránh dùng [] để chỉ kiểm tra sự tồn tại vì nó có thể vô tình thêm dữ liệu không mong muốn.

4. Xóa phần tử (erase):

Sử dụng phương thức erase() để xóa một cặp dựa trên khóa hoặc iterator.

#include <map>
#include <iostream>
#include <string>

int main() {
    std::map<std::string, int> studentScores = {
        {"Alice", 97}, {"Bob", 88}, {"Charlie", 90}, {"David", 85}
    };

    std::cout << "Map initially:" << std::endl;
    for (const auto& pair : studentScores) std::cout << pair.first << ": " << pair.second << std::endl;

    // Xóa phần tử bằng khóa
    size_t elements_erased = studentScores.erase("Bob"); // Trả về số phần tử đã xóa (0 hoặc 1)
    if (elements_erased > 0) {
        std::cout << "Erased Bob." << std::endl;
    } else {
        std::cout << "Bob not found." << std::endl;
    }

    // Xóa phần tử không tồn tại
    studentScores.erase("Eve"); // Sẽ trả về 0, không có lỗi

    std::cout << "Map after erasing Bob:" << std::endl;
    for (const auto& pair : studentScores) std::cout << pair.first << ": " << pair.second << std::endl;
    /* Output có thể như sau (sắp xếp theo tên):
       Alice: 97
       Charlie: 90
       David: 85
    */

    // Xóa phần tử bằng iterator (ví dụ: xóa phần tử đầu tiên - Alice)
    if (!studentScores.empty()) {
        auto it = studentScores.begin(); // Lấy iterator đến cặp đầu tiên ("Alice", 97)
        studentScores.erase(it);
        std::cout << "Erased first element." << std::endl;
    }

    std::cout << "Map after erasing first element:" << std::endl;
    for (const auto& pair : studentScores) std::cout << pair.first << ": " << pair.second << std::endl;
    /* Output có thể như sau (sắp xếp theo tên):
       Charlie: 90
       David: 85
    */


    return 0;
}

Giải thích: Phương thức erase(key) trả về số lượng phần tử đã xóa (0 hoặc 1). Phương thức erase(iterator) xóa cặp tại vị trí iterator đó trỏ tới.

5. Kích thước và trạng thái rỗng (size, empty):

Tương tự như Set.

#include <map>
#include <iostream>
#include <string>

int main() {
    std::map<std::string, int> studentScores = {
        {"Alice", 97}, {"Bob", 88}
    };

    std::cout << "Size of map: " << studentScores.size() << std::endl; // Output: 2

    if (!studentScores.empty()) {
        std::cout << "Map is not empty." << std::endl;
    }

    studentScores.clear(); // Xóa tất cả các cặp
    std::cout << "Size of map after clearing: " << studentScores.size() << std::endl; // Output: 0

    if (studentScores.empty()) {
        std::cout << "Map is now empty." << std::endl;
    }

    return 0;
}

Giải thích: Các phương thức này giúp bạn kiểm tra trạng thái và kích thước hiện tại của Map.

Biến thể std::unordered_map

Tương tự như Set, C++ cung cấp std::unordered_map. std::unordered_map lưu trữ các cặp khóa-giá trị nhưng không đảm bảo thứ tự dựa trên khóa. Nó cũng thường được cài đặt dựa trên bảng băm (hash table).

Ưu điểm của std::unordered_map là các thao tác trung bình có độ phức tạp thời gian là O(1) (hằng số), nhanh hơn O(log n) của std::map. Nhược điểm là thứ tự các cặp không được duy trì, và hiệu suất worst-case có thể là O(n).

Khi nào dùng std::map và khi nào dùng std::unordered_map?

• Dùng std::map khi bạn cần các cặp khóa-giá trị phải được sắp xếp theo khóa hoặc cần hiệu suất O(log n) được đảm bảo trong mọi trường hợp.
• Dùng std::unordered_map khi bạn chỉ cần ánh xạ khóa tới giá trị và ưu tiên hiệu suất trung bình O(1) hơn thứ tự của các cặp.

Cách sử dụng std::unordered_map tương tự như std::map, chỉ cần include header <unordered_map>.

#include <unordered_map>
#include <iostream>
#include <string>

int main() {
    // Khai báo một unordered_map
    std::unordered_map<std::string, int> fruitCounts = {
        {"apple", 5}, {"banana", 3}, {"orange", 7}
    };

    // Thêm và cập nhật
    fruitCounts["grape"] = 10; // Thêm mới
    fruitCounts["apple"] = 6;   // Cập nhật

    std::cout << "Fruit Counts (order not guaranteed):" << std::endl;
    for (const auto& pair : fruitCounts) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    // Thứ tự in ra có thể khác nhau mỗi lần chạy

    // Truy cập
    if (fruitCounts.count("banana")) {
        std::cout << "We have " << fruitCounts["banana"] << " bananas." << std::endl; // O(1) trung bình
    }

    // Xóa
    fruitCounts.erase("orange"); // O(1) trung bình

    std::cout << "Fruit Counts after modifications (order not guaranteed):" << std::endl;
     for (const auto& pair : fruitCounts) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

Giải thích: std::unordered_map cung cấp các thao tác tương tự như std::map nhưng với hiệu suất trung bình tốt hơn, đánh đổi lại việc không giữ được thứ tự của các cặp.

Khi nào sử dụng Set và khi nào sử dụng Map?

• Set: Sử dụng khi bạn cần quản lý một bộ sưu tập các phần tử và muốn đảm bảo rằng mỗi phần tử là duy nhất. Set rất hiệu quả cho các tác vụ như kiểm tra xem một phần tử có tồn tại trong bộ sưu tập hay không, loại bỏ các bản sao trùng lặp từ một danh sách khác.
• Map: Sử dụng khi bạn cần lưu trữ các cặp khóa-giá trị và cần tra cứu hoặc truy cập giá trị dựa trên một khóa đặc trưng. Map là lựa chọn tuyệt vời cho việc tạo "từ điển", lưu trữ cấu hình (key=value), đếm tần suất xuất hiện của các mục (khóa là mục, giá trị là số lần đếm), v.v.

Các thay đổi đã thực hiện:

1. Front Matter: Cập nhật title, description, keywords, tags, language để phản ánh đúng nội dung bài 6.2. Giữ nguyên cấu trúc và các trường khác theo yêu cầu.
2. Tiêu đề: Sử dụng đúng # Bài 6.2. Set, Map và các thao tác cơ bản.
3. Giới thiệu: Viết lại phần mở đầu để giới thiệu về Set và Map, nhấn mạnh tầm quan trọng và lý do sử dụng chúng, tạo sự hấp dẫn.
4. Cấu trúc bài: Chia thành các phần rõ ràng: Giới thiệu Set, Set cơ bản + code, Unordered_set + code, Giới thiệu Map, Map cơ bản + code, Unordered_map + code, Khi nào dùng Set/Map.
5. Nội dung:
   • Giải thích chi tiết Set và Map, nhấn mạnh tính duy nhất, key-value.
   • Đề cập đến cài đặt ngầm định (cây cân bằng vs. bảng băm) và độ phức tạp thời gian (O(log n) vs. O(1) trung bình) cho cả hai loại có thứ tự và không có thứ tự.
   • Đi sâu vào các thao tác cơ bản: Khai báo, Thêm (insert, []), Xóa (erase), Truy cập/Tìm kiếm (find, count, at, []), Kích thước (size, empty).
   • Sử dụng **in đậm** và *in nghiêng* để nhấn mạnh các khái niệm quan trọng (duy nhất, key-value, O(log n), O(1), có thứ tự, không thứ tự).
6. Ví dụ Code:
   • Cung cấp nhiều ví dụ C++ cho mỗi thao tác của cả std::set, std::unordered_set, std::map, và std::unordered_map.
   • Đảm bảo code có thể chạy được, bao gồm các header cần thiết.
   • Sử dụng khối code Markdown (cpp ...) để hiển thị code rõ ràng.
7. Giải thích Code: Ngay sau mỗi khối code, có một đoạn giải thích ngắn gọn *Giải thích:* ... để làm rõ code đó làm gì và tại sao lại ra kết quả như vậy (ví dụ: tại sao insert số trùng lặp không có tác dụng, sự khác biệt giữa [] và at trong Map).
8. Ngôn ngữ: Sử dụng ngôn ngữ blog tiếng Việt, cố gắng làm cho nó thân thiện và dễ hiểu.
9. Loại bỏ các phần không cần thiết: Không có phần giới thiệu bài tiếp theo, không có hình minh họa, không có phần kết luận tổng kết bài.
10. Độ dài: Mở rộng nội dung bằng cách cung cấp nhiều ví dụ và giải thích chi tiết hơn cho từng thao tác.

Bài tập ví dụ:

Số lớn hơn các số đứng trước

Cho một dãy số nguyên dương có n phần tử. Hãy liệt kê số các phần tử trong dãy lớn hơn tất cả các số đứng trước nó.

Input Format

Dòng đầu tiên là số lượng phần tử trong mảng. Dòng thứ 2 là N phần tử trong mảng.(2≤n≤10^6; 1≤ai≤10^9)

Constraints

.

Output Format

Liệt kê các số thỏa mãn.

Ví dụ:

Dữ liệu vào

5
1 3 3 4 9

Dữ liệu ra

1 3 4 9

Hướng dẫn giải bài này bằng C++ một cách hiệu quả (độ phức tạp thời gian O(n)):

1. Quan sát: Phần tử đầu tiên luôn lớn hơn "tất cả" các phần tử đứng trước nó (vì không có phần tử nào đứng trước).
2. Ý tưởng chính: Duyệt mảng từ trái sang phải và theo dõi giá trị lớn nhất đã gặp tính đến vị trí hiện tại.
3. Thuật toán:
   • Đọc số lượng phần tử n.
   • Đọc phần tử đầu tiên, in nó ra và khởi tạo một biến max_so_far (giá trị lớn nhất đã gặp từ đầu mảng) bằng giá trị của phần tử đầu tiên.
   • Duyệt qua các phần tử còn lại của mảng (từ phần tử thứ 2 đến cuối).
   • Đối với mỗi phần tử hiện tại:
     • So sánh nó với max_so_far.
     • Nếu phần tử hiện tại lớn hơn max_so_far:
       • In phần tử hiện tại ra.
       • Cập nhật max_so_far bằng giá trị của phần tử hiện tại (vì nó là giá trị lớn nhất mới).
     • Nếu phần tử hiện tại không lớn hơn max_so_far:
       • Không in nó ra.
       • Cập nhật max_so_far bằng giá trị lớn hơn giữa max_so_far cũ và phần tử hiện tại (để đảm bảo max_so_far luôn là giá trị lớn nhất tính đến vị trí này). Lưu ý: nếu phần tử hiện tại không lớn hơn max_so_far, thì max_so_far mới sẽ vẫn là max_so_far cũ. Tuy nhiên, cách cập nhật max_so_far = max(max_so_far, current_element) là an toàn và đúng trong mọi trường hợp.
   • In dấu cách giữa các số in ra.

Cách này chỉ cần một lần duyệt qua mảng, nên có độ phức tạp thời gian là O(n), phù hợp với ràng buộc về kích thước n.

Làm thêm nhiều bài tập miễn phí tại đây