c++ Map和题目

c++ map

1.dev-c++ 使用c++11的设置方法

2.map基本用法简介

构造：

函数原型	功能
map mp;	map默认构造函数。
map(const map &mp);	拷贝构造函数。

赋值：（可以写赋值等号=）

函数原型	功能
map& operator=(const map &mp);	重载等号操作符。

map是STL的一个关联容器，它提供一对一的映射。

第一个可以称为关键字(key)，每个关键字只能在map中出现一次；first
第二个可能称为该关键字的值(value)；second

map以模板(泛型)方式实现，可以存储任意类型的数据，包括使用者自定义的数据类型。

map內部的实现自建一颗红黑树，这颗树具有对数据自动排序的功能, ( 后面有个题目会见识到 )

map和multimap区别：

map不允许容器中有重复key值元素
multimap允许容器中有重复key值元素

使用步骤 1.引入头文件#include 2.定义一个map

这里只来一个简单的定义（样例） map mymap;

定义：map<类型1，类型2> 名字; 类型1,2可以是自定义类型，自定义类型的话有注意事项，下面会有介绍；

这样就定义了一个map了，键值对就是int—>string，mymap里面的元素就是这样的键值对。

3.使用

遍历

我们先不管怎么插入的，直接来看看遍历：

#include 
#include 
#include 
using namespace std;
int main()
{
	map mymap;
	//数组形式插入
	mymap[1] = "田小锋";
	mymap[0] = "田小锋二号";
	mymap[-1] = "田小锋三号";
	
	//普通遍历
	cout << "普通遍历n";
    //嫌太长了，可以typedef map::iterator Iter;起个别名
	for (map::iterator it = mymap.begin(); it != mymap.end(); it++ ) {
		cout << it->first << "-->" << it->second << endl;
	}
	
	cout << endl;
	//c++11遍历
	cout << "c++11遍历n";
	for(auto &temp : mymap ) {
		cout << temp.first << "-->" << temp.second << endl;
	}
	
	return 0;
}

map的迭代器指向的是一个键值对，it->first 是key，it->second是value.

插入

根据上面的例子，可知，map是根据key来排序的( 所以我们的key一定要可以比较 )

1.数组形式插入

map mymap;
//数组形式插入
mymap[1] = "田小锋";
mymap[0] = "田小锋二号";
mymap[-1] = "田小锋三号";
mymap[1] = "txf"; //按顺序来这条语句会覆盖上面的"田小锋";


map mymap;
//数组形式插入
mymap["txf"] = "田小锋";
mymap["txf02"] = "田小锋二号";
mymap["txf03"] = "田小锋三号";
mymap["txf"] = "txf"; //同理

2.insert

insert插入的是pair

pair、map::value_type()、make_pair()函数

//看看make_pair函数
template pair make_pair(T1 a, T2 b) { 
    return pair(a, b); 
}
//本质还是一个pair，
//pair是将2个数据组合成一个数据，当有这样的需求时就可以使用pair，如stl中的map就是将key和value放在一起来保存
//当一个函数需要返回2个数据的时候，可以选择pair。 pair的实现是一个结构体，

#include 
#include 
#include 
using namespace std;

typedef map::value_type Value;
int main()
{
	map mymap;

	//1
	mymap.insert(pair("txf","田小锋"));
	mymap.insert(pair("txf1","田小锋1"));
	mymap.insert(pair("txf11","田小锋2"));
	mymap.insert(pair("txf0","田小锋3"));
	
	//2
	mymap.insert(map::value_type("txf007","小锋007"));
	mymap.insert(map::value_type("txf007","小锋007"));//不生效，key重复
	mymap.insert(map::value_type("txf007","小锋008888"));//insert不会更新key相同的
	
	mymap.insert(Value("txfqwer","小锋玩亚索"));//看上面起的别名

	//3
	mymap.insert(make_pair("txfnb","小锋牛逼"));
    
	//普通遍历
	cout << "普通遍历n";
    //嫌太长了，可以typedef map::iterator Iter;起个别名
	for (map::iterator it = mymap.begin(); it != mymap.end(); it++ ) {
		cout << it->first << "-->" << it->second << endl;
	}

	cout << endl;
	//c++11遍历
	cout << "c++11遍历n";
	for(auto &temp : mymap ) {
		cout << temp.first << "-->" << temp.second << endl;
	}

	return 0;
}

