当前位置：网站首页>【STL】关联容器之map用法总结

【STL】关联容器之map用法总结

2022-06-23 05:57:00 【舒泱】

       

一、基本原理

        map是C++标准库提供的关联容器之一，保存的是键值对（key-value），我们可以通过key快速查找到其对应的value。map底层使用的数据结构是红黑树，因此在map中查找、添加或删除元素时间复杂度都是O(log(n))。此外，map中的元素还是有序的。

       
map使用场景：

        现在假设有一个寝室501，寝室有4个学生，我们要用一种容器来保存这4个学生的学号和姓名，需求是我要通过学号来查找这个学号对应的姓名。

        此时我们用一个map来保存，学号作为key，姓名作为value，一个学生的这两个信息作为map的一个元素pair（pair用法总结），这4个元素是按学号(key)升序存放的，我们可以通过学号来得到对应的姓名。

        也许你会有这样的疑问，为什么要用关联容器呢，我用一个二维数组不是也一样能存放寝室4个学生的学号和姓名吗？

        是的，存是可以存，但是操作的时间复杂度就不一样了，比如我知道学号"sc0303"，我想查找对应的姓名，如果用map保存的，红黑树是一种自平衡的二叉搜索树，只需要O(log(n))的时间就能查到对应的姓名。如果用的二维数组保存的，需要从头遍历二维数组的第一列，需要O(n)的时间才能查到。这就是使用map的意义。

在这里插入图片描述

       

       

       

二、用法

       map中的元素是一对对键值对，类型pair，用法可参考博客pair用法总结
       

初始化

map<T1,T2>    容器名;T1、T2是类型名，可以是基本数据类型int、double等，也可以是类类型string等
map<T1,T2>   m1;创建一个名为m1的空map，key的类型为T1，value的类型为T2
map<T1,T2>   m1{p1,p2……};m1中的元素被初始化为p1,p2……，p1、p2是pair类型
map<T1,T2>   m1{ {key1,value1},{key2,value2}……};m1中的元素被初始化为 键值对{key1,value1},{key2,value2}……
map<T1,T2>   m2(m1);m2中包含和m1一样的元素
map<T1,T2>   m2=m1;m2中包含和m1一样的元素

程序示例：

pair<string, string> p1("sc0301","小杨");	            // 方式一，创建一个pair名为p1
pair<string, string> p2 = make_pair("sc0302", "小马");	// 方式二，make_pair函数返回一个用"sc0302"和 "小马"初始化的pair
pair<string, string> p3("sc0303", "小王");
pair<string, string> p4("sc0304", "小何");

map<string, string> m1;                 // 创建一个空map
map<string, string> m2{
     p1,p2,p3,p4 };  // 创建一个包含键值对p1、p2、p3、p4的map
map<string, string> m3{
     {
    "sc0301","小杨"},{
    "sc0302", "小马"},{
    "sc0303", "小王"},{
    "sc0304", "小何"} }; // 效果同上一句
map<string, string> m4(m2);   // 创建一个map，m4中包含和m2一样的元素
map<string, string> m5 = m2;  // 创建一个map，m5中包含和m2一样的元素

       

访问元素

访问元素
T2 value = m1[key];得到关键字key对应的值value
m1.at(key);得到关键字key对应的值value
*iter访问迭代器iter指向的元素
获取迭代器
m1.begin();获取指向m1首元素的迭代器
m1.end();获取指向m1尾元素的后一个位置的迭代器
m1.rbegin();获取指向m1首元素的前一个位置的迭代器
m1.rend();获取指向m1尾元素的迭代器
m1.cbegin(); m1.cend();含义同上，但获取到的是const_iterator
m1.crbegin(); m1.crend();含义同上，但获取到的是const_iterator

程序示例：

string p2_name = m2["sc0302"];	   // 得到学号（关键字）"sc0302"对应的姓名（值）
string p3_name = m2.at("sc0303");  // 得到学号"sc0303"对应的姓名 

map<string, string>::iterator it1 = m2.begin();	 // 得到指向m2首元素的迭代器
map<string, string>::iterator it2 = m2.end();    // 得到指向m2尾元素的下一个位置的迭代器
pair<string, string> p11 = *it1;   // 得到m2的首元素{"sc0301","小杨"}
string p1_ID = it1->first;         // 得到m2的首元素{"sc0301","小杨"}的fisrt成员
string p1_name = it1->second;	   // 得到m2的首元素{"sc0301","小杨"}的second成员

       

遍历容器

1、使用迭代器

for (auto it_b = m2.begin(), it_e = m2.end(); it_b != it_e;++it_b) {
    
	pair<string, string> current = *it_b;
	cout << "学号：" << it_b->first << "; 姓名:" << it_b->second << endl;
	// 上面这一句等同于下面这一句
	cout << "学号：" << current.first << "; 姓名:" << current.second << endl;
}

