# map / multimap - 映射

## map / multimap 基本概念

map 的特性是，所有的元素都会根据元素的键值自动排序；

map 的所有元素都是pair，同时拥有实值和键值。

* pair的第一元素被视为键值，第二元素被视为实值；
* map不允许两个元素有相同的键值；

和set类似的原因，我们不能通过迭代器改变map的键值，但我们可以任意修改实值。

map和list在增删元素的时候具有相似的性质。

map和multimap的操作类似，唯一的区别是multimap键值可重复。

map和multimap都是以红黑树作为底层实现机制。

> map和multimap包含在同一个头文件中。

![](https://images.unsplash.com/photo-1476973422084-e0fa66ff9456?crop=entropy\&cs=srgb\&fm=jpg\&ixid=MnwxOTcwMjR8MHwxfHNlYXJjaHw2fHxtYXB8ZW58MHx8fHwxNjQ0NTA0MjU4\&ixlib=rb-1.2.1\&q=85)

## map 的遍历

```cpp
for (map<T1, T2>::iterator it = m.begin(); it != m.end(); it++)
{
    cout << "key = " << it->first << " value = " << it->second << endl;
}
```

## map/multimap 常用API

### map 构造函数

```cpp
map<T1, T2> mapTT; // map默认构造函数
map(const map& mp); // 拷贝构造函数
```

### map 赋值操作

```cpp
map& operator=(const map& mp); // 重载等号操作符
swap(mp); // 交换两个集合容器
```

### map 大小操作

```cpp
int size(); // 返回容器中元素的数目
bool empty(); // 判断容器是否为空
```

### map 插入元素操作

```cpp
pair<iterator, bool> insert(pair<T1, T2> p); // 通过pair的方式插入对象
/*
1. 参数部分可以用pair的构造函数创建匿名对象
2. 也可以使用make_pair创建pair对象
3. 还可以用map<T1, T2>::value_type(key, value)来实现
*/

T2& operator[](T1 key); // 通过下标的方式插入值
// 如果通过下标访问新的键却没有赋值，会自动用默认值填充
```

> map指定排序规则的方式和set类似，都是利用functor在模版类型表的最后一个参数处指定。

### map 删除操作

```cpp
void clear(); // 删除所有元素
iterator erase(iterator pos); // 删除pos迭代器所指的元素，返回下一个元素的迭代器
iterator erase(beg, end); // 删除区间[beg, end)内的所有元素，返回下一个元素的迭代器
erase(keyElem); // 删除容器中key为keyElem的对组
```

### map 查找操作

```cpp
iterator find(T1 key); 
// 查找键key是否存在，若存在，返回该键的元素的迭代器；若不存在，返回map.end()
int count(T1 keyElem);
// 返回容器中key为keyElem的对组个数，对map来说只可能是0或1，对于multimap可能大于1

iterator lower_bound(T keyElem);
// 返回第一个key>=keyElem元素的迭代器
iterator upper_bound(T keyElem);
// 返回第一个key>keyElem元素的迭代器
pair<iterator, iterator> equal_range(T keyElem);
// 返回容器中key与keyElem上相等的两个上下限迭代器
```

{% hint style="success" %}
至此，读者应当对map/multimap的特点及基本操作有了较为全面的认识，使用时API记不清可以回头多看。
{% endhint %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://cui-jiacai.gitbook.io/c++-stl-tutorial/rong-qi-container/map-multimap-ying-she.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.