STL之map与pair与unordered_map常用函数详解

STL之map与pair与unordered_map常用函数详解

一、map的概述

map是STL的一个关联容器,它提供一对一(其中第一个可以称为关键字,每个关键字只能在map中出现一次,第二个可能称为该关键字的值)的数据处理能力,由于这个特性,它完成有可能在我们处理一对一数据的时候,在编程上提供快速通道。这里说下map内部数据的组织,map内部自建一颗红黑树(一种非严格意义上的平衡二叉树),这颗树具有对数据自动排序的功能,所以在map内部所有的数据都是有序的,后边我们会见识到有序的好处。

下面举例说明:

众所周知,在定义数组的时候比如(int array[10]) ,array[0]=25,array[1]=10,其实就是一个映射,将0—>25,1—>10,就是将0映射到25,将1映射到10,这种一一对应的关系就是映射,就数组来说,他的下标和其下标所对应的值就是一种映射关系,但是这一种关系比较死板,于是就有map,这一种容器,map可以建立将任何基本类型(包括STL容器)映射到任何基本数据类型(包括STL容器)

二、map的定义与初始化(插入)

  • 单独定义一个map:
//  引入一个头文件
#include <map>
map<typename1,typename2> mp;
  • typename1是键值的数据类型

  • typename2是值的数据类型

  • 如果是字符串映射到整型数组,键值必须使用string类型,而不能使用char数组。

    这是因为char作为数组,不能作为键值。

  • map的键和值可以是STL的容器,我们将set映射到一个字符串

map<set<int>,string> mp;

三、map的元素的访问

  • map中的容器值可以通过:下标和迭代器进行访问。
  • 下标访问map键值是唯一的
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main()
{
map<char,int> mp;
mp['c']=20;
mp['c']=30; // 由于键值唯一,第一个他的值将会被覆盖
cout<<mp['c']<<endl;
return 0;
}
// 输出
30
  • 通过迭代器访问

    map的迭代器与其他STL容器相同

map<typename1,typename2>::iterator it;
// 由于一个it对应两个值,我们使用 it->first 访问键 it->second 访问值
  • 下面来看一个示例:

    PS:下面我以3种不同的方式进行插入不懂得可以参照这一篇文章:

//   以类似数组的的表达方式来进行
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main()
{
map<char,int> mp;
char key;
int val;
int t=5;
while(t--)
{
cin>>key>>val;
mp[key]=val;
}
// 通过迭代器来访问
for(map<char,int>::iterator it=mp.begin();it!=mp.end();it++)
{
cout<<it->first<<" "<<it->second<<endl;
}
return 0;
} a 5
s 8
z 6
p 3
t 7 a 5
p 3
s 8
t 7
z 6

其实细心的小伙伴已经发现,其输出结果是按照键值进行升序排序的。C++11中有unordered_map,以散列来代替map内部的红黑树实现,其不需要排序速度就 快很多了。下面会有介绍。

#include <iostream>
#include <map>
#include <string>
using namespace std;
int main()
{
map<char,int> mp;
char key;
int val;
int t=5;
while(t--)
{
cin>>key>>val;
mp.insert(make_pair(key,val)); // 以make_pair来插入
}
for(map<char,int>::iterator it=mp.begin();it!=mp.end();it++)
{
cout<<it->first<<" "<<it->second<<endl;
}
return 0;
}
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main()
{
map<char,int> mp;
char key;
int val;
int t=5;
while(t--)
{
cin>>key>>val;
mp.insert(pair<char,int>(key,val)); // 以pair来插入
}
for(map<char,int>::iterator it=mp.begin();it!=mp.end();it++)
{
cout<<it->first<<" "<<it->second<<endl;
}
return 0;
}
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main()
{
map<char,int> mp;
char key;
int val;
int t=5;
while(t--)
{
cin>>key>>val;
mp.insert(pair<char,int>(key,val));
}
// 这种基于范围的for循环,只有C++11以上才可以
for(auto it=mp.begin();it!=mp.end();it++)
{
cout<<it->first<<" "<<it->second<<endl;
}
return 0;
}
  • 用insert函数插入value_type数据,下面举例说明
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {
map<int, string> mapStudent;
mapStudent.insert(map<int,string>::value_type(1,"student1"));
mapStudent.insert(map<int,string>::value_type(2,"student2"));
mapStudent.insert(map<int,string>::value_type(3,"student2"));
for(map<int,string>::iterator it=mapStudent.begin();it!=mapStudent.end();it++)
cout<<it->first<<" "<<it->second<<endl;
return 0;
} // 输出结果:
G:\clion\qifei\cmake-build-debug\qifei.exe
1 student1
2 student2
3 student2 Process finished with exit code 0