3.插入自定义类型

前面说了，自定义类型的时候,key一定要能比较，先来看不比较的，value是我们自定义的数据类型

//例子一
#include 
#include 
#include 
using namespace std;

typedef struct{
	int no;
	string name;
}MyType;

int main()
{
	map mymap;

	MyType a{1,"田小锋"};
	mymap[1] = a;

	cout << "c++11遍历n";
    
	for(auto &temp : mymap ) {
		cout << temp.first << "-->" << temp.second.no <<":" << temp.second.name << endl;
	}

	return 0;
}


//下面是重写了<<运算符的,可以略过不看哈,重写<<运算符
#include 
#include 
#include 
using namespace std;

class MyType
{
	public:
		MyType(){no = 0, name="";}
		MyType(int no, string name){
			this->no = no;
			this->name = name;
		}
		int getNo() {
			return no;
		}
		string getName() {
			return name;
		}
		
		friend ostream& operator<< (ostream &out, MyType &p ) {
			out << p.getNo() << ":" << p.getName();
			return out;
		}
	private:
		int no;
		string name;
};

int main()
{
	map mymap;

	MyType a(1,"田小锋"), b(2,"田小锋二号");
	
	mymap[1] = a;
	mymap[2] = b;
	mymap.insert(make_pair(3, MyType(3,"田小锋三号")));

	cout << "c++11遍历n";
	for(auto &temp : mymap ) {
		cout << temp.first << "-->" << temp.second << endl;
	}

	return 0;
}

这里来说说当我们的key是自定义类型的时候：

重写<运算符，经验之谈就别问为什么了

#include 
#include 
#include 
using namespace std;

//定义了一个结构体
typedef struct{
	int a;
}Myint;

//前面说了，key默认是排序的，这里我写的是l.a 如果 > r.a
//就返回true，说明key大的排在了前面
bool operator < (const Myint l, const Myint r ) {
	return l.a > r.a;
}

int main()
{
	map mymap;
	Myint t0 = {1};
	Myint t1 = {2};
	Myint t2 = {3};
	mymap[t0] = "田小锋0";
	mymap[t1] = "田小锋1";
	mymap[t2] = "田小锋2";
	
	cout << "c++11遍历n";
	for(auto &temp : mymap ) {
		cout << temp.first.a << "-->" << temp.second << endl;
	}

	return 0;
}

typedef struct myint{
	int a;
	bool operator< ( const myint &r) {
		return a > r.a;
	}
}Myint;

上面的例子这样重写会报错，[Error] passing 'const myint' as 'this' argument of 'bool myint::operator<(myint)' discards qualifiers [-fpermissive]
大意是：将'const myint'作为'bool myint:：operator<（myint）'的'this'参数传递将丢弃限定符[-fppermissive]
    
源码这样的：
    /// One of the @link comparison_functors comparison functors@endlink.
    template
    struct less : public binary_function<_Tp, _Tp, bool>
    {
        bool
            operator()(const _Tp& __x, const _Tp& __y) const  //注意这里,const限定符
        { return __x < __y; }
    };

所以上面要这么写:
typedef struct myint{
	int a;
	bool operator< ( const myint &r) const {
		return a > r.a;
	}
}Myint;

我反正是这么理解的，可能有不对之处，望大家指出来。

上面演示的是结构体，类类型的话就跟这个差不多了，我就不演示了，下面抄一个别人的，定义一个类来重写比较自定义类型的

typedef struct tagStudentInfo
{
    int nID;
    string strName;
    
}StudentInfo,*PStudentInfo;
class sort
{
public:
    bool operator()(tagStudentInfo const &_A,tagStudentInfo const &_B) const
    {
        if(_A.nID<_B.nID) 
            return true;
        return false;
    }
}
int main()
{
    map mapStudent;
    StudentInfo studentInfo;
    studentInfo.nID=1;
    studentInfo.strName="student_one";
    mapStudent.insert(pair(studentInfo,80));
    return 0;
}
//选自CSDN 小C博客

