Map

C++ 中的有序字典，使用红黑树实现。对元素的搜索、插入和删除具有时间复杂度\(O(log{}N)\)。

简单使用

// 默认参数
map<int, int> map1;
// 默认使用 less 比较函数，从小到大
map<int, int, less<int>> map2;
print_map(map2); // 1 2 3
// greater 比较函数，从大到小
map<int, int, greater<int>> map3;
print_map(map3); // 3 2 1


// 自定义排序函数（结构体）
struct CustomComparePairs {
    bool operator()(const pair<int, int>& a, const pair<int, int>& b) const {
        if (a.second != b.second) {
            return a.second > b.second; 
        }
        return a.first < b.first; 
    }
};
map<pair<int, int>, int, CustomComparePairs> map4;

// 自定义排序函数（函数）
// `const` 非常重要
auto customComparePairs = [](const pair<int, int>& a, const pair<int, int>& b) -> bool {
    if (a.second != b.second) {
        return a.second > b.second;
    }
    return a.first < b.first;
};

map<pair<int, int>, int, decltype(customComparePairs)> map5(customComparePairs);

map<int, int> map1;

// 匹配的键值对数量，只有 0 或 1 两种情况
map1.count(1);
// C++20
// 检查是否包含特定键值对
map1.contains(1);

map1.insert({1,2});
map1.emplace(1,2);
map1.try_emplace(1, 2);
map1[3] = 1;

// 无边界检查访问元素
map1.at(3);

// 遍历访问
for (auto it = map1.begin(); it != map1.end(); it++) {
    printf("(%d, %d) ", it->first, it->second);
}
printf("\n");

for (auto& it: map1) {
    printf("(%d, %d) ", it.first, it.second);
}
printf("\n");

for (auto& [key, value] : map1) {
    printf("(%d, %d) ", key, value);
}
printf("\n");

// `lower_bound` 在前闭后开区间进行二分查找，返回**大于或等于目标值**的第一个元素位置。如果所有元素都小于目标值，则返回区间最后元素的位置。
// `upper_bound` 在前闭后开区间查找的关键字的上界，返回**大于目标值**的第一个元素位置。如果目标值大于所有元素，则返回区间最后元素的位置。

map<int, int> map1;
map1.emplace(1, 2);
map1.emplace(3, 4);
map1.emplace(5, 6);

auto it1 = map1.lower_bound(3);
printf("it1 (%d, %d)\n", it1->first, it1->second);
// it1 (3, 4)

auto it2 = map1.upper_bound(3);
printf("it2 (%d, %d)\n", it2->first, it2->second);
// it2 (5, 6)