四.map常用函数解析

  • find()用find函数来定位数据出现位置,它返回的一个迭代器,当数据出现时,它返回数据所在位置的迭代器,如果map中没有要查找的数据,它返回的迭代器等于end函数返回的迭代器,程序说明:
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {
map<int, string> mapStudent;
mapStudent.insert(map<int,string>::value_type(1,"student1"));
mapStudent.insert(map<int,string>::value_type(2,"student2"));
mapStudent.insert(map<int,string>::value_type(3,"student2"));
map<int,string>::iterator pter=mapStudent.find(2);
cout<<pter->first<<" "<<pter->second<<endl;
return 0;
}
// 输出结果:
2 student2
  • erase()删除元素有两种方法:删除单个元素;删除一个区间的元素。

    1. 删除单个元素:

      • mp.erase(it), it为要删除的元素的迭代器

        #include <iostream>
        #include <map>
        #include <string>
        using namespace std;
        int main() {
        map<int, string> mapStudent;
        mapStudent.insert(map<int,string>::value_type(1,"student1"));
        mapStudent.insert(map<int,string>::value_type(2,"student2"));
        mapStudent.insert(map<int,string>::value_type(3,"student2"));
        map<int,string>::iterator pter=mapStudent.find(2);
        mapStudent.erase(pter);
        for(map<int,string>::iterator it=mapStudent.begin();it!=mapStudent.end();it++)
        cout<<it->first<<" "<<it->second<<endl;
        return 0;
        } // 输出结果:
        1 student1
        3 student2
        • 通过键值来删除一个元素:
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {
map<int, string> mapStudent;
mapStudent.insert(map<int,string>::value_type(1,"student1"));
mapStudent.insert(map<int,string>::value_type(2,"student2"));
mapStudent.insert(map<int,string>::value_type(3,"student2"));
map<int,string>::iterator pter=mapStudent.find(2);
mapStudent.erase(2);
for(map<int,string>::iterator it=mapStudent.begin();it!=mapStudent.end();it++)
cout<<it->first<<" "<<it->second<<endl;
return 0;
} // 输出结果:
1 student1
3 student2

2.erase(first,last),可以删除整个区间的元素;删除区间为[first,last)。

#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {
map<int, string> mapStudent;
mapStudent.insert(map<int,string>::value_type(1,"student1"));
mapStudent.insert(map<int,string>::value_type(2,"student2"));
mapStudent.insert(map<int,string>::value_type(3,"student3"));
mapStudent.insert(map<int,string>::value_type(4,"student4"));
mapStudent.insert(map<int,string>::value_type(5,"student5"));
mapStudent.insert(map<int,string>::value_type(6,"student6"));
mapStudent.insert(map<int,string>::value_type(7,"student7"));
map<int,string>::iterator pter=mapStudent.find(4);
mapStudent.erase(pter,mapStudent.end());
for(map<int,string>::iterator it=mapStudent.begin();it!=mapStudent.end();it++)
cout<<it->first<<" "<<it->second<<endl;
return 0;
} // 输出结果:
1 student1
2 student2
3 student3
  • size() ,可以获取map中的映射对数。
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {
map<int, string> mapStudent;
mapStudent.insert(map<int,string>::value_type(1,"student1"));
mapStudent.insert(map<int,string>::value_type(2,"student2"));
mapStudent.insert(map<int,string>::value_type(3,"student3"));
mapStudent.insert(map<int,string>::value_type(4,"student4"));
mapStudent.insert(map<int,string>::value_type(5,"student5"));
mapStudent.insert(map<int,string>::value_type(6,"student6"));
mapStudent.insert(map<int,string>::value_type(7,"student7"));
cout<<mapStudent.size()<<endl;
return 0;
} // 输出结果:
7
  • clear(),请空所有的元素。
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {
map<int, string> mapStudent;
mapStudent.insert(map<int,string>::value_type(1,"student1"));
mapStudent.insert(map<int,string>::value_type(2,"student2"));
mapStudent.insert(map<int,string>::value_type(3,"student3"));
mapStudent.insert(map<int,string>::value_type(4,"student4"));
mapStudent.insert(map<int,string>::value_type(5,"student5"));
mapStudent.insert(map<int,string>::value_type(6,"student6"));
mapStudent.insert(map<int,string>::value_type(7,"student7"));
mapStudent.clear();
cout<<mapStudent.size()<<endl;
return 0;
} // 输出结果:
0

