美文网首页
STL | Map(映射)的使用(一)

STL | Map(映射)的使用(一)

作者: 0与1的邂逅 | 来源:发表于2019-06-11 16:28 被阅读0次

写在前面:

Map是STL的一个关联容器,它提供一对一(其中第一个可以称为关键字,每个关键字只能在map中出现一次,第二个可能称为该关键字的值)的数据处理能力。由于这个特性,它完成有可能在我们处理一对一数据的时候,在编程上提供快速通道。

Map

图片来源:https://www.cnblogs.com/empty16/p/6395813.html

这里说下map内部数据的组织,map内部自建一颗红黑树(一 种非严格意义上的平衡二叉树),这颗树具有对数据自动排序的功能,所以在map内部所有的数据都是有序的。

这里略过红黑树,感兴趣的童鞋自行百度,可以先从二叉排序树入手。(后面有时间我再来总结)



进入正题:

一. 定义一个Map(映射)

map共提供了6个构造函数,这块涉及到内存分配器这些东西,我也没深入去了解。因此,我们就来介绍最常见的一种构造方法:

#include<map>// 头文件
map<char,int>Map;// 定义一个从char类型到int类型的映射Map

构造函数包含了两个参数,第一个参数是关键字Key,第二个参数是关键字的值Key_Value。这两个参数可以是任意类型

通常,我们习惯用typedef来定义Map,为什么呢?因为在定义迭代器的时候,我们可以不用多写多余的重复代码,而且要修改Map的时候,也不需要修改多处地方。

#include<map>
typedef map<char,int> m;// 自定义一种类型——m
m Map;

二. 插入数据

定义好了映射Map,接下来就需要向Map插入数据。插入数据主要有以下三种方法。

  • 用insert函数插入pair数据
    (pair是什么,其实就是一个结构体,包含(first,second)这样的数据的结构体)
#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
typedef map<char,int>m;
m Map;

int main()
{
    char ch;
    for(int i=0;i<10;i++)
    {
        cout<<"input character:";
        cin>>ch;
        // 方法一:用insert函数插入pair数据
        Map.insert(pair<char,int>(ch,i));
    }
}
  • 用insert函数插入value_type数据
#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
typedef map<char,int>m;
m Map;

int main()
{
    char ch;
    for(int i=0;i<10;i++)
    {
        cout<<"input character:";
        cin>>ch;
        // 方法二:用insert函数插入value_type数据
        // 这里就可以看出用typedef定义Map的好处
        Map.insert(m::value_type(ch,i));
    }
}
  • 用数组方式插入数据
    形式:Map[Key]=Key_Value;
#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
typedef map<char,int>m;
m Map;

int main()
{
    char ch;
    for(int i=0;i<10;i++)
    {
        cout<<"input character:";
        cin>>ch;
        // 方法三:用数组方式插入数据
        Map[ch]=i;
    }
}

以上三种插入方法,虽然都可以实现数据的插入,但是它们是有区别的。当然,第一种和第二种在效果上是完成一样的。

insert函数插入数据,在数据的插入上涉及到集合的唯一性这个概念,即当map中有这个关键字时,想要再次插入该关键字,insert操作是插入不了的。

但是用数组方式就不同了,它可以覆盖以前该关键字对应的值。

下面用一个程序来验证。

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

typedef map<char,int> m;
m Map_1;// 数组方式插入 
m Map_2;// insert函数插入 