总结：自定义类型左key一定要能比较，即重写<运算符！！！！

判断是否插入成功，我这里偷个懒：

查找

1.count

传入key，查看key的个数，（很明显有就是只有一个，map的key不能重复）

#include 
#include 
#include 
using namespace std;

int main()
{
	map mymap;
	
	mymap["t0"] = "田小锋0";
	mymap["t1"] = "田小锋1";
	mymap["t2"] = "田小锋2";
	
    //有就是1，没有就是0
	int i = mymap.count("t0"), j = mymap.count("45");
	cout << i << "n" << j << endl;

	return 0;
}

2.find

定位到key出现的位置，该方法返回一个迭代器。
当数据找到时，返回数据所在位置的迭代器；
否则，返回的迭代器等于end方法返回的迭代器。

#include 
#include 
#include 
using namespace std;
typedef map::iterator MapIt;
int main()
{
	map mymap;
	
	mymap["t0"] = "田小锋0";
	mymap["t1"] = "田小锋1";
	mymap["t2"] = "田小锋2";
	
//    MapIt it = mymap.find("t4");
	MapIt it = mymap.find("t0");
	if ( it != mymap.end() ) cout << "找到了" << it->first << "->" << it->second << endl;
	else cout << "找不到n";
	return 0;
}

删除

erase

三种形式：传入key根据key删除；根据迭代器删除；根据迭代器的区间删除；

#include 
#include 
#include 
using namespace std;
typedef map::iterator MapIt;
int main()
{
	map mymap;
	
	mymap["t0"] = "田小锋0";
	mymap["t1"] = "田小锋1";
	mymap["t2"] = "田小锋2";
	mymap["t3"] = "田小锋3";
	mymap["t4"] = "田小锋4";
	
	//key
	mymap.erase("t0");
	int i = mymap.erase("t5");//找不到，所以i为0
	cout << i << endl;
	
	for (auto &temp : mymap ) {
		cout << temp.first << "->" << temp.second << endl;
	}
	return 0;
}

//迭代器删除
#include 
#include 
#include 
using namespace std;
typedef map::iterator MapIt;
int main()
{
	map mymap;
	
	mymap["t0"] = "田小锋0";
	mymap["t1"] = "田小锋1";
	mymap["t2"] = "田小锋2";
	mymap["t3"] = "田小锋3";
	mymap["t4"] = "田小锋4";
	//下面的会异常，因为找不到，
	//it指向的是end(),没有元素
//	MapIt it = mymap.find("t5");
//	mymap.erase(it);
	MapIt it = mymap.find("t0");
    if ( it != mymap.end()) //判断一下就行了，t0肯定是能找到的
		mymap.erase(it);
	
	for (auto &temp : mymap ) {
		cout << temp.first << "->" << temp.second << endl;
	}
	return 0;
}

//区间删除
#include 
#include 
#include 
using namespace std;
typedef map::iterator MapIt;
int main()
{
	map mymap;
	
	mymap["t0"] = "田小锋0";
	mymap["t1"] = "田小锋1";
	mymap["t2"] = "田小锋2";
	mymap["t3"] = "田小锋3";
	mymap["t4"] = "田小锋4";

	MapIt s = mymap.find("t1");
	MapIt e = mymap.find("t3");
	//c++传统，左闭右开
	mymap.erase(s,e);  //区间是[位置s,位置e),
	
	for (auto &temp : mymap ) {
		cout << temp.first << "->" << temp.second << endl;
	}
	return 0;
}

总结常用方法：

方法	用途
insert()	插入元素，返回一个东西，我没写
find()	查找元素，返回迭代器
count()	查找个数
erase()	删除元素，key，迭代器
size()	返回元素个数
empty()	判断map是否为空
begin()	返回开始的迭代器
end()	返回最后一个元素后面的迭代器
swap();	交换两个map

#include 
#include 
#include 
using namespace std;
typedef map::iterator MapIt;
//交换
int main()
{
	map mymap0, mymap2;
	
	mymap0["t0"] = "田小锋0";
	mymap2["t2"] = "田小锋2";
	mymap0.swap(mymap2);
	
	cout << "mymap0n";
	for (auto &temp : mymap0 ) {
		cout << temp.first << "->" << temp.second << endl;
	}
	
	cout << "mymap2n";
	for (auto &temp : mymap2 ) {
		cout << temp.first << "->" << temp.second << endl;
	}
	return 0;
}

