map基本概念

简介：

• map中所有元素都是pair

• pair中第一个元素为key（键值），起到索引作用，第二个元素为value（实值）

• 所有元素都会根据元素的键值自动排序

底层实现：

• 基于红黑树实现，红黑树是一种自平衡的二叉搜索树。

• 元素按照键的顺序存储，键是有序的。

• 插入、删除和查找操作的时间复杂度为O(log n)，其中n是容器中元素的数量。

查找性能：

• std::map：查找效率为O(log n)，适合对查找性能要求不高，但需要按键值有序存储的场景。

插入和删除性能：

• std::map：插入和删除操作的时间复杂度为O(log n)。

键的有序性 

• 键是有序的，元素会按照键的顺序存储和遍历。

• 遍历时可以保证按键的升序（或自定义的比较顺序）

内存使用

• 内存使用相对较为紧凑，因为红黑树的节点结构相对简单。

• 但红黑树的指针结构会占用一定的内存。

使用场景

• 适用于需要按键值有序存储的场景，例如：

  • 按键值排序输出。

  • 实现有序的映射关系。

  • 需要频繁的范围查找（如lower_bound、upper_bound）。

优点：

• 可以根据key值快速找到value值

map和multimap区别：

• map不允许容器中有重复key值元素

• multimap允许容器中有重复key值元素

map构造和赋值

功能描述：

• 对map容器进行构造和赋值操作

函数原型：

• map<T1 T2> mp; //map默认构造函数

• map(const map &mp); //拷贝构造函数

赋值：

• map& operator=(const map &mp); //重载等号操作符

map大小和交换

功能描述：

• 统计map容器大小以及交换map容器

函数原型：

• size(); //返回容器中元素的数目

cout << "Size: " << myMap.size() << endl;

• empty(); //判断容器是否为空

if (myMap.empty()) {
    cout << "Map is empty" << endl;
}

• swap(st); //交换两个集合容器

map<int, string> anotherMap;
myMap.swap(anotherMap); // 交换两个map的内容

map访问元素

• operator[]

myMap[4] = "four"; // 插入或修改键为4的元素
cout << myMap[4] << endl; // 输出 "four"

注意：如果键不存在，则会插入一个默认值。 请谨慎使用该方法访问不存在的元素！！！

当调用 mp[key] 时：

情况 1：key 已存在

map<string, int> mp;
mp["a"] = 1;

int &u = mp["a"];  // 返回已存在元素的引用，u = 1

情况 2：key 不存在

map<string, int> mp;  // mp 是空的

int &u = mp["b"];  
// 1. 自动插入 {key, value}，value 是 int 的默认值
// 2. int 的默认值是 0
// 3. 所以 mp 变为 {"b": 0}
// 4. 返回 value 的引用，u = 0

为什么默认是 0？

C++ 标准规定：map::operator[] 对于不存在的 key，会执行值初始化（value-initialization）。

// map<T1, T2> 中，如果 T2 是：
map<string, int>        // int 的默认值：0
map<string, double>     // double 的默认值：0.0
map<string, bool>       // bool 的默认值：false
map<string, string>     // string 的默认值："" (空字符串)
map<string, int*>       // 指针的默认值：nullptr

• at()

string value = myMap.at(4); // 安全访问，如果键不存在会抛出异常

map插入和删除

功能描述：

• map容器进行插入数据和删除数据

函数原型：

• insert(elem); // 在容器中插入元素。

//四种插入方法
map<int,int>m;
//第一种
m.insert(pair<int,int>(1,10));
//第二种
m.insert(make_pair(2,20));
//第三种
m.insert(map<int,int>::value_type(3,30));
//第四种，不建议使用[]插入，但可以使用[]访问
//当错误的使用 [] 赋值时，会在map中额外的插入一个元素
m[4] = 40;

• emplace() 原地构造一个键值对并插入，效率更高。

myMap.emplace(3, "three");

• clear(); // 清除所有元素