map和unordered_map(c++11)的使用

unordered_map的用法和map是一样的,提供了 insert,size,count等操作,并且里面的元素也是以pair类型来存贮的。其底层实现是完全不同的,上方已经解释了,但是就外部使用来说却是一致的

map和unordered_map的差别

需要引入的头文件不同

map: #include < map >
unordered_map: #include < unordered_map >

内部实现机理不同

map: map内部实现了一个红黑树(红黑树是非严格平衡二叉搜索树,而AVL是严格平衡二叉搜索树),红黑树具有自动排序的功能,因此map内部的所有元素都是有序的,红黑树的每一个节点都代表着map的一个元素。因此,对于map进行的查找,删除,添加等一系列的操作都相当于是对红黑树进行的操作。map中的元素是按照二叉搜索树(又名二叉查找树、二叉排序树,特点就是左子树上所有节点的键值都小于根节点的键值,右子树所有节点的键值都大于根节点的键值)存储的,使用中序遍历可将键值按照从小到大遍历出来。

unordered_map: unordered_map内部实现了一个哈希表(也叫散列表,通过把关键码值映射到Hash表中一个位置来访问记录,查找的时间复杂度可达到O(1),其在海量数据处理中有着广泛应用)。因此,其元素的排列顺序是无序的。哈希表详细介绍

优缺点以及适用处

map:

优点:

有序性,这是map结构最大的优点其元素的有序性在很多应用中都会简化很多的操作

红黑树,内部实现一个红黑书使得map的很多操作在lgn的时间复杂度下就可以实现,因此效率非常的高

缺点:空间占用率高,因为map内部实现了红黑树,虽然提高了运行效率,但是因为每一个节点都需要额外保存父节点、孩子节点和红/黑性质,使得每一个节点都占用大量的空间

适用处:对于那些有顺序要求的问题,用map会更高效一些

unordered_map:

优点: 因为内部实现了哈希表,因此其查找速度非常的快

缺点: 哈希表的建立比较耗费时间

适用处:对于查找问题,unordered_map会更加高效一些,因此遇到查找问题,常会考虑一下用unordered_map

总结:

内存占有率的问题就转化成红黑树 VS hash表 , 还是unorder_map占用的内存要高。

但是unordered_map执行效率要比map高很多

对于unordered_map或unordered_set容器,其遍历顺序与创建该容器时输入的顺序不一定相同,因为遍历是按照哈希表从前往后依次遍历的

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;
int main() {
unordered_map<int, string> mapStudent;
mapStudent.insert(unordered_map<int,string>::value_type(2,"student2"));
mapStudent.insert(unordered_map<int,string>::value_type(4,"student4"));
mapStudent.insert(unordered_map<int,string>::value_type(5,"student5"));
mapStudent.insert(unordered_map<int,string>::value_type(3,"student3"));
mapStudent.insert(unordered_map<int,string>::value_type(7,"student7"));
mapStudent.insert(unordered_map<int,string>::value_type(6,"student6"));
mapStudent.insert(unordered_map<int,string>::value_type(1,"student1"));
for(auto it=mapStudent.begin();it!=mapStudent.end();it++)
cout<<it->first<<" "<<it->second<<endl;
return 0;
} // 输出结果:
G:\clion\qifei\cmake-build-debug\qifei.exe
1 student1
6 student6
7 student7
2 student2
4 student4
5 student5
3 student3 Process finished with exit code 0
上一篇:译《The Part-Time Parliament》——终于读懂了Paxos协议!


下一篇:oracle常用函数详解(详细)