Question

关于map的c++ acm题目推荐

最好有代码！！

Answer 1

1. map的构造函数 map<int, string> maphai; map<char,int> maphai; map<string,char> mapstring; map<string,int> mapstring; map<int ,char>mapint; map<char,string>mapchar; 2. 数据的插入 在构造map容器后，我们就可以往里面插入数据了。这里讲三种插入数据的方法： 第一种：用insert函数插入pair数据， #include <map> #include <string> #include <iostream> Using namespace std; Int main() { Map<int, string> mapStudent; mapStudent.insert(pair<int, string>(1, “student_one”)); mapStudent.insert(pair<int, string>(2, “student_two”)); mapStudent.insert(pair<int, string>(3, “student_three”)); map<int, string>::iterator iter; for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++) { Cout<<iter->first<<” ”<<iter->second<<end; } } 第二种：用insert函数插入value_type数据，下面举例说明 #include <map> #include <string> #include <iostream> Using namespace std; Int main() { Map<int, string> mapStudent; mapStudent.insert(map<int, string>::value_type (1, “student_one”)); mapStudent.insert(map<int, string>::value_type (2, “student_two”)); mapStudent.insert(map<int, string>::value_type (3, “student_three”)); map<int, string>::iterator iter; for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++) { Cout<<iter->first<<” ”<<iter->second<<end; } } 第三种：用数组方式插入数据，下面举例说明 #include <map> #include <string> #include <iostream> Using namespace std; Int main() { Map<int, string> mapStudent; mapStudent[1] = “student_one”; mapStudent[2] = “student_two”; mapStudent[3] = “student_three”; map<int, string>::iterator iter; for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++) { Cout<<iter->first<<” ”<<iter->second<<end; } } 以上三种用法，虽然都可以实现数据的插入，但是它们是有区别的，当然了第一种和第二种在效果上是完成一样的，用insert函数插入数据，在数据的插入上涉及到集合的唯一性这个概念，即当map中有这个关键字时，insert操作是插入数据不了的，但是用数组方式就不同了，它可以覆盖以前该关键字对应的值，用程序说明 mapStudent.insert(map<int, string>::value_type (1, “student_one”)); mapStudent.insert(map<int, string>::value_type (1, “student_two”)); 上面这两条语句执行后，map中1这个关键字对应的值是“student_one”，第二条语句并没有生效，那么这就涉及到我们怎么知道insert语句是否插入成功的问题了，可以用pair来获得是否插入成功，程序如下 Pair<map<int, string>::iterator, bool> Insert_Pair; Insert_Pair = mapStudent.insert(map<int, string>::value_type (1, “student_one”)); 我们通过pair的第二个变量来知道是否插入成功，它的第一个变量返回的是一个map的迭代器，如果插入成功的话Insert_Pair.second应该是true的，否则为false。 下面给出完成代码，演示插入成功与否问题 #include <map> #include <string> #include <iostream> Using namespace std; Int main() { Map<int, string> mapStudent; Pair<map<int, string>::iterator, bool> Insert_Pair; Insert_Pair ＝ mapStudent.insert(pair<int, string>(1, “student_one”)); If(Insert_Pair.second == true) { Cout<<”Insert Successfully”<<endl; } Else { Cout<<”Insert Failure”<<endl; } Insert_Pair ＝ mapStudent.insert(pair<int, string>(1, “student_two”)); If(Insert_Pair.second == true) { Cout<<”Insert Successfully”<<endl; } Else { Cout<<”Insert Failure”<<endl; } map<int, string>::iterator iter; for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++) { Cout<<iter->first<<” ”<<iter->second<<end; } } 大家可以用如下程序，看下用数组插入在数据覆盖上的效果 #include <map> #include <string> #include <iostream> Using namespace std; Int main() { Map<int, string> mapStudent; mapStudent[1] = “student_one”; mapStudent[1] = “student_two”; mapStudent[2] = “student_three”; map<int, string>::iterator iter; for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++) { Cout<<iter->first<<” ”<<iter->second<<end; } } 3. map的大小 在往map里面插入了数据，我们怎么知道当前已经插入了多少数据呢，可以用size函数，用法如下： Int nSize = mapStudent.size(); 4. 数据的遍历 这里也提供三种方法，对map进行遍历 第一种：应用前向迭代器，上面举例程序中到处都是了，略过不表 第二种：应用反相迭代器，下面举例说明，要体会效果，请自个动手运行程序 #include <map> #include <string> #include <iostream> Using namespace std; Int main() { Map<int, string> mapStudent; mapStudent.insert(pair<int, string>(1, “student_one”)); mapStudent.insert(pair<int, string>(2, “student_two”)); mapStudent.insert(pair<int, string>(3, “student_three”)); map<int, string>::reverse_iterator iter; for(iter = mapStudent.rbegin(); iter != mapStudent.rend(); iter++) { Cout<<iter->first<<” ”<<iter->second<<end; } } 第三种：用数组方式，程序说明如下 #include <map> #include <string> #include <iostream> Using namespace std; Int main() { Map<int, string> mapStudent; mapStudent.insert(pair<int, string>(1, “student_one”)); mapStudent.insert(pair<int, string>(2, “student_two”)); mapStudent.insert(pair<int, string>(3, “student_three”)); int nSize = mapStudent.size() //此处有误，应该是 for(int nIndex = 1; nIndex <= nSize; nIndex++) //by rainfish for(int nIndex = 0; nIndex < nSize; nIndex++) { Cout<<mapStudent[nIndex]<<end; } } 5. 数据的查找（包括判定这个关键字是否在map中出现） 在这里我们将体会，map在数据插入时保证有序的好处。 要判定一个数据（关键字）是否在map中出现的方法比较多，这里标题虽然是数据的查找，在这里将穿插着大量的map基本用法。 这里给出三种数据查找方法 第一种：用count函数来判定关键字是否出现，其缺点是无法定位数据出现位置,由于map的特性，一对一的映射关系，就决定了count函数的返回值只有两个，要么是0，要么是1，出现的情况，当然是返回1了 第二种：用find函数来定位数据出现位置，它返回的一个迭代器，当数据出现时，它返回数据所在位置的迭代器，如果map中没有要查找的数据，它返回的迭代器等于end函数返回的迭代器，程序说明 #include <map> #include <string> #include <iostream> Using namespace std; Int main() { Map<int, string> mapStudent; mapStudent.insert(pair<int, string>(1, “student_one”)); mapStudent.insert(pair<int, string>(2, “student_two”)); mapStudent.insert(pair<int, string>(3, “student_three”)); map<int, string>::iterator iter; iter = mapStudent.find(1); if(iter != mapStudent.end()) { Cout<<”Find, the value is ”<<iter->second<<endl; } Else { Cout<<”Do not Find”<<endl; } } 第三种：这个方法用来判定数据是否出现，是显得笨了点，但是，我打算在这里讲解 Lower_bound函数用法，这个函数用来返回要查找关键字的下界(是一个迭代器) Upper_bound函数用法，这个函数用来返回要查找关键字的上界(是一个迭代器) 例如：map中已经插入了1，2，3，4的话，如果lower_bound(2)的话，返回的2，而upper-bound（2）的话，返回的就是3 Equal_range函数返回一个pair，pair里面第一个变量是Lower_bound返回的迭代器，pair里面第二个迭代器是Upper_bound返回的迭代器，如果这两个迭代器相等的话，则说明map中不出现这个关键字，程序说明 #include <map> #include <string> #include <iostream> Using namespace std; Int main() { Map<int, string> mapStudent; mapStudent[1] = “student_one”; mapStudent[3] = “student_three”; mapStudent[5] = “student_five”; map<int, string>::iterator iter; iter = mapStudent.lower_bound(2); { //返回的是下界3的迭代器 Cout<<iter->second<<endl; } iter = mapStudent.lower_bound(3); { //返回的是下界3的迭代器 Cout<<iter->second<<endl; } iter = mapStudent.upper_bound(2); { //返回的是上界3的迭代器 Cout<<iter->second<<endl; } iter = mapStudent.upper_bound(3); { //返回的是上界5的迭代器 Cout<<iter->second<<endl; } Pair<map<int, string>::iterator, map<int, string>::iterator> mapPair; mapPair = mapStudent.equal_range(2); if(mapPair.first == mapPair.second) { cout<<”Do not Find”<<endl; } Else { Cout<<”Find”<<endl; } mapPair = mapStudent.equal_range(3); if(mapPair.first == mapPair.second) { cout<<”Do not Find”<<endl; } Else { Cout<<”Find”<<endl; } }

Answer 2

都得不到样例，只能把这分给我的马甲了。。。