myMap.clear(); // 清空所有元素

• erase(pos); // 删除pos迭代器所指的元素，返回下一个元素的迭代器。

• erase(beg, end); // 删除区间[beg, end)的所有元素，返回下一个元素的迭代器。

• erase(key); // 删除容器中值为key的元素。

myMap.erase(1); // 删除键为1的元素
myMap.erase(it); // 删除迭代器指向的元素

map查找和统计

功能描述：

• 对map容器进行查找数据以及统计数据

函数原型：

• find(key); // 查找key是否存在，若存在，返回该键的元素的迭代器；若不存在，返回set.end();

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

• count(key); // 统计key的元素个数，返回1表示存在，0表示不存在。

int count = myMap.count(2); // 返回1或0

• 查找 --- find （返回的是迭代器）

• 统计 --- count （对于map，结果为0或者1）

int main() {
    std::map<int, std::string> myMap;
    myMap[1] = "one";
    myMap[2] = "two";
    
    int key = 3;
    
    // count() 返回键出现的次数（map中只能是0或1）
    if (myMap.count(key) > 0) {
        std::cout << "键 " << key << " 存在" << std::endl;
    } else {
        std::cout << "键 " << key << " 不存在" << std::endl;
    }
    
    // 或者更简洁
    if (myMap.count(key)) {
        std::cout << "键存在" << std::endl;
    }
    
    return 0;
}

map容器自定义排序

• map容器默认排序规则为按照key值进行从小到大排序

主要技术点：

• 利用仿函数可以指定map容器的排序规则

• 对于自定义数据类型，map必须要指定排序规则，同set容器

内置数据类型定义仿函数调整map排序方法

#include<iostream>
#include<string>
#include<map>
using namespace std;

class myCompare{
public:
    //定义仿函数
    bool operator()(int a, int b)const{
        return a > b;
    }
};
int main(){
    
   map<int,string> m1;
   m1.insert(pair<int,string>(10,"a"));
   m1.insert(pair<int,string>(20,"b"));
   m1.insert(pair<int,string>(30,"c"));
   m1.insert(pair<int,string>(40,"d"));
   
   for(map<int,string>::iterator it = m1.begin(); it != m1.end(); it++){
       cout << it->first << "   " << it ->second << endl; 
   }
   cout << "--------------------------------" << endl;
    map<int,string,myCompare> m2;
    m2.insert(pair<int,string>(10,"a"));
    m2.insert(pair<int,string>(20,"b"));
    m2.insert(pair<int,string>(30,"c"));
    m2.insert(pair<int,string>(40,"d"));
    
    for(map<int,string,myCompare>::iterator it = m2.begin(); it != m2.end(); it++){
        cout << it->first << "   " << it ->second << endl; 
    }
}

 输出结果如下：

自定义数据类型定义仿函数调整map排序方法

如果不定义仿函数，则无法直接按键插入自定义数据类型

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

class Person{
public:
    Person(string name, int age){
        this->m_Name = name;
        this->m_Age = age;
    }
    string m_Name;
    int m_Age;
};


class comparePerson{
public:
    // 定义仿函数
    bool operator()(const Person&p1,const Person&p2)const{
        return p1.m_Age > p2.m_Age;
    }
};

int main(){
    
    Person p1("张三",20);
    Person p2("李四",21);
    Person p3("王五",22);
    Person p4("赵六",23);
    map<Person,string,comparePerson> m1;
    m1.insert(pair<Person,string>(p1,"a"));
    m1.insert(pair<Person,string>(p2,"b"));
    m1.insert(pair<Person,string>(p3,"c"));
    m1.insert(pair<Person,string>(p4,"d"));
    
    for(map<Person,string,comparePerson>::iterator it = m1.begin(); it != m1.end(); it++){
        cout << " 姓名：" << it->first.m_Name << " 年龄：" << it->first.m_Age << " 等级：" << it ->second << endl; 
    }
    
}

输出结果如下：