STL map 概述

性质

关联容器：map 是STL（Standard Template Library）中的一个关联容器，提供一对一的数据处理能力（有序键值对）。 唯一键：map 中的每个键都是唯一的，但值可以重复。 自动排序：map 内部基于红黑树实现，因此所有的元素都会按照键的顺序自动排序。 泛型：map 是模板类，可以存储任意类型的数据，包括自定义类型。 高效查找：根据键进行查找的复杂度是 O(log N)，其中 N 是 map 中元素的数量。

操作

插入

insert 方法：可以插入单个键值对或一个范围的键值对。

map<int, string> myMap;  
myMap.insert(pair<int, string>(1, "one"));  
myMap.insert(make_pair(2, "two"));  
myMap[3] = "three"; // 另一种插入方式，如果键已存在则覆盖值

注意：使用 operator[] 插入时，如果键不存在，则会插入新的键值对，并将值初始化为类型的默认值。

查找

find 方法：通过键查找元素，返回一个迭代器。如果找到元素，迭代器指向该元素；否则，迭代器等于 end()。

auto it = myMap.find(1);  
if (it != myMap.end()) {  
    cout << "Found: " << it->second << endl;  
}

删除

erase 方法：可以删除单个元素、一个范围内的元素或通过键删除元素。

myMap.erase(it); // 删除迭代器指向的元素  
myMap.erase(1);  // 通过键删除元素  
myMap.erase(myMap.begin(), myMap.end()); // 删除所有元素

其他操作

size：返回 map 中元素的数量。
empty：检查 map 是否为空。
clear：删除 map 中的所有元素。
迭代器：提供 begin()、end()、rbegin() 和 rend() 来遍历 map。

复杂度

插入：平均时间复杂度为 O(log N)。 查找：平均时间复杂度为 O(log N)。 删除：平均时间复杂度为 O(log N)。 这里提到的“平均”是因为红黑树保持平均平衡，但在最坏情况下，这些操作的时间复杂度可能会更高，但这种情况较为罕见。

用法

包含头文件

#include <map>
定义和使用
cpp
#include <iostream>  
#include <map>  
using namespace std;  

int main() {  
    map<int, string> myMap;  

    // 插入数据  
    myMap[1] = "one";  
    myMap.insert(make_pair(2, "two"));  

    // 遍历map  
    for (auto& it : myMap) {  
        cout << it.first << ": " << it.second << endl;  
    }  

    // 查找元素  
    auto it = myMap.find(1);  
    if (it != myMap.end()) {  
        cout << "Found: " << it->second << endl;  
    }  

    // 删除元素  
    myMap.erase(2);  

    // 输出当前map的大小  
    cout << "Size: " << myMap.size() << endl;  

    return 0;  
}

以上就是一个关于STL map 的基本概述，包括其性质、操作、复杂度和用法。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com