Chinaunix首页 | 论坛 | 博客
  • 博客访问: 544972
  • 博文数量: 104
  • 博客积分: 2089
  • 博客等级: 大尉
  • 技术积分: 1691
  • 用 户 组: 普通用户
  • 注册时间: 2010-06-29 08:48
文章分类

全部博文(104)

文章存档

2015年(1)

2013年(13)

2012年(31)

2011年(59)

分类: C/C++

2011-12-09 15:05:17

Map is an associative container that contains a sorted list of unique key-value pairs. That list is sorted using the comparison function Compare applied to the keys. Search, removal, and insertion operations have logarithmic complexity. Maps are usually implemented as

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

下面举例说明什么是一对一的数据映射。比如一个班级中,每个学生的学号跟他的姓名就存在着一一映射的关系,这个模型用map可能轻易描述,很明显学号用int描述,姓名用字符串描述(本篇文章中不用char *来描述字符串,而是采用STL中string来描述),下面给出map描述代码:

Map mapStudent;

1.       map的构造函数

map共提供了6个构造函数,这块涉及到内存分配器这些东西,略过不表,在下面我们将接触到一些map的构造方法,这里要说下的就是,我们通常用如下方法构造一个map:

Map mapStudent;

2.       数据的插入

在构造map容器后,我们就可以往里面插入数据了。这里讲三种插入数据的方法:

第一种:用insert函数插入pair数据,下面举例说明


  1. #include <map>
  2. #include <string>
  3. #include <iostream>

  4. using namespace std;

  5. int main()
  6. {

  7.         map<int, string> mapStudent;

  8.         mapStudent.insert(pair<int, string>(1, "student_one"));
  9.         mapStudent.insert(pair<int, string>(2, "student_two"));
  10.         mapStudent.insert(pair<int, string>(3, "student_three"));

  11.         map<int, string>::iterator iter;

  12.         for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
  13.                 cout << iter->first << " " << iter->second << endl;

  14. }

第二种:用insert函数插入value_type数据,下面举例说明

  1. #include <map>
  2. #include <string>
  3. #include <iostream>

  4. using namespace std;

  5. int main()
  6. {

  7.         map<int, string> mapStudent;

  8.         mapStudent.insert(map<int, string>::value_type (1, "student_one"));
  9.         mapStudent.insert(map<int, string>::value_type (2, "student_two"));
  10.         mapStudent.insert(map<int, string>::value_type (3, "student_three"));

  11.         map<int, string>::iterator iter;

  12.         for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
  13.                 cout << iter->first << " " << iter->second << endl;

  14. }

第三种:用数组方式插入数据,下面举例说明

  1. #include <map>
  2. #include <string>
  3. #include <iostream>

  4. using namespace std;

  5. int main()
  6. {

  7.         map<int, string> mapStudent;

  8.         mapStudent[1] = "student_one";
  9.         mapStudent[2] = "student_two";
  10.         mapStudent[3] = "student_three";

  11.         /* the below will cover the above
  12.         mapStudent[3] = "student_three_1";
  13.         */
  14.         map<int, string>::iterator iter;

  15.         for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
  16.                 cout << iter->first << " " << iter->second << endl;

  17.         cout << "student size:" << mapStudent.size() << endl;
  18. }

以上三种用法,虽然都可以实现数据的插入,但是它们是有区别的,当然了第一种和第二种在效果上是完成一样的,用insert函数插入数据,在数据的插入上涉及到集合的唯一性这个概念,即当map中有这个关键字时,insert操作是插入数据不了的,但是用数组方式就不同了,它可以覆盖以前该关键字对应的值

用pair来获得是否插入成功

  1. using namespace std;


  2. int main()
  3. {

  4.         map<int, string> mapStudent;

  5.         #define MAP_INSERT_CHECK(nr,str) do { \
  6.                 pair < map <int, string>::iterator,bool> InsertPair; \
  7.                 InsertPair = mapStudent.insert(pair<int, string>(nr, str)); \
  8.                 if(InsertPair.second) \
  9.                         cout << "Insert Successfully \n"; \
  10.                 else \
  11.                         cout << "Insert Failure \n" ; \
  12.         }while(0)

  13.         MAP_INSERT_CHECK(1,"student_one");
  14.         MAP_INSERT_CHECK(2,"student_two");
  15.         MAP_INSERT_CHECK(3,"student_three");

  16.         map<int, string>::iterator iter;

  17.         for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
  18.                 cout << iter->first << " " << iter->second << endl;

  19.         cout << "student size:" << mapStudent.size() << endl;

  20. }

