因为前些天做了一道题：PTA:查询首都或国名-CSDN博客
这道题我和朋友的实现方式不同，想要学习学习她的这种方式，于是乎有了这篇研究 map 的文章。
先学习一下 map 的基本定义吧：
map 是标准模板库（STL）中的一个关联容器，它存储的是键值对，而且每个键都是唯一的。
特性：红黑树实现，键唯一，自动排序。
PS：
红黑树是一种自平衡二叉搜索树，它在每个节点上增加了一个存储位来表示节点的颜色，可以是红色或黑色。红黑树通过限制从根到叶子节点的路径上节点的颜色，保证了最长路径不超过最短路径的两倍，因此它是近似平衡的。
红黑树具有以下特点：
● 每个节点不是红色就是黑色。
●根节点是黑色。
● 如果一个节点是红色的，则它的两个子节点
必须是黑色的（即没有连续的红色节点）。
● 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
接下来看看 map 中的一些基本操作。
1. 头文件
#include <map>
2. 定义和初始化
#include <iostream>
#include <map>
#include <string>
int main() {
// 定义一个存储string到int映射的map
std::map<std::string, int> myMap;
// 插入元素
myMap["apple"] = 1;
myMap["banana"] = 2;
myMap["cherry"] = 3;
// 另一种插入元素的方式
myMap.insert(std::make_pair("date", 4));
return 0;
}
3. 访问元素
可以通过键来访问 map 中的元素
#include <iostream>
#include <map>
#include <string>
int main() {
std::map<std::string, int> myMap = {{"apple", 1}, {"banana", 2}, {"cherry", 3}};
// 通过键访问元素
std::cout << "Value of apple: " << myMap["apple"] << std::endl;
// 使用find方法查找元素
auto it = myMap.find("banana");
if (it != myMap.end()) {
std::cout << "Value of banana: " << it->second << std::endl;
}
return 0;
}
4. 遍历元素
可以使用迭代器或者范围 for 循环来遍历 map
#include <iostream>
#include <map>
#include <string>
int main() {
std::map<std::string, int> myMap = {{"apple", 1}, {"banana", 2}, {"cherry", 3}};
// 使用迭代器遍历
for (auto it = myMap.begin(); it != myMap.end(); ++it) {
std::cout << it->first << ": " << it->second << std::endl;
}
// 使用范围for循环遍历
for (const auto& pair : myMap) {
std::cout << pair.first << ": " << pair.second << std::endl;
}
return 0;
}
5. 删除元素
可以使用 erase 来删除 map 中的元素
#include <iostream>
#include <map>
#include <string>
int main() {
std::map<std::string, int> myMap = {{"apple", 1}, {"banana", 2}, {"cherry", 3}};
// 通过键删除元素
myMap.erase("banana");
// 通过迭代器删除元素
auto it = myMap.find("cherry");
if (it != myMap.end()) {
myMap.erase(it);
}
return 0;
}
6. 检查元素是否存在
可以使用 count 或者 find 来检查某个键是否存在于 map 中
#include <iostream>
#include <map>
#include <string>
int main() {
std::map<std::string, int> myMap = {{"apple", 1}, {"banana", 2}, {"cherry", 3}};
// 使用count方法检查元素是否存在
if (myMap.count("apple") > 0) {
std::cout << "apple exists in the map." << std::endl;
}
// 使用find方法检查元素是否存在
auto it = myMap.find("date");
if (it == myMap.end()) {
std::cout << "date does not exist in the map." << std::endl;
}
return 0;
}
学习好基本定义后，现在来研究 map 在实际应用中的作用，用我最喜欢的 vector 与 map 做比较看看有哪些异同。
题目：
编写程序实现：首先从键盘输入若干个国名与首都的偶对，以空行作结束标记。然后输入一个国名或首都，输出对应的首都或国名；若不存在该国名或首都，则输出“查无此名”。
提示：可以同时创建两个字典。
输入格式:
每行输入一对国名与首都，以空格分隔。
输出格式:
在一行中输出结果。
输入样例1:
中国 北京
日本 东京
美国 华盛顿
英国 伦敦
德国 柏林
法国 巴黎
俄罗斯 莫斯科
英国
输出样例1:
伦敦
输入样例2:
中国 北京
日本 东京
美国 华盛顿
英国 伦敦
德国 柏林
法国 巴黎
俄罗斯 莫斯科
巴黎输出样例2:
法国
1）用 vector 的思路就是用一个二维数组的形式来构建一个 dictionary ，实现方式如下：
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main()
{
vector<vector<string>> dictionary;
string line;
while(getline(cin,line)&&!line.empty())
{
string country,capital;
int spaceIndex=0;
while(line[spaceIndex]!=' '&&spaceIndex<line.length())
{
spaceIndex++;
}
country=line.substr(0,spaceIndex);
capital=line.substr(spaceIndex+1);
vector<string> entry;
entry.push_back(country);
entry.push_back(capital);
dictionary.push_back(entry);
}
string search;
getline(cin,search);
bool found=false;
for(int i=0;i<dictionary.size();i++)
{
if(dictionary[i][0]==search)
{
cout<<dictionary[i][1]<<endl;
found=true;
break;
}
}
if(!found)
{
for(int i=0;i<dictionary.size();i++)
{
if(dictionary[i][1]==search)
{
cout<<dictionary[i][0]<<endl;
found=true;
break;
}
}
}
if(!found)
{
cout<<"查无此名"<<endl;
}
return 0;
}2）而用 map 的话，是应用键值对的方式来实现对应关系，代码如下：
#include<iostream>
#include<string>
#include<map>
using namespace std;
int main() {
map<string, string> capital;
map<string, string> country;
string country1, capital1;
while (getline(cin, country1)) {
if (country1.empty()) break;
size_t spacePos = country1.find(' ');//找到空格的地方
capital1 = country1.substr(0, spacePos);//把空格前的字符串赋值
country1 = country1.substr(spacePos + 1);
country[country1] = capital1;
capital[capital1] = country1;
}
string s;
getline(cin, s);
if (country.count(s) > 0) {//找到为1，没找到为0
cout << country[s] << endl;
}
else if (capital.count(s) > 0) {
cout << capital[s] << endl;
}
else {
cout << "查无此名" << endl;
}
return 0;
}我画了一个图来直观感受 map（有点丑，见谅了哈）
可以看到键与值是处于一种一一对应的关系（其实有点像是浏览器中，local storage的存储方式，也是一种键值对的存储方式）
比较一下两种方式的区别：
1）使用 vector 的话，因为 vector 是连续存储数据的，相比 map 的节点式存储，空间利用率更高；其次是插入操作快，通常的情况下时间复杂度仅仅是 O(1)。但是 vector 在遍历时会耗费更多的时间。而且直观上来看，也会发现，使用 map 的代码会更加简洁。
2）使用 map 的话，查找效率比较高，因为 map 内部是基于红黑树实现的，其查找操作的时间复杂度为 O( log n) ，（ n 是 map 中元素的数量）。而且 map 会自动根据键对元素进行排序，并且可以方便地插入、删除和查找键值对，确实有不小的优势。但是 map 会耗费更多的时间插入（虽然这一点在宏观上是感受不到的，毕竟计算机的运算速度实在是太快了），所以这个小缺点可以忽略不计。