map和multimap概述
- map和multimap中存储的是使用pair对象的键值对。
- map和multimap底层也是使用红黑树的数据结构进行实现的。所以,map和multimap内部存储的键值对也是有序的。并且内部数据也是使用链表的形式进行关联。所以其的迭代器和指针,也只能进行++,--(前置和后置),==,!=。
- 而且和set一样map的键不能重复。(值可以) multimap可以重复。
- map容器的键是不支持修改的,map<const 键类型,值类型>
- map支持我们使用[]和at()函数,方便我们通过键来操作其对应的值。
成员方法 | 功能 |
---|---|
begin() | 返回指向容器中第一个(注意,是已排好序的第一个)键值对的双向迭代器。如果 map 容器用 const 限定,则该方法返回的是 const 类型的双向迭代器。 |
end() | 返回指向容器最后一个元素(注意,是已排好序的最后一个)所在位置后一个位置的双向迭代器,通常和 begin() 结合使用。如果 map 容器用 const 限定,则该方法返回的是 const 类型的双向迭代器。 |
rbegin() | 返回指向最后一个(注意,是已排好序的最后一个)元素的反向双向迭代器。如果 map 容器用 const 限定,则该方法返回的是 const 类型的反向双向迭代器。 |
rend() | 返回指向第一个(注意,是已排好序的第一个)元素所在位置前一个位置的反向双向迭代器。如果 map 容器用 const 限定,则该方法返回的是 const 类型的反向双向迭代器。 |
cbegin() | 和 begin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改容器内存储的键值对。 |
cend() | 和 end() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改容器内存储的键值对。 |
crbegin() | 和 rbegin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改容器内存储的键值对。 |
crend() | 和 rend() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改容器内存储的键值对。 |
find(key) | 在 map 容器中查找键为 key 的键值对,如果成功找到,则返回指向该键值对的双向迭代器;反之,则返回和 end() 方法一样的迭代器。另外,如果 map 容器用 const 限定,则该方法返回的是 const 类型的双向迭代器。 |
lower_bound(key) | 返回一个指向当前 map 容器中第一个大于或等于 key 的键值对的双向迭代器。如果 map 容器用 const 限定,则该方法返回的是 const 类型的双向迭代器。 |
upper_bound(key) | 返回一个指向当前 map 容器中第一个大于 key 的键值对的迭代器。如果 map 容器用 const 限定,则该方法返回的是 const 类型的双向迭代器。 |
equal_range(key) | 该方法返回一个 pair 对象(包含 2 个双向迭代器),其中 pair.first 和 lower_bound() 方法的返回值等价,pair.second 和 upper_bound() 方法的返回值等价。也就是说,该方法将返回一个范围,该范围中包含的键为 key 的键值对(map 容器键值对唯一,因此该范围最多包含一个键值对)。 |
empty() | 若容器为空,则返回 true;否则 false。 |
size() | 返回当前 map 容器中存有键值对的个数。 |
max_size() | 返回 map 容器所能容纳键值对的最大个数,不同的操作系统,其返回值亦不相同。 |
operator[] | map容器重载了 [] 运算符,只要知道 map 容器中某个键值对的键的值,就可以向获取数组中元素那样,通过键直接获取对应的值。 |
at(key) | 找到 map 容器中 key 键对应的值,如果找不到,该函数会引发 out_of_range 异常。 |
insert() | 向 map 容器中插入键值对。 |
erase() | 删除 map 容器指定位置、指定键(key)值或者指定区域内的键值对。后续章节还会对该方法做重点讲解。 |
swap() | 交换 2 个 map 容器中存储的键值对,这意味着,操作的 2 个键值对的类型必须相同。 |
clear() | 清空 map 容器中所有的键值对,即使 map 容器的 size() 为 0。 |
emplace() | 在当前 map 容器中的指定位置处构造新键值对。其效果和插入键值对一样,但效率更高。 |
emplace_hint() | 在本质上和 emplace() 在 map 容器中构造新键值对的方式是一样的,不同之处在于,使用者必须为该方法提供一个指示键值对生成位置的迭代器,并作为该方法的第一个参数。 |
count(key) | 在当前 map 容器中,查找键为 key 的键值对的个数并返回。注意,由于 map 容器中各键值对的键的值是唯一的,因此该函数的返回值最大为 1。 |
map和multimap使用必须导入头文件#include<map>
1. map的默认构造
代码
int main(void) {
/*
map<string, int> m1;
map<int, int>m2;
map<Student,int>m3;
map<Student,Student*>m4;
map<int,int*>m5;
*/
system("pause");
return 0;
}
2. map的有参构造
代码
/*
map<string, int> m1({ {"张三",18},{"李四",20} });
map<string, int> m1{ {"张三",18},{"李四",20} };
pair<string, int> p1("张三",20);
pair<string, int> p2("李四",30);
map<string, int> m2({p1,p2});
map<string, int> m2{p1,p2};
map<string, int> m3(m1.begin(), m1.end());
map<string, int> m3{ m1.begin(), m1.end() };
map<string,int> m3(m1); // 调用拷贝构造函数
// 借助make_pair()函数
map<string, int> m1({ make_pair("张三", 18) });
map<string, int> m1{ make_pair("张三", 18) };
*/
3.map容器元素的个数
代码: 使用size()函数
int main(void) {
map<string, int>m1{ {"数学",108},{"语文",80},{"英语",100} };
cout << "m1的键值对个数:" << m1.size() << endl; // 3
system("pause");
return 0;
}
代码: 使用count()函数
int main(void) {
map<string, int>m1{ {"数学",108},{"语文",80},{"英语",100} };
map<string,int>::size_type t1 = m1.count("数学");
cout << t1 << endl;
system("pause");
return 0;
}
相关知识点
- count(elem)函数,以map中存储的键值对的键为参数,返回键值为elem的键值对的个数。
- 因为map中的键是唯一的,所以count()函数返回的值为0或者1,multimap返回可能大于1。
- size_type在vector中已经说到过了。
4.map的元素访问(有变动)
代码: 使用[]和at()
int main(void) {
string s1(20, '-');
map<string, int>m1{ {"数学",108},{"语文",80},{"英语",100} };
// 使用[]访问
cout << "键: 数学, 值: " << m1["数学"] << endl;
cout << s1 << endl;
// 使用[]修改
m1["数学"] = 110;
// 使用[]添加
m1["政治"] = 90;
for (map<string, int>::iterator it = m1.begin(); it != m1.end(); it++) {
cout << "键:" << (*it).first << " 值: " << (*it).second << endl;
}
cout << s1 << endl;
// 使用at()访问
cout << "键: 数学, 值: " << m1.at("数学") << endl;
cout << s1 << endl;
// 使用at()修改
m1.at("语文") = 110;
for (map<string, int>::iterator it = m1.begin(); it != m1.end(); it++) {
cout << "键:" << (*it).first << " 值: " << (*it).second << endl;
}
cout << s1 << endl;
system("pause");
return 0;
}
相关知识点
- map和set不同,map是可以使用[]下标运算符来进行访问数据的,不止如此,我们也可以通过[]将对应键的值进行修改。
- map还可以通过[]添加元素,当[]中的使用的键值不存在的时候,那么[]运算符就会将对应的键值对添加到map中去。
- 同样,map也可以使用at()函数,访问键对应的值。也可以将键对应的值进行修改。
- 但是,通过at()不能给map添加元素,如果at()中的键值不存在,at()函数会抛出异常。
5.map的迭代器
成员方法 | 功能 |
---|---|
begin() | 返回指向容器中第一个(注意,是已排好序的第一个)键值对的双向迭代器。如果 map 容器用 const 限定,则该方法返回的是 const 类型的双向迭代器。 |
end() | 返回指向容器最后一个元素(注意,是已排好序的最后一个)所在位置后一个位置的双向迭代器,通常和 begin() 结合使用。如果 map 容器用 const 限定,则该方法返回的是 const 类型的双向迭代器。 |
rbegin() | 返回指向最后一个(注意,是已排好序的最后一个)元素的反向双向迭代器。如果 map 容器用 const 限定,则该方法返回的是 const 类型的反向双向迭代器。 |
rend() | 返回指向第一个(注意,是已排好序的第一个)元素所在位置前一个位置的反向双向迭代器。如果 map 容器用 const 限定,则该方法返回的是 const 类型的反向双向迭代器。 |
cbegin() | 和 begin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改容器内存储的键值对。 |
cend() | 和 end() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改容器内存储的键值对。 |
crbegin() | 和 rbegin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改容器内存储的键值对。 |
crend() | 和 rend() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改容器内存储的键值对。 |
map的迭代器也值能进行++,--(前置和后置)的运算操作,==,!=的比较操作,以及不能使用迭代器修改键的值。
其它的操作和前面的容器是想用的。
6. map在指定位置插入元素
代码: 使用insert()函数
/*
map<string, int> m1;
pair<string, int> p1("张三", 18);
m1.insert(p1);
m1.insert(pair<string, int>("李四", 20));
m1.insert(m1.begin(), p1);
m1.insert({ p1,pair<string,int>("王五",30) });
// 使用make_pair构建并返回一个pair对象,然后添加
m1.insert(make_pair("张三", 25));
// 使用内置类型value_type对象(value_type表示存储在容器中的元素类型,此处为pair类型)
m1.insert(map<string, int>::value_type("张三", 25));
*/
相关知识点
我们前面说过map找那个存放的是键值对,也就是pair的队组形式,所以我们使用insert插入数据的时候,应该插入pair对象。
使用make_pair()函数和value_type对象插入
- make_pair(value1,value2); // 此函数用于构建一个pair对象,然后返回,将返回的pair对象插入map中。
- value_type 是容器内部的一个类,其表示容器中存储数据的类型,map中存储的类型就是pair类型,所以此时value_type就表示pair,创建的对象也是pair对象。
insert()返回值
- 当我们直接插入pair对象,insert函数返回一个pair<iterator,bool>。迭代器指插入元素的位置(插入失败,指向键值与插入元素相同的元素位置),bool表示插入是否成功 (如果map中存放的键值和插入数据的键值有相同则会插入失败)。
- 当我们在指定位置插入pair对象时,insert(iterator,pair); // 其返回一个迭代器,指向插入元素的位置(插入失败,指向键值与插入元素相同的元素位置)
- 当使用初始化列表进行插入的时候,insert()返回void。(因为初始化列表一次可以插入多个pair对象)
代码: 使用emplace()和emplace_hint()函数
map<string, int> m1;
// emplace()函数
m1.emplace("张三",20);
m1.emplace("李四", 21);
// emplace_hint()函数
m1.emplace_hint(m1.begin(), "张三", 20);
相关知识点
- emplace()我们之前用到过,是c++11为了增加insert效率问题,提出的函数,这里同样使用emplace()函数给map对象添加键值对,不需要创建pair对象,我们直接在emplace()函数的参数中写上要添加的键值对就行,其内部会自己在相应位置创建一个pair对象。
两函数的区别
- emplace()和emplace_hint()的区别是,emplace_hint()函数的第一个参数传入一个迭代器,用来指向插入元素的位置,后面的参数形式和emplace()一样。 (也就是输emplace_hint()用于在指定位置插入数据)
在指定位置插入时应该注意
- map在指定位置插入数据和set是一样的,因为其都是有序的,所以即使我们指定了插入的位置,我们插入的数据也不一定会在对应位置上,因为插入的时候底层会根据你插入的键值与原来数据进行比较,放到相应的位置上。 所以,即使我们指定了插入位置,数据也不一定会放到哪个位置。
7. map删除元素
代码: erase()和clear()函数
map<string, int> m1{ {"张三",25},{"李四",26} };
// 擦除对应的数据
m1.erase("张三");
m1.erase(m1.begin());
m1.erase(m1.begin(), m1.end());
// 请空map中的元素
m1.clear();
相关知识点
- erase(key); // 删除键值为key的键值对
- erase(iter); // 删除迭代器iter指向位置的键值对
- erase(beg,end); // 删除迭代器beg和迭代器end范围内的键值对
- clear(); // 删除map中所有的键值对
erase()函数的返回值
- erase(key); // 返回的是size_t(或者size_type)类型,用于表示删除的键值个数。(因为map中的键不能相同,所以使用这重载返回的值只能为1或者0,但是multimap就可以大于1了)
map<string,int>::size_type t = m1.erase("张三");
- erase(iter);和erase(beg,end); // 返回的是删除键值对下一个键值对的迭代器。
map<string,int>::iterator it1 = m1.erase(m1.begin());
map<string,int>::iterator it2 = m1.erase(m1.begin(), m1.end());
erase()函数和循环结合删除元素时注意事项
注意: 在erase和循环结合使用的时候,应该注意删除时迭代器的指向。(在vector中详述)
8. map查找元素
代码: 使用find()函数
map<string, int> m1{ {"张三",25},{"李四",26} };
map<string,int>::iterator it1 = m1.find("张三");
if (it1 != m1.end()) {
cout << (*it1).first << ":" << (*it1).second << endl;
}
else {
cout << "没有找到!!!" << endl;
}
相关知识点
- find(key); // 查找对应键值的键值对,返回一个迭代器,指向与key相同键值的元素。
如何判断find()是否查找成功
- find()如果没有找到对应元素,那么就会返回一个和end()函数返回值一样的迭代器,所以我们判断是否查找成功,就可以通过find()返回的迭代器是否等于end()返回的迭代器。
代码:使用[]和at()访问
在前面已经说过了
代码: 使用lower_bound(),upper_bound()和equal_range()函数
map<int, string> m1{ {25,"张三"},{26,"李四"} };
map<int, string>::iterator it1 = m1.lower_bound(25);
map<int, string>::iterator it2 = m1.upper_bound(25);
pair<map<int, string>::iterator,map<int, string>::iterator> p1 = m1.equal_range(25);
相关知识点
- lower_bound(key); // 此函数返回指向map中键值对的键值>=key的第一个元素的迭代器(迭代器指向的是pair类型)
- upper_bound(key); // 此函数返回指向map中键值对的键值>key的第一个元素的迭代器
- equal_range(key); // 此函数返回一个pair对象,内部包含两个迭代器,第一个迭代器指向键值与key相同的第一个键值对的位置,第二个迭代器指向键值与key相同的最后一个键值对的下一个位置。(因为map中的键值不能相同,所以对于map两个迭代器的范围最大为1,但是对于multimap就可以大于1了)
如果没有我们要找的键值会怎么样
- 如果key不存在,那么两个迭代器就都指向按照规则key的下一个元素,(如果从小到大排列就指向第一个key的元素)。 当然如果按照规则,set排在最后,则两个迭代器都指向最后一个元素的下一位。(比如: 从小到大排时,set比map中的元素都要大)
- 举个例子,lower_bound(key); 要找到是>=key的键值对(并且排序是从小到大排),如果键值为key的键值对不存在,那么返回的两个迭代器,就会指向第一个键值>key的键值对。
9. map的排序规则
- map和set是类似的,其内部都是有序的,同样我们也都可以指定数据的排序规则(使用函数对象)
- 在默认情况下map是使用内置的less函数对象,进行从小到大排序的。
map<int, string,greater<int>> m1{ {25,"张三"},{26,"李四"} };
- 上面我们使用另外一个内置的函数对象greater,其是让map从大到小排列。
- 注意: 函数对象我们只需要指定一个类型就行,用这个类型的数据作为排序的数据。
10. map的value_comp()函数
map<int, string, greater<int>>::value_compare v1 = m1.value_comp();
map<int, string, greater<int>>::value_type t1 = make_pair(25,"张三");
map<int, string, greater<int>>::value_type t2 = make_pair(26,"李四");
if (v1(t1, t2)) {
cout << "t1在t2之前" << endl;
}
else {
cout << "t2在t1之后" << endl;
}
相关知识点
- value_comp(); // 返回一个map<>::value_compare的函数对象。
- 此函数对象重载的()运算符,支持两个类型为value_type的参数。(就是容器内存储数据的类型,map中为pair)
- 我们可以使用value_compare的函数对象,传入两个对应类型的参数,其会返回第一个个参数的键是否在第二个参数的键的前面,如果是:返回true,如果不是:返回false。
注意: 上面判断第一个参数的键是否在第二个参数的键的前面,是根据我们指定的容器的排序规则进行判断的。
比如: map指定从小到大排,键25就在键26的前面。
注意: 两个参数只要满足类型规则就行,不需要在容器当中,可以理解为用来判断value_type类型的数据,在容器指定的规则下谁前谁后。
11. map中的key_comp()函数
map<int, string,greater<int>> m1{ {25,"张三"},{26,"李四"} };
greater<int> g1 = m1.key_comp();
if (g1(1, 2)) {
cout << "1在2之前" << endl;
}
else {
cout << "1在2之后" << endl;
}
相关知识点
- key_comp(); // 无参数,返回一个函数对象或者函数指针,也就是我们指定的容器排序规则。(map是第三个类型参数指定)
如上: 代码中我们使用的map容器使用greater的内置函数对象进行排序,所以此函数返回的就是一个greater的函数对象。
- 我们可以使用返回的函数对象重载的()运算符,传入对应类型的两个参数,根据对应的规则判断传入参数谁前谁后。(按照规则,第一个参数在前返回true,第一个参数再回返回false)
12. map的其它函数
- swap(m1); //使调用此函数的map容器和m1的元素进行互换
- empty(); // 判断map容器是否为空
- max_size(); // 和vector类似
13. map和multimap的不同之处
multimap和map的函数大多数在使用的时候都是一样的,我们就不再说明了。
但是由于multimap可以存放不同的元素所以和map会有点区别。
区别:
- multimap在调用erase(key),方法时期返回值可以大于1。
- 同理count(key)这个函数的返回值也可以大于1。
- lower_bound(key)、upper_bound(key)、equal_range(key)其对应查找的数据范围也不再是一个,所以这些函数更加常用于multimap。
注意事项
- 由于map内部是有序的,所以我们不能随便修改其内部的值,因为如果修改了某一位置的值,很可能会导致其不再是有序排列的了。所以使用迭代器(即使迭代器不是const修饰的)或者其它方式都不能对map中的元素进行修改。如果要修改,那必须将这个元素删除,然后再添加一个新元素。
- size_type和value_type和vector的用法一样。(或者其他的内嵌类型)
- multimap是类似的。