上面已经有iterator方式的遍历了,看看数组方式遍历

  1. #include <map>
  2. #include <string>
  3. #include <iostream>

  4. using namespace std;

  5. int main()
  6. {

  7.         map<int, string> mapStudent;

  8.         mapStudent.insert(pair<int, string>(1, "student_one"));
  9.         mapStudent.insert(pair<int, string>(2, "student_two"));
  10.         mapStudent.insert(pair<int, string>(3, "student_three"));

  11.         int size = mapStudent.size();

  12.         for(int i=0; i<size; i++)
  13.                 cout << i+1 << " " << mapStudent[i+1] << endl;

  14. }

upper_bound,很有意思的东西

  1. #include <map>
  2. #include <string>
  3. #include <iostream>

  4. using namespace std;

  5. int main()
  6. {

  7.         map<int, string> mapStudent;

  8.         mapStudent[1] = "student_one";
  9.         mapStudent[3] = "student_three";
  10.         mapStudent[5] = "student_five";

  11.         map<int, string>::iterator iter;
  12.         for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
  13.                 cout << iter->first << " " << iter->second << endl;

  14.         cout << "student size:" << mapStudent.size() << endl;

  15.         cout << "test bound\n" ;

  16.         iter = mapStudent.lower_bound(2);
  17.         cout <<"lower_bound(2):" <<iter->second << endl;

  18.         iter = mapStudent.upper_bound(2);
  19.         cout <<"upper_bound(2):" <<iter->second << endl;

  20.         iter = mapStudent.lower_bound(3);
  21.         cout <<"lower_bound(3):" <<iter->second << endl;

  22.         iter = mapStudent.upper_bound(3);
  23.         cout <<"upper_bound(3):" <<iter->second << endl;


  24.         /* for justifying exiting */
  25.         pair < map<int,string>::iterator, map<int,string>::iterator > mapPair;
  26.         mapPair = mapStudent.equal_range(2);
  27.         if(mapPair.first == mapPair.second)
  28.                 cout <<"key 2 not find\n";
  29.         else
  30.                 cout <<"key 2 fount\n";

  31.         mapPair = mapStudent.equal_range(3);
  32.         if(mapPair.first == mapPair.second)
  33.                 cout <<"key 3 not find\n";
  34.         else
  35.                 cout <<"key 3 fount\n";


  36. }

反向遍历

看清 不是iterator 而是 reverse_iterator,我是看了好久才检查出来的

  1. #include <map>
  2. #include <string>
  3. #include <iostream>

  4. using namespace std;

  5. int main()
  6. {

  7.         map<int, string> mapStudent;

  8.         mapStudent.insert(pair<int, string>(1, "student_one"));
  9.         mapStudent.insert(pair<int, string>(2, "student_two"));
  10.         mapStudent.insert(pair<int, string>(3, "student_three"));

  11.         map<int, string>::reverse_iterator riter;

  12.         for(riter = mapStudent.rbegin(); riter != mapStudent.rend(); riter++)
  13.                 cout << riter->first << " " << riter->second << endl;

  14. }

 数据的清空与判空

清空map中的数据可以用clear()函数,判定map中是否有数据可以用empty()函数,它返回true则说明是空map

数据的删除

  1. #include <map>
  2. #include <string>
  3. #include <iostream>

  4. using namespace std;

  5. int main()
  6. {
  7.         map<int, string> mapStudent;

  8.         mapStudent.insert(pair<int, string>(1, "student_one"));
  9.         mapStudent.insert(pair<int, string>(3, "student_two"));
  10.         mapStudent.insert(pair<int, string>(5, "student_three"));

  11.         map<int, string>::iterator iter;

  12.         cout << "\nthe BILL of all student" << endl;
  13.         for(iter = mapStudent.begin(); iter != mapStudent.end(); iter ++)
  14.                 cout << iter->first << " " << iter->second << endl;
  15.         cout << "--------------------------" << endl;

  16.         //by iterator
  17.         iter = mapStudent.find(1);
  18.         mapStudent.erase(iter);
  19.         for(iter = mapStudent.begin(); iter != mapStudent.end(); iter ++)
  20.                 cout << "\t" << iter->first << " " << iter->second << endl;

  21.         //by key
  22.         mapStudent.insert(pair<int, string>(1, "student_one"));
  23.         cout << "\nthe BILL of all student" << endl;
  24.         for(iter = mapStudent.begin(); iter != mapStudent.end(); iter ++)
  25.                 cout << iter->first << " " << iter->second << endl;
  26.         cout << "--------------------------" << endl;

  27.         int rt = 0;
  28.         rt = mapStudent.erase(1);
  29.         cout << "erase(1):" << rt << endl;
  30.         rt = mapStudent.erase(2);
  31.         cout << "erase(2):" << rt << endl;
  32.         for(iter = mapStudent.begin(); iter != mapStudent.end(); iter ++)
  33.                 cout << "\t" << iter->first << " " << iter->second << endl;

  34.         //delete a range item
  35.         mapStudent.insert(pair<int, string>(1, "student_one"));
  36.         cout << "\nthe BILL of all student" << endl;
  37.         for(iter = mapStudent.begin(); iter != mapStudent.end(); iter ++)
  38.                 cout << iter->first << " " << iter->second << endl;
  39.         cout << "--------------------------" << endl;
  40.         mapStudent.erase(mapStudent.begin(), mapStudent.end());
  41.         //Removes the elements in the range [first; last).
  42.         for(iter = mapStudent.begin(); iter != mapStudent.end(); iter ++)
  43.                 cout << "\t" << iter->first << " " << iter->second << endl;
  44. }


