C++回顾map的用法
map<T, T>是C++的STL中存储key-value键值对数据结构的最基础的模板类,相对于multimap可以重复的key值,map的key是非重复的。
C++的reference这样说明的:
std::map
is a sorted associative container that contains key-value pairs with unique keys. Keys are sorted by using the comparison function Compare
. Search, removal, and insertion operations have logarithmic complexity. Maps are usually implemented as red-black trees.
首先map里的数据是以key根据Compare函数排序的(sorted),可以用标准库提供的迭代器实现元素的有序遍历。下面的代码运行后输出"Hello, I am Bryce";
#include<iostream>
#include<map>
using namespace std; int main(){
map<int, string> amap; //contains string "Hello,I am Bryce."
amap.insert(make_pair(,"Hello,"));
amap.insert(make_pair(,"Bryce."));
amap.insert(make_pair(,"I "));
amap.insert(make_pair(,"am "));
string output = "";
for(map<int, string>::iterator it = amap.begin(); it!=amap.end(); ++it){
output += it->second;
}
cout<< output<<endl; return ;
}
再次map底层是由红黑树实现,红黑树请看July的博客 教你透彻了解红黑树。所以元素操作插入元素(insert),删除元素(erase),查找元素(find),lower_bound(value), upper_bound(value)等成员函数的时间复杂皆是O(ln n)。
用一个应用实例说明map的使用(可以达到对数级复杂度哦):查找给出数组里的出现次数最多的元素。在数组元素特征可以预知而且元素是整型或可以转化为整型并且元素的范围有限(怎么这么多限定条件啊,对,谁让你用hash的)的情况下,当然用自建Hash映射效率最高,但是在一般情况下,数组元素都是随机的,用C++标准库提供的map是不二选择(如果你用C++编程的话)。贴代码,注意细节
#include<iostream>
#include<map> using namespace std;
int majorityElement(int num[], int sz) {
map<int,int> map;
for(int itv = ; itv != sz; ++itv){
if(map.count(num[itv]) == ){
map.insert(pair<int,int>(num[itv],));
}else{
int count = map[num[itv]];
map.erase(num[itv]); //注意此处要先删除,再插入新元素,如果直接调用insert元素不会更新
map.insert(pair<int,int>(num[itv],count+));
}
}
int majority=;
int majKey = -;
for(std::map<int,int>::iterator it = map.begin(); it != map.end(); ++it){
//cout<<it->first<<endl;
if(it->second > majority ){
majKey = it->first;
majority = it->second;
}
}
return majKey;
} int main(){
int num[] = {,,,,,,,,,};
cout<< majorityElement(num,)<<endl;
return ;
}
打印输出出现最多次的元素1。
对于特定问题用好map将节约很多时间。
最新文章
- YARN基本框架介绍
- [工作中的设计模式]责任链模式chain
- HTML之Hello World
- 模拟操作网页 webBrowser
- pushlet实现服务器端向客户端推送信息
- eclipse新建maven项目(1)
- 【翻译】使用Knockout, Web API 和 ASP.Net Web Forms 进行简单数据绑定
- xenserver+starwind架构布署
- C# 问题解决思路--《数组bytes未定义》,ASP.NET页面加载顺序
- SY全局系统字段
- ASP.NET中DesignMode属性
- BZOJ2375: 疯狂的涂色
- JavaEE开发之SpringMVC中的路由配置及参数传递详解
- 【vue系列之一】使用vue脚手架工具搭建vue-webpack项目
- Bootstrap中的datetimepicker用法,只看一眼就全懂了
- IPFS开发团队是如何工作的?
- S2第一本书内测
- HTML required
- 同时安装 Python 2 与Python 3 的方法及pip模块的下载安装
- 大数据入门基础系列之Hadoop1.X、Hadoop2.X和Hadoop3.X的多维度区别详解(博主推荐)