int main()
{
    char ch;
    for(int i=0;i<4;i++)
    {
        cout<<"input the character:";
        cin>>ch;
        Map_1[ch]=i;
        Map_2.insert(pair<char,int>(ch,i));
    }
    m::iterator iter_1,iter_2;// 前向迭代器 
    cout<<"--------------------------\n";
    cout<<"数组:\n";
    for(iter_1=Map_1.begin();iter_1!=Map_1.end();iter_1++)
    {
        cout<<iter_1->first<<"->"<<iter_1->second<<endl;
    }
    cout<<"--------------------------\n";
    cout<<"insert:\n";
    for(iter_2=Map_2.begin();iter_2!=Map_2.end();iter_2++)
    {
        cout<<iter_2->first<<"->"<<iter_2->second<<endl;
    }
    cout<<"\n";
    
    // 重新插入已经存在的关键字Key
    // 尝试将其Key_Value值改为520 
    cout<<"重新插入character:\n";
    cin>>ch;
    Map_1[ch]=520;
    Map_2.insert(pair<char,int>(ch,520));
    
    cout<<"--------------------------\n";
    cout<<"数组:\n";
    for(iter_1=Map_1.begin();iter_1!=Map_1.end();iter_1++)
    {
        cout<<iter_1->first<<"->"<<iter_1->second<<endl;
    }
    cout<<"--------------------------\n";
    cout<<"insert:\n";
    for(iter_2=Map_2.begin();iter_2!=Map_2.end();iter_2++)
    {
        cout<<iter_2->first<<"->"<<iter_2->second<<endl;
    }
}
验证结果
三. Map容器的大小:

Map容器已经插入了数据,那么Map容器的大小(目前)是多大呢?或者说插入了多少组数据呢?

我们可以用size函数,这跟STL中其他容器(如vector)用法一致。


四. 遍历Map容器:

既然插入了数据,那么我们怎么去遍历呢?(借此也看看是不是插入成功)同样的,也有三种方法可以对Map容器进行遍历。

  • 前向迭代器遍历
map<char,int>::iterator iter;// 前向迭代器 
for(iter=Map.begin();iter!=Map.end();iter++)
{
    cout<<iter->first<<" "<<iter->second<<endl;
}
  • 反向迭代器遍历
    所谓反向,就是从末尾开始遍历。
map<char,int>::reverse_iterator r_iter;// 反向迭代器
for(r_iter=Map.rbegin();r_iter!=Map.rend();r_iter++)
{
    cout<<r_iter->first<<" "<<r_iter->second<<endl;
} 
  • 数组的形式遍历
    这种方法好像有bug,我的编译器是DEVC++,没在VS上跑。因此,这里就不加以说明了,有兴趣的童鞋也可以自己去尝试。不过一般情况下,用迭代器迭代就足够了。相关信息可以看看这篇博客

判定关键字是否在Map中:

这里有三种判断关键字是否在Map中的方法。

  • ① 用count()函数
    由于Map的特性,一对一的映射关系(且无重复元素),决定了count函数的返回值只有两个,要么是0,要么是1。若关键字在Map中,count函数返回1;不在则返回0。
    使用形式:count(Key)

  • ② 用find()函数
    用find函数来定位数据出现位置,它返回的一个迭代器。当数据出现时,它返回数据所在位置的迭代器,如果map中没有要查找的数据,它返回的迭代器等于end函数返回的迭代器。