排序

因为是红黑树存储,本身要有有顺序,因此在构造时就必须明确iterator->first的比较方法,基本数据类型不说了,如果是结构体有两种,一是在结构体或者类重载“<”,二是利用第三个类进行重载“()”进行排序。

  1. #include <map>
  2. #include <iostream>
  3. #include <string>
  4. using namespace std;
  5. typedef struct tagStudentInfo {
  6.         int nID;
  7.         string strName;

  8.         /* in map, the sort need "<" for sorting, so this needed */
  9.         bool operator < (tagStudentInfo const& _A) const {
  10.                 if(nID < _A.nID) return true;
  11.                 if(nID == _A.nID) return strName.compare(_A.strName) < 0;
  12.                 return false;
  13.         }
  14. }StudentInfo, *PStudentInfo;

  15. int main()
  16. {
  17.         int nSize;

  18.         map<StudentInfo, int>mapStudent;
  19.         map<StudentInfo, int>::iterator iter;
  20.         StudentInfo studentInfo;

  21.         studentInfo.nID = 1;
  22.         studentInfo.strName = "student_one";
  23.         mapStudent.insert(pair<StudentInfo, int>(studentInfo, 90));

  24.         studentInfo.nID = 2;
  25.         studentInfo.strName = "student_two";
  26.         mapStudent.insert(pair<StudentInfo, int>(studentInfo, 80));

  27.         studentInfo.nID = 3;
  28.         studentInfo.strName = "student_three";
  29.         mapStudent.insert(pair<StudentInfo, int>(studentInfo, 95));

  30.         cout << "ID\tName\t\tScore\n";
  31.         for (iter = mapStudent.begin(); iter != mapStudent.end(); iter++ )
  32.                 cout << iter->first.nID <<"\t"
  33.                         << iter->first.strName <<"\t"
  34.                         << iter->second <<endl ;
  35. }

第二种

  1. #include <map>
  2. #include <iostream>
  3. #include <string>
  4. using namespace std;
  5. typedef struct tagStudentInfo {
  6.         int nID;
  7.         string strName;
  8. }StudentInfo, *PStudentInfo;

  9. class BySort{
  10.         public:
  11.                 bool operator()
  12.                 (StudentInfo const &_A, StudentInfo const &_B) const
  13.                 {
  14.                         if(_A.nID < _B.nID)
  15.                                 return true;
  16.                         if(_A.nID == _B.nID)
  17.                                 return _A.strName.compare(_B.strName) < 0;
  18.                         return false;
  19.                 }
  20. };
  21. int main()
  22. {
  23.         int nSize;

  24.         map<StudentInfo, int, BySort>mapStudent;
  25.         map<StudentInfo, int>::iterator iter;
  26.         StudentInfo studentInfo;

  27.         studentInfo.nID = 1;
  28.         studentInfo.strName = "student_one";
  29.         mapStudent.insert(pair<StudentInfo, int>(studentInfo, 90));

  30.         studentInfo.nID = 2;
  31.         studentInfo.strName = "student_two";
  32.         mapStudent.insert(pair<StudentInfo, int>(studentInfo, 80));

  33.         studentInfo.nID = 3;
  34.         studentInfo.strName = "student_three";
  35.         mapStudent.insert(pair<StudentInfo, int>(studentInfo, 95));

  36.         cout << "ID\tName\t\tScore\n";
  37.         for (iter = mapStudent.begin(); iter != mapStudent.end(); iter++ )
  38.                 cout << iter->first.nID <<"\t"
  39.                         << iter->first.strName <<"\t"
  40.                         << iter->second <<endl ;
  41. }



参考:

http://www.cnblogs.com/wanghao111/archive/2009/08/10/1542974.html



阅读(676) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~