C++ map 的使用-CSDN博客

下面的是关于 map 的介绍。来自 map - C++ Reference (cplusplus.com) 的翻译您可以看也可以不看哈

1. map 是关联容器它按照特定的次序(按照 key 来比较)存储由键值 key 和值 value组合而成的元素。
2. 在 map 中键值 key 通常用于排序和惟一地标识元素而值 value 中存储与此键值 key 关联的内容。键值 key 和值 value 的类型可能不同并且在 map 的内部key 与 value 通过成员类型 value_type 绑定在一起为其取别名称为 pair: typedef pair value_type
3. 在内部map 中的元素总是按照键值 key 进行比较排序的。
4. map 中通过键值访问单个元素的速度通常比 unordered_map 容器慢但 map 允许根据顺序对元素进行直接迭代(即对 map 中的元素进行迭代时可以得到一个有序的序列)。
5. map 支持下标访问符即在 [] 中放入 key就可以找到与 key 对应的 value。
6. map 通常被实现为二叉搜索树(更准确的说红黑树)。

默认构造函数

map 的构造函数不止默认构造函数哈他还可以使用一段迭代器区间来初始化一个 map当然他还有拷贝构造函数。不过在平时刷算法题的过程中使用次数最多的还是默认构造函数啦要使用 C++ 的 map 需要包含头文件

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

int main()
{
    map<int, int> m; //定义一个 map你要理解map 的底层就是红黑树红黑树我们不是都实现过了嘛红黑树怎么定义map就怎么定义
    return 0;
}

pair<iterator,bool> insert (const pair<key, val>& val);

这里的 key 和 value 都是模板参数哈

这个函数就是向 map 里面插入一个节点。如果插入成功了那么返回值中的 first 就是新插入的节点对应的迭代器返回值中的 second 就是 true如果插入失败了那么返回值中的 first 就是与新插入的节点的 first 相同的那个节点的迭代器(map 中 key 值是不能够重复的)返回值中的 second 就是 false。

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

int main()
{
    map<int, int> m;
    auto p = m.insert({1,1}); //向 map 中插入键值对 11

    //输出1, 1 表示新插入节点的 value 值为 1 插入的结果为 1 (true)
    cout << (*(p.first)).second << " " << p.second << endl; //根据返回值来读取新插入节点的数据

    auto q = m.insert({1,2}); //向 map 中插入键值对 1,2
    //输出1, 0 表示已经存在相同的key值对应的value值为 1插入的结果为 0 (false)
    cout << (*(q.first)).second << " " << q.second << endl;

    return 0;
}

map 的删除函数

size_t erase (const key& k)

这个函数可以删除 map 中 key 值为 k 的节点返回值是返回删除节点的个数。

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

int main()
{
    map<int, int> m;
    m.insert({1,1});
    m.insert({2,2});
    m.insert({3,3});
    m.insert({4,4});
    m.insert({5,5});
    m.insert({5,5});

    cout << m.erase(5) << endl; //输出 1 
    cout << m.erase(0) << endl; //输出 0 
    

    return 0;
}

我们都知道 map 里面是不允许存在相同 key 值的节点的因此 erase 函数的返回值要么是 0 要么是 1。

void erase(iterator pos)

删除 pos 位置的节点pos 是 map 的迭代器哈

void erase(iterator first, iterator last)

这个函数是删除 map 中一段迭代器区间的所有元素区间的范围是[first, last)。

value& operator[] (const key& k)

在 map 的实现中重载了 [] 运算符可以使用方括号通过 key 值直接拿到 value 值非常方便。平时在做算法题也会经常用到的。具体的实现逻辑会在模拟实现 map 的那一节细讲我可以提示一下是用 insert 来实现的。

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

int main()
{
    map<int, int> m;
    m.insert({1,-1});
    m.insert({2,-2});
    m.insert({3,-3});
    m.insert({4,-4});
    m.insert({5,-5});

    cout << m[1] << endl; //输出 -1

    return 0;
}

iterator find(key& k)

这个函数用来在 map 查找是否存在一个 key 值为 k 的节点。如果存在返回该节点对应的迭代器如果不存在返回 end() 迭代器。

size_t size()

返回 map 中元素的个数

bool empty()

判断 map 是否为空。

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

int main()
{
    map<int, int> m;
    m.insert({1,-1});
    m.insert({2,-2});
    m.insert({3,-3});
    m.insert({4,-4});
    m.insert({5,-5});

    cout << (*(m.find(1))).first << " " << (*(m.find(1))).second << endl; //输出 1 -1
    cout << m.size() << endl; //输出 5
    cout << m.empty() << endl; //输出0表示 map 不为空

    return 0;
}