2、范围for语句

for (auto p : m2) {
    
	cout << "学号：" << p.first << "; 姓名:" << p.second << endl;
}

       

添加、修改元素

m1.insert(p1);在map中插入已有的pair
m1.insert({key1,value1});在map中插入键值对{key1,value1}
m1.insert(pair<T1, T2> (key1, value1));// 创建一个无名pair对象，并插入到map中
m1.insert(make_pair(key1, value1));// 创建一个无名pair对象，并插入到map中
m1.insert(map<T1, T2>::value_type (key1, value1));// 创建一个无名pair对象，并插入到map中
m1[key] = value;如果key不存在则插入该键值对，如果key已存在则修改该key对应的value
m1.emplace(p1);在map中插入已有的pair
m1.emplace(pair<T1, T2> (key1, value1));// 创建一个无名pair对象，并插入到map中

程序示例：

m1.insert(p1);	                   // 在map中插入已有的pair
m1.insert({
     "sc0302", "小马" });   // 插入键值对{ "sc0302", "小马" }
m1.insert(pair<string, string> ("sc0303", "小王"));  // 创建一个无名pair对象，并插入到map中 
m1.insert(make_pair("sc0303", "小王"));              // 要插入的关键字已在容器中，emplace/insert什么都不做
m1.insert(map<string, string>::value_type("sc0303", "小王"));   // 要插入的关键字已在容器中，emplace/insert什么都不做
m1["sc0304"] = "小何";             // 如果key不存在则插入该键值对，如果key已存在则修改该key对应的value。

m1.emplace(p1);			                             // 要插入的关键字已在容器中，emplace/insert什么都不做
m1.emplace(pair<string, string>("sc0303", "小王"));  // 要插入的关键字已在容器中，emplace/insert什么都不做

       

删除元素

m1.erase(key)删除关键字为key的元素
m1.erase(iter);删除迭代器iter指向的元素
m1.erase(iter1,iter2);删除迭代器iter1和ter2指向的范围中元素
m1.clear();删除m1中的所有元素

程序示例：

m1.erase("sc0301");		  // 删除关键字为"sc0301"的元素
auto iter = m1.begin();   // 指向m2的首元素的迭代器
m1.erase(iter);           // 删除迭代器指向的元素
auto iter1 = m1.begin(), iter2 = m1.end();
m1.erase(iter1, iter2);   // 删除迭代器iter1、iter2指向的范围中的元素
m2.clear();               // 删除容器中的全部元素

       

map的大小

m1.szie();获得m1的大小
m1.empty();若m1为空返回值为true，否则返回值为false

程序示例：

int s = m3.size();    // 获得m1的大小
bool e = m3.empty();  // 若m1为空返回值为true，否则返回值为false

       

查找

       我们通常不对关联容器使用泛型算法。我们可以用泛型find算法来查找map中的元素，但此算法会进行顺序搜索。使用关联容器定义的专用find成员会比调用泛型find快得多。
       

m1.find(key)返回一个迭代器，指向第一个关键字为key的元素，若key不在容器中，则返回尾后迭代器
m1.count(key);返回关键字等于key的元素的数量。对于不允许重复关键字的容器map，返回的值是0或1
m1.lower_bound(key);返回一个迭代器，指向第一个关键字不小于key的元素
m1.upper_bound(key);返回一个迭代器，指向第一个关键字大于key的元素

程序示例：

map<string, string>::iterator it = m4.find("sc0301");  // 查找关键字为"sc0301"的元素,返回一个迭代器
if (it == m4.end()) {
             // 若"sc0301"不在容器中，则it等于尾后迭代器
	cout << "未找到！" << endl;
}
else {
    
	pair<string, string> result1 = *it;	// 找到了
}

int result2 = m4.count("sc0305");  // 查找关键字为"sc0301"的元素,返回关键字等于"sc0301"的元素数量
if (result2==0) {
    
	cout << "未找到！" << endl;
}
else {
    
	cout << "找到了！" << endl;
}

map<string, string>::iterator it_up = m4.upper_bound("sc0301");  // 返回一个迭代器，指向第一个关键字大于"sc0301"的元素
pair<string, string> result3 = *it_up;

       

三、程序示例

#include <iostream>
#include <string>
#include <utility>
#include <map>

using namespace std;