map<char,int>Map;
map<char,int>::iterator iter=Map.find(Key);
if(iter==Map.end())cout<<"can't find"<<endl;
else cout<<"find"<<endl;
  • ③ 用lower_bound()函数upper_bound()函数或者equal_value()函数:(虽然方法显示笨重了些,但是体现了Map数据的有序性
  1. lower_bound():返回键值>=给定元素的第一个位置(下界)
  2. upper_bound():返回键值>给定元素的第一个位置(上界)
  3. equal_range():返回特殊条目的迭代器对。具体表现为:
    返回一个pair,pair里面第一个变量是lower_bound返回的迭代器,pair里面第二个迭代器是upper_bound返回的迭代器。

如果这两个迭代器(上、下界)相等的话,则说明Map中不存在这个关键字。

if(iter_1!=iter_2)cout<<"find"<<endl;
else cout<<"can't find"<<endl;

完整代码,测试lower_bound、upper_bound、equal_value函数 👇👇👇

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

typedef map<char,int>m;
m Map;

int main()
{
    char ch;
    for(int i=0;i<5;i++)
    {
        cout<<"input character:";
        cin>>ch;
        Map[ch]=i;
    }
    m::iterator iter_1,iter_2;
    iter_1=Map.lower_bound('C');
    iter_2=Map.upper_bound('C');
    cout<<"lower_bound:\n";
    cout<<iter_1->first<<"->"<<iter_1->second<<endl;
    cout<<"upper_bound:\n";
    cout<<iter_2->first<<"->"<<iter_2->second<<endl;
    cout<<"*********************\n";
    cout<<"queal_value:\n";
    pair<m::iterator,m::iterator> p=Map.equal_range('C');
    iter_1=p.first;
    iter_2=p.second;
    cout<<iter_1->first<<"->"<<iter_1->second<<endl;
    cout<<iter_2->first<<"->"<<iter_2->second<<endl;
} 

查找关键字:

find函数:返回一个pair对象,pair->first表示Key的值,pair->second表示Key_Value的值。

result = Map.find(Key);
cout << result->first << "->" << result->second << endl;


Map总结:

为什么选择Map?/ Map的功能作用?
  • 自动建立Key-Key_Value的对应(映射)。Key 和 Key_Value可以是任意你需要的类型。

  • 根据Key值快速查找记录,查找的复杂度基本是O(log(N)),如果有1000个记录,最多查找10次,1,000,000个记录,最多查找20次。

  • 快速插入Key - Key_Value 记录。

  • 快速删除记录。

  • 根据Key 修改Key_Value记录。

  • 遍历所有记录。


Map的基本操作函数:
*begin() 返回指向Map头部的迭代器
*clear() 删除所有元素
*count() 返回指定元素出现的次数,Map中只有0和1两个值
*empty() 如果Map为空,则返回true
*end() 返回指向Map末尾的迭代器
equal_range() 返回特殊条目的迭代器对
*erase() 删除一个元素
*find() 查找一个元素
get_allocator() 返回Map的配置器
*insert() 插入元素
key_comp() 返回比较元素Key的函数
lower_bound() 返回键值>=给定元素的第一个位置
max_size() 返回可以容纳的最大元素个数
*rbegin() 返回一个指向Map尾部的反向迭代器
*rend() 返回一个指向Map头部的反向迭代器
*size() 返回map中元素的个数
*swap() 交换两个Map容器
upper_bound() 返回键值>给定元素的第一个位置
value_comp() 返回比较元素Key_Value的函数

PS:带*的函数:表示我比较常用的函数。



写在最后:

参考资料:

因为文章篇幅原因,剩下一些内容(删除和排序)就留着下次再讲。

其实,对于STL,很多容器都具有功能相同的函数、迭代器。前面讲过vector容器,也是经常需要被用到的。就我而言,vector可能比map用的频率还大一些。

关于vector容器的文章:

相关文章

  • 算法笔记(12)| STL之map

    map翻译为映射,即map可以将任何基本类型(包括STL容器)映射到任何基本类型。使用map需要添加头文件#inc...

  • STL | Map(映射)的使用(一)

    写在前面: Map是STL的一个关联容器,它提供一对一(其中第一个可以称为关键字,每个关键字只能在map中出现一次...

  • 4. 入门并实践STL——map篇

    map map可以将任何基本类型(包括stl容器)映射到任何基本类型(包括stl容器) map的键是唯一的, 如果...

  • STL | Map(映射)的使用(二)

    对Map进行排序: 前面我们已经讲了Map的一些常见用法,同时提到了Map是有序的,自动按照Key进行升序排序(S...

  • STL: list ,set ,pair.map的使用

    STL: list ,set ,pair.map的使用

  • map

    map可以将任何基本类型(包括STL容器)映射到任何基本类型(包括STL容器),也就可以建立string型到 in...

  • STL库的映射容器的使用实例

    STL库的映射容器有两个,一个是map,另一个是multimap。 这两个容器具体的使用原则,主要的区别在于key...

  • Java数据结构总结之Map

    Java中使用Map接口描述映射结构,映射Map是一个独立的接口,描述的是键key-值value的对应关系,Map...

  • map hash_map(挖坑)

    学习内容来自C++ STL中哈希表 hash_map 未学C++之哈希表的使用 map 使用count,返回的是被...

  • Scala 箭头

    -> 映射,map时使用:a->5,把a映射成5 <- 遍历: for(a<-books) { printIn(a...

网友评论

      本文标题:STL | Map(映射)的使用(一)

      本文链接:https://www.haomeiwen.com/subject/rwvffctx.html