题目实战： 1.pta数据结构与算法：

实现QQ新帐户申请和老帐户登陆的简化版功能。最大挑战是：据说现在的QQ号码已经有10位数了。
输入格式:
输入首先给出一个正整数N（≤105），随后给出N行指令。每行指令的格式为：“命令符（空格）QQ号码（空格）密码”。其中命令符为“N”（代表New）时表示要新申请一个QQ号，后面是新帐户的号码和密码；命令符为“L”（代表Login）时表示是老帐户登陆，后面是登陆信息。QQ号码为一个不超过10位、但大于1000（据说QQ老总的号码是1001）的整数。密码为不小于6位、不超过16位、且不包含空格的字符串。
输出格式:
针对每条指令，给出相应的信息：

1）若新申请帐户成功，则输出“New: OK”；
2）若新申请的号码已经存在，则输出“ERROR: Exist”；
3）若老帐户登陆成功，则输出“Login: OK”；
4）若老帐户QQ号码不存在，则输出“ERROR: Not Exist”；
5）若老帐户密码错误，则输出“ERROR: Wrong PW”。
输入样例:
5
L 1234567890 myQQ@qq.com
N 1234567890 myQQ@qq.com
N 1234567890 myQQ@qq.com
L 1234567890 myQQ@qq
L 1234567890 myQQ@qq.com
输出样例:
ERROR: Not Exist
New: OK
ERROR: Exist
ERROR: Wrong PW
Login: OK

#include 
#include 
#include 
using namespace std;

map mydata;
int n;
string qq, pwd;

char choice;

int main()
{
	cin >> n;
	while (n--) {
		cin >> choice >> qq >> pwd;
		if ( choice == 'L' ) {
			if ( mydata.count(qq) == 0 ) {
				cout << "ERROR: Not Existn";
			}
			else {
				if ( mydata[qq] != pwd ) {
					cout << "ERROR: Wrong PWn";
				}
				else {
					cout << "Login: OKn";
				}
			}
		}
		else {
			if ( mydata.count(qq) == 1 ) {
				cout << "ERROR: Existn";
			}
			else {
				cout << "New: OKn";
				pair p(qq, pwd);
				mydata.insert( p );
			}
		}
	}
	return 0;
}

2.洛谷寄包柜

题目描述
超市里有 n(n≤10^5)个寄包柜。每个寄包柜格子数量不一，第 i 个寄包柜有 ai(ai≤10^5)个格子，不过我们并不知道各个 ai 的值。对于每个寄包柜，格子编号从 1 开始，一直到 ai。现在有 q(q≤10^5) 次操作：

1 i j k：在第 i个柜子的第 j 个格子存入物品 k(0≤k≤10^9)。当 k=0时说明清空该格子。
2 i j：查询第 i 个柜子的第 j个格子中的物品是什么，保证查询的柜子有存过东西。

已知超市里共计不会超过 10^7个寄包格子，ai 是确定然而未知的，但是保证一定不小于该柜子存物品请求的格子编号的最大值。当然也有可能某些寄包柜中一个格子都没有。
输入格式
第一行 2 个整数 n 和 q，寄包柜个数和询问次数。

接下来 q 个整数，表示一次操作。
输出格式
对于查询操作时，输出答案。
输入输出样例
输入 #1
5 4
1 3 10000 114514
1 1 1 1
2 3 10000
2 1 1
输出 #1
114514
1

#include 
#include 
using namespace std;
map m[100005];
int main()
{
	int n, q, c, a, b, num;
	cin >> n >> q;
	while ( q-- ) {
		cin >> c >> a >> b;
		if ( c == 1 )
		{
			cin >> num;
			m[a][b] = num;
		}
		else {
			cout << m[a][b] << 'n';
		}
	}
	return 0;
}

看图就知道了：(map查找是很快的)，一维map就是一个红黑树，二维map就是下图这样的嘛，差不多是这个样子。

c++ Map和题目

C/C++/C#相关栏目本月热门文章