int main() {
    	
	// 初始化-----------------------------------------------------------------------------------
	pair<string, string> p1("sc0301","小杨");	            // 方式一，创建一个pair名为p1
	pair<string, string> p2 = make_pair("sc0302", "小马");	// 方式二，make_pair函数返回一个用"sc0302"和 "小马"初始化的pair
	pair<string, string> p3("sc0303", "小王");
	pair<string, string> p4("sc0304", "小何");

	map<string, string> m1;                 // 创建一个空map
	map<string, string> m2{
     p1,p2,p3,p4 };  // 创建一个包含键值对p1、p2、p3、p4的map
	map<string, string> m3{
     {
    "sc0301","小杨"},{
    "sc0302", "小马"},{
    "sc0303", "小王"},{
    "sc0304", "小何"} }; // 效果同上一句
	map<string, string> m4(m2);   // 创建一个map，m4中包含和m2一样的元素
	map<string, string> m5 = m2;  // 创建一个map，m5中包含和m2一样的元素

	// 访问元素-----------------------------------------------------------------------------------
	string p2_name = m2["sc0302"];	   // 得到学号（关键字）"sc0302"对应的姓名（值） 
	string p3_name = m2.at("sc0303");  // 得到学号"sc0303"对应的姓名 
	
	map<string, string>::iterator it1 = m2.begin();	 // 得到指向m2首元素的迭代器
	map<string, string>::iterator it2 = m2.end();    // 得到指向m2尾元素的下一个位置的迭代器
	pair<string, string> p11 = *it1;   // 得到m2的首元素{"sc0301","小杨"}
	string p1_ID = it1->first;         // 得到m2的首元素{"sc0301","小杨"}的fisrt成员
	string p1_name = it1->second;	   // 得到m2的首元素{"sc0301","小杨"}的second成员

	// 遍历容器-----------------------------------------------------------------------------------
	for (auto it_b = m2.begin(), it_e = m2.end(); it_b != it_e;++it_b) {
    
		pair<string, string> current = *it_b;
		cout << "学号：" << it_b->first << "; 姓名:" << it_b->second << endl;
		// 上面这一句等同于下面这一句
		cout << "学号：" << current.first << "; 姓名:" << current.second << endl;
	}

	for (auto p : m2) {
    
		cout << "学号：" << p.first << "; 姓名:" << p.second << endl;
	}

	// 添加、修改元素-----------------------------------------------------------------------------------
	m1.insert(p1);	                   // 在map中插入已有的pair
	m1.insert({
     "sc0302", "小马" });   // 插入键值对{ "sc0302", "小马" }
	m1.insert(pair<string, string> ("sc0303", "小王"));  // 创建一个无名pair对象，并插入到map中 
	m1.insert(make_pair("sc0303", "小王"));              // 要插入的关键字已在容器中，emplace/insert什么都不做
	m1.insert(map<string, string>::value_type("sc0303", "小王"));   // 要插入的关键字已在容器中，emplace/insert什么都不做
	m1["sc0304"] = "小何";             // 如果key不存在则插入该键值对，如果key已存在则修改该key对应的value。

	m1.emplace(p1);			                             // 要插入的关键字已在容器中，emplace/insert什么都不做
	m1.emplace(pair<string, string>("sc0303", "小王"));  // 要插入的关键字已在容器中，emplace/insert什么都不做

	// 删除元素-----------------------------------------------------------------------------------
	m1.erase("sc0301");		  // 删除关键字为"sc0301"的元素
	auto iter = m1.begin();   // 指向m2的首元素的迭代器
	m1.erase(iter);           // 删除迭代器指向的元素
	auto iter1 = m1.begin(), iter2 = m1.end();
	m1.erase(iter1, iter2);   // 删除迭代器iter1、iter2指向的范围中的元素
	m2.clear();               // 删除容器中的全部元素

	// 大小-----------------------------------------------------------------------------------
	int s = m3.size();    // 获得m1的大小
	bool e = m3.empty();  // 若m1为空返回值为true，否则返回值为false

	// 查找-----------------------------------------------------------------------------------
	map<string, string>::iterator it = m4.find("sc0301");  // 查找关键字为"sc0301"的元素,返回一个迭代器
	if (it == m4.end()) {
             // 若"sc0301"不在容器中，则it等于尾后迭代器
		cout << "未找到！" << endl;
	}
	else {
    
		pair<string, string> result1 = *it;	// 找到了
	}

	int result2 = m4.count("sc0305");  // 查找关键字为"sc0301"的元素,返回关键字等于"sc0301"的元素数量
	if (result2==0) {
    
		cout << "未找到！" << endl;
	}
	else {
    
		cout << "找到了！" << endl;
	}

	map<string, string>::iterator it_up = m4.upper_bound("sc0301");  // 返回一个迭代器，指向第一个关键字大于"sc0301"的元素
	pair<string, string> result3 = *it_up;
}
原网站

版权声明
本文为[舒泱]所创，转载请带上原文链接，感谢
https://blog.csdn.net/weixin_43222324/article/details/112169852

边栏推荐

猜你喜欢

随机推荐